CD Notes
Deep dive into inherited attributes: computation semantics, parent-to-child propagation, L-attributed grammars, evaluation algorithms, practical uses in type checking and code generation with examples.
Definition
An inherited attribute of a grammar symbol is an attribute computed from the symbol's parent node and siblings in the parse tree. Inherited attributes flow downward (top-down) from parent to child.
Key Properties
L-Attributed Grammars
An L-attributed grammar permits both synthesized and inherited attributes with one restriction:
Example: L-Attributed Grammar
| Production: E | E₁ + T { |
| E.val | = E₁.val + T.val |
| T.expected_type | = E.expected_type |
Practical Example: Type Propagation
Grammar with Inherited Attributes
Declaration Grammar
Program → Decl* {
Program.scope := new GlobalScope()
Decl.scope := Program.scope
}
Decl → id : Type {
addToSymbolTable(id, Type.type, Decl.scope)
}
Type → int {Type.type := "int"}
| array [ num ] of Type' {
Type.type := ArrayType(num, Type'.type)
Type'.expected_size := compute_size(num)
}
Inherited attributes
- Decl.scope: passes scope down
- Type'.expected_size: passes expected size to inner type
Evaluation Algorithms
Algorithm: Depth-First Top-Down Traversal
Example Execution
Grammar
Program → Decl*
Decl → id : Type
Parse: int x; real y;
Execution order
1. Program: inherited = {}
2. Decl₁ (int x): inherited = {scope: global}
3. Type: inherited = {scope: global}
- Type.type := "int"
4. Back to Decl₁: addToSymbolTable(x, int)
5. Decl₂ (real y): inherited = {scope: global, sym_table: updated}
6. Type: inherited = {scope: global}
- Type.type := "real"
7. Back to Decl₂: addToSymbolTable(y, real)
Implementation with LL(1) Parsers
Recursive Descent with Inherited Attributes
def parse_E(expected_type):
"""Expected_type is inherited attribute"""
e1_val = parse_E_with_expected(expected_type)
if lookahead == '+':
advance()
# T inherits same expected type
t_val = parse_T_with_expected(expected_type)
# Verify types match
if type(e1_val) != type(t_val):
error("Type mismatch")
result_val = e1_val + t_val
else:
result_val = e1_val
return result_val
def parse_T_with_expected(expected):
"""T receives expected type from caller"""
return parse_Factor_with_expected(expected)Practical Applications
Application 1: Type Inference with Context
Grammar
Expr → id { assumed_type: Type }
{
var_type = symbolTable[id].type
if assumed_type != var_type:
error("Type mismatch")
Expr.type := "error"
else:
Expr.type := var_type
}
Usage
Assignment: Var := Expr (assumed_type: Var's type)
Array access: A[i] (assumed_type: int)
Application 2: Code Generation with Context
Grammar
Statement → for id in Expr do Block
{ assumed_collection_type: inherited from scope
Expr.assumed_type := ArrayType(inherited.element_type)
Block.loop_depth := inherited.loop_depth + 1
}
Semantic action
- Generate loop entry code
- Generate loop body (with new loop depth)
- Generate loop exit code
Application 3: Scope Management
| Block | { Decl* Stmt* } |
| { current_scope | inherited |
| new_scope | = new Scope(parent: current_scope) |
| Decl*.scope | = new_scope |
| Stmt*.scope | = new_scope |
Comparison: Inherited vs Synthesized
| Aspect | Inherited | Synthesized |
|---|---|---|
| Flow direction | Downward (parent→child) | Upward (child→parent) |
| Grammar class | L-attributed (restricted) | S-attributed |
| Evaluation | Top-down (like LL) | Bottom-up (like LR) |
| Use case | Context propagation | Translation/computation |
| Parser compatibility | LL(1) natural | LR(1) natural |
Error Handling with Inherited Attributes
def parse_E_with_expected(expected_type):
try:
result = parse_T_with_expected(expected_type)
except TypeError as e:
# Error in child - inherit error status
return ErrorNode(expected_type, str(e))
# Propagate errors upward
if isinstance(result, ErrorNode):
return ErrorNode(expected_type, result.error_msg)
return resultQuick Revision Notes
- Inherited attribute: Value computed from parent and left siblings
- L-attributed grammar: Inherited can depend on parent and left only
- Evaluation: Top-down, breadth-first pass (process parent before children)
- Typical use: Context propagation (scope, type, depth, flags)
- LL(1) natural fit: Predictive parser naturally evaluates top-down
- Combines with synthesized: Many practical grammars use both types
- Order restriction: Right siblings not available when computing inherited
Interview Q&A
Q1: What types of information typically flow as inherited attributes?
A: Context information: scope/symbol table, type expectations, loop depth, declaration context, expression context, namespace, visibility rules. Anything determined by parent and siblings that children need to know.
Q2: Why can't inherited attributes depend on right siblings?
A: In top-down evaluation, right siblings haven't been processed yet. You don't know their attributes. Allowing this would require: 1) Multiple passes, or 2) Speculative values (risky), or 3) Restructuring grammar. L-attributed restriction keeps one-pass evaluation feasible.
Q3: How do inherited and synthesized attributes interact in L-attributed grammars?
A: Inherited attributes of a node may depend on synthesized attributes of its left siblings. This creates a left-to-right data flow. A node's synthesized attributes can be used by right siblings or parent, but not vice versa.
Q4: Can you simulate inherited attributes using only synthesized?
A: Yes, but with extra passes or restructuring. Make parent pass data through children (threading). Or: compute both directions—one pass synthesized up, next pass inherited down. Less efficient but possible for any language.
Q5: What's the connection between inherited attributes and recursive descent?
A: Recursive descent naturally supports inherited attributes via procedure parameters. Pass inherited as parameters, return synthesized as return values. This makes LL(1) + inherited attributes very natural to implement.
Q6: Why are inherited attributes important for semantic analysis?
A: Many language semantics are context-dependent (type depends on declaration, variable meaning depends on scope). Inherited attributes elegantly express this context-dependent computation during a single tree traversal.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Inherited Attributes: Top-Down Attribute Computation for Context Transfer.
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, inherited
Related Compiler Design Topics