CSE P 501 Project III - Abstract Syntax

Due: Wednesday, February 6, by 11 pm. Turn in your project using the CSEP 501 Wi08 dropbox.

Overview

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. Don't worry about excessively long lines in the output, but have each complete statement start out on a new line, indented to show the relative nesting of the statements in each method. The tree printout does not need to include all of the syntactic details of the original program - it's fine to omit curly braces ({}), semicolons, and other punctuation, and let the indenting show the structure instead. If it is more convenient, you can print the tree with the root at the bottom instead of the top.

The tree should represent the abstract structure of the code, not the concrete syntax.  Nodes for nonterminals should contain references to nodes representing non-trivial component parts of the nonterminal, i.e., the non-trivial symbols on the righthand side of an abstract grammar rule.  Trivial symbols 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.

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. For instance, there should almost certainly be only one node type for conditional statements, even though the else part of an if statement is optional.

The classes defining the different abstract syntax tree nodes should take advantage of the Java class hierarchy to build a strongly-typed, self-describing tree.  There should be a handful of abstract classes and/or interfaces for major nonterminals like Stmt and Exp.  Extend these classes to represent different productions in the abstract grammar, such as specific kinds of statements.  For convenience, each class should contain a constructor that initializes appropriate fields in a node when it is created as part of a semantic action in the parser.  Each class should also contain an appropriate toString() method that yields a readable form of that node including, in simple cases like a single statement or expression, its children. For higher-level constructs like a block, it's probably easiest if toString() returns a fairly short string describing the block, leaving it to a Visitor pattern to print the statements in the block if desired, indented on succeeding lines.

We suggest that you use the MiniJava AST code on the MiniJava project web page as a starting place for your code.

Your main program for this phase of the project should execute the parser and build an AST, then print the AST using the Visitor pattern.

What to Hand In

Turn in the following fiiles:

• The specification, including semantic actions, for your parser.
• Java source files containing definitions of the AST node classes.
• A README file explaining how to build and run your compiler, along with any notes about extensions or other unusual or interesting things in this phase of your compiler.
• Printed AST representations produced by the visitor pattern of some small sample programs.

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.