Due: Thursday, October 2 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 computers in the robotics lab have flex installed already, so if you have difficulty installing and using flex on your machine, you are welcome to use one of these. You can either physically access or remotely SSH to these machines. To SSH to one of the machines, use the command line ssh yourColbyUserName@machineName where machineName is in the range d122-01 to d122-15. Assume Ying picks d122-03, the command line would be ssh yingli@d122-03

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. Using Flex, make a program that makes your prose slightly more exciting and less numeric. You can think of this as an editor who wants to bring your prose up a level in terms of conventions (use "one" instead of "1") and more emphatic words. But we are going to be very simplistic with the emphatic words. We simply make every "cat" a "lion".

   • Replace each instance of the work "cat" with the word "lion" but be sure not replace just the letters cat within a longer word. You should not care what case the letters are and you should handle both "cat" and "cats".
   • Replace each number (digits 0-9, and the number 10) with the word version of that number (e.g. "1" should be "one"). Here also, be sure not to replace any of these numbers in the context of a longer number or word (e.g. "123" should be left as "123" and "cat2cat" should be left as "cat2cat".

   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. For your self-checking, the test example result should look like this.
   • Explain your flex code. Include in that explanation an example of how you avoided changing "Catch" into "lionch".

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 language you picked in Project 1 but that it cannot be Python or Java, if you took CS231 and CS25X at Colby).

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.

   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.

1. Get comments working properly in your parser for Clite. Be sure to try out a variety of examples.
2. Make the encoder more complex.
3. Make the parser for improving the prose do some more interesting things.
4. 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.

      Please do NOT include: Executable files. On Windows, these have the .exe extension. On Mac and Linux, there is no e xtension. We have found that graders often have difficulty downloading submissions if they contain executable files.

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: .