Syntax-Directed Translation: SDDs, Attributes, and Code Generation

Core Concepts

1. Syntax-Directed Definitions (SDDs)

An SDD is a grammar augmented with semantic rules that define how to compute attributes (e.g., types, values, or intermediate code) during parsing. It consists of:

• A context-free grammar (CFG) defining syntax.
• Semantic rules tied to grammar productions, often written as:

  <non-terminal> → <production> { semantic action }
  

  Example:

  E → E₁ + E₂ { $$ = E₁.val + E₂.val }  // $$ = left-hand-side attribute
  

Why SDDs?

• Separation of concerns: Syntax (grammar) and semantics (actions) are distinct.
• Early error detection: Type checking, scope resolution, or code generation happens during parsing.
• Efficiency: Avoids separate passes for translation.

2. Attributes and Attribute Grammars

Attributes are properties of grammar symbols (terminals/non-terminals) that carry meaning (e.g., type, value, address). There are two types:

Example Grammar with Attributes:

E → id { $$ = id.lexeme }          // Synthesized: $$ = id’s value
  | E₁ + E₂ { $$ = E₁.val + E₂.val } // Synthesized
S → if (E) then S₁ else S₂ { }     // Inherited: E must be boolean

In the Real World

1. eSewa Transaction Validation

   • Idea Used: Type checking via SDDs
   • How: When you pay a bill, eSewa’s compiler-like system checks if the amount (a numeric attribute) matches the service_type (e.g., electricity, phone). If the grammar rule for Payment requires amount.type = numeric and service_type.type = string, a mismatched type (e.g., entering "abc" for amount) triggers an error before processing.

2. Daraz Order Processing Queue

   • Idea Used: Inherited attributes for state tracking
   • How: Daraz’s backend uses SDDs to track order status. The grammar rule for Order might inherit status (e.g., "processing", "shipped") from parent nodes like Payment or Shipping. If Payment.status = "failed", the inherited attribute forces Order.status to "cancelled" without further checks.

3. Khalti Loan Interest Calculation

   • Idea Used: Synthesized attributes for arithmetic
   • How: When you apply for a loan, Khalti’s system computes total_payable = principal + (principal * rate * time). This is a synthesized attribute in the grammar rule for Loan, where = E₁.val + (E₂.val * E₃.val * E₄.val).

3. Syntax Trees and Annotated Parse Trees

A syntax tree represents the hierarchical structure of a program. Annotated parse trees add semantic information (attributes) to nodes.

Example: Translate A = B + C * D into 3-address code (3AC) using SDDs.

Grammar:
E → E₁ + E₂ { t = newTemp(); emit(t = E₁.val + E₂.val); $$ = t }
  | E₁ * E₂ { t = newTemp(); emit(t = E₁.val * E₂.val); $$ = t }
  | id { $$ = id.lexeme }

Steps:

1. Parse A = B + C * D → Tree:

   A = +
     /   \
    B     *
       /   \
      C     D
   

2. Annotate with semantic rules:
   • C * D → t1 = C * D
   • B + t1 → t2 = B + t1
   • Final: A = t2
3. 3AC Output:

   t1 = C * D
   t2 = B + t1
   A = t2
   

4. Three-Address Code (3AC) and Intermediate Representations

3AC is a low-level, easy-to-generate intermediate form where each instruction has at most one operator and three addresses (e.g., t1 = A + B). Other forms:

Example: Convert A = (B + C) - (D - E) to Quadruple and DAG.

Quadruple Form:
1. t1 = B + C
2. t2 = D - E
3. A = t1 - t2

DAG Advantage: If (B + C) is reused, the DAG avoids recomputing it.

5. L-Attributed and S-Attributed Definitions

Example L-Attributed Grammar for if Statements:

S → if (E) S₁ else S₂ {
      if (E.type != bool) error("Condition must be boolean");
      E.type = bool; // Inherited to E
    }

6. Backpatching for Control Flow

Backpatching is used to generate code for if, while, and goto by:

1. Emitting jump instructions to placeholder labels.
2. Filling labels later when control flow is resolved.

Example: Translate if (A > B) x = 1 else x = 0 to 3AC.

Grammar:
S → if (E) S₁ else S₂ {
      nextquad = quad.length + 1;
      emit(if E.val goto L1);
      emit(x = 0; goto L2);
      emit(L1: x = 1);
      emit(L2: );
    }

3AC Output:

1. if A > B goto 4
2. x = 0; goto 5
3. L1:
4. x = 1
5. L2:

Exam Tip

1. SDD Questions:

   • Always annotate the parse tree with semantic rules. Show how attributes propagate.
   • For type checking, explicitly state inherited/synthesized attributes and error conditions.

2. 3AC/DAG Questions:

   • Draw the syntax tree first, then derive 3AC step-by-step.
   • For DAGs, highlight shared subexpressions and explain optimizations.

3. Backpatching:

   • Show placeholder jumps and label filling in your trace.
   • Example: For while (E) S, emit goto L1 at the start, then backpatch S’s end to L1.

4. Common Pitfalls:

   • Forgetting to initialize temporary variables in 3AC.
   • Misplacing inherited attributes (e.g., E.type must be checked before S is processed).
   • Not handling operator precedence in arithmetic expressions (use grammar rules that enforce precedence).

Worked Example: Full Translation Trace

Input: if (a < b && c > d || e == f) x = 1; else x = 0; Grammar:

E → E₁ relop E₂ { $$ = E₁.val relop E₂.val }
  | E₁ && E₂ { t = newTemp(); emit(t = E₁.val && E₂.val); $$ = t }
  | E₁ || E₂ { t = newTemp(); emit(t = E₁.val || E₂.val); $$ = t }
S → if (E) S₁ else S₂ { backpatch(E, S₁, S₂) }

Steps:

1. Parse a < b && c > d || e == f:
   • a < b → t1 = a < b
   • t1 && c > d → t2 = t1 && (c > d)
   • t2 || e == f → t3 = t2 || (e == f)
2. Backpatch for if:
   • Emit if t3 goto L1
   • Emit x = 0; goto L2
   • Emit L1: x = 1
   • Emit L2:

Final 3AC:

1. t1 = a < b
2. t4 = c > d
3. t2 = t1 && t4
4. t5 = e == f
5. t3 = t2 || t5
6. if t3 goto 10
7. x = 0; goto 11
8. L1:
9. x = 1
10. L2:
11.

Comparison Table: Intermediate Code Forms

Key Algorithms

Algorithm: Backpatching for while Loops

Code Example (Pseudocode):

def backpatch_while(E, S):
    nextquad = quad.length + 1
    emit("goto L1")  # Start of loop
    emit(E)          # Condition
    emit("if false goto L2")  # Exit if false
    emit(S)          # Body
    emit("goto L1")  # Loop back
    emit("L2:")      # End

Trace for while (x > 0) x = x - 1:

Visual: Syntax Tree for A = B + C * D

graph TD
    A["A ="] --> B["+"]
    B --> C["B"]
    B --> D["*"]
    D --> E["C"]
    D --> F["D"]

Annotated with 3AC:

Visual: Stack During Expression Evaluation

For A = B + C * D (postfix evaluation):