Parser conflicts (shift-reduce, reduce-reduce) in Compiler Design - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to identify the type of parser conflict when a parser must choose between shifting the next input symbol or reducing the current symbols.

Compiler Design

The parser conflict where the parser must decide between shifting or reducing is called a [1] conflict.

Drag options to blanks, or click blank then click option'

Ashift-reduce

Breduce-reduce

Csyntax error

Dlexical error

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing shift-reduce with reduce-reduce conflict

Thinking it is a syntax error

A shift-reduce conflict occurs when the parser can either shift the next input symbol onto the stack or reduce the symbols on the stack to a non-terminal. This is a common parser conflict in LR parsing.

2fill in blank

medium

Complete the sentence to describe the reduce-reduce conflict.

Compiler Design

A [1] conflict happens when the parser has to choose between two or more possible reductions at the same point.

Drag options to blanks, or click blank then click option'

Ashift-reduce

Bsemantic

Creduce-reduce

Dlexical

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up with shift-reduce conflict

Thinking it relates to lexical analysis

A reduce-reduce conflict occurs when the parser can reduce the input in more than one way at the same point, causing ambiguity in parsing.

3fill in blank

hard

Fix the error in the statement about parser conflicts.

Compiler Design

A [1] conflict occurs when the parser must decide between shifting the next input symbol or reducing the current symbols on the stack.

Drag options to blanks, or click blank then click option'

Asemantic

Breduce-reduce

Csyntax

Dshift-reduce

Attempts:

3 left

💡 Hint

Common Mistakes

Choosing reduce-reduce instead of shift-reduce

Confusing with syntax errors

The correct term for the conflict where the parser chooses between shifting or reducing is shift-reduce conflict.

4fill in blank

hard

Fill both blanks to complete the explanation of parser conflicts.

Compiler Design

In LR parsing, a [1] conflict happens when the parser can either [2] the next input symbol or reduce the symbols on the stack.

Drag options to blanks, or click blank then click option'

Ashift-reduce

Bshift

Creduce-reduce

Ddiscard

Attempts:

3 left

💡 Hint

Common Mistakes

Using reduce-reduce for the first blank

Using 'discard' instead of 'shift' for the second blank

A shift-reduce conflict occurs when the parser must decide whether to shift the next input symbol onto the stack or to reduce the current symbols on the stack.

5fill in blank

hard

Fill all three blanks to complete the dictionary comprehension describing parser conflicts.

Compiler Design

conflicts = [1]: '[2]' if type == '[3]' else 'other' for type in ['shift-reduce', 'reduce-reduce']

Drag options to blanks, or click blank then click option'

A{type.upper()}

Bshift-reduce

D{type}

Attempts:

3 left

💡 Hint

Common Mistakes

Using {type.upper()} as key which is invalid syntax

Mixing up the string values for the condition

This comprehension creates a dictionary where keys are the conflict types and values are 'shift-reduce' if the type is 'shift-reduce', otherwise 'other'. The key uses the variable type directly.

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