Due: Wednesday, March 5 2025, 11:59 pm

Part I: Lexical Analysis

The first thing we have to do with any programming language is build a lexical analyzer that converts a text string into a series of tokens. There are lots of tools for handling this. For this assignment, you'll make use of the Flex lexical analysis tool and build a few different parsers.

The dwarves in the robotics lab have flex installed already. If you have an account, you can either physically access or remotely SSH to these machines. If you have difficulty installing and using flex on your machine and don't have access to the dwarves, please let Stephanie know ASAP. To SSH to one of the machines, use the command line ssh yourColbyUserName@machineName.cs.colby.edu. Here is a list of the machine names. Assume Ying picks fili, the command line would be ssh yingli@fili.cs.colby.edu

If you want to use your computer for this project and your computer doesn't have Flex installed, here are some resources for Flex installation.

• If your computer is a Mac, you can use homebrew to install Flex.
• If your computer is a Windows machine and you have Cygwin installed, you can install the flex packet provided by Cygwin.
• If your computer is an Ubuntu box, you can use apt-get to install flex.

To check whether you machine has flex install, you can use the command line flex --version. If your machine has flex, you should get some information to indicate the flex version (e.g., flex 2.6.4).

Tasks

Flex is an open source lexical analysis tool. The way it works is you first create an input file that defines symbols and production rules that describe how to parse a text file. Then you run Flex and it produces a C file. You can then compile the C file and run it on some input.

As an example, consider the following Hello World program for Flex. The line beginning with blah defines a rule that says to replace instances of blah with hello world.

/**
* Hello World: replace "sadness" with "happiness""
*/

%%

sadness    printf("happiness");

%%

int main ( int argc, char *argv[] ) {

	yylex();

	return 0;

}

If you type the above into a file called replace.yy and then execute the following commands, you get the resulting behavior.

$ flex replace.yy
$ gcc -o repl lex.yy.c -ll
$ echo "sadness and more sadness" | ./repl
happiness and more happiness

If you'd like to explore beyond the sample code discussed in class, the documentation for flex provides many more examples and a description of the syntax.

Note that flex is based on regular expressions, which are similar to the extended BNF notation we've gone over in class. There are lots of documentation for regular expressions, and they can be very useful in many situations.

1. Using flex, make a program called encode that takes any character in a-z or A-Z and shifts it 13 spaces forward in the alphabet, with wraparound from z back to a. Run it on a text file of your choice. You can test that it is working correctly by running the output of encode through encode again. The result should be the original document. Make use of the fact that you can get the ASCII value of any character by wrapping it in single quotes (e.g. 'a' is the value 97). You can treat it as an integer and do math.

   Report: Your goal is to describe your pattern-matching code and demonstrate that it works correctly.

   • Include an image of your terminal running flex, gcc, and finally the flex-generated program. Demonstrate that if you run the program with on output from a first run, you get the same output as your original input.
   • Explain your flex code. Include in that explanation an example of how one particular letter (of your choosing) is correctly shifted by your code.

2. Using Flex, make a program that reads in a text file and tells you not only the number of rows and characters, but also how many of each vowel [a, e, i, o, u] are in the file.

   Report: Your goal is to describe your pattern-matching code and demonstrate that it works correctly.

   • Include an image of your terminal running flex, gcc, and finally the flex-generated program. Demonstrate that your output is correct. The easiest way to do this is to put the text being analyzed in image close to that of the output. Use text to describe how you can tell it is correct.
   • Explain your flex code. Include in that explanation an example of how one letter is counted.

3. Make a program that strips an html file of tags, single-line comments, and extraneous whitespace.

   • An html tag is a string that starts and ends with a pair of angle brackets < and >.
   • An html comment is a string that starts and ends with <!-- and -->. It is relatively straight-forward to remove comments that begin and end on the same line (you can match it with one pattern), but multi-line comments require more careful code. Please remove one-line comments for this task. (Removing multi-line comments is an extension.)
   • It should also strip the file of extraneous whitespace (leading spaces and tabs, trailing spaces and tabs, more hthan one space or tab in a row, more than one newline in a row). Tags such as headers, titles, list beginnings, list items, and paragraphs should put a newline character in.

   Note that this is challenging to do in a way that make the output reasonably formatted, so we will not be grading on perfect formatting. If you pay particular attention to formatting, be sure to demonstrate and describe it in your report as an extension. As a straight-forward extension, you can make your program do more sophisticated things like replace > with >.

   Report: Your goal is to describe your pattern-matching code and demonstrate that it works correctly.

   • Include an image of your terminal running flex, gcc, and finally the flex-generated program both on the test example and then on this webpage. For your self-checking, the test example result should look like this.
   • Explain your flex code. Include in that explanation an example of how one particular tag is handled.

4. Implement a parser for Clite. For now, the output of your program should just be a sequence of strings, one per line. Please use the following strings.

   Integer-<value>	A sequence of one or more digits.
   Float-<value>	An integer, a dot, and another integer.
   Keyword-<word>	if | else | while | for | int | float
   Identifier-<name>	Legal names/identifiers.
   Assignment	=
   Comparison-<symbol>	== | < | > | <= | >=
   Operator-<symbol>	+ | - | * | /
   Open-bracket	{
   Close-bracket	}
   Open-paren	(
   Close-paren	)

   Ideally, your program should also ignore comments. You can test your program on this example. You should get something like this result.

   Report: Your goal is to describe your pattern-matching code and demonstrate that it works correctly.

   • Include an image of your terminal running flex, gcc, and finally the flex-generated program on the test example.
   • Explain your flex code. Include in that explanation an example of how one particular token type (e.g. Float) is handled.

Part II: Selected Langauges

Select one language that you don't know and want to learn this semester from list A in the Languages section in the syllabus page (Note that it can be the same A langaue you picked in Project 1). You may work with a partner for the non-C language tasks. You and your partner need to choose the same language. You two will hand in your C work separately, but have a single subpage and handin for your non-C language assignments (and each person must contribute to completing the tasks for the selected language).

If you want to learn other selected languages from B/C list, you are encouraged to do so, and it can count your extension. See the Extensions section below for more details.

Tasks

1. Organize your Google Sites home page. It should be a top-level page for the course from which a user can navigate to the selected language and other non-C languages you picked as extensions. There should be a section for each language that should have a link to each project page. If you are working with a partner, there should be only one page for the selected language you learn together, but each of you should have the structure on the home page to navigate to it. In other words, the grader should be able to get to all the pages of your projects from either your or your partner's home page.

   Make sure there is a link to your project 1 on your top level page for the course.

   Having a properly organized home page is worth 3 points in this project.

   Here is a sample page for your reference.

2. For each of the selected languages, including the required one and those you picked as extensions (if you want to learn other langauges as extensions), create a subpage for Project 2.
3. The first section of each subpage lists out the language resources. Spend some time searching for useful resources, documentation, and formal descriptions of the language. Organize them in a useful way and annotate the links (e.g. "I found this site useful for explaining the concept of ..."). Think of it as your reference manual for the rest of the semester, so make it useful for you.
4. Write a "hello world" program for each language. Do something more interesting than printing hello world (i.e. don't just copy and paste a hello world example and do something more than print text). An explanation of what the code is doing, a snapshot of the program and its outputs are the second section of the report page.

Extensions

Extensions are a way for you to customize the assignment and learn something of interest to you. Pick a task and dig deeper. Pick a different language and learn something about it. Do something interesting. The following are possible extensions, but you can choose your own. Extensions can be undertaken individually or jointly. If you complete some extension individually, please specify along with your extension description in the README file. The unspecified extensions will be considered as being undertaken jointly.

1. Get comments working properly in your parser for HTML. Be sure to try out this one.
2. Get comments working properly in your parser for Clite. Be sure to try out a variety of examples.
3. Make the encoder more complex.
4. Make the parser for analyzing a document to some more interesting things.
5. A perfectly acceptable extension for any assignment going forward is to do a second language. You are encouraged to pick the second language from List B or C. The second language should have its own subdirectory on your Google Sites homepage. Under this subdirectory, there should be a set of links for all projects.

Please note that it is your responsibility to explicitly indicate the extensions you have undertaken. If you complete extensions for the parsers, please indicate explicitly in the codes and README file. If you complete extensions in selected languages, please indicate explicitly in your Google Sites report. Because extensions can be individual or joint, you need to indicate this along with your description of the extension. If no indication is provided, the grader will assume the extensions were completed jointly.

Submission

The submission of this project has two components:

1. Create a folder for Project2_<username> (e,g. for Stephanie Taylor, this would be Project2_srtaylor). Place the required files into it, zip it, and upload it to the Google Classroom.

   Required Files:

   1. Code: Create a fold for each language, including C (in this case is for flex) and your selected language(s). Place all of your C code and .yy files into the folder for C and selected language programs to corresponding folders. It should be clear which files correspond to which tasks. All these language folders should be placed into the Project2_<username> folder. Note that the quality of your comments counts toward your grade.
   2. README: We use markdown files for README files. Markdown files are files with the .md filename extension. Each project should have a README file along with all your source codes. The README file will contain:
      • Project identifier, your name, and the submission date.
      • The URL of your Google Sites report.
      • The directory layout for your hand-in folder. You can use the Unix tree command to generate this.
      • Your operating system and C compiler (e.g. use gcc --version).
      • For each task, include how to compile your program, how to run your program, known bugs if there is any, and the program output (a screenshot). The screenshot should include the actual output of running the program if the output is no more than 100 lines. Otherwise, give a brief version of the output.
      • Text and images reporting on the C part of the project.
      • A description of each extension you undertook (for the C part of the project).

      You can follow the instructions for the README file from Project 1.

2. Google Sites Report: The report of this project should have the following elements.
   • Title of the project and your name
   • Resources for the selected language(s)
   • The snapshot of the "hello world" program(s)
   • The output of the "hello world" program(s)

   To check whether you've made your report well organized, you may ask yourself the following questions:

   • Is there a top-level home page that contains a section for each selected language?
   • Does each section have a title (e.g. Ying Li CS 333, Ying’s Explorations in R, Ying’s Notes in JS)?
   • In each section, are there clearly organized links to supporting pages?
   • Does each supporting page have a title that indicates its role in the set of pages?

   Here is a recommended layout.

   	Ying Li CS333 (Home Page)
   	|_ P1 (subpage)
   	|
   	|_Ying’s Explorations in R (a section on the home page) 
   	| |
   	| |_P1 (listed in the section with a link to a subpage for P1)
   	| |_P2 (listed in the section with a link to a subpage for P2)
   	| |_...
   	|
   	|_Ying’s Notes in JS (a section on the home page)
   	| |
   	| |_P1 (listed in the section with a link to a subpage for P1)
   	| |_P2 (listed in the section with a link to a subpage for P2)
   	| |_...
   

   Here is a sample home page that reflects the above layout for your reference. Please log in to Google Sites using your Colby account before clicking the links.

© 2025 Ying Li. Page last modified: .