CD Notes
In-depth exploration of synthesized attributes in compilers: definition, computation rules, dependency analysis, parsing table integration, S-attributed grammar implementation with complex examples.
Definition and Characteristics
A synthesized attribute is an attribute of a grammar symbol that is computed from the attributes of its children in the parse tree. Values flow upward (bottom-up) from leaves to root.
Key Properties
- Direction: Bottom-up computation
- Dependencies: Only on children's values
- Flexibility: No restrictions on dependency order
- Evaluation: Can use depth-first post-order traversal
S-Attributed Grammars
An S-attributed grammar uses only synthesized attributes. These are the simplest and most efficient attribute grammars.
Advantages of S-Attributed Grammars
| 1. Simple evaluation order | Post-order (leaves first) |
| 2. Single pass | One tree traversal computes all |
| 3. Efficient | O(n) where n = tree nodes |
| 4. Compatible | Works naturally with LR parsers |
| 5. No inheritance | Simpler implementation |
Example: Expression Evaluation Grammar
| 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 | num {F.val = num.val} |
Computation Rules and Constraints
Semantic Rule Format
For production A → X₁ X₂ ... Xₖ:
A.s := f(X₁.a, X₁.b, X₂.c, ...)
Where:
- X₁, X₂, ... are grammar symbols
- a, b, c are synthesized attributes
- f is any computable functionWell-Formedness Constraints
| 1. Single-valued | Each attribute assigned exactly once |
| A.s | = ... (exactly one rule) |
| 2. Acyclic | No attribute depends on itself |
| E.val | = E.val + 1 ✗ Circular |
| 3. Deterministic | Same input always produces same output |
| A.s | = random() ? (non-deterministic) |
Evaluation Algorithms
Algorithm: Post-Order Traversal
postorder(node):
if node is leaf:
compute node's synthesized attributes from tokens
else:
for each child in node.children:
postorder(child)
compute node's synthesized attributes using children's values
evaluate(root):
postorder(root)
return root's attributesExample Execution
| Expression | 2 + 3 * 4 |
| 1. F (leaf 2) | F.val = 2 |
| 2. T | T.val = 2 |
| 3. F (leaf 3) | F.val = 3 |
| 4. F (leaf 4) | F.val = 4 |
| 5. T | T.val = 3 * 4 = 12 |
| 6. E | E.val = 2 + 12 = 14 |
| Result | 14 ✓ |
Integration with LR Parsers
Why LR Parsers Love Synthesized Attributes
Implementation with LR Parsing
| Stack | [(state₁, attr₁), (state₂, attr₂), ...] |
| Action | shift a |
| Action: reduce by A | X₁X₂...Xₖ |
| Gather attributes | X₁.attrs, X₂.attrs, ..., Xₖ.attrs |
| Compute | A.attrs = f(X₁.attrs, X₂.attrs, ...) |
Example: Type-Checking Synthesized Attributes
Grammar
D → id : T {T.sym_entry = addSymbol(id, T.type)}
T → int {T.type = "int"; T.size = 4}
T → real {T.type = "real"; T.size = 8}
Code
int x;
Execution (LR)
1. Shift int
2. Shift id (x)
3. Reduce: T → int {T.type = "int", T.size = 4}
4. Shift :
5. Reduce: D → id : T {addSymbol("x", "int")}
Practical Implementation Examples
Example 1: Arithmetic Expression Compiler
Grammar
E → E₁ + E₂ {E.code = E₁.code || E₂.code || "add"}
E → E₁ - E₂ {E.code = E₁.code || E₂.code || "sub"}
E → E₁ * E₂ {E.code = E₁.code || E₂.code || "mul"}
E → id {E.code = "load " || id}
E → num {E.code = "push " || num}
Input: 2 + 3
Output code
push 2
push 3
add
Example 2: Type Inference
Comparison: Synthesized vs Inherited Attributes
| Aspect | Synthesized | Inherited |
|---|---|---|
| Flow | Upward (child → parent) | Downward (parent → child) |
| Grammar class | S-attributed | L-attributed (more complex) |
| Evaluation | Post-order (natural for LR) | Top-down (natural for LL) |
| Dependencies | Children only | Parent, ancestors, siblings |
| Efficiency | Simple O(n) one-pass | May need reordering |
Error Propagation via Synthesized Attributes
Quick Revision Notes
- Synthesized attribute: Computed from children's attributes only
- S-attributed grammar: Uses only synthesized attributes
- Evaluation order: Post-order (depth-first, leaves first)
- Complexity: O(n) single pass for trees
- LR integration: On reduce action, compute parent's attributes
- Acyclic: Synthesized attributes form DAG (directed acyclic graph)
- No inheritance: Simplifies language design and implementation
Interview Q&A
Q1: Why are synthesized attributes so common in LR parsers?
A: LR parsing is naturally bottom-up (shift-reduce). When you reduce (pop children, push parent), it's the perfect time to compute the parent's synthesized attributes from the children's values. The parser's execution order naturally aligns with attribute computation order.
Q2: Can every semantic computation be expressed using only synthesized attributes?
A: Not easily for all cases. Some languages need top-down context (inherited attributes). However, you can often reformulate using multiple passes or by pushing context down explicitly. S-attributed grammars are restrictive but much simpler.
Q3: What's the time complexity of evaluating synthesized attributes for a parse tree?
A: O(n) where n is the number of nodes in the parse tree. Each node is visited once (post-order), and each attribute computation is O(1). This is optimal—you must look at every node at least once.
Q4: How do you handle synthesized attributes that depend on multiple children with complex computations?
A: Write the semantic rule as a function that takes all needed child attributes as parameters. Practical implementations allow multi-line actions with complex logic, calling helper functions, accessing global state (symbol tables), etc.
Q5: How do synthesized attributes interact with error recovery?
A: On error in an attribute computation, propagate an "error" attribute upward. Leaf nodes that detect errors set error=true; parents check if any child has error=true before using those values. This lets parsing continue while tracking errors.
Q6: Why not just use synthesized attributes for everything (avoid inherited)?
A: Some semantic tasks need top-down context: type information passed to declarations, scope depth for variables, expected result type for coercions. You can simulate inherited via extra passes or restructuring, but it's unnatural and less efficient.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Synthesized Attributes: Bottom-Up Attribute Computation in Compiler Design.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.
Search Terms
compiler-design, compiler design, compiler, design, syntax, directed, translation, synthesized
Related Compiler Design Topics