Translation Scheme

A Syntax-Directed Translation scheme (SDT) is a context-free grammar in which semantic actions — program fragments enclosed in braces { } — are embedded inside the production bodies.

The placement of an action is what makes an SDT different from an SDD. An SDD is declarative: it attaches a semantic rule to each production but never says when the rule runs. An SDT fixes the evaluation order by where the action sits in the body — so translation can happen during parsing rather than as a separate pass over a finished tree.

Position decides timing. Scanning a production body left to right, an action runs after everything on its left has been processed and before anything on its right.

Postfix SDT. When every action sits at the very end of its body, the scheme is a postfix SDT. A postfix SDT corresponds exactly to an S-attributed definition (only synthesized attributes — values built bottom-up from children), because each action fires only after the whole right-hand side is complete.

The rest of this topic follows one running example the whole way through.

Take the standard expression grammar and turn it into an SDT that translates infix to postfix (Reverse Polish). The trick is simple: print each operator after its operands, and print a digit as soon as it is reduced.

Grammar with semantic actions

Here n is the end-of-line marker that finishes a complete expression, and digit is a single numeric token whose value is digit.lexval.

Why this is a postfix SDT. Every action sits at the end of its body:

• print('+') fires only after both E₁ and T are done — so + is emitted after its two operands.
• print('*') fires only after both T₁ and F are done.
• print(digit.lexval) fires the moment a digit is reduced to F.

Because all actions are end-of-body, this scheme is S-attributed-style: there is nothing to pass down the tree, only output produced bottom-up. That is exactly what makes the postfix order fall out automatically.

Our input for the rest of the topic is:

Run the SDT on ( 3 \* 5 + 2 ) \* 2 n. The actions fire in post-order during a bottom-up parse: every node's action runs after all of its children's actions. We build the output string one action at a time.

Order in which the actions fire

Final postfix output

Walking through it. Inside the parentheses, 3 and 5 reduce to F and are printed, then T → T₁ \* F fires print('*'), giving 3 5 * for the subexpression 3 \* 5. Next 2 is printed, and E → E₁ + T fires print('+') to close off (3 \* 5) + 2 as 3 5 * 2 +. The parentheses themselves produce no output — F → ( E ) has no action; they only shape the parse. Finally the outer 2 is printed and the top-level T → T₁ \* F fires print('*'), multiplying the whole parenthesised result by 2.

Verification. The postfix 3 5 * 2 + 2 * evaluates as: 3 5 * → 15, then 15 2 + → 17, then 17 2 * → 34. And the infix (3 \* 5 + 2) \* 2 = (15 + 2) \* 2 = 17 \* 2 = 34. They match. ✓

Why post-order gives postfix. Each operator's action sits at the end of its production, so it cannot fire until both operand subtrees have finished printing. Operators therefore always appear after their operands in the output — which is the definition of postfix.

(The diagram shows the inner subexpression 3 \* 5 + 2; the outer \* 2 wraps this whole tree under one more T → T₁ \* F node, firing the final print('*').)

In our running example every action sat at the end of the body — and that is the rule for synthesized attributes and postfix translation: output (or a value) built purely from the children is produced after the whole body is parsed. That is why print('+') could go at the end and still come out in the right place.

But not every translation is bottom-up. If an action needs an inherited value — information passed down from the parent or a left sibling — it must be placed before the symbol that uses it. This is the L-attributed rule.

Placement rule. For a body α { action } β, the action runs after all of α (so α's attributes are ready) and before any of β (so it can hand inherited values to β).

A tiny one-line illustration of an inherited action — passing a type down to a list of identifiers:

If that action were moved to the end (D → T L { ... }) it would be too late: L would already be parsed without ever seeing the type. Our infix-to-postfix scheme needs none of this — every value flows upward, so end-of-body placement is enough.

Our scheme is a postfix SDT, so it implements most naturally on a bottom-up (LR) parser: each action is code that runs at the moment the parser performs the corresponding reduce.

The parser keeps a value stack alongside its state stack: shifting a digit makes its lexval available, and each reduction's action consumes the relevant top-of-stack values. This is exactly how yacc / bison attach C code to grammar rules. (Top-down recursive-descent parsers can run the same scheme too, firing each print right after the matching operands are parsed — see the code variants.)

Key points

• An SDT is a CFG plus actions in { } embedded in production bodies; position decides execution order — unlike a declarative SDD.
• All actions at the end of bodies → a postfix SDT → corresponds to an S-attributed definition → runs on the value stack at each LR reduce, in post-order.
• An action needing an inherited value must go before the symbol that uses it (the L-attributed rule).
• For ( 3 \* 5 + 2 ) \* 2 n, end-of-body print actions emit operators after their operands, giving the postfix 3 5 * 2 + 2 * — which evaluates to 34, matching the infix expression.