CIT 594 Program Tree Interpreter
Spring 2007, David Matuszek

Purposes:

General Idea:

Programs can be represented as general trees. In this assignment you are to build some trees and evaluate them. Your programs will include arithmetic expressions, conditions, a "print" statement, and a few control statements. You will need to deal with both boolean and numeric expressions, and variables.

Also, please refer to the Rules for Assignments.

Provided software:

Tree.java and TreeTest.java, in package trees.zip. This is a package; to use it, copy the entire folder into your Interpreter project folder, and use the statement import trees.Tree; as the first line in your program file. In Eclipse, it should look something like this:

Basic documentation for the Tree class is on Tree.html.

Details:

Write a class named Interpreter with these methods:

int evaluate(Tree<String>)
The argument to this method is a Tree that evaluates to an integer.

boolean evaluateBoolean(Tree<String>)
The argument to this method evaluates to a boolean.

void interpret(Tree<String>)
The argument to this method has no value.

You should also have a JUnit class, InterpreterTest, to test your Interpreter methods. You are testing to make sure your methods give correct results for legal inputs; you do not have to test your methods with incorrect Trees, or Trees of the wrong type. For example, you should not call evaluateBoolean with a Tree that has an integer result.

Each method may recursively call itself and/or the other methods. For example, you would call interpret on an if node, and the interpret method would call evaluateBoolean on its first child. If I have done this correctly, there should never be a problem deciding which method to call.

To test the interpret methods, you will need to be able to access the Map<String, Integer> in which you keep the values of variables. Provide these two methods in the Interpreter class:

I will discuss (briefly) in class how to test the print node, and will add the instructions to this page in a day or two.

To construct Trees for testing, use the parse method in my Tree class. The syntax it expects is not very much like Java--the statement x=x+1 would be represented as =(x, +(x, 1)) -- so read the documentation!

Node contents Number of children Use method Comments
An integer
0
evaluate
The value in every node is a String. To convert a String to an int, use Integer.parseInt(String).
A variable name
0
evaluate
A string represents a variable name if it isn't one of the other node types described here. All variable names have integer values; if no assignment has been made to them, they have an initial value of zero.
To evaluate a variable name, look it up in a Map<String, Integer>. This should be familiar to you from an earlier assignment.
+   or   -
1 or 2
evaluate
If a "+" or "-" node has only a single child, treat it as a unary operator.

*  / or  %
2
evaluate
Evaluate the children and perform the operation.
true or false
0
evaluateBoolean
Return the corresponding boolean value.
not
1
evaluateBoolean
Evaluate the child and negate the result.
and  or  or
2
evaluateBoolean
Use short-circuit evaluation, as in Java.
<  <=  =
 !=  >=  >
2
evaluateBoolean
Evaluate both children (as integers) and perform the operation.
When used as an argument to evaluateBoolean, = (not ==) represents a test.
=
2
interpret
When used as an argument to evaluate interpret, this represents an assignment statement. The second child is to be evaluated as an integer, and that value is assigned to the variable in the first child.
block
any number
interpret
Interpret each of the children, in order.
if
2 or 3
interpret
Evaluate (as boolean) the first child; if true, interpret the second child; but if false, interpret the third child (if present).
while
2
interpret
Evaluate (as boolean) the first child; if true, interpret the second child. Repeat until the first child becomes false.
repeat
2
interpret
Evaluate (as integer) the first child; then interpret the second child that number of times.
print
any number
interpret
Prints its children on a single line, separated by spaces. If a child is a (known) variable, print it as variable=value; otherwise just print it as a string.

Due date:

Zip the complete Eclipse project and submit via Blackboard before midnight Tuesday, February 6.