Define attribute grammar with example of inherited and synthesized attributes

Attribute grammars enhance context-free grammars by adding attributes (semantic properties) and semantic rules to process language constructs during parsing. They bridge syntax and semantics, enabling tasks like type checking and code generation.

---

Synthesized Attributes

Attributes computed from child nodes in the parse tree (bottom-up propagation).

Example: Arithmetic Expression Evaluation

Expr → Term Elist {Expr.val = Term.val + Elist.val}  
Term → Factor Tlist {Term.val = Factor.val * Tlist.val}  
Factor → num {Factor.val = num.val}

• val is synthesized:
  • Factor.val derives from num.val (leaf node).
  • Term.val combines Factor.val and Tlist.val.
  • Final Expr.val aggregates results upward.

For 3 + 4 * 2, the parse tree computes:

Factor(3) → Term(3) → Expr(3)  
Factor(4) → Term(4)  
Factor(2) → Term(2) → Term(4*2=8)  
Expr(3+8=11)

---

Inherited Attributes

Attributes derived from parent/sibling nodes (top-down or horizontal propagation).

Example: Variable Type Propagation

Decl → T L {L.type = T.type}  
T → int {T.type = int}  
L → id {id.type = L.type}

• L.type is inherited from T.type (parent node).
• id.type inherits from L.type.

For int x, y;:

1. T.type becomes int.
2. L.type inherits int from T.
3. x and y inherit int type via L.

---

Key Differences

Feature	Synthesized Attributes	Inherited Attributes
Direction	Bottom-up (children → parent)	Top-down (parent → children)
Use Case	Expression evaluation	Context-dependent rules (e.g., type checking)
Dependencies	Child attributes only	Parent/sibling attributes

---

Attribute grammars are foundational for semantic analysis, enabling compilers to validate type consistency, optimize code, and generate intermediate representations.