CIS505 Assignment 2

10 points; due Monday, September 20

Use Python to write an interpreter for the mini-C language that looks like the one in the Lecture notes, Chapter 2, Section 2.1. Here is the language's grammar:

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

P : Program
C : Command
E : Expression
D : Declaration
L : LefthandSide
I : Identifier
N : Numeral

P ::=  D ; C

C ::=  C1 ; C2  |  L = E  |  while E { C }  |  print E

E ::=  N  |  ( E1 + E2 )  |  ( E1 == E2 ) |  ( E1 != E2 )  |  L  |  &L

D ::=  int I  |  int* I  |  D1 ; D2

L ::=  I  |  *I

N ::=  0 | 1 | 2 | ...

I ::=  strings of letters, not including the keywords, 
        int,  while,  print

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

The language has integer (int) variables and integer-pointer (int*) variables. See Section 2.2 to review the semantics of variables, &, and * when they appear within expressions and within the left-hand sides of assignments.

Input format

The input to the interpreter is a list-represented operator tree. The syntax of operator trees looks like the example from Chapter 1, Section 1.3.3:

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

PTREE ::=  [ DLIST, CLIST ]

CLIST ::=  [ CTREE+ ]
           where  CTREE+  means  one or more CTREEs

CTREE ::=  ["=", LTREE, ETREE]  |  ["while", ETREE, CLIST]  |  ["print", ETREE]

ETREE ::=  NUM  |  ["+", ETREE, ETREE]  |  ["==", ETREE, ETREE] |  ["!=", ETREE, ETREE]
           |  ["deref", LTREE]  |  ["ref", LTREE ]

DLIST ::=  [ DTREE+ ]
           where  DTREE+  means  one or more DTREEs

DTREE ::=  ["int", ID]  |  ["int*", ID]

LTREE ::=  ID  |  ["deref", LTREE]

NUM   ::=  a nonempty string of digits

ID    ::=  a nonempty string of letters

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

(Note that "*" is converted to "deref" and "&" is converted to "ref". This will help you think straight when you write the interpreter. "==" and "!=" are the equal and not-equal operators which return Boolean values)

Interpreter operation

You are free to use code from the online textbook in implementing your interpreter. You will certainly need to modify the existing code so that it processes operator trees that match the above grammar. The interesting part is writing the semantics of variables, because you must respect the data types in the variable declarations:

Only integers are assigned to int-variables and only locations of int-variables are assigned to int*-variables.
+ can only be applied on int values. You cannot combine locations and integers with +. (That is, pointer arithmetic is disallowed.)
The operation, *L, that is, pointer deferencing, is allowed only when L has data type int*.
The comparison operator "==" and "!=" can only be applied on data of the same type.
The condition for a while loop must be Boolean.

So, this is legal: int x; int* y; y = &x; *y = 2
and it places a 2 in the cell named by x. But this is illegal: int* y; y = &y
because y is an int* variable and not an int variable. Similarly, this is illegal: int x; int* y; x = &y

You probably want to refer to the interpreter in Section 2.1.1. When a type check fails, your interpreter shall report an error message and exit gracefully, instead of crash.

Implementation and testing

The interpreter is a family of seven functions, one for each form of operator tree. Each function should be specified in a style similar to the interpreter code in the textbook. There will also be the two global data structures, the environment (which holds variable declarations) and the memory (which holds the stored values of assignments).

You should write and test the interpreter functions in stages. Say that you have written evalDTREE, evalCTREE, and evalETREE and saved these in the file, interp.py. You test like this: Open a command window and type

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

python -i interp.py

>>> evalETREE(["+", "2", "1"])

  ...should display  ("int",3)...

>>> evalDTREE(["int", "x"])

  ...should allocate a cell in memory and bind its location to  x...

>>>evalCTREE(["=", "x", ["+", "2", "1"]])

   ...should place 3 into  x's  cell in memory...

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

At any time during your testing, you can examine the values of env and memory by merely typing their names, e.g.,

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

>>> env
{"x":("int",0)}

>>>memory
[3]

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

When you are convinced that your interpreter is operating correctly, try it on these programs. (Note: just cut-and-paste these tests into your command window.)

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

evalPTREE([[["int", "a"]],
           [["=", "a", ["+", "2", "1"]],
            ["=", "a", ["+", ["deref", "a"], ["deref", "a"]]]
           ]
          ])

evalPTREE([[["int", "a"]],
           [["=", "a", "3"],
            ["while", ["!=", ["deref", "a"], "6"],
                      [["=", "a", ["+", ["deref", "a"], "1"]]]],
            ["print", ["deref", "a"]]
           ]
          ])

evalPTREE([[["int", "a"],
            ["int*", "b"],
            ["int*", "c"]
           ],
           [["=", "b", ["ref", "a"]],
            ["=", "c", ["deref", "b"]],
            ["=", ["deref", "c"], "2"],
            ["print", ["deref", "a"]],
            ["print", ["deref", "b"]],
            ["print", ["deref", "c"]]
           ]
          ])

# This example contains multiple errors:
evalPTREE([[["int", "a"],
            ["int*","a"],
            ["int", "b"],
            ["int*", "c"]
           ],
           [["=", "b", ["deref", "b"]],
            ["=", "c", "2"],
            ["=", "c", ["+", ["ref", "b"], "1"]],
            ["=", "c", ["ref", "c"]]
           ]
          ])

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

Submission procedure

Place your interpreter file in a folder, named Ex2, and zip the folder. Submit the zipped folder to the CIS505 site on K-State Online.