Syntax-Directed Translation: Semantic Rules, Attribute Grammars & Code Generation

Core Concepts

What is Syntax-Directed Translation?

Syntax-directed translation is the process of generating intermediate or target code while parsing the source program, guided by the grammar rules. Unlike pure parsing (which only checks syntax), translation attaches meaning to each grammar rule via semantic actions (code snippets) embedded in the grammar.

Key Idea: Grammar rules define both syntax and translation simultaneously.

1. Attribute Grammars: The Formalism Behind Translation

An attribute grammar extends a context-free grammar (CFG) by:

• Adding attributes to non-terminals (e.g., E.val for expression value).
• Defining semantic rules to compute attributes based on syntax.

Types of Attributes

Example: Arithmetic Expression Translation

Grammar Rule (with semantic actions):

E → T E'
E' → + T { print("+") } E' | ε
T → F T'
T' → * F { print("*") } T' | ε
F → ( E ) | id

Semantic Actions:

• + and * are printed as operators.
• Parentheses are handled by recursion.

Trace for id1 + id2 * id3:

1. Parse id1 → F.val = id1.
2. See + → print +, compute id1 + T.val.
3. Parse id2 * id3 → T.val = id2 * id3.
4. Final expression: id1 + id2 * id3.

MERMAID FLOWCHART:

flowchart TD
    A["Start: E → T E'"] --> B["Parse T: id1 → F.val = id1"]
    B --> C["Parse E': + → print('+')"]
    C --> D["Parse T: id2 * id3 → T.val = id2 * id3"]
    D --> E["Final: id1 + id2 * id3"]

2. Translation Schemes

L-Attributed Definitions

An attribute grammar is L-attributed if:

1. All synthesized attributes are computed from left-to-right.
2. Inherited attributes flow only left-to-right.

Why L-attributed?

• Works naturally with top-down parsers (e.g., recursive descent).
• Simplifies implementation (no backtracking for inherited attrs).

Example: Variable Declaration Translation

Grammar Rule:

D → type id { emit("var ", id, ": ", type) }

Trace for int x;:

1. type = "int", id = "x".
2. Emit: var x: int.

MERMAID FLOWCHART:

flowchart TD
    A["D → type id"] --> B["type = int"]
    B --> C["id = x"]
    C --> D["emit('var x: int')"]

3. Handling Control Structures

If-Else Translation

Grammar Rule:

S → if ( E ) S1 else S2 { emit("if (", E, ") { ", S1, " } else { ", S2, " }") }

Trace for if (x > 0) S1 else S2:

1. Parse E: x > 0 → E.val = "x > 0".
2. Emit:

   if (x > 0) { S1 } else { S2 }
   

4. Error Handling in Translation

Recovery Strategies

MERMAID FLOWCHART:

flowchart TD
    A["Parse error detected"] --> B["Check error type"]
    B --> C["Missing ';'?"]
    C -->|"Yes"| D["Insert ';'"]
    C -->|"No"| E["Mismatched paren?"]
    E -->|"Yes"| F["Skip to match"]
    E -->|"No"| G["Undeclared var?"]
    G -->|"Yes"| H["Replace with 0"]

In the Real World

1. Khalti (Nepal):

   • Idea Used: Syntax-directed translation for transaction validation.
   • How: When you enter Khalti.transfer("user1", 500), the compiler translates this into intermediate code that checks:
     • Account balance (user1.balance >= 500).
     • Transaction rules (e.g., no negative amounts).
     • The semantic action emits SQL like UPDATE accounts SET balance = balance - 500 WHERE id = "user1".

2. Daraz Order Processing:

   • Idea Used: Attribute grammars for order validation.
   • How: An order like order.addItem("Laptop", 50000, 1) is parsed and translated into:
     • Check stock (stock["Laptop"] >= 1).
     • Calculate total (total += 50000).
     • Emit database update: UPDATE inventory SET stock = stock - 1 WHERE product = "Laptop".

3. Ncell Billing System:

   • Idea Used: L-attributed grammars for call duration calculation.
   • How: A call log like call("01234567", 180) is translated to:
     • duration = 180 seconds.
     • cost = duration * rate.
     • Emit billing record: INSERT INTO bills (phone, duration, cost) VALUES ("01234567", 180, 300).

WORKED EXAMPLE: NTC Traffic Route Optimization Assume NTC’s traffic system uses a grammar to parse routes like: route.addStop("Kathmandu", "Lalitpur", "Bhaktapur"). The compiler translates this into:

1. Syntax Check: Ensure addStop has 3 args.
2. Semantic Action:

   stops = ["Kathmandu", "Lalitpur", "Bhaktapur"]
   emit("UPDATE routes SET path = ", stops, " WHERE id = current_route")
   

3. Output:

   UPDATE routes SET path = ["Kathmandu", "Lalitpur", "Bhaktapur"] WHERE id = 101
   

5. Code Generation vs. Intermediate Code

Exam Tip

What to Expect in TU/PU Exams:

1. Grammar Translation:

   • Given a grammar with semantic actions, write the output for a sample input (e.g., a + b * c).
   • Common Pitfall: Forgetting operator precedence in arithmetic expressions.

2. Attribute Grammar Questions:

   • Identify synthesized vs. inherited attributes in a given grammar.
   • Example Question: "For the grammar E → T E', where E'.op is inherited, classify the attributes."

3. Error Handling:

   • Trace recovery for missing tokens (e.g., ; or )).
   • Example: "How would you recover from if (x > 0 (missing ))?" Answer: Skip to the next ) or treat as if (x > 0) {}.

4. Code Generation:

   • Convert a simple statement (e.g., while (x > 0) x = x - 1) into intermediate/target code.
   • Tip: Use stack machines (e.g., PUSH x; PUSH 1; SUB) for intermediate code.

5. Comparison Tables:

   • Compare L-attributed vs. S-attributed grammars or intermediate vs. target code.
   • Memorize: L-attributed = left-to-right inherited attrs; S-attributed = any direction.

Final Checklist for Full Marks:

• Show attribute flow in diagrams (L-attributed arrows).
• Trace semantic actions step-by-step for given inputs.
• Link real-world examples (Khalti, Daraz) to grammar rules.
• Handle edge cases (missing tokens, undeclared vars).
• Differentiate intermediate vs. target code clearly.