MC97 Lab 3: Parsing and AST generation (Spring 1999)

Due: March 10, 1999

For this lab, you are to do the parsing and AST generation assignments from pages 83-84 and 106 of the textbook. You need not turn in a separate solution for the chapter 3 part; it should be included in your solution to the chapter 4 portion. However, it may be to your advantage to deal with the chapter 3 issues (parsing) first, and only then move on to chapter 4 (AST generation).

First, copy the chap3 directory and the chap4 directory of files that Appel provides into the directory you are going to work in and look at them. You can access the chap3 directory off of this web page or copy it from ~max/www-docs/courses/S1999/MC97/tiger/chap3 and similarly for chap4. The simplest way to do this would be using the command

cp -pr ~max/www-docs/courses/S1999/MC97/tiger/chap[34] .

which will give you your very own chap3 and chap4 directory trees, just like mine. Note that I have fixed a couple bugs in Appel's code; if you for some reason want to use the code from his web site instead of mine, you'll need to make those same fixes.

Next, copy your chap2/Parse/Tiger.lex into chap3/Parse. Then compile the program as it stands. To do this, change directory to the chap3 directory, set your CLASSPATH environment variable so that java can find JLex and java_cup, and then run the make command:

cd chap3
setenv CLASSPATH ~max/JavaLib:.
make

To test this initial minimal version of the lexical analyzer, make a file (called foo.tig, for instance) containing nothing but a single identifier (possibly with spaces, newlines, and comments). Then give the command

java Parse.Main foo.tig

This should terminate silently, which is the sign of a successful parse. If you now repeat the experiment, but with foo.tig containing any other sequence of tokens, you should get a syntax error reported. This is because the initial grammar specifies that a program is nothing but a single identifier.

Your lab report should include documentation of design and testing as well as your code.

Tips regarding tiger/chap3

The Parsetest.java mentioned in the book is actually Parse/Parse.java and Parse/Main.java.
The makefile may need to be altered to give java_cup an -expect argument if your grammar has conflicts, and they make sense.
Note that the makefile is set up to produce Grm.out and Grm.err as well as Grm.java from Grm.cup; these contain the standard output and error output from java_cup.
The makefile will need to be altered if you choose to start from my Yylex.class rather than your Tiger.lex
The way Appel set the makefile up, if there is an error in the Grm.cup file, you see a strange error from javac. The relevant error message (from java_cup) is in Grm.err.
If you use my Yylex.class, you need to not change the list of terminals in Grm.cup, except possibly by adding terminals (such as UMINUS) to its end. To repeat: any addition must be at the end of the list. (Otherwise the numerical codes assigned to the terminals will be different than assumed by my Yylex.class.)
Sometimes to get make to actually regenerate everything that needs regeneration, you may need to either manually delete some files first, or add a make clean action to the makefile to use for this purpose. Then again, you could rewrite the makefile so that this isn't necessary.
Dealing with the confusion mentioned at the bottom of page 83 is non-trivial. Here are some hints:
- Remember, it is up to you whether to have a separate type_id nonterminal or instead just use the ID terminal.
- Remember that you can introduce other nonterminals and restructure the grammar relative to Appendix A; you needn't slavishly copy it. This may allow you to avoid a conflict.
- Be sure you really accept the full Tiger language. It is easy when trying to resolve conflicts to accidentally trim the language down to only a subset of what it should be.
Chapter 4 will be easier if you define lists as either empty or nonempty, and then use a right-recursive definition for nonempty lists. (From the perspective just of chapter 3, other options, such as left recursion, would be at least as sensible.)
To make later chapters easier, change the language specification to disallow empty records. Note that this makes testcases/test33.tig test a different error than the comment indicates.

Tips regarding tiger/chap4

Starting with the given files plus your Parse/Tiger.lex (or with the makefile altered to use my Parse/Yylex.class), you can do
```
setenv CLASSPATH ~max/JavaLib:.
make
java Parse.Main added-tests/foo.tig
```
And see an AST printed for a very simple program.
Initially ignore the combining of adjacent (mutually recursive) type or function declarations. Add this in later once you have the basics working.
Be tuned in to Appel's dual use of null. He uses it it both for omitted information (e.g, the type of a variable that has had no type declared, or the return type of a procedure) and also for empty lists.
Beware of the switch in mnemonics going from terminals (which have NEQ, TIMES, DIVIDE) to OpExps (which have NE, MUL, DIV).
If you do error recovery, you will need to provide semantic values for errors.
Beware using java_cup keywords (like init or start) as names in your grammar.
Beware that ExpList and DecList have no pos.
Treating a parenthesized expression as a one-element sequence is likely to make matters easier.
Using grammatical means to group adjacent type or function declarations is probably the hard way. (The alternative is to do it using your Java code.)

Instructor: Max Hailperin