Syntax-Directed Translation

A grammar tells you the shape of a legal program. But a compiler must do something as it recognises that shape — compute a value, build an AST, emit code, fill a symbol table. Syntax-directed translation is the discipline of hanging those computations directly onto the grammar's productions, so that the structure of the parse drives the translation. You do not write a separate pass that re-discovers the program's structure; you piggyback on the structure the parser already found.

The idea comes in two flavours that are easy to confuse. A syntax-directed definition (SDD) is declarative: it attaches semantic rules to each production — equations relating the attributes of the symbols — and says nothing about when they run. A syntax-directed translation scheme (SDT) is operational: it embeds semantic actions (code fragments in { … }) at specific points inside the production's right-hand side, fixing exactly when each action fires during the parse. The SDD says what the translation is; the SDT says how and when to carry it out.

Attributes: the values that ride on grammar symbols

Every grammar symbol carries a bag of attributes — named values computed from its children (or, sometimes, its context). For a calculator, each expression symbol carries a single attribute \text{.val}: the number it evaluates to. A production's semantic rule then says how the parent's attribute is built from its children's. Reading the classic expression grammar as an SDD:

Production	Semantic rule
L \to E\ \mathbf{n}	L.\text{val} = E.\text{val} (print it)
E \to E_1 + T	E.\text{val} = E_1.\text{val} + T.\text{val}
E \to T	E.\text{val} = T.\text{val}
T \to T_1 \times F	T.\text{val} = T_1.\text{val} \times F.\text{val}
T \to F	T.\text{val} = F.\text{val}
F \to ( E )	F.\text{val} = E.\text{val}
F \to \mathbf{digit}	F.\text{val} = \mathbf{digit}.\text{lexval}

Every rule computes a parent attribute purely from its children's attributes and moves the value up the tree. Attributes of this kind — flowing strictly upward from children to parent — are called synthesized, and an SDD that uses only synthesized attributes is S-attributed. S-attributed definitions are exactly the ones you can evaluate in a single bottom-up pass, which is why they pair so naturally with an LR parser: reduce a production, run its rule. (The full theory of synthesized vs inherited attributes is the subject of attribute grammars.)

A decorated parse tree

Evaluating an SDD means decorating the parse tree: annotate each node with its attribute value, computing children before parents. Watch 3 \times 4 + 5 light up from the leaves. Each digit's \text{.val} comes straight from the token; each interior node combines its children according to its production's rule; the answer, 17, emerges at the root.

The arrows point the way the values flow: always upward, children first. That single direction is what makes the evaluation a straightforward post-order walk — and what lets a bottom-up parser interleave it with parsing, computing 3 \times 4 = 12 at the moment it reduces T \to T \times F, long before it has seen the + 5.

From rules to actions: the translation scheme

To actually run an SDD you turn each semantic rule into a semantic action and place it in the production. For an S-attributed definition the placement is trivial — every action goes at the end of the right-hand side, because a parent's value can only be computed once all its children exist:

E → E1 + T { E.val = E1.val + T.val } T → T1 * F { T.val = T1.val * F.val } F → ( E ) { F.val = E.val } F → digit { F.val = digit.lexval }

In a bottom-up parser this is literally what the tool does: alongside the parse stack it keeps a value stack, and when it reduces by a production it pops the children's values, runs the action, and pushes the result. Below, a tiny recursive-descent calculator makes the same idea concrete — each parse routine returns the synthesized attribute of the nonterminal it recognises, so the "value stack" is just the call stack.

// A syntax-directed calculator. Each routine returns its nonterminal's .val attribute. function calc(src: string): number { let i = 0; const peek = () => src[i]; const eat = (c: string) => { if (src[i] === c) i++; else throw new Error(`expected ${c}`); }; // E → T { +T }* (semantic rule: E.val = E1.val + T.val) function E(): number { let v = T(); while (peek() === "+" || peek() === "-") { const op = src[i++]; const rhs = T(); v = op === "+" ? v + rhs : v - rhs; // action fires on reduction } return v; } // T → F { *F }* (semantic rule: T.val = T1.val * F.val) function T(): number { let v = F(); while (peek() === "*" || peek() === "/") { const op = src[i++]; const rhs = F(); v = op === "*" ? v * rhs : v / rhs; } return v; } // F → ( E ) | digit (F.val = E.val or digit.lexval) function F(): number { if (peek() === "(") { eat("("); const v = E(); eat(")"); return v; } let n = ""; while (peek() >= "0" && peek() <= "9") n += src[i++]; return Number(n); } return E(); } console.log("3*4+5 =", calc("3*4+5")); // 17 — * binds tighter than + console.log("(3+4)*5 =", calc("(3+4)*5")); // 35 — parens override console.log("2*3*4-5 =", calc("2*3*4-5")); // 19

There is no separate AST here at all: the translation happens as the parse proceeds, and the "tree" exists only implicitly in the recursion. That is syntax-directed translation in its purest, one-pass form. Swap each numeric action for one that builds a node instead of a number, and the very same skeleton builds an AST — the calculator and the tree-builder are the same algorithm with different actions.

When placement stops being free

For S-attributed definitions, actions always sit at the end and life is easy. The moment a production needs a value to flow downward — an inherited attribute, such as a type declared on the left being pushed onto a list of identifiers on the right — the action can no longer wait until the end. It must fire in the middle of the right-hand side, at exactly the point where the value it needs is available and before the symbol that consumes it is parsed.

D → T { L.inh = T.type } L // push T's type DOWN into L, mid-rule L → L1 , id { addType(id.entry, L.inh) ; L1.inh = L.inh } L → id { addType(id.entry, L.inh) }

An SDT that can be evaluated in a single left-to-right parse pass — allowing inherited attributes, but only ones that depend on already-parsed siblings to the left — is called L-attributed. Mid-rule actions are legal precisely when they respect that left-to-right dependency. Place an action too early (before the value it reads has been computed) and it reads a stale or undefined attribute; place it too late and the symbol that needed it has already been parsed with the wrong information. Action placement is not cosmetic — in a one-pass translator it is the whole ballgame.

Because they are S-attributed translators by construction. An LR parser only ever knows it has finished a production at the instant it reduces, so that is the only safe moment to run an end-of-production action — all the children (and hence their values, sitting on the value stack as $1, $2, …) are guaranteed to exist. Yacc does let you write mid-rule actions, but under the hood it silently rewrites them into fresh marker nonterminals that reduce to \varepsilon at the right spot — so even a "mid-rule" action is really an end-of-production action for an invisible helper rule. The machinery bends over backwards to preserve the one-pass, bottom-up story.

The seductive error is to treat semantic actions as if their order did not matter — "they all run eventually, so drop them wherever." For a purely synthesized (S-attributed) translation that is nearly true; every action lands at the end and the post-order walk sorts it out. But the instant an inherited attribute appears, a mid-rule action that fires before the value it depends on has been computed reads garbage, and the whole one-pass translation quietly produces wrong output with no error. The safe discipline: a translation scheme is one-pass-correct only if it is L-attributed — every inherited attribute of a right-hand symbol depends solely on attributes of symbols to its left (and on inherited attributes of the parent), and each action is placed after everything it reads. When in doubt, draw the dependency arrows and check none point rightward across an action.