Due: Tuesday, Feb. 9, by 11 pm. Turn in your project using the assignment drop box (links on the project page).
Add semantic actions to your parser to create an Abstract Syntax Tree (AST)
representation of the program. For this assignment, just build the AST.
Semantic analysis and type checking will come next. In addition to building
the AST, you should implement the Visitor pattern and use it to print a nicely
indented representation of the tree on standard output. The goal of this output
is to produce 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 format 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 occupied by the output, 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.
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 rule in the 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 righthand 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.
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 include a test program for this phase of the project in a class TestAST
stored in file
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 thing we're looking at in this phase of the project are the following:
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.
If you are working with others, you should turn in only one copy per group with everyone's name on it, listed in the same order as before.