Chapter 7: Syntax-Directed Translation


Getting Started

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.



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");
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");
makes p the parent of the siblings n1 and n2.