Shift-reduce parsing in Compiler Design - Step-by-Step Execution

Concept Flow - Shift-reduce parsing

Start: Input tokens

↓

Shift: Push next token to stack

↓

Check: Can we reduce?

No→Shift next token

Yes↓

Reduce: Replace stack top by grammar rule

↓

Is input empty and stack has start symbol?

No→Repeat Shift/Reduce

Yes↓

Accept

Shift-reduce parsing reads tokens one by one (shift), then tries to replace parts of the stack with grammar rules (reduce), repeating until the input is accepted or rejected.

Execution Sample

Compiler Design

Input: id + id * id
Stack: []
Actions: shift, reduce

Step 1: shift 'id'
Step 2: reduce 'id' to F
Step 3: shift '+'
Step 4: shift 'id'
Step 5: reduce 'id' to F
Step 6: shift '*'
Step 7: shift 'id'
Step 8: reduce 'id' to F
Step 9: reduce 'F * F' to T
Step 10: reduce 'F + T' to E
Step 11: accept

This example shows shifting tokens onto the stack and reducing them step-by-step until the input is fully parsed.

Analysis Table

Step	Stack	Input	Action	Explanation
1	[]	id + id * id	Shift 'id'	Push 'id' onto stack
2	['id']	+ id * id	Reduce 'id' to F	Replace 'id' by non-terminal F
3	['F']	+ id * id	Shift '+'	Push '+' onto stack
4	['F', '+']	id * id	Shift 'id'	Push 'id' onto stack
5	['F', '+', 'id']	* id	Reduce 'id' to F	Replace 'id' by F
6	['F', '+', 'F']	* id	Shift '*'	Push '*' onto stack
7	['F', '+', 'F', '*']	id	Shift 'id'	Push 'id' onto stack
8	['F', '+', 'F', '*', 'id']		Reduce 'id' to F	Replace 'id' by F
9	['F', '+', 'F', '*', 'F']		Reduce 'F * F' to T	Apply grammar rule for multiplication
10	['F', '+', 'T']		Reduce 'F + T' to E	Apply grammar rule for addition
11	['E']		Accept	Input fully parsed as start symbol E

💡 Parsing stops when input is empty and stack contains start symbol E

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	Final
Stack	[]	['id']	['F']	['F', '+']	['F', '+', 'id']	['F', '+', 'F']	['F', '+', 'F', '*']	['F', '+', 'F', '*', 'id']	['F', '+', 'F', '*', 'F']	['F', '+', 'T']	['E']	['E']
Input	id + id * id	+ id * id	+ id * id	id * id	* id	* id	id

Key Insights - 3 Insights

Why do we sometimes shift tokens even if we can reduce?

In shift-reduce parsing, we only reduce when the top of the stack matches a grammar rule's right side. If not, we must shift the next token to get more input before reducing. See steps 1 and 3 in the execution_table.

What does 'reduce' mean in this parsing?

Reduce means replacing a sequence of tokens or non-terminals on the stack with a single non-terminal according to a grammar rule. For example, at step 9, 'F * F' is replaced by 'T'.

When does the parser accept the input?

The parser accepts when the input is empty and the stack contains only the start symbol (here 'E'), as shown at step 11 in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 5. What is the top of the stack after the action?

A ['F', '+', 'F']

B ['F', '+', 'id']

C ['F', '+']

D ['F']

💡 Hint

Check the 'Stack' column at step 5 in the execution_table.

At which step does the parser first reduce a sequence of multiple tokens to a non-terminal?

A Step 2

B Step 5

C Step 9

D Step 10

💡 Hint

Look for the first 'Reduce' action that replaces more than one token in the 'Action' column.

If the input started with '+' instead of 'id', what would happen at step 1?

A Reduce '+' to F

B Shift '+' onto stack

C Reject input immediately

D Shift 'id' instead

💡 Hint

Shift always pushes the next input token onto the stack; see step 1 action.

Concept Snapshot

Shift-reduce parsing:
- Reads input tokens left to right (shift).
- Tries to replace stack top by grammar rules (reduce).
- Repeat shift/reduce until input empty and stack has start symbol.
- Accept if successful, else reject.
- Core actions: shift (push token), reduce (replace by non-terminal).

Full Transcript

Shift-reduce parsing is a method used by compilers to analyze input strings based on grammar rules. It works by reading tokens one at a time (shifting) and storing them on a stack. When the top of the stack matches the right side of a grammar rule, the parser replaces that sequence with the rule's left side (reducing). This process repeats until the entire input is consumed and the stack contains only the start symbol, meaning the input is accepted. The execution table shows each step, the stack content, remaining input, and the action taken. Beginners often wonder why shifting happens even when reduction seems possible; the parser only reduces when a grammar rule matches exactly. The parser accepts only when the input is empty and the stack has the start symbol. This visual step-by-step helps understand how shift-reduce parsing works in practice.

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