CIS505 Assignment 3

10 points; due Friday, Oct 8

Use Python to write an interpreter for a mini-Java language, where a programmer can define and call procedures and can allocate array and struct objects in the heap. Here are some example programs:

var x;  x = 0

var x;  x = new array[3];
x[1] = 99 ;
x[2] = new array[2] ;
x[2][0] = x

var s;
proc p : s = 0 end;
s = new struct f, g, h end;
s.g = 99;
s.f = new array[2];
print s.g;
print s.f[0] ;
call p

Unlike Java, the language does not enforce data-typing laws. Also the language does not allow procedures in objects, which greatly simplified the task.

Here is the language's syntax:

===================================================

P : Program
D : Declaration
C : Command
E : Expression
T : TypeStructure
F : Field
L : LefthandSide
I : Identifier
N : Numeral

P ::=  D ; C

D ::=  D1 ; D2  |  var I  |  proc I : C end

C ::=  C1 ; C2  |  L = E  |  if E : C1 else C2 end  |  print L  |  call I

E ::=  N  |  ( E1 + E2 )  |  L  |  new T

T ::=  array [ N ]  |  struct F end  

F ::=  I  |  F1 , F2

L ::=  I  |  L [ E ]  |  L . I

N ::=  strings of digits

I ::=  strings of letters, not including the keywords used above

===================================================

A parser has been provided that translates programs in the above grammar into operator trees. The syntax of the operator trees is documented in commentary in the parser.

Storage layout

Java uses a storage layout like that described in Section 2.2 of the Lecture notes. There is a heap, whose locations hold array and struct objects. An array is an object indexed by ints, and its elements can be ints or heap locations (pointers to objects). A struct is an object indexed by identifiers, and its elements can be ints, heap locations, or procedure bodies.

The main program's environment ("namespace") is a struct that is stored in the heap. The details of the namespace and the heap are given in a long comment within the skeleton interpreter that is also provided. Here is a sample heap:

===================================================

 heap = { "0": {"x": 7,
                "y":"1",
                "z": "nil",
                "p": [["=" ["x"], "7"]]
               },
          "1": ["2", "nil", 0], 
          "2": {"r": 99}
        }

===================================================

Here, heaploc "0" holds a struct whose x field holds int 7, y field holds heaploc "1" (a link to the object at heaploc "1"), z holds nil (uninitialized), and p holds a one-command CLIST (the operator tree for the command, x = 7). Heaploc "1" holds a three-celled array whose elements are heaploc "2", nil, and int 0; Heaploc "2" holds a struct with a single field, r.

This heap was constructed by this program:

var x; var y; var z;
proc p: x = 7 end;
y = new array[3];
y[2] = 0;
y[0] = new struct r end;
y[y[2]].r = 99;
call p

Notice that the new command allocates new objects in the heap, whose heaplocs are assigned to variables. The program's variables, x, y, z, p, are saved in the struct stored in heaploc "0". Heaploc "0" points to the program's namespace, and the namespace is used to look up global variables.

Interpreter operation

Read Section 2.2 and the lecture slides carefully on the interpreter's operation. A driver, scanner, parser, and interpreter skeleton has been provided for this assignment. Your job is to finish the interpreter. A folder holding these files, plus some useful test cases, can be found here.

Submission

Submit to K-State Online a zipped folder containing the driver, scanner, parser, and finished interpreter. Also include a text-file log of the successful test cases and their outputs.