CS G111 Machine Problem 4: Simple Interpreters and Compilers in Java

Out: Tuesday, October 9, 2007

Due: Tuesday, October 16, 2007

All programs in this machine problem are to be written in Java using DemeterJ to generate the abstract data types. Some parts use DJ to practice structure-shy programming using visitors. Note that structure-shy programming partially automates the "follow the grammar" approach that we use in earlier machine problems.

In part 1 you write an interpreter using the "follow the grammar approach". In Part 2 you compile the same expressions as in part 1 using structure-shy programming with visitors. In part 3 you extend your compiler by adding an additional operator to your language. In part 4 you write a visitor for computing the depth of an expression.

It is strongly recommended that you use ssh or a college Solaris machine to do the hw. This will eliminate many installation problems. The installation instructions are here: Simple CCIS installation. If you want to install DemeterJ and DJ on your own machine, the instructions are here: Complete installation For further information on DJ, check: DJ home page. An introduction on how to use the tools will be given in the lecture.


Write an interpreter for the following simple expression language:
Class Dictionary

A skeleton of your interpreter is in:
Partial Interpreter


Write a compiler for the same language.
The target machine is a simple stack machine.
The result is left on top of the stack:

ADI for integer addition
MLI for integer multiplication
LOC: for loading a constant on the stack

Your compiler should produce the following output for the given input.
// is the comment character.

// 1
 LOC 1

// * 2 3 
 LOC 2
 LOC 3

// + 3 4
 LOC 3
 LOC 4

// + * 3 4 * 2 3 
 LOC 3
 LOC 4
 LOC 2
 LOC 3

A partial program is in:
Partial Compiler


Extend your compiler so that it properly handles binary subtraction.
Discuss in your answer where you had to perform 
surgery to the previous program and where you only had to add code.
The name of the instruction for subtraction is SBI.

- 3 4

should translate into:


PART 4: DEPTH two ways

Write two programs using DemeterJ and DJ
that computes the maximum nesting depth of an expression.
The first program uses the "follow the grammar" approach,
the other one uses a DJ visitor.

+ * 3 4 * 2 3 has depth 2.
* 3 4 has depth 1.
1 has depth 0.

For all four parts turn in your program.cd, program.beh, and several
program.input files that you used for testing.
(Keep file program.prj in its generated form so that you don't have to turn it in.).

Last modified: Thu Feb 15 16:49:28 EST 2007