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

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding Attributes in Syntax-directed Definitions

In syntax-directed definitions, what is the primary role of attributes associated with grammar symbols?

A To optimize the parsing algorithm for faster execution

B To define the syntax rules for the language

C To specify the lexical tokens recognized by the scanner

D To store semantic information related to the symbols during parsing

💡 Hint

Think about what extra information is needed beyond just the structure of the language.

Attributes hold semantic information such as values or types that are computed during parsing to help understand the meaning of the input.

📋 Factual

intermediate

Types of Attributes in Syntax-directed Definitions

Which of the following correctly describes the difference between synthesized and inherited attributes?

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

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

C Both synthesized and inherited attributes are computed only from sibling nodes

D Synthesized attributes are used only in lexical analysis; inherited attributes are used only in syntax analysis

💡 Hint

Consider the direction of information flow in the parse tree.

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

🔍 Analysis

advanced

Evaluating Attribute Grammar Evaluation Order

Given a syntax-directed definition with both synthesized and inherited attributes, which condition ensures that attribute evaluation can be done in a single bottom-up pass?

A All attributes are inherited, so evaluation proceeds from root to leaves without dependency conflicts

B Synthesized and inherited attributes alternate at each level, allowing parallel evaluation

C All attributes are synthesized, so evaluation proceeds from leaves to root without dependency conflicts

D Attributes are cyclically dependent, requiring multiple passes

💡 Hint

Think about which attribute type naturally fits bottom-up evaluation.

If all attributes are synthesized, they can be computed during a bottom-up traversal without needing information from parents, enabling a single pass.

❓ Comparison

advanced

Distinguishing Between S-Attributed and L-Attributed Definitions

Which statement correctly distinguishes S-attributed definitions from L-attributed definitions in syntax-directed definitions?

A S-attributed definitions use only synthesized attributes; L-attributed definitions allow inherited attributes but with restrictions to enable left-to-right evaluation

B S-attributed definitions allow both synthesized and inherited attributes; L-attributed definitions allow only synthesized attributes

C S-attributed definitions are used only in bottom-up parsers; L-attributed definitions are used only in top-down parsers

D S-attributed definitions require multiple passes; L-attributed definitions require a single pass

💡 Hint

Focus on attribute types and evaluation order constraints.

S-attributed definitions have only synthesized attributes, making them easy to evaluate bottom-up. L-attributed definitions allow inherited attributes but restrict their use so evaluation can proceed in a single left-to-right pass.

❓ Reasoning

expert

Identifying Semantic Errors Using Syntax-directed Definitions

Consider a syntax-directed definition designed to check type consistency in expressions. If the attribute rules fail to detect a type mismatch in an expression like a + true, what is the most likely cause?

A The grammar does not allow boolean literals like <code>true</code>

B The semantic rules do not include type checking logic for the '+' operator

C The inherited attributes are incorrectly passed from parent to child nodes

D The synthesized attributes are computed before the inherited attributes

💡 Hint

Think about what part of the semantic rules enforces type correctness.

If the semantic rules lack checks for operator operand types, type mismatches like adding a boolean to a variable will not be detected.

Practice

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

easy

A. To associate computations with grammar rules using attributes

B. To optimize machine code after compilation

C. To manage memory allocation during program execution

D. To handle user input and output operations

Solution

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

   They link grammar rules to computations by associating attributes with grammar symbols.

2. Step 2: Identify the correct purpose

   This linking helps in semantic analysis and translation during compilation.

3. Final Answer:

   To associate computations with grammar rules using attributes -> Option A

4. Quick Check:

   Syntax-directed definitions = associate computations with grammar rules [OK]

Hint: Remember: syntax-directed means linking syntax to actions [OK]

Common Mistakes:

• Confusing syntax-directed definitions with code optimization
• Thinking they handle runtime memory management
• Assuming they manage input/output operations

2. Which of the following is the correct syntax to define an attribute in a syntax-directed definition?

easy

A. A.attr = B.attr + 1

B. attr A = B + 1

C. A := B + 1

D. define A.attr as B + 1

Solution

1. Step 1: Recall attribute assignment syntax

   Attributes are assigned using dot notation like A.attr = ....

2. Step 2: Match correct syntax

   A.attr = B.attr + 1 uses the correct form: A.attr = B.attr + 1.

3. Final Answer:

   A.attr = B.attr + 1 -> Option A

4. Quick Check:

   Attribute assignment uses dot and equals sign [OK]

Hint: Look for dot notation and equals sign for attributes [OK]

Common Mistakes:

• Using := instead of = for attribute assignment
• Writing attribute declarations like variables
• Using keywords like 'define' incorrectly

3. Given the syntax-directed definition:

S -> A B
A.val = 2
B.val = 3
S.val = A.val + B.val

What is the value of S.val after evaluation?

medium

A. Error

B. 6

C. 23

D. 5

Solution

1. Step 1: Identify attribute values for A and B

   A.val is 2 and B.val is 3 as given.

2. Step 2: Calculate S.val using the rule

   S.val = A.val + B.val = 2 + 3 = 5.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   S.val = 2 + 3 = 5 [OK]

Hint: Add attribute values as per rules to find result [OK]

Common Mistakes:

• Concatenating numbers as strings (23 instead of 5)
• Mixing up attribute names
• Assuming syntax error without checking values

4. Consider this syntax-directed definition snippet:

E -> E1 + T
E.val = E1.val + T.val
E1.val = 5
T.val = 7

What is the error in this definition?

medium

A. The rule causes infinite recursion

B. No error; the definition is correct

C. Attributes are assigned in the wrong order

D. Attribute E1.val is used before being defined

Solution

1. Step 1: Check attribute usage and definitions

   E1.val and T.val are both defined before use in E.val.

2. Step 2: Verify rule correctness

   The rule correctly sums E1.val and T.val to get E.val without recursion or order issues.

3. Final Answer:

   No error; the definition is correct -> Option B

4. Quick Check:

   Attributes defined before use, no recursion [OK]

Hint: Check if all attributes are defined before use [OK]

Common Mistakes:

• Assuming recursion error without context
• Thinking attribute order matters if dependencies are clear
• Confusing attribute names

5. You want to compute the value of an arithmetic expression using syntax-directed definitions. The grammar is:

Expr -> Expr1 '+' Term
Expr.val = Expr1.val + Term.val
Expr -> Term
Expr.val = Term.val
Term -> 'num'
Term.val = num.value

Given the input expression 3 + 4 + 5, how should the attributes be evaluated to get the correct total?

hard

A. Use inherited attributes to pass partial sums from left to right

B. Use semantic actions to print values without computing sum

C. Use synthesized attributes only, evaluating bottom-up

D. Use attributes to store tokens but not compute values

Solution

1. Step 1: Understand attribute types in the grammar

   The grammar uses synthesized attributes (Expr.val, Term.val) computed bottom-up.

2. Step 2: Evaluate expression bottom-up

   Each Term.val is the number's value; Expr.val sums left Expr1.val and Term.val recursively.

3. Step 3: Confirm correct evaluation method

   Using synthesized attributes bottom-up correctly computes 3 + 4 + 5 = 12.

4. Final Answer:

   Use synthesized attributes only, evaluating bottom-up -> Option C

5. Quick Check:

   Synthesized attributes compute values bottom-up [OK]

Hint: Use synthesized attributes to compute expression values bottom-up [OK]

Common Mistakes:

• Confusing inherited and synthesized attributes
• Trying to pass partial sums left to right incorrectly
• Ignoring attribute evaluation order