Syntax-Directed Definitions

Parsing tells the compiler how a program is structured; it does not compute anything about the program. Syntax-directed translation attaches information to grammar symbols, called attributes, and attaches rules to productions that compute those attributes. The value of an expression, the type of a declared name, the code for a statement and the syntax tree of an expression are all attributes.

A syntax-directed definition (SDD) is a context-free grammar together with attributes and semantic rules. It says what must be computed but not when; the order of evaluation follows from the dependencies between attributes. Two restricted classes, S-attributed and L-attributed definitions, can always be evaluated in a fixed order during parsing, which is why examination questions concentrate on recognising them.

Synthesized versus inherited: where the rule lives. A synthesized attribute is computed in the production where its symbol is the head, so its information flows up the tree. An inherited attribute is computed in the production where its symbol is in the body, so its information flows down or sideways. Terminals have synthesized attributes only, supplied by the lexical analyser (for example digit.lexval); the start symbol normally has no inherited attributes.

Side effects. A rule such as addType(id.entry, L.inh) or print(E.val) does not define an attribute; it is treated as defining a dummy attribute of the head so that it gets a place in the dependency graph.

Any order consistent with the dependency graph, that is any topological sort, evaluates every attribute after the attributes it uses. If the graph has a cycle, no order exists and the SDD is circular for that tree. Testing whether an arbitrary SDD can be circular for some parse tree is decidable but takes exponential time, which is the practical reason for restricting attention to S- and L-attributed definitions.

Every S-attributed SDD is L-attributed (there are no inherited attributes to restrict).

($\textbf{n}$ is an end-of-line token; subscripts distinguish two occurrences of the same nonterminal.) For the input 3 * 4 + 5 n the annotated parse tree has, bottom-up: $F.val = 3$, $T.val = 3$, $F.val = 4$, $T.val = 12$, $E.val = 12$, then $F.val = 5$, $T.val = 5$, $E.val = 17$, and $L.val = 17$ at the root. Every value is computed from the children, so a postorder walk, or an LR parser at each reduction, evaluates the whole tree.

The type is known at $T$, on the left, but must reach every identifier in $L$, on the right and further down: an inherited attribute carries it. For float x, y, z the parse tree has three $L$ nodes. The dependency graph has 10 nodes: $T.type$, three $L.inh$, three $\textbf{id}.entry$, and three dummy nodes for the addType calls. It has 9 edges: $T.type \to L.inh$ at the top, two edges passing $L.inh$ down to $L_1.inh$, and two edges into each addType node (from that $L$'s $inh$ and from its $\textbf{id}.entry$). The SDD is L-attributed: $L.inh$ depends on its left sibling $T$, and $L_1.inh$ on the head's inherited attribute.

Left-recursion removal moves the left operand of an operator into a different subtree. An inherited attribute carries it across:

For 3 * 5 * 2: the first $T'$ inherits 3; the next inherits $3 \times 5 = 15$; the last inherits $15 \times 2 = 30$ and, being $\varepsilon$, copies it to $syn$; the 30 is passed back up to $T.val = 30$. The running product is the left-associative value $((3 \times 5) \times 2)$, even though the tree leans to the right. The SDD is L-attributed: each $T'_1.inh$ uses the head's inherited attribute and the left sibling $F$.

For binary numerals, $N \to L$, $L \to L_1 B \mid B$, $B \to 0 \mid 1$, the rules $L.val = 2 \times L_1.val + B.val$, $L.val = B.val$, $B.val = 0$ or $1$, and $N.val = L.val$ are all synthesized. The input 1101 gives $N.val = 13$: the partial values are 1, 3, 6, 13.

The symbol # means multiplication and & means addition, and & is on the lower level $T$, so it binds tighter. For 2 # 3 & 5 # 6 & 4 the tree groups the & pieces first: $T$-values $2$, $3 + 5 = 8$ and $6 + 4 = 10$, and then $E.val = (2 \times 8) \times 10 = 160$. Reading the string with the usual "multiplication first" habit gives $2 \times 3 + 5 \times 6 + 4 = 40$, the trap answer.

$S.d$ is the nesting depth of a balanced string of parentheses. For (()())(), the outer pair encloses ()(), whose depth is 1, so it contributes $1 + 1 = 2$; the trailing () contributes 1. Hence $S.d = \max(2, 1) = 2$ at the root. The definition is S-attributed.

For the only tree, $A$ over $B$ over b, the dependency graph has 2 nodes, $A.s$ and $B.i$, and 2 edges, $B.i \to A.s$ and $A.s \to B.i$: a cycle, so no evaluation order exists. The definition is not L-attributed either, because $B.i$ reads the head's synthesized attribute. L-attributed definitions can never be circular: their inherited attributes use only the head's inherited attributes, attributes from the left, or acyclic same-symbol dependencies. Respecting that local dependency order during a left-to-right depth-first visit makes each required source available.

For each rule, ask: which symbol's attribute does it define, and from which positions does it read?

A whole SDD is S-attributed only if every rule is of the first kind, and L-attributed only if every inherited attribute satisfies the left-to-right restriction.

Common misconceptions.