Attribute Grammars

Attribute Grammars

1. Definition

An attribute grammar adds attributes (values) to grammar symbols plus semantic rules per production. It gives meaning to syntax — types, values, addresses — computed over the parse/syntax tree.

2. Two Attribute Kinds

Kind	Flows	Example
Synthesized	child → parent (bottom-up)	E.val = E1.val + T.val
Inherited	parent/sibling → child (top-down/sideways)	T.inh = E.inh, type env propagation

3. Example — desk calculator

E → E1 + T   { E.val = E1.val + T.val }
E → T        { E.val = T.val }
T → num      { T.val = num.lexval }

For 3+4: leaves val 3,4 → root val 7. Purely synthesized → evaluates bottom-up in one pass.

4. S vs L Attributed

• S-attributed: only synthesized → evaluate in LR order, stack machine friendly.
• L-attributed: synthesized + inherited with left-to-right flow (A → B C uses only inherited(A) + left siblings) → works with LL/top-down and one DFS pass.

5. Exam Points

• Define attribute grammar, synthesized vs inherited — 5 marks, very frequent.
• S vs L attributed + evaluation order — 5 marks, frequent.
• Give attribute grammar for expr / type — 5-7 marks, frequent.