Comp 212 Homework 4
Abstract Syntax Tree and Visitor Pattern

Due Wednesday, February 16, 2005, 1:00 PM

No late submission will be accepted.

I. Abstract Syntax Tree

A common problem in computing is to read in an arithmetic expression such as 3 * (4 + 5) and evaluate it.  This can be done by first parsing it and create a corresponding "abstract syntax tree" (AST):

  /    \
3      +
      /     \
    4        5

Once the AST is built, one can then traverse and evaluate it.  We are not concerned with the problem of parsing at this point in time.  What we want to do in this exercise is to build an object model for the AST and then write visitors to interpret it.  We shall restrict ourselves to arithmetic expressions containing integers, strings (representing variables), and binary operations such as  addition and multiplication.  To evaluate such an expression, we need to have an environment that matches each variable in the expression with an integer value.  An environment can be viewed as a set of id/value pairs.  The complete UML diagrams with full javadoc documentation of an AST, its visitors and environments are given here.  Because of the limitation of our UML tool, the variable arguments notion Object ... input is represented as Object[] input.

Your assignment is to

You need not submit the UML class diagrams as shown.

II. Submission

The homework is to be submitted electronically.

The due date is due Wednesday, Feb. 146 2005 at 1:00 PM.  

The homework is to be submitted via the turn-in script, with project name ast.  No late submission will be accepted.  The submission should contain the following:

dxnguyen at         Please let us know of any broken links             Revised February 09, 2005