Recall that the parser must produce output (e.g., an abstract-syntax tree) for the next phase of the compiler. This involves doing a syntax-directed translation -- translating from a sequence of tokens to some other form, based on the underlying syntax.

A syntax-directed translation is defined by augmenting the CFG: a translation rule is defined for each production. A translation rule defines the translation of the left-hand side nonterminal as a function of:

* constants

* the right-hand-side nonterminals' translations

* the right-hand-side tokens' values (e.g., the integer value associated with an INTLIT token, or the String value associated with an ID token)

To translate an input string:

1. Build the parse tree.

2. Use the translation rules to compute the translation of each nonterminal in the tree, working bottom up (since a nonterminal's value may depend on the value of the symbols on the right-hand side, you need to work bottom-up so that those values are available).

The translation of the string is the translation of the parse tree's root nonterminal.

Example 1

Below is the definition of a syntax-directed translation that translates an arithmetic expression to its integer value. When a nonterminal occurs more than once in a grammar rule, the corresponding translation rule uses subscripts to identify a particular instance of that nonterminal. For example, the rule exp -> exp + term has two exp nonterminals; exp1 means the left-hand-side exp, and exp2 means the right-hand-side exp. Also, the notation xxx.value is used to mean the value associated with token xxx.