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:

• Parse/Grm.cup This file is the one you need to update with your grammar for Ocelot and the auxiliary print actions (so you can see that you are recognizing the constructs correctly). This file provides the skeleton of your input to CUP. You may need to add some CUP directives to complete this file. You should leave this edited file in the Parse subdirectory. A sample of the code already provided includes the following; note the trivial grammar rule at the end.

  
  ...
  scan with {: return lexer.nextToken(); :}; 
  terminal String ID, STRING;
  terminal Integer INT;
  ...
  non terminal program;
  
  start with program;
  
  program ::= ID
           ;
  

• Parse/Lexer.java This file contains the definition of an interface which the Yylex class implements. It provides a nextToken() method which throws an exception if the input stream is empty when it looks for a token. It is the same as in assignment 2.

  
  interface Lexer {
      public java_cup.runtime.Symbol nextToken() throws java.io.IOException;
  }
  

• Parse/Main.java This file provides a sample test driver to use to test your parser; note this program is different than the main method you used to test your scanner.

• ErrorMsg/ This directory contains a package ErrorMsg which consists of the class ErrorMsg that provides methods for keeping track of where the scanner is looking for a token in terms of character position in which line of input. This is the same package we used with assignment 2.

• makefile This new makefile contains new dependences for assignment 3, needed to construct the parser with the scanner.

Description of Ocelot

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