Syntax-Directed Definitions

Definition. A Syntax-Directed Definition (SDD) is a context-free grammar in which each grammar symbol may carry attributes (named values) and each production has semantic rules that say how to compute those attributes. Applying the rules over a parse tree produces an annotated (or decorated) parse tree.

The grammar gives the structure; the attributes and rules give the meaning. When the parser builds a parse tree, the semantic rules fill in an attribute value at every node. A parse tree with all its attribute values filled in is the annotated parse tree — that is the whole output of an SDD.

We will use one example for the entire chapter: a desk calculator that reads an arithmetic expression and prints its value.

Here is the one grammar we use throughout. Every non-terminal carries a single synthesized attribute val; the terminal digit carries lexval, which the lexer sets.

Grammar

Semantic rules

Every rule computes a parent's value from its children, so all attributes are synthesized. The terminal n marks end of input and the rule for S → E n prints the final answer.

Input sentence

In the next section we run this exact input through the rules.

Because all attributes are synthesized, we evaluate bottom-up: each node's val is computed only after its children are known. Here is the full trace, in the order the values become available.

The inner parenthesised expression 3 * 5 + 2 evaluates to 17; the parentheses pass that value up unchanged through F → ( E ); then the outer * 2 gives 17 * 2 = 34.

The annotated parse tree (values shown in braces):

Each node is decorated only after its children, and the root E carries val = 34. The rule S → E n then runs print(E.val) — the program prints 34.

Two subclasses of SDDs can be evaluated in a single pass during parsing, which is why they matter in practice.

S-attributed: every attribute is synthesized. Evaluable during a bottom-up (LR) parse — compute each value on every reduce.

L-attributed: synthesized attributes are allowed, plus inherited attributes, where an inherited attribute of Xⱼ in A → X₁ … Xₙ may depend only on A's inherited attributes or on attributes of the left siblings X₁ … Xⱼ₋₁. Evaluable during a top-down (LL) parse or one left-to-right traversal.

Our running calculator is S-attributed: there is exactly one attribute, val, and every rule sets a parent's val from its children. Nothing flows down. That is precisely why the bottom-up trace above worked — each val was ready the moment its children were reduced, with no second pass.

Since every S-attributed SDD is also L-attributed, the calculator is L-attributed too; it simply never needs the extra inherited-attribute freedom that L-attributed definitions allow.

• SDD = grammar + attributes + semantic rules. Applying the rules to a parse tree gives an annotated parse tree.
• Synthesized attribute → value from children, flowing bottom-up. In our example val is the only attribute and it is synthesized everywhere.
• The desk calculator on ( 3 * 5 + 2 ) * 2 n evaluates the inner expression to 17, passes it up through F → ( E ), then computes 17 * 2 = 34 and prints 34.
• Because every attribute is synthesized, the SDD is S-attributed and evaluable in one bottom-up (LR) pass — one value computed per reduce.
• Every S-attributed SDD is also L-attributed; L-attributed merely adds left-restricted inherited attributes, which this example does not need.