|CIT 594 Assignment 5: Interpreter, Part II
Spring 2004, David Matuszek
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.
Object get(Object key)-- Given the key, returns the associated value.
You can find more details in the Java API.
Note that the parameters and return values are
Strings are fine to use as keys, but
int values must
Integer wrapper in order to be put into the hash table.
So here's all you need to do. Whenever you are evaluating a
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:
<factor> ::= <name> | <number> | "(" <expression> ")"
<factor> ::= <variable> | <number> | "(" <expression> ")"
<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).
nullvalue back from the hash table, that means you never put this variable into the table. This is an error in the Logo program.
First of all, you should get the rest of your program running reasonably well before you attempt procedures.
to defines a procedure. The
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.
<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> binary tree and, for
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 need to create a hash table 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 (procedure call):
<expression>s in the
headernode of the procedure you found in step 1).
tonode found in step 1).
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.
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?
The standard JUnit package is not designed for GUI testing. For this assignment,
please include all previous JUnit tests (for
Parser, but not
updated as appropriate.
Also include one Logo program (call it
sample.logo) that we can
run. This program should showcase all the features of the language, and should
draw something interesting. We will also want to run our own Logo test programs,
so make sure that we can use the Load button to replace the
current Logo program--we don't want to have to stop and restart your interpreter!
Tuesday, March 2, before midnight.