Syntax-directed translation in Compiler Design - Step-by-Step Execution

Concept Flow - Syntax-directed translation

Start: Input Source Code

↓

Parse Input using Grammar

↓

At each Grammar Rule Match

↓

Apply Semantic Rules

↓

Generate Intermediate Code or Output

↓

End: Translated Output Ready

The process starts by parsing source code using grammar rules. When a rule matches, semantic actions run to produce translated output step-by-step.

Execution Sample

Compiler Design

E -> E + T { print('+') }
E -> T { print('num') }
T -> id { print('id') }

This shows grammar rules with semantic actions that print symbols during parsing to translate expressions.

Analysis Table

Step	Grammar Rule Matched	Semantic Action	Output Produced
1	T -> id	print('id')	id
2	E -> T	print('num')	num
3	T -> id	print('id')	id
4	E -> T	print('num')	num
5	E -> E + T	print('+')	+

💡 All grammar rules matched and semantic actions executed to produce translation output.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
Output Stream		id	idnum	idnumid	idnumidnum	idnumidnum+	idnumidnum+

Key Insights - 2 Insights

Why do semantic actions run only when a grammar rule matches?

Semantic actions are attached to grammar rules and run exactly when those rules match during parsing, as shown in execution_table steps where each matched rule triggers its action.

How does the output build up step-by-step?

The output stream grows by appending results of semantic actions at each step, visible in variable_tracker where output accumulates after each rule match.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what semantic action runs?

A print('num')

B print('id')

C print('+')

D No action

💡 Hint

Check the 'Semantic Action' column for Step 3 in execution_table.

At which step does the output first include a '+' symbol?

A Step 2

B Step 4

C Step 5

D Step 6

💡 Hint

Look at the 'Output Produced' column in execution_table for '+' symbol.

If the semantic action for E -> T changed to print('expr'), how would the output after Step 2 change?

A Output would be 'idexpr'

B Output would be 'exprid'

C Output would be 'expr'

D Output would remain 'idnum'

💡 Hint

Refer to variable_tracker and see how output accumulates after semantic actions.

Concept Snapshot

Syntax-directed translation uses grammar rules with attached semantic actions.
When a rule matches during parsing, its semantic action runs.
Actions produce translated output step-by-step.
This links syntax structure to translation output.
Common in compilers for code generation or analysis.

Full Transcript

Syntax-directed translation is a method used in compilers to translate source code by attaching semantic actions to grammar rules. When the parser matches a rule, it runs the corresponding semantic action to produce part of the translated output. This process continues step-by-step until the entire input is processed, building the final translation. The execution table shows each grammar rule matched, the semantic action executed, and the output produced at each step. The variable tracker shows how the output grows over time. Beginners often wonder why actions run only on rule matches and how output builds incrementally. The visual quiz tests understanding of these steps by asking about specific actions and output changes. Overall, syntax-directed translation connects the structure of code to its meaning or translation in a clear, stepwise way.

Practice

1. What is the main purpose of syntax-directed translation in compiler design?

easy

A. To manage memory allocation during runtime

B. To optimize machine code for faster execution

C. To check syntax errors in source code

D. To associate grammar rules with actions for translation

Solution

1. Step 1: Understand the role of syntax-directed translation

   It connects grammar rules with specific actions or computations to translate source code.

2. Step 2: Differentiate from other compiler tasks

   Unlike optimization or error checking, it focuses on translation based on syntax structure.

3. Final Answer:

   To associate grammar rules with actions for translation -> Option D

4. Quick Check:

   Syntax-directed translation = associate grammar with actions [OK]

Hint: Focus on linking grammar rules to translation actions [OK]

Common Mistakes:

• Confusing translation with optimization
• Thinking it only checks syntax errors
• Assuming it manages runtime memory

2. Which of the following is the correct way to write a semantic rule in syntax-directed translation for an expression E -> E1 + T that computes the value of E?

easy

A. val(E) = val(E1) * val(T)

B. E = E1 + T

C. E.val = E1.val + T.val

D. E.val = E1.val - T.val

Solution

1. Step 1: Identify the semantic rule for addition

   The rule should compute the value of E by adding values of E1 and T.

2. Step 2: Match the correct syntax for semantic rules

   Using E.val = E1.val + T.val correctly assigns the computed value.

3. Final Answer:

   E.val = E1.val + T.val -> Option C

4. Quick Check:

   Semantic rule for addition uses '+' operator [OK]

Hint: Semantic rules use attribute assignments like X.val = ... [OK]

Common Mistakes:

• Using assignment without '.val' attributes
• Using wrong operators like '*' or '-'
• Writing rules as expressions without assignment

3. Given the grammar rule and semantic actions:
E -> E1 + T { E.val = E1.val + T.val }
T -> digit { T.val = digit.lexval }
What is the value of E.val for input 3 + 5?

medium

A. 8

B. 35

C. Error

D. 0

Solution

1. Step 1: Evaluate terminal values

   For digits 3 and 5, digit.lexval gives 3 and 5 respectively.

2. Step 2: Apply semantic rule for addition

   Using E.val = E1.val + T.val, compute 3 + 5 = 8.

3. Final Answer:

   8 -> Option A

4. Quick Check:

   3 + 5 = 8 [OK]

Hint: Add digit values as per semantic rules [OK]

Common Mistakes:

• Concatenating digits as strings (35)
• Assuming syntax error without reason
• Returning zero without calculation

4. Identify the error in the following semantic rule for the grammar E -> E1 + T:
{ E.val = E1.val - T.val }

medium

A. Missing attribute assignment for E1

B. Wrong operator used; should be addition instead of subtraction

C. Semantic rule should be outside braces

D. No error; rule is correct

Solution

1. Step 1: Check grammar operation

   The grammar rule uses '+' operator, so semantic rule must reflect addition.

2. Step 2: Identify mismatch in semantic action

   The semantic rule uses '-', which contradicts the grammar's '+' operator.

3. Final Answer:

   Wrong operator used; should be addition instead of subtraction -> Option B

4. Quick Check:

   Operator in semantic rule must match grammar [OK]

Hint: Semantic operator must match grammar operator [OK]

Common Mistakes:

• Ignoring operator mismatch
• Thinking braces placement causes error
• Assuming missing attribute assignment

5. Consider a syntax-directed translation scheme that computes the value of arithmetic expressions with addition and multiplication:

E -> E1 + T { E.val = E1.val + T.val }
E -> T { E.val = T.val }
T -> T1 * F { T.val = T1.val * F.val }
T -> F { T.val = F.val }
F -> digit { F.val = digit.lexval }

What is the computed value of 2 + 3 * 4 using this scheme?

hard

A. 14

B. 20

C. 24

D. Error due to ambiguity

Solution

1. Step 1: Apply operator precedence in grammar

   Multiplication (T -> T1 * F) has higher precedence than addition (E -> E1 + T).

2. Step 2: Compute multiplication first

   Calculate 3 * 4 = 12, then add 2: 2 + 12 = 14.

3. Final Answer:

   14 -> Option A

4. Quick Check:

   Multiplication before addition = 14 [OK]

Hint: Multiply before adding as per grammar rules [OK]

Common Mistakes:

• Adding before multiplying (2+3=5, then 5*4=20)
• Multiplying all digits (2*3*4=24)
• Assuming ambiguity error