Programming Assignment 2
An Interpreter with Dynamic Binding

Due on Tuesday March 22 before midnight


The goal of this programming assignment is to build an interpreter for a simple language that uses dynamic binding to bind variables to integer values. You may use either Java or C to implement this project. I have created skeleton files for both Java and C. You are free to use these files or modify them or adapt them in any way you like:

  1. Java skeleton file: Just put your code in the eval method.
  2. C skeleton file: Just put your code in the eval function.
Your interpreter must be able to evaluate expressions represented as trees (much like abstract syntax trees). These trees represent expressions that correspond to the following grammar:
E → id = E
  | E + E
  | E - E
  | E * E
  | { E ; E }
  | int
  | id
That is, the leaves of the tree are either integer constants, such as -5, or variable references, such as x. The internal nodes are one of the following: For example, the main program of the Java/C skeleton files must evaluate the expression:
{ x = 1; { y = { x = x+1; x+1 }; x+y } }
and must return 4. It has three declarations, two for x and one for y. The inner declaration of x is valid within the block { x = x+1; x+1 } only. Of course, your code should return the correct result for any kind of expression built using the above data constructors, not just this example.

Your task is to write the code for the eval function to evaluate expressions using dynamic binding. Your program should run correctly for any kind of expression built by the data constructors provided. The bindings of variables to integer values are stored in a stack env. It defines two functions: lookup (to search for a variable) and insert (to insert a new binding).

What to Submit

Use the form below to submit your programming assignment. We do not accept email or hardcopy submissions. The only acceptable file format for your submitted file is plain text (you source file). You may submit your file as many times as you like, but only the most recently submitted file will be retained and evaluated.

Submit Project #2:

Last modified: 03/07/11 by Leonidas Fegaras