Programming Assignment 6 (With Arithmetic Expression - WAE)

Write a Python program to "evaluate" WAEs. I am providing the syntax checker part of the program in the following files:

1. WAELexer.py
2. WAEParser.py
3. WAE.py

You will have to implement the following function in WAE.py.

	def eval_expression(tree):
		pass

You may need additional helper functions to complete this assignment. The syntax checker part of the program needs the ply package. You should install this using the pip or the pip3 command.

What are WAEs?

With-Arithmetic Expressions (WAEs) are arithmetic expressions written in "prefix" form (operator followed by the operands) and have two advanced features: conditional-expression and with-expression. WAEs are inductively defined as one of the following:

1. a number, such as 45 or -3.26
2. a variable, such as x or y
3. { + wae1 wae2 }
4. { - wae1 wae2 }
5. { * wae1 wae2 }
6. { / wae1 wae2 }
7. { if wae1 wae2 wae3 }
8. { with { {ID1 wae1} {ID2 wae2} ... } wae }

where wae, wae1, wae2, ..., etc. are themselves WAEs.

The evaluation of WAEs is defined as follows:

1. eval(num) = num
2. eval(var) = UNDEFINED
3. eval({ + wae1 wae2 }) = eval(wae1) + eval(wae2).
4. eval({ - wae1 wae2 }) = eval(wae1) - eval(wae2).
5. eval({ * wae1 wae2 }) = eval(wae1) * eval(wae2).
6. eval({ / wae1 wae2 }) = eval(wae1) / eval(wae2).
7. eval({ if wae1 wae2 wae3 }) = if eval(wae1) is non-zero then eval(wae2) else eval(wae3) .
8. eval({ with { {ID1 wae1} {ID2 wae2} ... } wae }) = eval(substitute({ {ID1 wae1} {ID2 wae2} ... }(wae)), where the substitute function replaces ID1, ID2, ... by their corresponding values eval(wae1), eval(wae2), ... in wae. The substitution should not take place if there is a "local" definition of the same variable in wae.

Implementation Notes:

There are at least two ways to implement evaluating the "with" clause of the WAEs. One is to faithfully implement the substitute function as described above. The other way is to maintain the variables/values in a dictionary and pass this dictionary (after updates!) to evaluate expressions in the subtree of the with-clause.

Sample Run:

A sample run is given in run.html.

Couple of Examples:

To understand the semantics of WAEs, it is useful to consider "expression" tree representations. The expression tree for the WAE

{+ {+ {+ 2 3} {+ 4 5}} {+ 5 7}};

is shown below:

The semantics/value of a WAE is computed bottom-up in the expression tree. For WAEs without the "with" expression the value calculation is quite straightforward.

The semantics/value calculation for the last WAE in the sample run is illustrated in the following figure.

The general idea with the "with" expression is to "substitute" values of variables specified in the with-clause in the subtree below the with-node. If there are with-expressions in the subtree, the substitution must happen in the values of the variables specified there. Also, of there is a "local" occurrence of the global variable, the value of the local variable takes precedence.

What to submit?

WAE.py, WAELexer.py, and WAEParser.py.