CIT 594 Assignment 8: Interpreter for Robot Language
CIT 594, Spring 2005

Purposes:

To give you more practice using stacks and trees
To introduce you to hash tables
To complete the study of recursive descent

General Idea:

In this assignment you will implement an interpreter for a mini-language based loosely on Karel the Robot; however, you won't implement the Robot itself just yet. That will be the subject of an additional (small) assignment.

Karel is a special-purpose programming language designed to introduce programming to beginners. The idea is that beginners write programs to move a robot around on a grid, avoiding obstacles and picking up "beepers."

Details:

For this version, you will need a main method that gets a String (representing an entire program) from a file (chosen by a JFileChooser dialog). Then parse the string as a <program> If there are any parsing errors, quit, otherwise interpret the program.

Writing the interpreter:

When the Parser finishes, it should have exactly one (possibly very large) Tree on its stack. That Tree should represent the entire program.

For example, if the complete
program consists of:

forward
turn left
back 1

Then the Tree
should look like:

To interpret the program, you simply interpret the top node. Usually this means interpreting its children, recursively. Almost every type of node will have a small amount of code associated with it, to interpret the node (do the thing that that node says to do).

Three of the most important methods in your interpreter will be:

int evaluateExpression(Tree expression): Given the root of a Tree representing an arithmetic expression, evaluate the expression and return the numerical result.
boolean evaluateCondition(Tree condition): Given the root of a Tree representing a condition, evaluate the condition and return the boolean result.
void interpret(Tree command): Given the root of a Tree representing a program or a command, interpret the program or command (that is, do what it says to do).

Your interpret method will most likely consist of a fairly large if...else if...else if statement, containing clauses something like the following:

...
else if ("while".equals(command)) {
    while (evaluateCondition(child[0])) {
        interpret(child[1]);
     }
}
else if ...

In the following table, I have tried to use the following terminology consistently:

interpret: Do what the statement says to do.
evaluate: Compute an integer or boolean result.

Grammar rule (partial)	Example input	How to interpret this
`<variable> ::= <name>`	`foo`	Depends on context. In an `<expression>`, look up the value of the variable. In a `<set>` statement, assign a value to the variable.
`<object> ::= <name>`	`foo`	This is just a "thing"--it evaluates to itself (a String).
`<command> ::= <move> <expression> <eol>`	`forward 5\n`	Evaluate the `<expression>` to get a number, then tell the robot to move forward that number of squares.
`<command> ::= "turn" <direction> <eol>`	`turn right \n`	Tell the robot to turn 90° to the right.
`<command> ::= "take" <object> <eol> \| "drop" <object> <eol>`	`take rock \n`	Tell the robot to pick up the object in the square directly in front of it. (It is an error if the named object is not directly in front of it.)
`<command> ::= "set" <variable> <expression> <eol>`	`set x 5 \n`	Evaluate the right child `<expression>` and save the numerical result in the left child `<variable>`. See below.
`<command> ::= "repeat" <expression> <block>`	`repeat 5 {\n turn left\n stop \n }\n`	Evaluate the right child `<expression>`. Then interpret the right child `<block>` that many times.
`<command> ::= "while" <condition> <block>`	`while x<5{\n turn left\n }\n`	Evaluate the left child `<condition>`. If `true`, interpret the `<block>` and start the while over again, otherwise do nothing.
`<command> ::= "if" <condition> <block> [ "else" <block> ]`	`if x < 5 {\n stop \n }\n`	Evaluate the left child `<condition>`. If `true`, interpret the `<block>`, otherwise do nothing.
`<command> ::= "if" <condition> <block> [ "else" <block> ]`	`if x < 5 {\n }\n else {\n stop\n }\n`	Evaluate the left child `<condition>`. If `true`, interpret the first `<block>`, else evaluate the second `<block>.`
`<command> ::= "do" <name> { <expression> } <eol>`	`do foo 2 3 6\n`	Evaluate each `<expression>` child except the first, then interpret the procedure `<name>` with these values as parameters. Seebelow.
`<command> ::= "stop" <eol>`	`stop \n`	Stop interpreting; the program is finished.
`<block> ::= "{" <eol> { <command> } "}" <eol>`	`{ \n turn left\n forward 5\n turn right\n } \n`	To evaluate a `<block>`, evaluate each statement in the block, beginning with the first.
`<expression> ::= <term> { <add_operator> <term> }`	`foo + 5`	Evaluate both children and add the results.
`<expression> ::= <term> { <add_operator> <term> }`	`2 + 3 + 6`	Evaluate both children and add the results.(Recursion will take care of the subtree.)
`<term> ::= <factor> { <multiply_operator> <factor> }`	`foo * 5`	When a `<term>` consists of a single factor, the tree is the same as it is for that `<factor>` alone
`<factor> ::= <name>`	`foo`	When a `<factor>` consists of a name or number, evaluate that `<name>` or `<number>`.
`<factor> ::= "(" <expression> ")"`	`(foo + 5)`	Evaluate both children and add the results.
`<condition> ::= <expression> <comparator> <expression>`	`x < 5`	Evaluate both children and compare the results, getting a `boolean` value.
`<procedure> ::= "to" <name> { <variable> } <eol> { <command> } "end" <eol>`	`to foo x y\n forward x\n turn left \n back y\n end \n`	Assign values to the left `<variable>` children, then interpret the right `<command>` children.
`<program> ::= <command> { <command> } { <procedure> }`	`forward 5\n turn left\n back 1\n`	Save the `<procedure>` children (none in this example) for later interpretation, then interpret the `<block>`.

Program architecture:

The RobotInterpreter (which contains the main method) walks the parse tree and interprets the commands as necessary. Many of these will be control commands, such as if, while, and set. These commands are handled directly by the RobotInterpreter class and are not sent to the robot. Expression evaluation is also done by the RobotInterpreter class, not the robot, although some expressions may involve getting values (for example, distance) from the robot.

Some commands, such as forward, will cause the robot to do something. For each such command, the RobotInterpreter will call a method in the Robot class (such as public void forward(int n)). The robot will then perform some appropriate action.

For this assignment, write a DummyRobot class that implements the following RobotInterface:

public interface RobotInterface {
    void turnRight();
    void turnLeft();
    void turnAround();
    int facing(); // North = 0, East = 1, South = 2, West = 3
    boolean forward(int n);
    boolean back(int n);
    int getRow();
    int getColumn();
    boolean take(String thing);
    boolean drop(String thing);
    String seeing();
    String[] holding();
    int distance();
}

The "implementation" of these methods will simply print out information about what method was called; they won't actually do anything. For example, calling

 
forward(5)

might print out "Moving forward 5 squares." (If you wish, you can provide very simple implementations to keep track of row and column numbers and the direction the robot is facing; but this is completely optional and will be replaced with more interesting code later.) To minimize output, each method call should print one and only one line.

Variables, part 1

An interpreter or compiler needs to keep track of variables. A compiler needs to keep track of the locations (machine addresses) of variables, while an interpreter needs to keep track of the values of variables.

The way this is done is with a symbol table, usually implemented as a hash table. Java supports several flavors of hash tables; the one I would like you to use is java.util.HashMap. Basically, the HashMap has two important methods:

put(Object key, Object value)

Puts the key and its associated value into the hash table. In this case, the key will be the name of the variable.

Object get(Object key)

Given the key, returns the associated value.

Note that the parameters and return values are Objects. Therefore, Strings are fine to use as keys, but int values must have an Integer wrapper in order to be put into the hash table. Java 5 generics can help you with this; you can specify that keys areStrings, values are Integers, and let Java 5 do auto-boxing and -unboxing for you.

So here's all you need to do. Whenever you are evaluating a <factor> and you want to get the value of a variable, look it up in the hash table. Whenever you are evaluating a <set> command and you have a value you want to save in a <variable>, put the variable/value pair into the hash table.

Some additional points:

<variable> is the only place in the grammar (that I can think of) where you have to evaluate something in two different ways (getting the value, and setting the value).
If you get a null value back from the hash table, that means you never put this variable into the table. This is an error in the user's Robot program.

Procedures

First of all, you should get the rest of your program running reasonably well before you attempt procedures.

The keyword to defines a procedure. The do command calls a procedure. Procedures consist of a list of commands, just like the rest of the program, but you have to do extra work to sort out the procedures from the rest of the program, and keep track of parameters.

A <procedure> is represented as a subtree of the parse tree produced by your Parser. You need to find the subrees representing these procedures and keep track of them separately, by name.

The best approach is to set up a separate hash table of procedures. Step through the right-hand side of your <program> tree and, for each <procedure> (to node), put it in the hash table. The <name> of the procedure will be the key (we won't allow more than one procedure with the same name), and the whole procedure (rooted at the to node) will be the value. It doesn't matter whether you take the procedure out of the program tree or just leave it there.

Procedures can have parameters, and can be recursive. This means that each time you call a procedure, you must create a new hashMap to keep track of its parameter values. Since one procedure can call another, you need to keep all these hash tables on a Stack.

When you encounter a do command (that is, a procedure call):

Look up the procedure, by name, in your hash table of procedure names.
Evaluate each of the <expression>s in the do command.
Create a hash table and put it on the stack of hash tables.
For each parameter, get the value of the actual parameter (from step 2), and put these values in the new hash table as the value of the matching formal parameter (listed in the right-hand subtree of the header node of the procedure you found in step 1).
Evaluate the procedure body (the right subtree of the to node found in step 1).
When the procedure finishes, pop the hash table you created in step 3.

Variables, part 2

In the absence of procedures, we need only a single hash table in which to keep variables.

When we have procedures, we need a stack of hash tables, one hash table for each procedure invocation. (A Vector would also do, given some of the operations we need to perform. Your choice.)

To find a variable, look for it first in the topmost hash table on the stack, then in the next one down, then the next one down, etc., until you either find it or you run out of hash tables.

If you find the variable, either set or get its value, as appropriate.
If you don't find the variable, and you are trying to get its value, this is an error.
If you don't find the variable, and you are trying to set its value, add the variable and its value to the topmost hash table.

Variables managed in this way won't follow the same scope rules as variables in Java, so don't expect them to. (If you are curious, variables have what is called dynamic scope.) You should think about the effects of this approach--do we have global variables? Local variables? From where in the program can we access which variables?

Testing

For this assignment, please include all previous JUnit tests (for Token, Tokenizer, Tree, and Parser, and optionally Recognizer), updated as appropriate.

It is possible to do unit testing on the interpreter itself. Good testing would involve some complexities that I don't want to go into just yet. For this assignment, test your interpreter the old-fashioned way: Interpret one or more programs on files, and examine the output.

Due date:

Tuesday, April 5, before midnight.