Parser conflicts (shift-reduce, reduce-reduce) in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding Shift-Reduce Conflict

In parser design, what does a shift-reduce conflict mean?

A The parser has two different grammar rules that can reduce the same set of symbols, causing ambiguity.

B The parser cannot decide whether to shift the next input symbol onto the stack or to reduce the symbols on the stack using a grammar rule.

C The parser fails because the input string does not match any grammar rule.

D The parser shifts symbols indefinitely without ever reducing.

💡 Hint

Think about the parser's choice between reading more input or applying a rule.

A shift-reduce conflict occurs when the parser must choose between shifting the next input symbol onto the stack or reducing the current symbols on the stack using a grammar rule. This ambiguity causes the parser to be unsure about the next action.

🧠 Conceptual

intermediate

Identifying Reduce-Reduce Conflict

What best describes a reduce-reduce conflict in parsing?

A The parser cannot decide which of two possible grammar rules to use to reduce the symbols on the stack.

B The parser cannot decide whether to shift or reduce next.

C The parser reduces symbols but then immediately shifts the same symbols back.

D The parser encounters an unexpected symbol and stops parsing.

💡 Hint

Focus on the parser's choice between two reductions.

A reduce-reduce conflict happens when the parser has two different grammar rules that can both reduce the same symbols on the stack, making it unclear which rule to apply.

🔍 Analysis

advanced

Detecting Conflict Type from Grammar

Given the grammar rules below, what type of parser conflict is most likely to occur?

S → a A d
A → b
A → b c

A No conflict

B Reduce-reduce conflict

C Shift-reduce conflict

D Syntax error

💡 Hint

Consider what happens when the parser sees 'b' and then 'c' or 'd'.

The parser sees 'b' and must decide whether to shift 'c' (to match A → b c) or reduce A → b. This is a classic shift-reduce conflict.

❓ Comparison

advanced

Difference Between Shift-Reduce and Reduce-Reduce Conflicts

Which statement correctly compares shift-reduce and reduce-reduce conflicts?

A Shift-reduce conflicts are easier to fix than reduce-reduce conflicts because they never involve ambiguity.

B Shift-reduce conflicts occur only in top-down parsers; reduce-reduce conflicts occur only in bottom-up parsers.

C Shift-reduce conflicts always cause syntax errors; reduce-reduce conflicts do not affect parsing.

D Shift-reduce conflicts involve choosing between shifting or reducing; reduce-reduce conflicts involve choosing between two reductions.

💡 Hint

Think about the parser's decision points in each conflict type.

Shift-reduce conflicts happen when the parser must decide whether to shift or reduce next. Reduce-reduce conflicts happen when the parser must choose between two possible reductions. Both cause ambiguity but differ in the parser's choice.

❓ Reasoning

expert

Resolving a Shift-Reduce Conflict in a Parser

A parser generator reports a shift-reduce conflict on the input string "id + id * id" with the grammar below:

E → E + E
E → E * E
E → id

Which approach correctly resolves this conflict to ensure multiplication has higher precedence than addition?

A Modify the grammar to use separate non-terminals for addition and multiplication expressions, enforcing precedence explicitly.

B Remove the multiplication rule to avoid conflicts.

C Always choose to reduce before shifting to resolve the conflict.

D Ignore the conflict since the parser will eventually parse the input correctly.

💡 Hint

Think about how to represent operator precedence in grammar rules.

To resolve shift-reduce conflicts caused by operator precedence, the grammar should be rewritten to separate expressions by precedence levels. For example, defining separate rules for terms and factors ensures multiplication binds tighter than addition.

Practice

1.

What is a shift-reduce conflict in parser design?

easy

A. When the parser cannot decide whether to read more input or apply a grammar rule

B. When the parser cannot decide which token to read next

C. When the parser cannot decide between two different grammar rules to apply

D. When the parser fails to recognize any input token

Solution

1. Step 1: Understand shift and reduce actions

   In parsing, 'shift' means reading the next input token, and 'reduce' means applying a grammar rule to replace tokens with a non-terminal.

2. Step 2: Define shift-reduce conflict

   A shift-reduce conflict happens when the parser must choose between shifting (reading more input) or reducing (applying a rule) but cannot decide which is correct.

3. Final Answer:

   When the parser cannot decide whether to read more input or apply a grammar rule -> Option A

4. Quick Check:

   Shift-reduce conflict = choice between shift or reduce [OK]

Hint: Shift-reduce = choose between reading input or applying rule [OK]

Common Mistakes:

• Confusing shift-reduce with reduce-reduce conflict
• Thinking it is about token recognition
• Assuming it means parser failure

2.

Which of the following is a correct way to describe a reduce-reduce conflict?

easy

A. The parser cannot decide which of two grammar rules to apply at the same point

B. The parser cannot decide whether to shift or reduce

C. The parser cannot decide which token to shift next

D. The parser cannot decide how to tokenize the input

Solution

1. Step 1: Understand reduce actions

   Reduce means applying a grammar rule to replace a sequence of tokens with a non-terminal symbol.

2. Step 2: Define reduce-reduce conflict

   A reduce-reduce conflict occurs when the parser has two or more possible grammar rules to reduce by and cannot decide which one to apply.

3. Final Answer:

   The parser cannot decide which of two grammar rules to apply at the same point -> Option A

4. Quick Check:

   Reduce-reduce conflict = choice between two reductions [OK]

Hint: Reduce-reduce = conflict between two possible reductions [OK]

Common Mistakes:

• Mixing reduce-reduce with shift-reduce conflict
• Thinking it involves token shifting
• Confusing it with lexical analysis errors

3.

Consider a parser encountering the input tokens id + id * id. If the grammar causes a shift-reduce conflict at the * token, what is the typical parser action to resolve this conflict?

medium

A. Reject the input due to ambiguity

B. Reduce immediately before reading the * token

C. Shift the * token to read more input before reducing

D. Ignore the * token and continue

Solution

1. Step 1: Understand operator precedence in parsing

   Multiplication (*) has higher precedence than addition (+), so the parser should process id * id before adding.

2. Step 2: Resolve shift-reduce conflict by shifting

   At the * token, the parser shifts (reads) the * to handle multiplication first, delaying reduction of addition.

3. Final Answer:

   Shift the * token to read more input before reducing -> Option C

4. Quick Check:

   Shift to handle higher precedence operator first [OK]

Hint: Shift on higher precedence operator to avoid premature reduce [OK]

Common Mistakes:

• Reducing too early ignoring operator precedence
• Rejecting input unnecessarily
• Skipping tokens instead of shifting

4.

Given a grammar that causes a reduce-reduce conflict, what is a common way to fix this issue?

medium

A. Add more tokens to the input stream

B. Rewrite the grammar to remove ambiguity between rules

C. Ignore one of the conflicting rules during parsing

D. Increase the parser's stack size

Solution

1. Step 1: Identify cause of reduce-reduce conflict

   Reduce-reduce conflicts arise from ambiguous grammar where two rules can apply at the same point.

2. Step 2: Fix by rewriting grammar

   To fix, rewrite or refactor the grammar to remove ambiguity so only one rule applies at a time.

3. Final Answer:

   Rewrite the grammar to remove ambiguity between rules -> Option B

4. Quick Check:

   Remove ambiguity to fix reduce-reduce conflict [OK]

Hint: Fix reduce-reduce by rewriting ambiguous grammar [OK]

Common Mistakes:

• Trying to fix by adding tokens
• Ignoring conflicting rules without fixing grammar
• Changing parser stack size which doesn't help

5.

You have a grammar with the following rules:
S -> A a | B a
A -> x
B -> x
Why does this grammar cause a reduce-reduce conflict when parsing input x a?

hard

A. Because S has no valid productions

B. Because the parser cannot decide whether to shift a or reduce x

C. Because a is missing from the input

D. Because both A and B can reduce x, causing ambiguity

Solution

1. Step 1: Analyze the grammar rules

   Both A and B produce the same token x. So when the parser sees x, it can reduce it to either A or B.

2. Step 2: Identify reduce-reduce conflict

   At the point of reducing x, the parser cannot decide which rule to apply, causing a reduce-reduce conflict.

3. Final Answer:

   Because both A and B can reduce x, causing ambiguity -> Option D

4. Quick Check:

   Same input reduces to two rules = reduce-reduce conflict [OK]

Hint: Same input reduces to multiple rules causes reduce-reduce conflict [OK]

Common Mistakes:

• Confusing shift-reduce with reduce-reduce conflict
• Thinking input is missing tokens
• Assuming no valid productions exist