Comp 212 Homework 04: Abstract Syntax Trees

Comp 212 Homework 4
Abstract Syntax Tree and Visitor Pattern

See Course Web Page for due date

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

read the documentation of each the diagrams, figure out what it means and implement (i.e. write the code for) it;
write appropriate JUnit test classes to test every concrete public method of every class;
document the code in javadoc as shown.

You need not submit the UML class diagrams as shown.

II. Submission

The homework is to be submitted electronically via OWLSPACE. No late submission will be accepted. The submission should contain the following:

A plain text file called README documenting what you have and/or have not done, describing specific details that you feel we need to know when grading your work. This README file alone is worth 5 points.
Pledge of Honor: add your pledge of honor to the README file.
All the Java source code necessary to compile and execute your test code.

dxnguyen at rice.edu Please let us know of any broken links Revised February 05, 2007