CSE 401/M501 23sp Project II - Parser+AST

Due: Thursday, April 27 at 11:00 pm. You will "turn in" your project as you did with the scanner by pushing it to your GitLab repository and providing a suitable tag. See the end of this writeup for details.

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. 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 two Visitors that print the AST in different ways. One should be an implementation of the Visitor pattern to print a nicely indented representation of the tree on standard output. The second should use the PrettyPrintVisitor supplied with the starter code to print a "decompiled" version of the AST as a Java source program when requested. These output formats are different and more details are given below.

Modify your MiniJava main program so that when it is executed using the command

   java MiniJava -A filename.java
it will parse the MiniJava program in the named input file and print an abstract representation of the AST on standard output (stdout).

Similarly, if your compiler is executed using the command

   java MiniJava -P filename.java
it should parse the MiniJava program in the named input file and print on standard output (stdout) a decompiled version of the AST ("prettyprint") in a format that is a legal Java source program that could be processed by any Java compiler. The -P option should use the PrettyPrintVisitor class provided in our project starter code, with whatever small modifications might be needed due to changes or additions made to the AST classes in your compiler. The decompiled version of a MiniJava program produced by this option won't necessarily have the same indenting, whitespace, or other details as the original program from which the AST was created, but it will be semantically identical.

To make this a bit more concrete, suppose we have this input file: Foo.java. The MiniJava -A abstract AST printout should resemble this output, while MiniJava -P should prettyprint the file and produce something resembling this output. Your actual output will undoubtedly be different -- these examples are intended as a concrete example of what we've got in mind, not something to be strictly matched character-for-character. In particular, the prettyprint output will very likely have differences in whitespace and line breaks, could have additional parentheses so there are no potential ambiguities, and so forth; and the AST names, indenting, and other details will depend on your compiler structure and implementation decisions. But the output needs to include the required information, appropriately formatted. (For more about parser output, see the Details section below.) Note that Foo.java is clearly an illegal Java program, but it is syntactically correct, so you should be able to parse it and build an AST.

The java commands shown above will also need a -cp argument or CLASSPATH variable as before to locate the compiled .class files and libraries. See the scanner assignment if you need a refresher on the details

Your MiniJava compiler should still be able to print out scanner tokens if the -S option is used instead of -P or -A. There is no requirement for how your compiler should behave if more than one of -A, -P, and -S are specified at the same time. That is up to you. You could treat that as an error, or, maybe more useful, the compiler could print tokens followed by the AST, or the abstract AST followed by the prettyprinted one, etc.

As with the scanner, when your compiler terminates it should return an exit or status code of 0 if no errors were detected in the input program while compiling (scanning and parsing). It should return an exit code of 1 if the input program contains any syntactic errors.

If the input program contains syntax errors, it is up to you how you handle the situation. You can simply report the error and quit immediately without producing the AST, or, if you wish, you can try to do better than that. As with the scanner, all error messages should continue to be written to the standard error stream (stderr).

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/visitors working first. You should document any extensions or error handling in the Notes/parser-notes.txt file described in the "What to Hand In" section.

Details

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 (in the parser-notes.txt file; see the end of this writeup for more details). 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 and explain how they are resolved and why this resolution is appropriate.

Note that the minijava.cup example file supplied with the starter code is intended only to show how the tools work together. The grammar given there is not a proper subset of the MiniJava grammar, and you should make appropriate changes as you create the full grammar for your MiniJava compiler.

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 like expr, term, factor, etc. CUP's input syntax is basically the same as 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.

Hint/warning: Be sure to test precedence and associativity carefully, and not just in the obvious cases involving operators like + and *. You should be sure that things like variables, array element references, parenthesized subexpressions, and method calls in expressions interact correctly with other operations, and that the resulting ASTs have the right structure (your AST print visitor can be very helpful here for visualizing the structure of the tree). For example, a+b.f() must have an AST that corresponds to a+(b.f()), not (a+b).f().

The starter code contains a DemoParser program that shows how the parsing tools work together. You can run that with ant demo-parser to see what it does (although you may need to use the original starter code versions of the jflex and CUP input files for this ant target to work successfully). You will need to adapt the ideas found there for your own compiler. Feel free to add additional targets to build.xml to help build and test your parser.

You should work out the details of the grammar and fix any conflicts first before adding semantic actions (code) to build the AST. It is easier to debug grammar problems if you work on the grammar productions by themselves before adding additional code.

Debugging

CUP has some useful features for debugging. First, the starter build.xml ant file already includes options that cause CUP to create a cup.out file in the build/ directory. This file contains details of the parser generation, including a description of the LR states and other information, which can be very useful for understanding conflicts and other problems with the grammar.

After the parser is generated, a MiniJava compiler parses its input by calling the parse() method. As described in the DemoParser.java sample program, if debug_parse() is called instead, the parser will print a detailed trace of all of the shift and reduce actions performed as it parses the input. That information can be very useful when trying to figure out parser problems, particularly in combination with the information in the cup.out file produced when the parser was generated, which describes the parser states in detail.

AST and AST Visitor Specifics

Once you have the parsing rules in place and have sorted out any grammar issues, add semantic actions (Java code associated with the grammar rules in the CUP input file) 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. Also add code to use the supplied PrettyPrintVisitor class to print the decompiled version of the AST when requested by the appropriate option used to run your MiniJava compiler.

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 in the classic expression grammar) 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 contained in the MiniJava project starter code in the src/AST directory. These are based on the ones from the MiniJava project web page with some small local changes for our purposes.

The output of the new AST Visitor 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 abstract 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 (indentation, 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 (perhaps by adding parentheses to show nesting if line breaks and indenting are not used). The sample output for the Foo.java example given above does this by printing arithmetic expressions and some individual method calls on a single line. You do not have to do this. Each of the component parts of an expression, or anything else in the tree, can be printed on a properly indented line by itself.

We have included the MiniJava Visitor interface and PrettyPrintVisitor.java file from the MiniJava project web site in the directory src/AST/Visitor in the starter code. Note that this PrettyPrintVisitor doesn't print the AST in the abstract format required above -- it is closer to the concrete syntax and doesn't have much indentation logic. But you will want to use it as the basis for your code to pretty-print the AST (compiler -P option) and you will find it useful as a starting point for understanding the visitor pattern and creating the new AST visitor (compiler -A option). Also, cloning an existing visitor is often an effective 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 continue to use your CSE 401 gitlab repository to store the code for this and remaining parts of the compiler project.

What to Hand In

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

As before you will submit your parser project by pushing code to your GitLab repository. Once you are satisfied that everything is working properly, create a parser-final tag and push that to the repository. Then we strongly suggest that you create a fresh clone of your repository in some completely different temporary directory, checkout the parser-final tag, and verify that everything works as expect. If necessary, fix any problems back in your regular working copy of the code, push the changes to the repository, and update the parser-final tag to refer to the correct commit in the repository. Then run your tests again on a fresh clone of the repository to be sure everything is working properly.

When you are satisfied that the parser-final tag in the repository correctly identifies the finished parser+ast project you are done.