Syntax-directed translation in Compiler Design - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is syntax-directed translation?

Syntax-directed translation is a method used in compilers where the meaning of a program is determined by attaching rules to the grammar of the language. These rules guide how to translate or process the source code based on its structure.

beginner

What are semantic rules in syntax-directed translation?

Semantic rules are instructions attached to grammar rules that specify how to compute values or perform actions during translation. They help convert the syntax into meaningful output like intermediate code or machine code.

intermediate

Explain the difference between synthesized and inherited attributes.

Synthesized attributes are computed from the attributes of child nodes and passed up the parse tree. Inherited attributes are passed down or across the parse tree from parent or sibling nodes to provide context.

intermediate

How does a syntax-directed translation scheme relate to a context-free grammar?

A syntax-directed translation scheme extends a context-free grammar by adding semantic rules to each production. This allows the grammar to not only describe the structure but also how to translate or interpret the code.

beginner

Why is syntax-directed translation important in compiler design?

It provides a systematic way to translate source code into intermediate or target code by combining syntax analysis with semantic processing. This helps ensure the program is correctly understood and translated.

What does a semantic rule in syntax-directed translation do?

A Specifies how to compute values during translation

B Defines the syntax of the language

C Checks for spelling errors

D Formats the output code

Semantic rules guide how to compute values or perform actions based on the syntax structure.

Which attribute type is passed from child nodes to parent nodes?

A Dynamic attribute

B Inherited attribute

C Static attribute

D Synthesized attribute

Synthesized attributes are computed from child nodes and passed up the parse tree.

Syntax-directed translation schemes are built on top of which grammar type?

A Regular grammar

B Context-sensitive grammar

C Context-free grammar

D Unrestricted grammar

Syntax-directed translation schemes extend context-free grammars by adding semantic rules.

Inherited attributes are typically passed from:

A Parent or sibling nodes to child nodes

B Child nodes to parent nodes

C Only from sibling nodes

D Only from leaf nodes

Inherited attributes provide context by passing information from parents or siblings down or across the parse tree.

What is the main goal of syntax-directed translation in compilers?

A To check for syntax errors only

B To translate source code into meaningful intermediate or target code

C To optimize the hardware

D To design user interfaces

Syntax-directed translation helps convert source code into intermediate or target code by combining syntax and semantic analysis.

Describe how semantic rules work in syntax-directed translation and their role in compiler design.

Think about how meaning is assigned to syntax.

Explain the difference between synthesized and inherited attributes with examples.

Consider how information moves up or down the parse tree.

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