Shift-reduce parsing in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the Basic Operation of Shift-Reduce Parsing

In shift-reduce parsing, what does the 'shift' action specifically do?

A It removes a sequence of symbols from the stack and replaces them with a non-terminal.

B It moves the next input symbol onto the parsing stack.

C It accepts the input string as successfully parsed.

D It reports a syntax error and stops parsing.

💡 Hint

Think about what happens when the parser reads the next symbol but has not yet reduced.

The 'shift' action takes the next symbol from the input and pushes it onto the stack, preparing for possible reductions later.

🧠 Conceptual

intermediate

Role of the 'Reduce' Action in Shift-Reduce Parsing

What does the 'reduce' action do in shift-reduce parsing?

A It replaces a sequence of symbols on the stack with a non-terminal according to a grammar rule.

B It moves the next input symbol onto the stack.

C It discards the current input symbol as invalid.

D It restarts the parsing process from the beginning.

💡 Hint

Consider how the parser recognizes a pattern matching the right side of a grammar rule.

Reduce replaces the matched symbols on the stack with the corresponding non-terminal from the grammar, effectively recognizing a phrase.

🔍 Analysis

advanced

Identifying the Correct Sequence of Actions in Shift-Reduce Parsing

Given the input string id + id * id and a grammar where id is a terminal, which sequence of actions correctly parses this input using shift-reduce parsing?

A Shift, Shift, Shift, Reduce, Reduce, Shift, Reduce, Reduce

B Shift, Reduce, Shift, Shift, Reduce, Shift, Reduce, Reduce

C Shift, Shift, Reduce, Shift, Shift, Reduce, Reduce, Reduce

D Shift, Shift, Reduce, Shift, Reduce, Shift, Reduce, Reduce

💡 Hint

Remember operator precedence: multiplication (*) has higher precedence than addition (+).

The correct sequence respects operator precedence by reducing the multiplication before addition, matching the grammar rules properly.

📋 Factual

advanced

Error Detection in Shift-Reduce Parsing

What kind of error does a shift-reduce parser detect when it encounters a situation where it can either shift or reduce but neither action leads to a valid parse?

A Syntax error

B Reduce-reduce conflict

C Shift-reduce conflict

D Lexical error

💡 Hint

Consider what happens when no valid parsing action can continue the process.

A syntax error occurs when the parser cannot decide on a valid action to continue parsing, indicating the input does not conform to the grammar.

❓ Reasoning

expert

Resolving Shift-Reduce Conflicts in Parsing Tables

In shift-reduce parsing, a shift-reduce conflict occurs when the parser's action table suggests both shifting and reducing are possible. Which of the following strategies is commonly used to resolve this conflict in practical parser generators?

A Always choose to reduce to avoid infinite loops.

B Always choose to shift to prefer longer matches.

C Abort parsing and report an ambiguous grammar error.

D Use operator precedence and associativity rules to decide between shift and reduce.

💡 Hint

Think about how arithmetic expressions are parsed correctly despite conflicts.

Operator precedence and associativity rules guide the parser to choose shift or reduce, resolving conflicts to parse expressions correctly.

Practice

1. What is the main purpose of shift in shift-reduce parsing?

easy

A. To move the next input symbol onto the stack

B. To remove symbols from the stack

C. To check the grammar rules

D. To accept the input string

Solution

1. Step 1: Understand the role of shift

   In shift-reduce parsing, shifting means taking the next input symbol and placing it on the stack.

2. Step 2: Differentiate shift from reduce

   Reduce means replacing symbols on the stack using grammar rules, while shift just moves input symbols onto the stack.

3. Final Answer:

   To move the next input symbol onto the stack -> Option A

4. Quick Check:

   Shift = move input symbol to stack [OK]

Hint: Shift means push next input symbol onto stack [OK]

Common Mistakes:

• Confusing shift with reduce
• Thinking shift removes symbols
• Assuming shift checks grammar

2. Which of the following is the correct sequence of actions in shift-reduce parsing?

easy

A. Accept, Shift, Reduce

B. Reduce, Shift, Accept

C. Shift, Reduce, Accept

D. Shift, Accept, Reduce

Solution

1. Step 1: Recall the parsing process order

   Shift-reduce parsing first shifts symbols onto the stack, then reduces them using grammar rules, and finally accepts if input is valid.

2. Step 2: Match the correct sequence

   The correct order is Shift, then Reduce, then Accept.

3. Final Answer:

   Shift, Reduce, Accept -> Option C

4. Quick Check:

   Shift -> Reduce -> Accept [OK]

Hint: Remember parsing order: shift first, then reduce [OK]

Common Mistakes:

• Mixing up reduce and shift order
• Thinking accept happens before reduce
• Assuming reduce happens before any shift

3. Given the grammar rules:
S -> aA
A -> b
And input string ab, what is the correct sequence of stack contents during shift-reduce parsing?

medium

A. [ ] -> [a] -> [b] -> [S]

B. [ ] -> [a] -> [S] -> [S, b]

C. [ ] -> [b] -> [a, b] -> [S]

D. [ ] -> [a] -> [a, b] -> [S]

Solution

1. Step 1: Shift input symbols onto stack

   First, shift 'a' onto the stack: stack = [a]. Then shift 'b': stack = [a, b].

2. Step 2: Apply reductions using grammar rules

   Reduce 'b' to 'A' using A -> b, then reduce 'aA' to 'S' using S -> aA. Final stack is [S].

3. Final Answer:

   [ ] -> [a] -> [a, b] -> [S] -> Option D

4. Quick Check:

   Shift a, shift b, reduce to S [OK]

Hint: Shift all input, then reduce using grammar rules [OK]

Common Mistakes:

• Reducing too early before all symbols shifted
• Mixing order of symbols on stack
• Skipping reduction steps

4. In a shift-reduce parser, if the parser tries to reduce a symbol that does not match any grammar rule, what is the likely problem?

medium

A. The parser is shifting symbols incorrectly

B. The input string is invalid or contains errors

C. The parser is correctly accepting the input

D. The grammar rules are too simple

Solution

1. Step 1: Understand reduction failure

   If no grammar rule matches the symbols on the stack, the parser cannot reduce, indicating a problem with the input.

2. Step 2: Interpret the failure meaning

   This usually means the input string does not follow the grammar rules and is invalid or contains errors.

3. Final Answer:

   The input string is invalid or contains errors -> Option B

4. Quick Check:

   Failed reduce = invalid input [OK]

Hint: No matching reduce means input error [OK]

Common Mistakes:

• Assuming parser is always correct
• Thinking reduce failure means grammar is simple
• Confusing shift errors with reduce errors

5. Consider the grammar:
E -> E + T | T
T -> int
For the input string int + int + int, which sequence of actions correctly shows the shift-reduce parsing steps to fully reduce the input?

hard

A. Shift int, reduce T, reduce E, shift +, shift int, reduce T, reduce E, shift +, shift int, reduce T, reduce E

B. Shift int, shift +, reduce T, reduce E, shift int, shift +, reduce T, reduce E, shift int, reduce E

C. Shift int, reduce T, shift +, reduce E, shift int, reduce T, shift +, reduce E, shift int, reduce T

D. Shift int, reduce E, shift +, shift int, reduce T, reduce E, shift +, shift int, reduce T, reduce E

Solution

1. Step 1: Shift and reduce first int

   Shift 'int', reduce to T, then reduce T to E (since E -> T).

2. Step 2: Process first plus and second int

   Shift '+', shift 'int', reduce 'int' to T, then reduce 'E + T' to E.

3. Step 3: Process second plus and third int

   Shift '+', shift 'int', reduce 'int' to T, then reduce 'E + T' to E again, fully reducing input.

4. Final Answer:

   Shift int, reduce T, reduce E, shift +, shift int, reduce T, reduce E, shift +, shift int, reduce T, reduce E -> Option A

5. Quick Check:

   Shift and reduce each int, then reduce E + T repeatedly [OK]

Hint: Shift int, reduce T, reduce E, repeat for each + int [OK]

Common Mistakes:

• Reducing E too early or too late
• Skipping shifts of '+' symbols
• Confusing order of reduce steps