Attribute Grammars

Syntax-directed translation showed us values riding up a parse tree. But real language semantics are not a one-way street. A type declared on the left of int x, y, z; must travel down and across to reach each identifier; a symbol's scope flows in from its surroundings; a label's address must be known before the jump that targets it is generated. An attribute grammar is the formal framework for all of this: a context-free grammar in which every symbol carries attributes, and every production carries equations (semantic rules) defining how those attributes relate. It is the theory that tells you which translations can be done in one pass, which need several, and which cannot be done at all.

The whole subject turns on one distinction: the direction an attribute flows.

Two kinds of attribute

Each attribute of a grammar symbol is one of two kinds, decided by which production computes it.

A synthesized attribute of a node N is defined by the rule of the production at N itself, in terms of the attributes of N's children (and N's own inherited attributes). Information flows up. Example: the value of an expression.
An inherited attribute of a node N is defined by the rule of the production at N's parent, in terms of the parent's attributes and those of N's left siblings. Information flows down and across. Example: a declared type pushed into a list of names.

A slogan captures it: values flow up, types flow down. Synthesized attributes summarise a subtree for its parent; inherited attributes carry context from the surroundings into a subtree. Terminals have only synthesized attributes (their lexical value), supplied by the scanner. The start symbol has no inherited attributes worth speaking of — there is nothing above it to supply them.

The picture: arrows up and arrows down

Consider the declaration real p, q with the SDD D \to T\ L, L \to L_1 , \mathbf{id} \mid \mathbf{id}. Here T.\text{type} is synthesized (it flows up out of the keyword), then handed to L as the inherited attribute L.\text{inh}, which each L passes down its left spine to stamp every identifier. Watch the two directions: one arrow up, then a cascade of arrows down and left.

The upward arrow (synthesized) and the downward-and-leftward arrows (inherited) are the entire story. This mixture — a synthesized attribute feeding an inherited one, which feeds a computation deeper in the tree — is exactly why some SDDs cannot be evaluated bottom-up: you cannot compute L.\text{inh} until T.\text{type} is known, yet L sits above the identifiers it must stamp.

The dependency graph decides the evaluation order

There is no "left to right" law of attribute evaluation — only the dependency graph. Draw a node for every attribute instance in the decorated parse tree, and an edge a \to b whenever the rule for b mentions a. Any topological sort of this graph is a legal evaluation order: compute each attribute only after everything it depends on. If the graph is acyclic, an order exists; if it has a cycle, the SDD is ill-defined for that tree and no order can rescue it.

Most real definitions fall into two well-behaved classes, and their whole appeal is that you can find a valid order without building the dependency graph at parse time:

An SDD is S-attributed if it uses only synthesized attributes. Every dependency then points from children to parent, so a single bottom-up (post-order) pass evaluates it — the natural fit for LR parsing.
An SDD is L-attributed if every inherited attribute of a right-hand symbol X_j depends only on (i) inherited attributes of the parent, and (ii) attributes of the symbols X_1,\dots,X_{j-1} to its left. Synthesized attributes are also allowed. Such an SDD is evaluable in one depth-first, left-to-right walk — the natural fit for recursive-descent (LL) parsing.
Every S-attributed SDD is L-attributed (there are no inherited attributes to violate the rule), but not conversely: L.\text{inh} above needs the inherited direction, so it is L-attributed but not S-attributed.

Evaluating an L-attributed definition, in code

The elegance of an L-attributed SDD is that its evaluation order is exactly a depth-first traversal: at each node, compute inherited attributes on the way down (before recursing into a child) and synthesized ones on the way up (after the children return). The recursion order and the legal attribute order coincide, so a single traversal suffices. Here we stamp a declared type onto a list of names — D \to T\,L — carrying inh down and reading nothing that is not already to the left.

// Attribute grammar for: T id, id, id ... type flows DOWN (inherited). type IdList = { names: string[] }; // parsed L subtree const table: Record<string, string> = {}; // id -> declared type // L rule: each id gets L.inh stamped onto it (inherited attribute flows down/left) function evalL(list: IdList, inh: string): void { for (const name of list.names) table[name] = inh; // "L.inh = T.type" applied } // D → T L : T.type is synthesized up, then handed to L as its inherited attr. function evalD(tokenType: string, list: IdList): void { const Ttype = tokenType; // synthesized: value flows UP out of the keyword evalL(list, Ttype); // inherited: Ttype flows DOWN into L } evalD("real", { names: ["p", "q"] }); evalD("int", { names: ["i", "j", "k"] }); for (const [name, ty] of Object.entries(table)) console.log(`${name} : ${ty}`);

Notice you could not reorder this into a pure bottom-up pass: evalL needs Ttype from its parent before it can touch a single name. That downward dependency is the signature of an inherited attribute, and it is precisely what a one-pass bottom-up (S-attributed) evaluator cannot express — you would have to buffer the names and patch them afterwards, i.e. take a second pass.

An LR/yacc value stack naturally supports only synthesized attributes — everything flows up on reduce. Yet yacc programmers routinely pass a declared type into a list of names. The trick is that the needed value is already sitting lower on the parse stack (it was reduced earlier, to the left), and yacc lets an action reach down the stack to read it via the $0, $-1 pseudo-variables. This works only for L-attributed definitions, because only a strictly-left dependency is guaranteed to be present-and-below on the stack at the moment you need it. Reach for a value that is to the right, and it simply has not been parsed yet — there is nothing on the stack to read. The stack discipline enforces L-attributedness whether you meant it to or not.

Two failures haunt attribute grammars. The first: a circular dependency. If attribute a is defined using b and, following the arrows around, b ends up defined using a, the dependency graph has a cycle, no topological sort exists, and the attributes are simply undefined — there is no "value" to compute. (Deciding whether an arbitrary SDD is circular for some tree is, famously, an exponential-time problem.) The cure is to design so the graph is acyclic — S- and L-attributed definitions are acyclic by construction.

The second, subtler trap: assuming every attribute can be computed in a single bottom-up pass. Synthesized attributes can. Inherited attributes cannot — an inherited attribute of a node depends on its parent and left siblings, which a post-order (children-before-parents) walk has not fully processed in the way you need. If your translation needs information to flow downward, either use an L-attributed evaluator (a depth-first walk that sets inherited attributes on the way down), or make two passes. Trying to force it bottom-up produces attributes read before they are written.