Shift-reduce parsing in Compiler Design - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is shift-reduce parsing?

Shift-reduce parsing is a bottom-up method used in compilers to analyze the structure of a sentence by shifting input symbols onto a stack and reducing them to grammar rules until the start symbol is reached.

beginner

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

The 'shift' action moves the next input symbol onto the top of the stack, preparing it for possible reduction later.

beginner

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

The 'reduce' action replaces a sequence of symbols on the stack that matches the right side of a grammar rule with the rule's left side non-terminal symbol.

intermediate

What is a handle in shift-reduce parsing?

A handle is a substring of the input that matches the right side of a grammar production and can be reduced to the non-terminal on the left side during parsing.

beginner

Why is shift-reduce parsing called a bottom-up parsing technique?

Because it starts from the input symbols (the bottom) and works upward by reducing them step-by-step to the start symbol, building the parse tree from leaves to root.

In shift-reduce parsing, what happens during the 'shift' step?

A Restart parsing from the beginning

B Replace symbols on the stack with a non-terminal

C Move the next input symbol onto the stack

D Discard the input symbol

The 'shift' step moves the next input symbol onto the stack to prepare for possible reduction.

What is the main goal of the 'reduce' action in shift-reduce parsing?

A To add more symbols to the input

B To replace a sequence of symbols on the stack with a non-terminal

C To remove symbols from the input without processing

D To split the input into smaller parts

The 'reduce' action replaces a matched sequence on the stack with a non-terminal symbol according to a grammar rule.

What does a 'handle' represent in shift-reduce parsing?

A A substring that matches the right side of a grammar rule and can be reduced

B The start symbol of the grammar

C The entire input string

D An error in the input

A handle is a substring ready to be reduced to a non-terminal during parsing.

Shift-reduce parsing is an example of which parsing approach?

A Bottom-up parsing

B Recursive descent parsing

C Top-down parsing

D Predictive parsing

Shift-reduce parsing builds the parse tree from the input symbols up to the start symbol, making it bottom-up.

What data structure is primarily used in shift-reduce parsing to hold symbols?

A Queue

B Tree

C Linked list

D Stack

A stack is used to hold symbols during shift and reduce operations.

Explain the process of shift-reduce parsing using a simple example.

Think about how input symbols move onto the stack and get replaced by grammar rules.

Describe why shift-reduce parsing is considered a bottom-up parsing technique.

Consider the direction of parsing compared to top-down methods.

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