Evaluator

How to "execute" a parse tree

The intermediate data structure that was outputted from the parser represents the source program in a way that it is easy to "execute" this program. The act of "generating" machine codes from this data structure is similar to know the "meaning" of this program. We will explore this point of view. We are going to write a program to perform (to "run" or to "execute") this data structure according to its "meaning".

let x be the parse tree

we define the follwing functions:

head x return the first element of x
tail x return the list without the first element
second x return the second element of x
third x return the third element of x

second x = head tail x
third x = head tail tail x

Example

x is (A B C)
head x = A
tail x = (B C)
second x = B
third x = C

eval x is
h = head x
if h == "+" then
     eval second x + eval third x
if h == "if" then
     if eval second x is true
     then eval third x
     else eval fourth x
....

The "eval" is written recursively. We make use of the builtin + of the implementation language to "execute" the following expression: eval second x + eval third x

This is quite nice and elegant.

26 June 2009