Ambiguity in grammars in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Identifying Ambiguity in a Grammar

Consider the grammar with rules:

S → aSb | ab

Is this grammar ambiguous?

A No, because each string generated has a unique parse tree.

B No, because the grammar only produces strings of length 2.

C Yes, because the grammar generates infinite strings.

D Yes, because the string 'aabb' can have two different parse trees.

💡 Hint

Try to draw parse trees for strings like 'ab' and 'aabb'.

This grammar generates strings with equal numbers of 'a's followed by equal numbers of 'b's. The string 'aabb' can be derived in more than one way, so the grammar is ambiguous.

📋 Factual

intermediate

Definition of Ambiguous Grammar

Which of the following best defines an ambiguous grammar?

A A grammar that cannot generate any string.

B A grammar that generates at least one string with multiple distinct parse trees.

C A grammar that generates only one string.

D A grammar that has no terminal symbols.

💡 Hint

Think about what ambiguity means in terms of parse trees.

An ambiguous grammar is one where at least one string can be generated in more than one way, resulting in multiple parse trees.

🔍 Analysis

advanced

Ambiguity in Expression Grammar

Given the grammar:

E → E + E | E * E | (E) | id

What is the main cause of ambiguity in this grammar?

A Lack of operator precedence and associativity rules.

B The use of parentheses in expressions.

C The presence of the terminal 'id'.

D The grammar does not generate any strings.

💡 Hint

Consider how expressions like 'id + id * id' can be parsed differently.

The grammar is ambiguous because it does not specify operator precedence or associativity, so expressions can be parsed in multiple ways.

❓ Comparison

advanced

Comparing Ambiguous and Unambiguous Grammars

Which statement correctly compares ambiguous and unambiguous grammars?

A Ambiguous grammars can generate strings with multiple parse trees; unambiguous grammars cannot.

B Unambiguous grammars generate no strings; ambiguous grammars generate all strings.

C Unambiguous grammars always have fewer production rules than ambiguous grammars.

D Ambiguous grammars always generate fewer strings than unambiguous grammars.

💡 Hint

Focus on the number of parse trees per string.

Ambiguous grammars allow multiple parse trees for some strings, while unambiguous grammars have exactly one parse tree per string.

❓ Reasoning

expert

Detecting Ambiguity in a Complex Grammar

Consider the grammar:

S → aSbS | bSaS | ε

Which of the following is true about this grammar?

A It is unambiguous because every string has a unique parse tree.

B It is ambiguous because it generates only the empty string.

C It is ambiguous because the string 'abab' can be derived in two different ways.

D It is unambiguous because it does not generate any strings.

💡 Hint

Try to find two different parse trees for the string 'abab'.

The grammar is ambiguous because the string 'abab' can be derived using different parse trees due to the recursive rules.

Practice

1. What does ambiguity in a grammar mean?

easy

A. A sentence can have more than one meaning

B. The grammar has no rules

C. All sentences are correct

D. The grammar is too simple

Solution

1. Step 1: Understand the definition of ambiguity in grammar

   Ambiguity means a sentence can be interpreted in multiple ways within the grammar.

2. Step 2: Compare options with the definition

   Only A sentence can have more than one meaning correctly states that ambiguity means multiple meanings for a sentence.

3. Final Answer:

   A sentence can have more than one meaning -> Option A

4. Quick Check:

   Ambiguity = Multiple meanings [OK]

Hint: Ambiguity means multiple meanings for one sentence [OK]

Common Mistakes:

• Confusing ambiguity with grammar errors
• Thinking ambiguity means no rules
• Assuming ambiguity means all sentences are correct

2. Which of the following grammar rules is ambiguous?

easy

A. S -> aSb | ab

B. S -> aS | b

C. S -> aSb | aSb

D. S -> ab | ba

Solution

1. Step 1: Analyze the grammar rules for ambiguity

   Rule A allows multiple parse trees for strings like 'aabb', causing ambiguity.

2. Step 2: Check other options for ambiguity

   Options B, C, and D do not produce multiple parse trees for the same string.

3. Final Answer:

   S -> aSb | aSb -> Option C

4. Quick Check:

   Multiple parse trees = Ambiguous [OK]

Hint: Look for rules generating multiple parse trees [OK]

Common Mistakes:

• Ignoring repeated rules that cause ambiguity
• Confusing ambiguity with grammar repetition
• Assuming all recursive rules are ambiguous

3. Given the grammar:
E -> E + E | E * E | id
What is the ambiguity in parsing the expression id + id * id?

medium

A. The expression cannot contain '*'

B. The expression is invalid

C. The expression has only one parse tree

D. The expression can be parsed as (id + id) * id or id + (id * id)

Solution

1. Step 1: Understand the grammar's ambiguity

   The grammar allows both '+' and '*' without precedence rules, causing multiple parse trees.

2. Step 2: Analyze the expression parsing

   The expression 'id + id * id' can be parsed as either 'id + (id * id)' or '(id + id) * id', showing ambiguity.

3. Final Answer:

   The expression can be parsed as (id + id) * id or id + (id * id) -> Option D

4. Quick Check:

   Multiple parse trees = Ambiguity [OK]

Hint: Check if operator precedence is missing [OK]

Common Mistakes:

• Assuming only one parse tree exists
• Ignoring operator precedence
• Thinking expression is invalid

4. Identify the error in this ambiguous grammar and suggest a fix:
S -> S + S | S * S | id

medium

A. Ambiguity due to missing operator precedence; fix by defining precedence rules

B. No error, grammar is unambiguous

C. Grammar is invalid syntax; fix by removing recursion

D. Ambiguity due to missing terminals; fix by adding more terminals

Solution

1. Step 1: Identify the cause of ambiguity

   The grammar allows multiple parse trees because it lacks operator precedence rules.

2. Step 2: Suggest a fix

   Define separate rules for '+' and '*' with precedence to remove ambiguity.

3. Final Answer:

   Ambiguity due to missing operator precedence; fix by defining precedence rules -> Option A

4. Quick Check:

   Missing precedence = Ambiguity fix [OK]

Hint: Add precedence rules to fix ambiguity [OK]

Common Mistakes:

• Thinking recursion causes ambiguity
• Assuming grammar syntax is invalid
• Ignoring operator precedence importance

5. How can ambiguity be resolved in a grammar that allows multiple parse trees for the same sentence?

hard

A. By allowing multiple parse trees

B. By rewriting the grammar to enforce operator precedence and associativity

C. By removing all terminals

D. By adding more recursive rules

Solution

1. Step 1: Understand the cause of ambiguity

   Ambiguity arises when the grammar allows multiple parse trees for the same sentence.

2. Step 2: Apply a solution

   Rewriting the grammar to include operator precedence and associativity rules removes ambiguity.

3. Final Answer:

   By rewriting the grammar to enforce operator precedence and associativity -> Option B

4. Quick Check:

   Rewrite grammar with precedence = Resolve ambiguity [OK]

Hint: Use precedence and associativity rules to fix ambiguity [OK]

Common Mistakes:

• Adding recursion increases ambiguity
• Removing terminals breaks grammar
• Accepting ambiguity as normal