Syntax-directed translation in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

What is the primary role of syntax-directed translation in a compiler?

Consider the process of compiling a program. What is the main purpose of syntax-directed translation?

A To optimize the machine code generated by the compiler

B To manage memory allocation during program execution

C To parse the source code and detect syntax errors only

D To associate semantic actions with grammar rules to produce intermediate code or perform semantic checks

💡 Hint

Think about how semantic meaning is attached to the structure of the source code.

Syntax-directed translation uses grammar rules with attached semantic actions to translate source code into intermediate forms or to perform semantic checks. It is not about optimization, parsing alone, or runtime memory management.

📋 Factual

intermediate

Which component typically executes semantic actions in syntax-directed translation?

In syntax-directed translation, which part of the compiler is responsible for executing the semantic actions attached to grammar rules?

A Symbol table manager

B Lexical analyzer

C Syntax analyzer (parser)

D Code generator

💡 Hint

Semantic actions are usually triggered during the parsing process.

The syntax analyzer or parser executes semantic actions as it recognizes grammar productions. The lexical analyzer handles tokens, the code generator produces machine code later, and the symbol table manager stores information but does not execute semantic actions.

🔍 Analysis

advanced

What is the output of this syntax-directed translation snippet?

Given the grammar rule and semantic action below, what will be the value of val after parsing the input 3 + 4?

Compiler Design

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

Input tokens: 3 + 4

A 7

B 34

C Syntax error

D Undefined value

💡 Hint

Consider how the semantic action computes the value by adding the values of subexpressions.

The semantic action adds the values of E1 and T. Since E1.val is 3 and T.val is 4, the result is 7.

❓ Comparison

advanced

How do synthesized attributes differ from inherited attributes in syntax-directed translation?

Compare synthesized and inherited attributes in the context of syntax-directed translation.

A Synthesized attributes are computed from children nodes up to the parent; inherited attributes are passed from parent to children

B Synthesized attributes are passed from parent to children; inherited attributes are computed from children to parent

C Both are computed only at the leaves of the parse tree

D Synthesized attributes are used only for error detection; inherited attributes are used for code generation

💡 Hint

Think about the direction of information flow in the parse tree.

Synthesized attributes flow upward from children to parent nodes, while inherited attributes flow downward or sideways from parent or siblings to children nodes.

❓ Reasoning

expert

Why might a syntax-directed translation scheme with only synthesized attributes be easier to implement than one with inherited attributes?

Consider the complexity of implementing syntax-directed translation schemes. Why is a scheme using only synthesized attributes generally simpler to implement than one that also uses inherited attributes?

A Because inherited attributes require no semantic rules, making them harder to track

B Because synthesized attributes can be evaluated in a single bottom-up traversal of the parse tree, while inherited attributes may require multiple passes or more complex evaluation orders

C Because synthesized attributes do not depend on grammar rules, while inherited attributes do

D Because inherited attributes are only used in lexical analysis, not in syntax-directed translation

💡 Hint

Think about how attribute values propagate in the parse tree and how that affects evaluation order.

Synthesized attributes flow upward and can be computed during a bottom-up parse in one pass. Inherited attributes flow downward or sideways, often requiring more complex evaluation strategies or multiple passes.

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