Compiler Design
S-Attributed & L-Attributed Definitions
S-Attributed and L-Attributed Definitions
To evaluate attributes efficiently during parsing, we restrict our Syntax Directed Definitions (SDDs) to specific subclasses. The two most important subclasses are S-attributed and L-attributed definitions.
S-Attributed Definitions
Definition
An SDD is S-attributed if it uses only synthesized attributes.Every semantic rule in an S-attributed SDD computes a synthesized attribute for the nonterminal on the left-hand side of the production.
- Evaluation Order: Can be evaluated in a single bottom-up pass during LR parsing.
- Traversal: Postorder traversal of the parse tree.
- Implementation: Typically managed by maintaining a parallel stack containing attribute values alongside the parser's state stack.
L-Attributed Definitions
Definition
An SDD is L-attributed if for every productionA → X_1 X_2 ... X_n, each inherited attribute of X_j depends only on:- The inherited attributes of
A(the parent). - Any attributes (synthesized or inherited) of symbols
X_1, X_2, ..., X_(j-1)located to the left ofX_jin the production body.
L-attributed definitions permit inherited attributes but enforce a strict left-to-right dependency to ensure single-pass evaluation.
- Evaluation Order: Can be evaluated in a single left-to-right depth-first traversal.
- Parser Compatibility: Highly compatible with LL (top-down) parsers and can also be evaluated during LR (bottom-up) parsing using specialized translation techniques.
- Relationship: All S-attributed definitions are, by definition, L-attributed as well (since they have zero inherited attributes).
Comparison Table
| Property | S-Attributed | L-Attributed |
|---|---|---|
| Attribute Types | Only Synthesized | Synthesized + Inherited (with left-dependency restriction) |
| Tree Traversal | Postorder (Bottom-Up) | Left-to-Right Depth-First (Top-Down/Bottom-Up) |
| Compatible Parsers | LR parsers (LALR, SLR, CLR) | LL parsers, also LR parsers |
| Inherited Support? | No | Yes (restricted flow) |
| Typical Use Case | Expression evaluation, simple code generation | Type checking, scoped translation, nested declarations |
Exam Tip
If asked how attribute evaluation is implemented:- For S-attributed: Use a parallel value stack in an LR parser. Values are pushed/popped alongside grammar states.
- For L-attributed: In recursive descent (LL) parsers, inherited attributes are passed as function parameters, and synthesized attributes are returned as function values.