Parser & AST using CUP

Need assistance with my Parser & AST using CUP. You will find more info in the file below..Its a hard deadline won’t be able to extend it.

Programming Assignment 2 – Parser & AST
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 an implementation of the Visitor pattern to print a
nicely indented representation of the tree on standard output. You should also 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 -P filename.java
it will call a parse function that will parse the MiniJava program in the named input file and print
on standard output a decompiled version of the AST (“prettyprint”) in a format that is a legal Java
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 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 (HW1) if you need a
refresher on the details.
As with the scanner, when your compiler terminates it should return an exit or status code of 0 if no
errors were detected while compiling (scanning and parsing) the input program. It should return an
exit code of 1 if any errors were detected.
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 without producing the AST, or, if you wish, you can try to do better
than that.
Your MiniJava compiler should still be able to print out scanner tokens if the -S option is used
instead of -P. There is no requirement for how your compiler should behave if more than one of -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 prettyprinted one, etc.
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.
Programming Assignment
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. You may need to massage
the MiniJava grammar to make it LALR(1) so that CUP 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 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.
Your grammar should not contain any reduce-reduce conflicts, and should have as few shift-reduce
conflicts as possible.
It is recommended that you start by compiling your minijava.cup file on the command line in order to
identify compilation errors, using the following command:
java -jar lib/java-cup-11b.jar -expect 1 src/Parser/minijava.cup
CUP has some useful features for debugging. First, the starter build.xml ant file includes options
that cause CUP to create a build.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 TestParser.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 build.out file produced when the parser was generated,
which describes the parser states in detail. You can run the TestParser.java sample program
from the command line by piping in the file data to the input stream as follows:
java -cp build/classes:lib/java-cup-11b.jar TestParser < SamplePrograms/Example.java For those building their program in Cygwin, the Windows operating system handles paths slightly different than Linux. To compile your program use the following command (note the use of a semicolon in place of a colon to separate paths, and the use of quotes): java -cp "build/classes;lib/java-cup-11b.jar" TestParser < SamplePrograms/Example.java Note that TestParser.java is designed to work with an incomplete form of the mini java grammar. After you complete the mini java grammar in this assignment, TestParser.java will require some adjustments in order to work, specifically when accessing the root node, which it assumes to be a list of Statements and not a Program. 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). 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 non-terminals 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) 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. It is suggested that you start with the AST classes given on
the MiniJava project web page. This code with some small local changes is included in the starter
code for our project.
Once the AST is complete, you should add Visitor code to print a nicely indented representation of
the AST on standard output using the supplied PrettyPrintVisitor class. The Pretty-Print
output should produce legitimate Java code that can be compiled. The MiniJava Visitor interface
and PrettyPrintVisitor.java file is located in the directory src/AST/Visitor.
You should test your parser, semantic actions, and printing visitor by processing several MiniJava
programs, both correct ones and ones with syntax errors. A directory of sample Java programs is
provided for you in the MiniJava starter project to use as input. To make this a bit more concrete, a
sample prettyprint of the BinarySearch.java program is provided for you to check your work. Your
actual output may differ slightly, but it should be relatively similar. Make sure to run your scanner
MiniJava program on all the programs in the SamplePrograms directory. It is expected that your
program will complete with no errors.
To compile and run MiniJava’s main method from a command prompt, the Java virtual machine
needs to know where the compiled classes and libraries are located. The following commands
should recompile any necessary files, run the parser, and print the code to screen:
ant
java -cp build/classes:lib/java-cup-11b.jar MiniJava -P filename.java
Again, for those building their program in Cygwin on Windows, use the following modified command:
java -cp “build/classes;lib/java-cup-11b.jar” MiniJava -P filename.java
What to Hand In
The main things we’ll be looking at in this phase of the project are the following:
•
•
•
The grammar specification, including semantic actions, for your parser.
Source files containing definitions of the AST node classes and visitors.
AST representations produced by PrettyPrint visitor (-P option).
To submit your code, you must first clean the entire directory using the following command:
ant clean
After the directory has been cleaned, compress the entire minijava_starter directory structure into a
.zip file with the following name structure: csc348_hw2_[lastname]_[firstname].zip
Submit the code to D2L along with sample output in an output.txt file in the submission folder –
separate from your zip file. This is to demonstrate that your code ran correctly before submitting it.
We will test your code by building and running your project using ant and Java from the command
line, using one or more sample programs from the project. Please make sure your program runs and
generates the correct output before submitting it.