Recall that a non-LL(1) grammar must be transformed to an equivalent LL(1) grammar if it is to be parsed using a predictive parser. Recall also that the transformed grammar usually does not reflect the underlying structure the way the original grammar did. For example, when left recursion is removed from the grammar for arithmetic expressions, we get grammar rules like this:
exp -> term exp'
exp' -> epsilon
-> + term exp'
It is not at all clear how to define a syntax-directed translation for rules like these. The solution is to define the syntax-directed translation using the original grammar (define translation rules, convert them to actions that push and pop using the semantic stack, and then incorporate the action numbers into the grammar rules). Then convert the grammar to be LL(1), treating the action numbers just like grammar symbols!
For example:
Non-LL(1) Grammar Rules With Actions
====================================
exp -> exp + term #1
-> term
term -> term * factor #2
-> factor
#1: TTrans = pop(); ETrans = pop(); push Etrans + TTrans;
#2: FTrans = pop(); TTrans = pop(); push Ttrans * FTrans;
After Removing Immediate Left Recursion
=======================================
exp -> term exp'
exp' -> + term #1 exp'
-> epsilon
term -> factor term'
term' -> * factor #2 term'
-> epsilon
Summary
A syntax-directed translation is used to define the translation of a sequence of tokens to some other value, based on a CFG for the input. A syntax-directed translation is defined by associating a translation rule with each grammar rule. A translation rule defines the translation of the left-hand-side nonterminal as a function of the right-hand-side nonterminals' translations, and the values of the right-hand-side terminals. To compute the translation of a string, build the parse tree, and use the translation rules to compute the translation of each nonterminal in the tree, bottom-up; the translation of the string is the translation of the root nonterminal.
There is no restriction on the type of a translation; it can be a simple type like an integer, or a complex type list an abstract-syntax tree.
To implement a syntax-directed translation using a predictive parser, the translation rules are converted to actions that manipulate the parser's semantic stack. Each action must pop all right-hand-side nonterminals' translations from the semantic stack, then compute and push the left-hand-side nonterminal's translation. Next, the actions are incorporated (as action numbers) into the grammar rules. Finally, the grammar is converted to LL(1) form (treating the action numbers just like terminal or nonterminal symbols).
