Spring 2001, CSE 428: Assignment 2


Distributed: Feb 1.
Due: Feb 13 in class. Note: because of MT 1, we need to publish the solution on Feb 13. Hence, no solutions can be turned in after this date (namely, late assignments will not be accepted this time).
Total maximum score: 100 points.

The purpose of this assignment is to provide experience with interpretation of expressions.

Consider the language of expressions, and the eval function for such language, defined in Class 5 (see lecture notes).

The homework consists in completing the definitions of the various classes (tree, node, and environment) with the necessary methods (and possibly additional fields, if needed), so to get a real C++ interpreter for the language of expressions. Please define also the destructor methods for all the dynamic user-defined structures.

We will test your program by adding to it a main function like the following:

   void main(){
        node* n1 = new node("dec","x");
        node* n2 = new node("num",2);
        node* n3 = new node("op","+");
        node* n4 = new node("ide","x");
        node* n5 = new node("num",5);
        tree* t2 = new tree(n2);
        tree* t4 = new tree(n4);
        tree* t5 = new tree(n5);
        tree* t3 = new tree(n3,t4,t5);
        tree* t1 = new tree(n1,t2,t3);
        environment *r = empty_environment();
        cout << eval(t1,r);
        delete t1;
        delete r;
   }
The call empty_environment() should return an empty environment, namely an environment containing no associations.

The tree t1 constructed in this main function corresponds to the expression

   let x = 2 in x + 5 end
and the result given in output by the program should be, of course, 7.

Note: your program should work in general, not just in this case. We will test your code also on other expressions, and in particular we will test it on expressions containing nested blocks, like

   let x = 2
    in let x = 3
        in x + 4 
       end 
       + x
   end
(result: 9)
   let x = 2
    in let y = 3
        in x * y 
       end 
       + 
       let y = 1
        in x - y
       end
   end
(result: 7).

Format of the solution

Please give an hard copy of the source code to the instructor by the due date. Furthermore, you should also email your source code to cg428@cse.psu.edu by the due date, so to allow us to check that your program runs correctly. Please send the code as an attachment (not by "cut-and-paste"), and use the last 4 digits of your student id, followed by ".C", as the filename (example: if the last digits of your id are 1001, then the file should have name 1001.C).

Please make sure that your program can be compiled and executed on Unix.

In order to link smoothly your code to the main function above, please use the same names for classes, such as "node", "tree" etc., and constructors with the same kind of parameters. Also, please use the same representation of expressions in parse trees as the lecture notes. You are welcome to use the code of the lecture notes for the eval function (with the necessary changes to transform it in a real C++ program). You can use different commands and different types in your program if you wish (for instance char* instead of string, an enumerated type for the operators, variant (union) classes, etc.) But please, make sure that your code does not give compilation errors when you use the main function above.