Attributes

An attribute is a value attached to a grammar symbol. Each occurrence of that symbol in a parse tree gets its own copy of the value.

We write an attribute as symbol.name. So E.val is the attribute named val on the non-terminal E. The value can be anything useful during translation: a number, a type, a string, or a symbol-table pointer.

There are exactly two kinds of attribute, decided by which production's rule defines it and what that rule is allowed to read:

Synthesized attribute. A synthesized attribute of a non-terminal A at a parse-tree node N is defined by a semantic rule of the production at N — the production whose head is A. Its value may depend only on the attributes of the children of N, and of N itself.

In plain words: the value is built from the symbols below it, so information flows bottom-up (leaves → root). A terminal gets its synthesized value (e.g. digit.lexval) directly from the lexer.

Inherited attribute. An inherited attribute of a symbol X at a parse-tree node N is defined by a semantic rule of the production at N's parent — the production in whose body X appears. Its value may depend only on the attributes of N's parent, N's siblings, and N itself.

In plain words: the value is handed down from the parent (or sideways from a sibling), so information flows top-down / left-to-right.

Quick test. Look at the rule that defines the attribute: if it reads only the children, the attribute is synthesized; if it reads the parent or a sibling, it is inherited.

Everything below uses one grammar and one input. We will hang two attributes on it: val (synthesized) and depth (inherited).

The grammar

The val attribute (synthesized)

val holds the numeric value of an expression. Each rule reads only its children:

The input

The rest of this topic evaluates exactly this input on exactly this grammar.

We compute val bottom-up: each leaf digit is given its value by the lexer, then every internal node combines its children. The final E.val is what S → E n prints.

The annotated parse tree

Bottom-up trace

Read it leaves-first; every value comes only from the children below it:

1. digit 3 → F.val = 3 → T.val = 3
2. digit 5 → F.val = 5
3. T.val = 3 \* 5 = 15 (the rule T → T₁ \* F)
4. E.val = 15 (via E → T)
5. digit 2 → F.val = 2 → T.val = 2
6. E.val = 15 + 2 = 17 (the rule E → E₁ + T)
7. F.val = 17 (via F → ( E )) → T.val = 17
8. digit 2 → F.val = 2
9. T.val = 17 \* 2 = 34 (the rule T → T₁ \* F)
10. E.val = 34 (via E → T)
11. S → E n runs print(E.val) → prints 34

No node ever needed information from above, so the whole tree evaluates in one bottom-up pass — exactly how an LR parser works.

Now add a second attribute, depth, to the same grammar and the same parse tree. depth is the distance of a node from the root. The root knows it is at depth 0; nothing below can know its own depth without being told from above — so depth is inherited and flows top-down.

The rules

A few depths on the same tree

Each value is computed from the parent, never from children:

The root is shallow and the buried digit 3 is deep. Crucially, the flow is reversed from val: a node receives depth from its parent before it can pass a larger value down to its own children. Same tree, opposite direction — that is the whole difference between inherited and synthesized.

These two classes are exactly the cases that evaluate in a single pass, and we can read both off the running example.

S-attributed definition. An SDD is S-attributed if every attribute is synthesized — no symbol ever carries an inherited attribute.

Using val alone, our grammar is S-attributed: every rule reads only its children, so an LR parser evaluates it bottom-up on a value stack — no separate tree walk needed.

L-attributed definition. An SDD is L-attributed if every attribute is either synthesized, or an inherited attribute that obeys this restriction: for a production A → X₁ X₂ … Xₙ, the rule that computes an inherited attribute of Xᵢ may use only

1. inherited attributes of the head A, and
2. attributes (synthesized or inherited) of the symbols X₁ X₂ … Xᵢ₋₁ that appear to the left of Xᵢ in the body.

The "L" stands for left: every dependency points left-to-right, so nothing ever needs a value from its right.

Adding depth keeps us L-attributed: each child's depth is computed from the parent's depth (case 1) and never looks right. So the combined definition still evaluates in one left-to-right depth-first walk — the way recursive-descent (LL) parsing runs.

Every S-attributed SDD is also L-attributed (it simply has no inherited attributes); the reverse is not true.

• Two kinds of attribute. Synthesized = from children, flows up (our val). Inherited = from parent/left-siblings, flows down/sideways (our depth).
• Same tree, opposite directions. On ( 3 \* 5 + 2 ) \* 2 n, val builds up to 34 while depth is pushed down from the root.
• Quick test. Read the rule: only children → synthesized; parent or sibling → inherited.
• S-attributed = synthesized only → one bottom-up pass → fits LR parsers.
• L-attributed = synthesized + inherited that look only left → one left-to-right depth-first pass → fits recursive-descent.
• Every S-attributed SDD is L-attributed; not the other way around.

In one line: val pushes values up to print 34, depth pushes values down from the root, and the S-/L-attributed classes are exactly the cases evaluable in a single pass.