Comp 212 Homework 3
Abstract Syntax Tree and Visitor Pattern
Due Monday, February 17, 2003, 1:00 PM
No late submission will be accepted.
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 concern 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. 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.
The homework is to be submitted electronically.
The due date is
due Monday, Feb. 17, 2003 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: