CSE 401, Winter 2014

Robert R. Henry

Assignment 4

Parser and AST builder for Mini Java

Due via dropbox Friday January 31 by the end of the day (midnight).  This assignment involves a lot of fairly repetitious work, so be sure to get started early!

Parsing

  1. In this assignment you will be extending the existing CUP specification for Mini Java to be able to parse the final mini Java language.
  2. Read the EBNF specification of the Mini Java grammar here http://www.cambridge.org/resources/052182060X/MCIIJ2e/grammar.htm. Remember that we’ve made some simple extensions on top of this specification; see the main project assignment for a discussion of these extensions.
  3. You’ll be modifying, mostly, the source file src/Parser/minijava.cup which is the grammar specification given as input to the CUP parser generation tool.
  4. Read up, as necessary, on the CUP parser generation tool for Java http://www2.cs.tum.edu/projects/cup/manual.html Don’t get bogged down, as there is a lot of stuff there that we won’t need to worry about.
  5. Familiarize yourself with the form and general contents of the CUP produced output diagnostic file src/Parser/cup.out
  1. Figure out where in the output the token (terminal) numbers are shown.
  2. Figure out where the state numbers are shown.
  3. Figure out what itemset makes up each state, together with the lookahead.
  4. The contents of this file will be invaluable when trying to figure out why you have a parse error (is my grammar wrong? is my test program wrong? is my scanner constructing the wrong token?).
  5. You’ll also need this file to help “grammar hack” as needed to resolve shift-reduce and reduce-reduce conflicts.
  1. Extend the existing grammar to handle the entire Mini Java grammar, including doubles.  (doubles syntactically are basically identical to integers)
  2. You will have to discard or rename or reuse the scaffolding display statement as your test programs should now be using System.out.println instead.
  3. You will have to carefully add precedence information to the CUP specification.
  4. You will come across a troubling situation where there are 2 concatenated optional constructs. Consider grammar hacking to cover all 4 (2**2) cases...
  5. When finished you should be able to parse (with main from src/TestParser.java) all of our test programs, perhaps with the exception of those involving doubles.
  6. You do not need to worry about syntactic error repair or recovery.  The CUP parser will just exit if it gets stuck.  That’s our general strategy for errors anyway.
  7. You can trace the actions of the parser by invoking the Mini Java compiler with the -p flag.  In fact, there’s a line in build.xml that is currently commented out that shows where/how to pass in the -p flag.

AST Building

  1. The AST data structure supplied in the base project is almost complete!
  2. If you don’t understand the EBNF productions for the language, or don’t understand what productions to use, consult the corresponding AST subclass for that part of the language, and your task ahead may all of a sudden look very easy.
  3. You will have to add AST subclasses for the set of operators we have added to extend the language, such as <= and ||.
  4. You may find the the AST subclasses need a little refactoring, for example adding a new intermediate base class, and then extending that new base class for the specific AST node.
  5. You will have to import the new AST classes as and where needed.
  6. You will have to figure out how to specify the Java types of terminals and nonterminals.
  7. You will have to connect all the inherited (bottom-up) attributes together, typically in a straight-forward 1:1 association with arguments to AST constructors.
  8. You will have to figure how the dorky identifiers CUP creates to track source line numbers, as every AST constructor wants to know the Mini Java source line number it came from, as you will want this information later…
  9. You should be able to have a PrettyPrintVisitor crawl the resulting AST and produce plausible output.  There’s (disabled) sample code in src/TestParser.java to do this.

Discussion

  1. Is the pretty printed output you produce syntactically equivalent to what you were given?  If not, why not, and what might you do to fix that?

What to turn in

  1. Your group will need to turn in through the class dropbox a tar file that contains your entire project directory.  This will make it easier for us to grade the project, either by executing what you have created, or letting us do some lateral exploration of your source code in order to ferret out and comment on problems we might see.
  2. PLEASE make sure to include a comment at the beginning of the .cup file that has your group’s name and the names of those in your group.
  3. The pretty printed output of a mini Java program we supply. In this way we can ensure that you have the parser and AST builder hanging together. You can find the program in the dropbox.