198:415 Compilers
Spring 1999
Professor Barbara G. Ryder

Programming Assignment 3
Constructing a Parser with CUP

due: 6pm Monday, March 1, 1999

This assignment is discussed in your textbook in Chapter 3. Essentially, your job is to construct a parser for a subset of the Tiger language, which we will call Ocelot, after a small wildcat that resembles a tiger (cf Webster's New World Dictionary). This parser will be constructed using CUP, a parser generator that, given a grammar with or without actions and related CUP directives, generates a parser written in Java which recognizes the language generated by that grammar. CUP is modelled after Yacc which generates parsers written in C, and was the first widely used such tool, written by Steve Johnson at AT&T Bell Laboratories in 1975.

To do this assignment you will have to construct a file that describes a grammar for Ocelot, includes directives to CUP and contains some auxiliary print actions to help you check your program. In later assignments we will include more actions in your parser, such as outputing abstract syntax trees for constructs in the language. Therefore, for this assignment your main task will be to construct a grammar that is complete (that is, it has to cover all the constructs in Ocelot) and is LALR(1) parsable, so that CUP can generate a parser for it. Since your parser will also need to scan for tokens, you will be using your scanner built in assignment2 for this assignment as well.

You will be using files stored in /usr/local/class/cs415/sp99/tiger/chap3. A description of the chap3 directory files follows:

Description of Ocelot

Ocelot is a subset of the Tiger language described in Appendix A of the Appel text. Ocelot contains no records and therefore has no recursive types nor nil constant (since it is only used with records). Arrays are limited to 1 dimension. There are no nested procedure definitions which means program structure resembles C more than Pascal with respect to procedure declarations. There are no nonterminals in the language which correspond to l-values (see p. 525, in Appel); instead we will ensure that assignments contain meaningful lefthand-side variables through a semantic check in assignment 4, rather than a grammar check. This means that your grammar will allow nonsensical constructs such as 2+3 := 4*x and our semantic analysis will have to catch such errors.

How to proceed?

For organizing your cs415 work, you should create a new subdirectory for every new assignment. All assignment directories and files should be read and write protected so that only you can read or write the directory and its files.

In addition, you will need to add to your CLASSPATH in order to access the packages needed to do this, and subsequent assignments. The easiest way to do this is to add the following line to your .cshrc or .tshrc file:

#a change to access packages in cs415
setenv CLASSPATH .:/ug/s1/class/cs415/sp99/JLex/classes/:/ug/s1/class/cs415/sp99/CUP/classes/

To begin, you should create a working directory proj3 for Assignment 3 and then copy the directory /usr/local/class/cs415/sp99/tiger/chap3 recursively (use -R to get subdirectories) to your working directory.

If your scanner worked, you should also copy your Tiger.lex file from your proj2/Parse subdirectory into your proj3/Parse subdirectory. Once this is done, the proj3 makefile should work correctly. Also, you can delete the subdirectory ./working-lexer/ and its files, as you will not need them.

If your scanner did not work, you will have to use the files in subdirectory ./working-lexer/ of directory /usr/local/class/cs415/sp99/tiger/chap3. They include (i) a scanner Yylex.class which you need to copy into your Parse subdirectory and (ii) a different makefile, makefile-wo-lexer which needs to be in your working directory. To use this makefile you will need to type make -f makefile-wo-lexer.

Augment Grm.cup to contain the CUP directives and grammar rules plus actions needed to parse Ocelot and print out nonterminals as you recognize them. Note: as before you can add rules for a few constructs at a time, just as long as you only include those constructs in the Ocelot programs you use as input. The Grm.cup file stays in your proj3/Parse subdirectory.

Make several files test%.tig (for %=1,2,3...), each containing a short program in the Ocelot language. Use them to test your parser.

In your working directory, after having updated the file Grm.cup, execution of the make command should echo to your terminal the steps its taking something like this:

380 remus!proj3> make
cd Parse; java java_cup.Main -parser Grm -expect 3 -dump_grammar -dump_states Grm.out 2>Grm.err
javac -g Parse/*.java

Now to execute your parser on input file test.tig in your working directory using the main method in Parse.Main, type: java Parse.Main test.tig

We will be using the handin program for this assignment. This time we want you to turn in a hard copy of your COMMENTED Grm.cup file, including a listing of the test data used to test your program. We also require a 1-2 page (not handwritten) summary of what you have done. Make sure you describe any error handling you have implemented and any other special features of your parser. Please make sure your code is runnable. It is preferable to submit code which contains only a subset of the language assigned, but which runs, rather than code that supposedly covers everything assigned, but does not compile or run correctly.

Last updated by Barbara Ryder at 11:09am on February 18, 1999.