Comp 212 Homework 4
Abstract Syntax Tree and Visitor Pattern
Due Wednesday, February 16, 2005, 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):
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 notionObject ... input is represented as Object input.
Your assignment is to
You need not submit the UML class diagrams as shown.
The homework is to be submitted electronically.
The due date isdue 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: