Attributes & Inheritance in Syntax-Directed Definitions

TAKEAWAYS:

• Attributes in syntax-directed definitions carry semantic information (e.g., types, values) during parsing, linking grammar rules to code generation.
• Synthesized attributes flow bottom-up (child→parent), while inherited attributes flow top-down (parent→child) in parse trees.
• L-attributed definitions restrict attribute dependencies to leftmost derivations, simplifying compiler implementation (e.g., used in GCC’s front-end).
• DAGs optimize intermediate code by eliminating redundant computations (e.g., A = B + C; D = B + C becomes a shared subtree).
• Type checking (static/dynamic) relies on inherited attributes to validate expressions (e.g., ensuring int + string fails in C++).
• Annotated parse trees visually represent attribute propagation, crucial for debugging and optimization phases.

---

1. Syntax-Directed Definitions (SDDs) and Attributes

Syntax-directed definitions extend context-free grammars (CFGs) by associating attributes (semantic values) with grammar symbols. These attributes enable translation (e.g., code generation) during parsing.

Key Concepts

• Attribute Grammar: A CFG augmented with:
  • Attributes: Variables tied to grammar symbols (terminals/non-terminals).
  • Semantic Rules: Equations defining how attributes compute from others.
• Parse Tree Annotations: Attributes are annotated on nodes (e.g., id.type = "int").

Example: Expression Evaluation

Consider the grammar for arithmetic expressions:

E → E₁ + T | T
T → T * F | F
F → (E) | id

Attributes:

• Synthesized (syn): Values computed and passed up (e.g., E.val).
• Inherited (inh): Values passed down (e.g., E.type for type checking).

Semantic Rules:

E.val = E₁.val + T.val   (if E → E₁ + T)
T.val = T₁.val * F.val   (if T → T₁ * F)
F.val = id.value         (if F → id)
E.type = E₁.type = T.type (inherited for type checking)

---

2. Synthesized vs. Inherited Attributes

Visual: Attribute Propagation in a Parse Tree

For the expression (5*3+2)*5:

Annotations:

• Synthesized: id.val → F.val → E.val.
• Inherited: E.type (e.g., int) passed to all children.

---

3. L-Attributed Definitions

Definition: A subset of attribute grammars where:

1. Inherited attributes of a non-terminal depend only on its ancestors (not siblings).
2. Synthesized attributes depend only on the left siblings and children.

Why? Simplifies parsing (e.g., left-to-right traversal).

Example: L-Attributed Grammar for if Statements

Grammar:

S → if E then S₁ else S₂

Attributes:

• E.type (inherited): Must be bool.
• S₁.type, S₂.type (synthesized): Types of statements.

Semantic Rules:

E.type = bool          (inherited)
S₁.type = S₁.type      (synthesized)
S₂.type = S₂.type      (synthesized)

Constraint: E.type must be checked before evaluating S₁/S₂.

---

4. Directed Acyclic Graphs (DAGs) for Optimization

Problem: Redundant subexpressions in parse trees waste space/time. Solution: DAGs share common subtrees (e.g., A = B + C; D = B + C → single B + C node).

Example: Expression A = (B + C) – (D – E)

1. Parse Tree:
2. DAG:

• Shared subtrees: B + C and D – E are unique nodes.

Intermediate Code (3AC):

---

5. Type Checking with Attributes

Static Type Checking (compile-time) uses inherited attributes to validate types. Dynamic Type Checking (run-time) defers checks (e.g., Python’s int + str).

Example: Type Error Detection

Grammar:

E → E₁ + T | T
T → id

Rule:

E.type = E₁.type = T.type (must be same)

Input: x + "hello" (where x is int). Error: E.type mismatch (int vs. string).

---

6. Real-World Applications

In the Real World

1. eSewa (Nepal):

   • Inherited Attributes: Validate transaction types (e.g., payment.type = "electricity").
   • Synthesized Attributes: Compute total bill (total = units * rate).

2. Java Compiler (javac):

   • L-Attributed Definitions: Check method return types (inherited) and local variable scopes (synthesized).

3. SQL Query Parsers:

   • DAGs: Optimize SELECT A, B FROM T WHERE A = B + 1 by reusing B + 1 subexpressions.

4. Pathao’s Ride Matching:

   • Inherited Attributes: Driver location (driver.location) passed to passenger matching logic.
   • Synthesized Attributes: Fare calculation (fare = distance * rate).

---

7. Worked Example: Annotated Parse Tree for (5*3+2)*5

Grammar:

E → E₁ + T | E₁ * T | (E) | id

Attributes:

• E.val, T.val: Synthesized.
• E.type: Inherited (int).

Steps:

1. Parse Tree:
2. Annotations:
   • J.val = 3, K.val = 5 → H.val = 15 (synthesized).
   • L.val = 2 → E.val = 17 (synthesized).
   • C.val = 5 → A.val = 85 (synthesized).
   • All type = int (inherited).

3AC Output:

t1 = 5 * 3
t2 = t1 + 2
t3 = t2 * 5

---

8. Code Example: Attribute Evaluation in Python

class Node:
    def __init__(self, val=None, left=None, right=None):
        self.val = val  # synthesized
        self.left = left
        self.right = right

def evaluate(node):
    if node.val is not None:  # leaf (id)
        return node.val
    if node.left and node.right:
        left_val = evaluate(node.left)
        right_val = evaluate(node.right)
        if node.val == '+':
            return left_val + right_val
        elif node.val == '*':
            return left_val * right_val

# Example: 5*3+2
tree = Node('+',
    Node('*',
        Node(val=5),
        Node(val=3)
    ),
    Node(val=2)
)
print(evaluate(tree))  # Output: 17

Trace Table:

---

Exam Tip

1. Define Clearly:

   • Attribute Grammar: CFG + attributes + semantic rules.
   • L-Attributed: Inherited attributes depend only on ancestors; synthesized only on left siblings/children.

2. Parse Tree Annotations:

   • Always show both synthesized and inherited attributes in diagrams.
   • Label arrows with attribute names (e.g., E.type → T.type).

3. DAGs vs. Parse Trees:

   • DAGs eliminate redundancy; parse trees are direct translations.
   • For (A+B)*C, DAG shares A+B; parse tree duplicates it.

4. Type Checking:

   • Static: Use inherited attributes (e.g., E.type).
   • Dynamic: Defer checks (e.g., Python’s +).

5. Common Pitfalls:

   • Forgetting to propagate inherited attributes to all children.
   • Misplacing synthesized attributes (e.g., computing E.val before children).

6. Exam Questions:

   • Construct annotated parse trees for given expressions (e.g., (5*3+2)*5).
   • Differentiate synthesized/inherited attributes with examples.
   • Optimize expressions using DAGs (show 3AC before/after).

---

Key Formula/Table: