CSE P 501 Project III - Abstract Syntax

Due: Wednesday, Nov. 4, by 11 pm. Turn in your project using the assignment drop box (links on the project page).

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 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 (or equivalent record type if you are using a different language) 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.  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.  It would be good for each class to 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, although this is not strictly required. 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 look at the MiniJava AST code on the MiniJava project web page as a possible starting place for your code. We have included those classes in the updated version of the MiniJava starter project for your convenience. You are, of course, welcome to proceed differently if that makes sense for your project, particularly if you are using a different implementation language.

We have also included the MiniJava Visitor interface and PrettyPrintVisitor.java file from the MiniJava project page in the directory AST/Visitor in the updated starter project. Note that this PrettyPrintVisitor doesn't produce the printed representation of the AST 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.

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.
• Source files containing definitions of the AST node classes and visitors.
• A README file explaining how to build and run your compiler, including a description of any required software or libraries if you're using your own project setup, along with notes about any extensions or other unusual or interesting things in this phase of your compiler.
• Printed AST representations produced by the visitor pattern for some small sample programs. These must include the Factorial.java sample program from the MiniJava web site.

As with the parser, it is ok to turn in your complete compiler source tree in an archive. If you do that, be sure that it's easy to find the requested items for this assignment, and do the equivalent of a make clean to clear out compiled files and other artifacts from the source tree you hand in.

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.