Recursive Decent Parsing:Action Symbols in the Grammar
Now that we have a parser that can recognize assignment statements, we need to add semantic actions to the parser so that useful work is done. These actions are specified by embedding semantic action symbols in the grammar productions, resulting in a set of rules called a translation scheme (Aho p.37-40: Translation Schemes, Emitting a Translation). First, look at the simple grammar without any action symbols:
Now, turn it into a translation scheme, with the semantic action symbols embedded in the grammar productions in the correct places:
<> --> ID {enter} = <> {pop;copy} ; <> --> ID {lookup;push} | CONST {eval;push}
Here are what each of the action symbols mean:
- {enter}: enter the ID into the symbol table if it isnt already there
- {pop}: pop the top value off the value stack
- {copy}: copy the value to the symbol table at the location of ID
- {lookup}: find this ID in the symbol table; get its current value
- {push}: push the current value on the value stack
- {eval}: evaluate the numeric constant
The action symbols are placed in the exact places we want the actions to occur. We map these locations to the corresponding locations in the code for the recursive-descent parsing functions, and we insert code that performs these actions. The value stack is used by the parser to hold values of expressions (including constants and identifiers).