CIT594 Program Tree Interpreter

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.

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:

int get(String variableName) to get the value of a variable, and

void clear() to empty out the Map containing variables and their values.

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.

Node contents

Number of children

Use method

Comments

An integer

evaluate

The value in every node is a String. To convert a String to an int, use Integer.parseInt(String).

A variable name

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 %

evaluate

Evaluate the children and perform the operation.

true or false

evaluateBoolean

Return the corresponding boolean value.

not

evaluateBoolean

Evaluate the child and negate the result.

and or or

evaluateBoolean

Use short-circuit evaluation, as in Java.

<  <=  =
 
     !=  >=  >

evaluateBoolean

Evaluate both children (as integers) and perform the operation.
When used as an argument to evaluateBoolean, = (not ==) represents a test.

=

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

interpret

Evaluate (as boolean) the first child; if true, interpret the second child. Repeat until the first child becomes false.

repeat

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.

Purposes:

General Idea:

Provided software:

Details:

Due date: