## Interpreting part 1Our first shunting yard example is an example of an interpreter, i.e. it interprets the expressions given it without generating machine code. In computer language we would encounter the same expression repeatedly if it were the test expression of a loop, so re-lexing and re-evaluating it each time it is encountered would be inefficient, so we would like to lex and parse the expression once while maintaining it's form for repeated evaluation during run-time. To do this we want to transform the expression into an expression tree. Consider this structure for a "
To make the shunting yard program generate an expression tree, we change our number stack to an expression node stack. Numeric constants are transformed into node leaves and operations pop nodes for their left and right side and then push the resulting tree back onto the node stack. Consider the expression:
The operator stack now will be drained (we've reached the end of the expression and so operators are poped off the operator stack until it is empty.) The first operator is the *, which pops the 3 and 2 which creates the tree:
Then we pop the + operator and create the following tree:
To do the constant folding during the parse phase, in the |