Due: This phase of the project has two deadlines. A debugged, working grammar (CUP specification) should be turned in by 11 pm, Wed., Oct. 27, and is worth 15% of the total credit . The completed parser and AST , including the printing visitor, is due on Mon. Nov. 1 at 11 pm.
For this part of the project, construct a parser (recognizer) and build abstract syntax trees (ASTs) for MiniJava. You should use the CUP parser generator tool to interface with your JFlex scanner. Be sure that your parser and scanner together can successfully parse legal MiniJava programs.
The semantic actions in the parser should create an Abstract Syntax Tree (AST) representation of the parsed program. For now, just build the AST. Semantic analysis and type checking will be included in the next part of the project.
In addition to building the AST, you should provide an implementation of the Visitor pattern to print a nicely indented representation of the tree on standard output (more below).
Feel free to experiment with language extensions (additional Java constructs not included in MiniJava) or syntactic error recovery if you wish, but be sure to get the basic parser/AST/visitor working first.
You may need to massage the MiniJava grammar to make it LALR(1) so that CUP can use it to produce a parser. Please keep track of the changes you make and turn in a description of them with this part of the project (see below).
Take advantage of precedence and associativity declarations in the
parser specification to keep the overall size of the parser grammar small.
(In particular, exp ::= exp op exp productions along
with precedence and associativity declarations for various operators will shorten
the specification
considerably
compared to a grammar that encodes that information in separate productions.)
CUP's input syntax is basically the same that used by YACC and Bison, described
in many compiler books. It should be easy enough to pick up the syntactic details
from
the CUP
documentation and
example
code.
Your grammar should not contain any reduce-reduce conflicts, and should have as few shift-reduce conflicts as possible. You should describe any remaining shift-reduce conflicts in your writeup.
Once you have the parsing rules in place and have sorted out any grammar issues, add semantic actions to your parser to create an Abstract Syntax Tree (AST) and add Visitor code to print a nicely indented representation of the AST on standard output.
The AST should represent the abstract structure of the code, not the concrete syntax. Each node in the tree should be an instance of a Java class corresponding to a production in an abstract grammar. The abstract grammar should be as simple as possible, but no simpler. Nodes for nonterminals should contain references to nodes representing non-trivial component parts of the nonterminal, i.e., the important items on the right-hand side of an abstract grammar rule. Trivial things like semicolons, braces, and parentheses should not be represented in the AST, and chain productions (like Expression -> Term -> Factor -> Identifier) should not be included unless they convey useful semantic information. The classes defining the different abstract syntax tree nodes should take advantage of inheritance to build a strongly-typed, self-describing tree. We suggest that you start with the AST classes given on the MiniJava project web page and included in the starter code for the project.
The Visitor output should be a readable
representation of the abstract tree, not a "de-compiled" version
of the program, and, in particular, the output will not be a syntactically
legal Java program that could then be fed back into a Java compiler. Each node
in the tree should normally begin on a seprate line, and children of a node
should be indentented to show the nesting structure. The tree printout should
not include syntactic noise from the original program like curly braces ({}),
semicolons, and other punctuation that is not retained in the AST, although
you should use reasonable punctuation (whitespace, parentheses, commas, etc.)
in your output to make things readable. Although most tree nodes should occupy
a single line in the output, you can, if you wish, print things like expressions
on fewer lines to reduce the vertical space used, as long as your output clearly
shows the AST structure of the expression. If it is more convenient, you can
print the tree and subtrees with the roots at
the bottom instead of the top.
We have also included the MiniJava Visitor interface and PrettyPrintVisitor.java file from the MiniJava project page in the directory AST/Visitor in the starter
code. Note that this PrettyPrintVisitor doesn't print the AST in the format
requested for this part of the project - it is closer to the concrete syntax
and doesn't have much indentation logic. But you may find it useful as a starting
point for understanding how the visitor parttern works, and cloning an existing
visitor is often a good way to start developing a new one.
You should test your parser, semantic actions, and printing visitor
by processing several MiniJava programs, both correct ones and ones with syntax
errors. You should create a test program for this phase of the project in
a class TestAST whose source file is TestAST.java in
directory src in
the MiniJava project tree. When executed without arguments, TestAST should
read a MiniJava source program from System.in, parse it, build
the AST, then print the AST using your Visitor implementation. If any errors
are detected while scanning or parsing the MiniJava input, TestAST should
exit with a non-zero return code (System.exit(1); or something
similar), otherwise it should exit normally.
The main things we'll be looking at in this phase of the project are the following:
Factorial.java sample
program from the MiniJava web site.README file describing any changes you made to the
grammar, and a list of shift-reduce conflicts remaining in the grammar (if
any) with an explanation
of why these are not a problem.As before, your code should run on attu when built with ant. You should do an "ant clean", then bundle up your compiler directory in a tar file and turn that in. That will ensure that we have all the pieces of your compiler if we need to check something.
You and your partner should turn in only a single copy of the project using
one of your UW netids, preferably the same one you used for the scanner, although
this is not required. Your README file should include your names and uw netids
so we can correctly identify
everyone
involved
in
the group
and
get
feedback
to you. Multiple
turnins are fine - we'll grade the last one you give us. In particular, if
you plan on adding error handling or other extra features, turn in a copy
of the
working,
basic
assignment first before you add these, then turn in the enhanced parser
later once you have it working.