Read this assignment thoroughly before beginning to write your solution. (This assignment is loosely based on the Chapter 1 assignment in Andrew Appel's Modern Compiler Implementation which is on reserve at the library.)

Goals

• To gain familiarity with the Eclipse Java development environment.
• To learn more about Java 5.0 features such as enumerated types, generic collections and enhanced for.
• To gain experience reading and augmenting code that manipulate recursive tree structures and algebraic data types via the instanceof construct.

Straight-line programs

A straight-line program consists of a list of instructions that are to be executed in sequence - i.e., there are no conditional operations, no loops, no jumps.

In this assignment you will be writing an interpreter for a straight-line expression language. The language is very simple: every instruction is an expression - meaning it can be evaluated to an integer. Programs in this language are a sequence of semi-colon terminated expressions with each expression in one of four forms:

1. numbers
2. identifiers (which corresponds to integer values)
3. binary operations: compound expressions consisting of the addition, subtraction or multiplication of left and right subexpressions.
4. assignments: an assignment consists of a subexpression (rvalue) on the right-hand side of the assignment which when evaluated becomes the value associated with the variable name (the identifier) on the left-hand side of the assignment. An assignment expression, much like in the C family of languages, evaluates to its rvalue.

Here is a transcript of my solution to the assignment run on three small examples which illustrate the facets of this simple language. Observe that a program evaluates to the value corresponding to the final expression in its list of instructions. If a variable is used before it is defined, a warning is issued, but the value is taken to be zero so that processing can continue.

You need not worry about any syntactic issues in the programming language - the programs are expressed using an abstract syntax formed by using Java class constructors. For instance:

  x = 3;
  x + 7;

  new Program(
    new AssignmentExpression("x", new NumberExpression(3)),
    new BinaryOperationExpression(
      new IdExpression("x"),
      Operator.PLUS,
      new NumberExpression(7)))

What you need to do

0. Download the project archive, import the project into Eclipse, try running it, and read through the various files. In particular, read Unparse to see a full-blown example of recursion over syntax trees.

1. Write Java code, using the supplied data constructors, to represent these straight-line programs:

   1.   gamma = 100;
        delta = gamma - 1;
        (gamma * gamma) - (delta * delta);
      

   2.   a = b = c + 5;
        b = (a = a * b) + 1;
        a + b;
      

   You should add these programs to the array in ExamplePrograms. You can then test that you have entered your programs correctly by running the program and looking at unparsed results. In order to make the first program work, you will need to add a symbol corresponding to subtraction to the Operator enumeration.

2. Add the necessary code to DefinedVariables so that showDefinedVariables prints in alphabetical order the variables that are defined (assigned values) in a program. Do not print duplicates. (See the solution transcript for an illustration.) Important: this is not intended to require a lot of coding on your part - take advantage of generic collections: for instance, you might use a TreeSet.

3. Finally, and most importantly, write the interpreter in the Evaluate class. Following the model provided by Unparse, you should use recursion over tree structures defining expressions. In order to keep track of the values of variables you will need a symbol table. There are many ways to do this. Again, I recommend taking advantage of generic collections, perhaps using a HashMap.

Files

All the files you need are included in this Eclipse-project archive. The individual Java files can also be found here.

Compilation and execution

All of your programs should be part of the interpreter package. To compile from the command line use:

  javac interpreter/Main.java 

  java interpreter/Main.java 

Coding conventions

Compiler writing involves substantial programming and you should be careful to follow coding conventions. That is: have conventions, and stick to them. A helpful place to start: Doug Lea's Draft Java Coding Standard. Another potentially useful site in this regard is: at geosoft.no/development/javastyle.html.

Extra credit

1. Anyone who has taken a course involving a C-style programming language with me has heard me complain about the problem with allowing assignments to be nested as expressions. Implement a test that reports such occurrences as:

     a = b = c;
   

2. Add C-style ternary expressions to the language. In other words, allow for expressions of the form:

     x ? y : z
   

   which results in the value associated with expression z if x evaluates to zero, and y otherwise.