CS 353 Lab 8: An Evaluator for Extended Expressions

Sample input data

There is some sample data in a file here.

Description

This lab starts off the process of writing a compiler: here we will define the basic tree structures which represent expressions in a simple expression language and evaluate them interactively (i.e., like an interpreter). This will give you a chance to familiarize yourself with how the language works in a relatively simple context before having to parse and generate code for it.

You should define a tree type for the following abstract context-free term structure:

E  ::=  V  |  N  |  READ  |  WRITE E  |  V P  |  P V  |  E O E  |  V = E  |  E ? E : E  |  ( E )

V  ::=  [a-z]+

N  ::=  [0-9]+

P  ::=  ++  |  --

O  ::=  +  |  -  |  *  |  <  |  >  |  ==  |  &  |  |

(Note that the final vertical bar here is in the object language you're implementing, not the meta-language of the BNF notation being used to describe the grammar.)

This structure constitutes a language of arithmetic and logical expressions with:

variables (x, y, ..., or other sequences of lowercase letters);
literal constants (357, 1, 0, ...; positive only);
input and output (READ returns a value interactively from the user; WRITE outputs the value of the expression and also returns its value);
prefix and postfix operators for increment and decrement (as in Java, the prefix ones change the variable's value before its returned, the postfix ones after);
infix operators (arithmetic, relational and logical, with the usual meanings);
variable assignment, but only with a variable on the left (this returns the value on the right as its result, just like in Java);
and, finally, conditional expressions (again, as in Java; note that only one of the two branches should be evaluated.

The operators will ultimately have precedences assigned (in the usual way); we don't need these yet, however, as we aren't parsing expressions, but rather just representing them internally. (Thus the parentheses are not explicitly represented in the trees, either, and will only be used later.)

The "mixed semantics" of integers and booleans is like that in C (and in some ways, like Java); more specifically, when consuming a value for boolean purposes (i.e., for logical operators or for the conditional expression), a zero value is taken as false and any non-zero value as true. On the other hand, when producing a boolean value (i.e., as the result of a relational or logical operator) a false value is given as zero, but a true value is always given as one.

For example, therefore, the expression (3*(5&(1>0))) would evaluate to 3, since:

(1 > 0) evaluates to 1;
(5 & 1) evaluates to 1;
(3 * 1) evaluates to 3;

In addition to defining the tree structure, you should define operations to print and evaluate an expression (use full parenthesization in the printing to verify that your tree structure is correct).

Use right-to-left evaluation order (as described in class) and the informal semantics above to determine how evaluation is done (note again that you will need to interactively request values from the user and to write out results).

Finally, note that you will want to plan for representing an extended language (with a few more features perhaps) for the next two labs, so design your trees in a good O-O fashion to allow for extensions.

Some hints and tips

You should design classes which can be used to represent expressions as trees, along with methods which allow them to be printed (i.e., toString) and evaluated. (The latter will use a global hash table (for the variables' values) as an "implicit" argument.)

So part of your code might look like the following (although of course you might use different class/constructor names):

    Expr myExpr = new PlusExpr( new MultExpr( new VarExpr("x"), new LitExpr(3)),
                                new PlusExpr( new LitExpr(5), new SetExpr("x", new LitExpr(7))));

(i.e., in order to build an example, you call constructors for the various classes you have created, supplying them with arguments which are either atomic data (ints, Strings, etc.) or sub-expressions created in the same way.

The above expression should print something like this:

    myExpr.toString()   ==   "((x*3)+(5+(x=7)))"

If you could use symbols for class names and spaced out the code a little differently, it's easy to see that the construction of the term with the java "new" keyword is really just a prefix form (i.e., prefix-order traversal) of the expression:

    ((x*3)+(5+(x=7)))  <==>  + * x 3 + 5 = x 7

              <==>

                      +       *           x             3
                              +           5         =   x           7


    Expr myExpr = new + ( new * ( new V( "x" ), new L(  3 )),
                          new + ( new L(  5  ), new =( "x" , new L( 7 ) )));

When you evaluate a sample expression you would get something like this:

    myExpr.value()   ==   33

(since 5+7 is 12 and x*3 (after x is set to 7) is 21, and 21 + 12 is 33).

(Note also that your value() method would need access to a hash table in order to get the values of the variables, and to set them. If you use a globally-accessed hash table, you should remember to re-set it before the evaluation of each new expression.)

The point of all this is to get your class structure and basic methods set up before going on to tackle parsing and code generation. Parsing takes a string and produces a tree: it's (roughly speaking) the inverse function from the toString method above. Code generation is just like evaluation, but it produces PC-231 code instead of a number (the idea being that when you run the PC-231 code and provide the same inputs, you get the same answer).

In many ways the class structure for this assignment is just like the class structure for the gate simulator, in that we have a tree-like structure of nodes with 0, 1 or 2 children, whose evaluation is based on the evaluation of thir children (plus a little bit on which sub-class we are in, i.e., PlusExpr or MultExpr vs. AndGate or OrGate in the logic version).