Parser conflicts (shift-reduce, reduce-reduce) in Compiler Design - Step-by-Step Execution

Concept Flow - Parser conflicts (shift-reduce, reduce-reduce)

Input tokens

↓

Parser reads token

↓

Check parser state

↓

Shift action?

Yes→Push token to stack

↓

Continue parsing

↓

Reduce action?

Yes→Replace tokens by rule

↓

Continue parsing

↓

Conflict?

↓

Shift-Reduce

↓

Parser unsure to

↓

shift or reduce

↓

Parsing error or

↓

needs resolution

The parser reads tokens and decides to shift (read more) or reduce (apply grammar rules). Conflicts happen when it can't decide between shifting or reducing (shift-reduce) or between two reductions (reduce-reduce).

Execution Sample

Compiler Design

Grammar:
E -> E + E
E -> id
Input: id + id + id

Parsing input 'id + id + id' with grammar that can cause shift-reduce conflict.

Analysis Table

Step	Stack	Next Token	Action Options	Chosen Action	Reason
1	[]	id	Shift	Shift	No conflict, shift id onto stack
2	[id]	+	Reduce E->id or Shift +	Shift	Shift to read + for longer expression
3	[id, +]	id	Shift	Shift	No conflict, shift id
4	[id, +, id]	+	Reduce E->id or Shift +	Shift	Shift to read next +
5	[id, +, id, +]	id	Shift	Shift	No conflict, shift id
6	[id, +, id, +, id]	$	Reduce E->id or Shift $	Reduce	Reduce id to E
7	[id, +, id, +, E]	$	Reduce E->E+E or Shift $	Conflict: Shift-Reduce	Parser unsure to shift or reduce
8	[id, +, id, +, E]	$	Resolve conflict (e.g., prefer shift)	Shift	Shift chosen to continue parsing
9	[id, +, id, +, E, $]	$	Reduce E->E+E	Reduce	Reduce E+E to E
10	[id, +, E]	$	Reduce E->E+E	Reduce	Reduce E+E to E
11	[E]	$	Accept	Accept	Parsing complete
12	[E]	$	No more tokens	Stop	Parsing finished successfully

💡 Parsing stops after input fully processed and stack reduced to start symbol.

State Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	Final
Stack	[]	[id]	[id, +]	[id, +, id]	[id, +, id, +]	[id, +, id, +, id]	[id, +, id, +, E]	[id, +, id, +, E]	[id, +, id, +, E, $]	[id, +, E]	[E]	[E]
Next Token	id	+	id	+	id	$	$	$	$	$	$	none
Action	Shift	Shift	Shift	Shift	Shift	Reduce	Shift (conflict)	Shift	Reduce	Reduce	Accept	Stop

Key Insights - 3 Insights

Why does the parser sometimes hesitate between shifting and reducing?

Because the grammar allows both continuing to read more tokens (shift) or applying a rule now (reduce). This is shown in execution_table step 7 where both actions are possible.

What is a reduce-reduce conflict?

It happens when the parser can apply two different grammar rules to reduce at the same time and can't decide which one to pick. This example focuses on shift-reduce, but reduce-reduce is similar confusion.

How does the parser resolve conflicts?

Usually by predefined rules like preferring shift over reduce or by rewriting grammar. In the table at step 8, the parser chooses to shift to continue parsing.

Visual Quiz - 3 Questions

Look at the execution_table at step 7. What are the possible actions the parser can take?

A Shift or Reduce

B Only Shift

C Only Reduce

D Accept

💡 Hint

Check the 'Action Options' column at step 7 in execution_table.

At which step does the parser first reduce 'id' to 'E'?

A Step 4

B Step 6

C Step 8

D Step 10

💡 Hint

Look at the 'Chosen Action' column for when 'Reduce' first appears in execution_table.

If the parser always preferred reduce over shift at conflicts, what would happen at step 7?

A It would shift and continue parsing

B It would reduce immediately

C It would accept the input

D It would stop with error

💡 Hint

Refer to the 'Conflict: Shift-Reduce' explanation and what choosing reduce means.

Concept Snapshot

Parser reads tokens and decides to shift (read more) or reduce (apply grammar rules).
Shift-Reduce conflict: parser unsure to shift or reduce.
Reduce-Reduce conflict: parser unsure which reduce rule to apply.
Conflicts cause parsing errors unless resolved by grammar changes or parser rules.
Common resolution: prefer shift or rewrite grammar to avoid ambiguity.

Full Transcript

Parser conflicts occur when the parser cannot decide between two actions: shifting the next token onto the stack or reducing the current stack using a grammar rule. The two main types are shift-reduce conflicts, where the parser hesitates between shifting or reducing, and reduce-reduce conflicts, where it cannot choose between two possible reductions. In the example grammar with rules E -> E + E and E -> id, parsing the input 'id + id + id' shows a shift-reduce conflict at step 7. The parser can either shift the next token or reduce the current tokens. Usually, parsers resolve this by preferring shift or by rewriting the grammar to remove ambiguity. Understanding these conflicts helps in designing grammars that parsers can handle without errors.

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