Expression evaluation

Expressions are evaluated by the methods of the Interpreter class. Each evaluates the expression represented by a single rule node of the tree. All of these methods have the same prototype, which specifies a single parameter and no result. But expression evaluation produces a result -- the value of the expression. Moreover, that result of evaluating an expression represented by a rule node must be used as an operand when evaluating the expression represented by it parent.

Consider an expression represented by an OpExp node. One way to evaluate such an expression would be to first invoke a routine to evaluate its left child, then a routine to invoke its right child. Finally, pass the resulting values to a routine that carries out the operation.

To implement this approach, all that is necessary is to provide mechanisms for passing arguments to a routine and returning results from that routine. Many current machines use a stack for these purposes: A caller pushes arguments onto the stack, the called routine removes those arguments and pushes its results. This strategy does not require that any explicit information be passed between invoker and invokee, so it can be used in the interpreter.

``Stack'' is a so-called container adaptor in the C++ standard template library. That means that it changes one container into another, and so the container to be adapted must be chosen. The container must be a sequence container, and for a number of reasons the vector seems to be the best choice. Since the values of the expressions in the simple serial programming language are all integers, the adapted container should be an integer vector:

Declare the expression evaluation stack[12] :

stack<vector<int> > ExpValues;

This macro is invoked in definition 11.

Here's how the interpreter evaluates expressions containing only constants and operators:

Interpret the NumExp and OpExp rules[13] :

void Interpreter::VisitNumExp(NumExp* node)
{ ExpValues.push(node->Child1());
}

void Interpreter::VisitOpExp(OpExp* node)
{ (node->Child1())->Accept(this);
  (node->Child3())->Accept(this);
  (node->Child2())->Accept(this);
}

This macro is invoked in definition 28.

Notice that VisitOpExp doesn't actually do any computation of its own. It simply visits its children in an appropriate order. The actual operation is performed by one of the subclasses of Binop, all of which have the same form:

Interpret any rule whose left-hand-side symbol is Binop[14]  :

void Interpreter::Visit ( * node)
{ int right, left;

  right = ExpValues.top(); ExpValues.pop();
  left = ExpValues.top(); ExpValues.pop();
  ExpValues.push(left right);
}

This macro is invoked in definition 28.

Here the first parameter is the name of a rule node (e.g. Plus) and the second is the corresponding C++ operator (e.g. +).