CSE P 501 Sp14 Project II - Parser and Abstract Syntax

Due: Monday, April 28, at 11:00 pm. You should turn your project in using the assignment dropbox

Overview

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.

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.

Details

You will need to massage the MiniJava grammar to make it LALR(1) so that CUP or equivalent tools can use it to produce a parser.

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 or shift-reduce conflicts.

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 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 separate line, and children of a node should be indented below it to show the nesting structure. The output should include source line numbers for major constructs in the tree (certainly for individual statements and for things like class, method, and instance variable declarations, but not necessarily for every minor node in, for example, expressions). 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 separate 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.

We have included the MiniJava Visitor interface and PrettyPrintVisitor.java file from the MiniJava project web site 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 pattern works, and cloning an existing visitor is often a good way to start developing a new one.

What to Hand In

The main things we'll be looking at in this phase of the project are the following: