Programming Assignment 3

Getting Started

* Locate and install the Labs/3 project into your eclipse workspace.

* Browse this lab document to get an idea of the work you will do for this assignment.



Abstract: You will gain experience with syntax-directed translation, bottom-up parsing, and the structure of the Java programming language by constructing abstract syntax trees.



Notes

In this lab, you are given jmm.cup, which is a CUP grammar for a subset of the Java language jmm , which stands for Java minus minus. Browse through the file and familiarize yourself with the structure of this grammar. It is the only file you should modify for this assignment.

You are advised to follow the following strategy as you develop your solution. Failure to follow this advice will increase your development time and could cause anxiety and confusion.

* The very top part of the AST is already created for you, starting at the rule for CompilationUnit and ending at TypeDeclaration (which is really just a completed class declaration).

* The build.xml file allows you to run your solution or the reference parser. The targets run a given parser on all of the test files found in the TestFiles directory.

* Take a look at the ASTs produced by the reference parser by running the appropriate ant task described below.

* Now look at what happens when you run your parser. You will see the topmost part of the tree only. It's your job to construct the rest of the AST.

* Proceed by slowly descending down the grammar, implementing a little more, and compiling and testing as you go. For example, the next thing you might do is create nodes for each ClassDeclaration. At first that node could just be a simple TemporaryNode, and you can fill in more detail later, such as the class name, protection bits, and class body.

* Proceed slowly and test as you go to make sure your AST is developing the direction you desire.



Debugging

Debugging with tools like CUP can be confusing, because:

* Your code in the .cup file is translated into .java code.
* Exceptions raised in the .java file are reported with respect to the .java line numbers.

To figure this out, you'll have to trace the exception back to problems in your .cup file:

1.) Go to the error line in the Parser.java file, and look up to find the case clause that shows the relevant production in your .cup file.
2.) Now look in your .cup file at the semantic code and try to find the problem.
3.) Failure to create objects in semantic actions will lead to null-pointer exceptions. As described below, the TemporaryNode class is available to act as a place-holder while you decide more customized node-types to instantiate.



The following ant tasks will help you with building and testing your lab:

build Default target, runs appropriate tools and compiles your project to bring it up-to-date. This does not run your parser on any inputs!
runYourParser Runs your parser on all files in the TestFiles directory
runYourParserTrace Runs your parser in trace mode on all files in the TestFiles directory. The trace shows the actions of the shift-reduce parser so that you can determine where and why the parser detects an error in a test file.
runReferenceParser Runs the reference parser on all files in the TestFiles directory, showing the resulting ASTs.
clean Deletes the class files and all automatically generated files. Use this if things are behaving weirdly.


Be certain only to modify the file jmm.cup as you work on this assignment.



Specifics

For the rules present in jmm.cup, you are asked to design and implement an abstract syntax tree (AST). It is suggested that you first think about your design and sketch some possible layouts on paper prior to working at the computer. You could also run the class solution to get ideas about how to structure your AST. To help you implement the tree, the following factory methods are provided in the jmm.cup file; each instantiates a subclass of AbstractNode.

makeNode(Symbol) Constructs an AST node, labeled by the Symbol supplied as input.
This is useful where you want to take a rule such as:

SelStmt ::= IF:ifterm LP Expr RP Stmt 

and make an AbstractNode out of it by:

AbstractNode ifnode = makeNode(ifterm); 
makeNode(String) This is the recommended way to put nodes in the AST to show us the structure you want. In future labs, you'll want more refined subclasses of AbstractNode so you can put in specialized code for each node type, but for now, this kind of node is very useful.
makeSibling(AbstractNode) is a method for class AbstractNodethat appends one or more sibling nodes. For example

 AbstractNode n1 = makeNode("SomeKindofNode");
 AbstractNode n2 = makeNode("AnotherKindofNode");
 n1.makeSibling(n2);

makes n2 a sibling of n1.

In general, if n1 is a node in the middle of sibling list1, and n2 is a node in the middle of sibling list2, then the above code would have the effect of appending list2 to list1.

This method returns the rightmost sibling in the resulting sibling list.
adoptChildren(AbstractNode) is a method for class AbstractNodethat brings a set of siblings under a parent. For example

 AbstractNode n1 = makeNode("Sib 1");
 AbstractNode n2 = makeNode("Sib 2");
 AbstractNode p  = makeNode("Boss");
 p.adoptChildren(n1.makeSibling(n2));

makes p the parent of the siblings n1 and n2.


* The class AbstractNode can be extended to make useful abstract syntax tree nodes. Important examples of this are IntegerNode and TemporaryNode which are included in the jmm.cup file in the action code block.

* If you need some auxilliary classes or methods to simplify your semantic actions, these can be placed as methods in the action code block. Several examples are already there for you to see how this can be done.