Syntax-Directed Translation
A Syntax-Directed Definition (SDD) attaches attributes to grammar symbols and semantic rules to productions.
| Synthesized attribute | Inherited attribute |
|---|---|
| Computed from the children's attributes | Computed from the parent's and siblings' attributes |
| Flows up the parse tree | Flows down or sideways |
Desk Calculator SDD
| Production | Semantic rule |
|---|---|
| L → E n | print(E.val) |
| E → E₁ + T | E.val = E₁.val + T.val |
| E → T | E.val = T.val |
| T → T₁ * F | T.val = T₁.val × F.val |
| T → F | T.val = F.val |
| F → ( E ) | F.val = E.val |
| F → digit | F.val = digit.lexval |
Annotated parse tree for 3 * 5 + 4 n:
L → prints 19
└─ E.val = 19
├─ E.val = 15 ── T.val = 15 ── T.val = 3 * F.val = 5
├─ +
└─ T.val = 4S-attributed vs L-attributed
- S-attributed: only synthesized attributes. Evaluate bottom-up; works naturally with LR parsers.
- L-attributed: inherited attributes may depend only on the parent and on siblings to the left. Evaluate in one depth-first, left-to-right pass; works with LL parsers.
- Every S-attributed SDD is L-attributed.
Type Checking
Semantic analysis also checks types, declarations and scope, and inserts conversions (coercions) such as int → float.
Track your progress through the Compiler Design course