Recursive Descent Parsing:The Interpreter Value Stack

• An interpreter doesn’t generate code. It performs semantic actions as it parses the input. For expressions, such as those used in the Toy Grammar, it uses a value stack to hold values and their types.

• The value stack stores intermediate results of parsing for later use in a grammar rule. Here’s an example using a simple translation scheme with semantic actions inserted in their proper places:

<> --> ID {enter} ‘=’ <> {pop;copy} ‘;’

<> --> <> ‘+’ <> {pop;pop;add;push}

<> --> ID {lookup;push} | CONST {eval;push}

Look at how the semantic actions use the value stack:

• {lookup;push}: When the parsing function implementing item() recognizes an ID token, it looks up the value and type of the identifier in the symbol table and pushes the current value and type of that identifier onto the value stack. (An undefined identifier would be a run-time error.)

• {eval;push}: When the parsing function implementing item() recognizes a constant, it evaluates the constant and pushes the value and type of the constant onto the value stack.

• {pop;pop;add;push}: The parsing function implementing plus() parses two items. Each call to item() pushes a value on the stack. After both items have been pushed, plus() pops each one off, adds them together, and pushes the result back on the stack. In more complex grammars, a separate execute(operator) function does the arithmetic.

• {pop;copy}: When the plus() function returns control to the parsing function implementing stmt(), stmt() pops the stack and copies the top value and type into the symbol table at the location for the identifier located at the start of stmt(). (Type checking would be done here, too.)

• {enter}: This semantic action doesn’t use the value stack. It looks up the identifier in the symbol table and returns a pointer to its location there. If the identifier doesn’t exist, it adds it and returns a pointer to it.