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 .
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:
setenv CLASSPATH ~max/JavaLib:.
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
- 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
Instructor: Max Hailperin