Lab 3: Abstract Syntax Trees
Lab Assigned Lab Due
(Start of class)
12 Feb 28 Feb

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

More so than usual, you are advised to begin this assignment right away. There are design decisions to be made as well as expertise to be developed in the grammar development cycle. For many students, beginning early on this lab can improve their final grade in this course by a letter! In student reviews of this course, the advice of beginning assignments early is often given.

In this lab, you are given a CUP (Constructor of Useful Parsers) grammar for a subset of the Java language jmm , which stands for "Java minus minus".


  1. 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.
  2. To turn in your work, use:
    mail -s 'homework 3 lastname_firstname' cs431@cec < jmm.cup
    Do not submit by any other method.