Purposes:

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

General Idea:

You finally get to see the point of everything we've been doing. In this assignment you will implement an interpreter for a mini-language based loosely on Logo. This is a fun assignment, guys!

Logo is a general-purpose programming language, originally designed for children. The idea is that you write a program to instruct a "turtle" how to walk around the screen; the turtle has colored pens which it drags as it walks, so you can see where it has been. The object is to teach the turtle how to draw various objects: squares, spirals, stars, houses, faces, etc. All important features of a programming language are included.

Details:

You will need a GUI for this assignment. I have provided some starter code; you are free to add to it, change it, modify it in any way you like, or just ignore it altogether.

The GUI should have:

• A drawing area, in which the turtle does its thing,
• A text area, that shows the program being executed, and
• A control panel, which allows the user to interact with the program.

The text area should be completely editable. (Java's java.awt.TextArea is just fine for this.)

The control panel should have:

• A Load button, to get a program from a text file.
• A Save button, to save a program to a file.
• A Start button, to tell the program to execute.
  • Clicking the Start button should clear the drawing area before the turtle begins.
  • You should always execute the current program, as displayed in the program text area.
• A Pause button, to tell the program to temporarily halt execution and wait for Start or Stop to be pressed.
• A Stop button, to tell the program to stop whatever it is doing.
• A speed control (probably a Scrollbar) to control how fast the turtle moves.
  • Note that only turtle movement commands should be affected; all other commands should proceed at full speed.
• Someplace to display error messages (mostly from the Parser).

Buttons should be grayed out when they are not applicable. For example, the Start button should be grayed out when there is no program, or when the program has a syntax error, or when the turtle is already running.

You are welcome to have other controls and display areas as well, so long as they work and their function is clear.

Writing the interpreter:

Clicking the Start button should cause the drawing area to be cleared and the program interpreted. Then interpret the program.

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

For example, if the complete      program consists of: penup pendown

Then the BinaryTree 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 little procedure associated with it, to interpret the node (do the thing that that node says to do).

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	The BinaryTree	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. See Part II of this assignment.
<command> ::= <move> <expression> <eol>	"forward 5 \n"		Evaluate the left child <expression>, and tell the turtle to move forward that distance. If the pen is down, the turtle draws; otherwise, it moves without drawing.
<command> ::= "penup" <eol>	"penup \n"		Tells the turtle to lift its pen, that is, don't draw.
<command> ::= "pendown" <eol>	"penup \n"		Tells the turtle to lower its pen. Future moves will draw lines.
<command> ::= "color" <colorname> <eol>	"color red \n"		Tells the turtle to use the color red in any future drawing.
<command> ::=    "home" <eol>	"home \n"		Tells the turtle to go to the center of the screen and face right.
<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> <eol>	"repeat 5 [ \n penup \n pendown \n ] \n"		Evaluate the right child <expression>. Then interpret the right child <block> that many times.
<command> ::=  "while" <condition> <block> <eol>	"while x < 5 [ \n penup \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> <eol>	"if x < 5 [ \n penup \n ] \n"		Evaluate the left child <condition>. If true, interpret the <block>, otherwise do nothing.
<command> ::= "do" <name> { <expression> } <eol>	"do foo 5 \n"		Evaluate each <expression> in the right child <list>, then interpret the procedure <name> with these values as parameters. See Part II of this assignment.
<block> ::= "[" <eol> { <command> } "]" <eol>	"[ \n home \n pendown \n penup \n ] \n		Evaluate, in order, each left child <command>.
<expression> ::= <term> { <add_operator> <term> }	"foo + 5"		Evaluate both children and add the results.
<term> ::= <factor> { <multiply_operator> <factor> }	"foo * 5"		Evaluate both children and multiply 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 z \n forward x \n end \n"		Assign values to the left <variable> children, then interpret the right <command> children. See Part II of this assignment.
<program> ::= <command> { <command> } { <procedure> }	penup \n pendown \n		Save the right <procedure> children for later interpretation (see below), then interpret the right <command> children in order.

Program architecture:

The LogoInterpreter (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 LogoInterpreter class.

Some commands, such as forward, will cause the turtle to do something. For each such command, the LogoInterpreter will call a method in the Turtle class (such as public void forward(int n)). The turtle will then change its state as necessary.

Some commands that the turtle receives, such as forward and color, will also affect what is drawn on the screen (the DrawingCanvas). In these cases, the method in the Turtle class will create a DrawingCommand to send to the DrawingCanvas. The DrawingCanvas keeps a Vector of all the DrawingCommands it has received, and executes them whenever the screen has to be repainted. (This is necessary because all actual drawing has to be done from the paint() method).

DrawingCommand is an abstract class with one method, apply(), that implementing classes must define. There should be several implementations of DrawingCommand; I've provided two, a DrawLineCommand that you will probably want to keep, and a DrawStringCommand, which is a throwaway example.

Here is the starter code.

But wait...there's more!

In order to get this posted, I put some of the description on a second page. There you will find:

• How to handle set commands,
• How to handle expressions involving variables (not just numbers), and
• Everything having to do with procedures (do and to),