Syntax-Directed Translation Schemes

A syntax-directed definition says what each attribute equals but leaves the order of evaluation to the dependency graph. A syntax-directed translation scheme (SDT) fixes the order: it is a context-free grammar with program fragments, called semantic actions, written in braces inside production bodies. An action runs at exactly the point where it appears, so an SDT is a recipe that a parser can follow while it parses.

SDTs are how translators are actually written: postfix converters, desk calculators, type checkers and intermediate-code generators. The working tasks are tracing a short SDT with print actions to find its output on an input string, and working out what an SDT with unusual actions computes.

To find the output, build the parse tree of the input using the grammar with the actions removed, put each action back as a leaf in its position, and walk the tree left to right, depth first, executing actions as they are met.

Example 1: infix to postfix. With $F \to \texttt{num}$ printing the number:

On 2 + 3 * 4 the tree has $E \to E + T$ at the root with $T \to T * F$ under its right child. The walk prints 2, then descends into the right $T$, printing 3, 4, *, and finally prints + at the end of the root body. The output is 2 3 4 * +. On 2 + 3 + 4 left recursion makes the left + deeper, and the output is 2 3 + 4 +. This is the same infix-to-postfix conversion that a stack-based algorithm performs, now driven by the grammar.

Example 2: actions in front give prefix. Move each operator's action to the front of its body:

The same walk on 2 + 3 * 4 now prints + 2 * 3 4, the prefix form. The parse tree is unchanged; only the action positions differ.

Example 3: mid-body actions. Consider

The input a a c b b has one parse tree: two nested $S \to aSb$ nodes around $S \to c$. The walk meets the first a, prints 1, descends, meets the second a, prints 1, descends to c and prints 3, then returns past each b, printing 2 twice. The output is 1 1 3 2 2. If the actions are moved to $S \to a\ S\ \{\text{print}(2)\}\ b\ \{\text{print}(1)\} \mid c\ \{\text{print}(3)\}$, the output on the same input becomes 3 2 1 2 1.

Example 4: unusual semantics. An SDT may swap the meanings of operators. With the usual grammar but

the input 3 + 4 * 5 is still parsed as $3 + (4 * 5)$ because the grammar, not the actions, fixes the structure. The inner * node computes $4 + 5 = 9$ and the root computes $3 \times 9 = 27$, while the ordinary value is 23. On 2 * 3 + 4 the tree is $(2 * 3) + 4$, giving $(2 + 3) \times 4 = 20$. Always build the tree from the grammar first and then apply the actions as written.

In a postfix SDT every action runs at a reduction. Keep the attribute of each grammar symbol in the same stack slot as the symbol (or its state). When the parser reduces by $E \to E_1 + T$, the three topmost slots hold $E_1$, + and $T$, so the action becomes

and the result sits where the new $E$ is pushed. This works for every S-attributed SDD on an LR-parsable grammar: turn each rule into an action at the end of its production.

A mid-body action, as in $S \to a\,\{a_1\}\,S\,b$, cannot run at a reduction of $S$ because the reduction happens after $b$. The standard fix replaces the action by a marker:

The language is unchanged and, for this grammar, the parser remains LALR(1): after a, the parser reduces $M \to \varepsilon$ on lookahead a or c and so runs $a_1$ at the right moment.

Markers can, however, create conflicts. The grammar $S \to a\,b \mid a\,c$ is LR(0). Put a different action at the start of each alternative, and the markers give $S \to M\,a\,b \mid N\,a\,c$ with $M \to \varepsilon$ and $N \to \varepsilon$. In the start state the parser must choose between reducing $M$ and reducing $N$ on the same lookahead a, before it has seen whether b or c follows. That reduce-reduce conflict remains even for a canonical LR(1) parser. With two symbols of lookahead the conflict disappears (reduce $M$ on ab and $N$ on ac), so the grammar is LR(2). An action can be run early only if the parser knows by then which production it is in.

For a top-down parser, left recursion must go, and the actions must move with it. For a postfix SDT

introduce $R$ with an inherited attribute $R.i$ (the value so far) and a synthesized attribute $R.s$ (the final value):

Example 5: subtraction stays left-associative. For $E \to E_1 - T\ \{E.val = E_1.val - T.val\} \mid T$, the transformed scheme is $E \to T\ \{R.i = T.val\}\ R\ \{E.val = R.s\}$, $R \to -\,T\ \{R_1.i = R.i - T.val\}\ R_1\ \{R.s = R_1.s\} \mid \varepsilon\ \{R.s = R.i\}$. On 9 - 5 - 2, $R.i$ takes the values 9, then 4, then 2, and the $\varepsilon$ production hands 2 back up: $(9 - 5) - 2 = 2$, the same as the left-recursive version. Simply reversing the recursion without the inherited attribute would compute $9 - (5 - 2) = 6$, the classic wrong answer.

Example 6: actions at the ends of bodies, nested input.

On a a b c b d the root is $S \to a\,S\,T$; its $S$ is again $S \to a\,S\,T$ over a b c, and its $T$ is $T \to S\,d$ over b d. The walk prints 2 (inner b), 3 (c), 1 (inner $S$ complete), 2 (the b in b d), 4 ($T \to S d$ complete), 1 (root complete): output 2 3 1 2 4 1. Every action is at the end of its body, so this is a postfix SDT, and the output order is exactly the order of reductions in an LR parse: $S \to b$, $T \to c$, $S \to a S T$, $S \to b$, $T \to S d$, $S \to a S T$.

Example 7: count the prints by counting reductions.

On x x x x y z z the derivation is $S \Rightarrow xxW \Rightarrow xxSz \Rightarrow xxxxWz \Rightarrow xxxxSzz \Rightarrow xxxxyzz$. Bottom-up, the reductions are $S \to y$, $W \to S z$, $S \to x x W$, $W \to S z$, $S \to x x W$, so the output is 2 3 1 3 1.

Common misconceptions.