Shift-reduce parsing in Compiler Design - Mini Project: Build & Apply

Understanding Shift-Reduce Parsing

📖 Scenario: You are learning how a simple shift-reduce parser works in a compiler. This parser reads input symbols and decides whether to shift (push the symbol onto a stack) or reduce (replace a sequence of symbols on the stack with a non-terminal) based on a set of rules.Imagine you have a stack and an input string of symbols. Your goal is to simulate the parser's actions step-by-step.

🎯 Goal: Build a simple shift-reduce parser simulation that uses a stack and input list. You will create the initial input, set a rule for reduction, perform shift and reduce actions, and finally complete the parsing process.

📋 What You'll Learn

Create an input list with exact symbols

Define a reduction rule as a tuple

Implement the core shift-reduce logic using a loop

Complete the parsing by showing the final stack state

💡 Why This Matters

🌍 Real World

Shift-reduce parsing is used in compilers to analyze and understand programming language syntax.

💼 Career

Understanding shift-reduce parsing helps in compiler development, language design, and debugging syntax errors.

1

Create the input list of symbols

Create a list called input_symbols with these exact elements in order: 'id', '+', 'id', '*', 'id'.

Compiler Design

# Create the input_symbols list with the exact symbols
# Your code here

Hint

Think of the input as a list of tokens the parser will read one by one.

2

Define the reduction rule

Create a variable called reduction_rule and set it to the tuple ('id', '+', 'id'). This represents the pattern the parser will reduce.

Compiler Design

input_symbols = ['id', '+', 'id', '*', 'id']
# Define the reduction_rule tuple
# Your code here

Hint

The reduction rule is a sequence of symbols that can be replaced by a non-terminal.

3

Implement the shift-reduce logic

Create an empty list called stack. Use a while loop to process input_symbols until it is empty. In each iteration, remove the first symbol from input_symbols and append it to stack (shift). Then check if the last three elements of stack match reduction_rule. If they do, replace those three elements with the string 'E' (reduce).

Compiler Design

input_symbols = ['id', '+', 'id', '*', 'id']
reduction_rule = ('id', '+', 'id')
# Implement shift-reduce parsing logic
# Your code here

Hint

Shift means moving a symbol from input to stack. Reduce means replacing a pattern on the stack with 'E'.

4

Complete the parsing process

After the loop ends, add a comment line that says # Final stack state shows the result of parsing. Then create a variable called final_stack and set it equal to the current stack.

Compiler Design

input_symbols = ['id', '+', 'id', '*', 'id']
reduction_rule = ('id', '+', 'id')
stack = []
while input_symbols:
    symbol = input_symbols.pop(0)
    stack.append(symbol)
    if len(stack) >= 3 and tuple(stack[-3:]) == reduction_rule:
        stack[-3:] = ['E']
# Add final_stack assignment below
# Your code here

Hint

The final stack contains the parsed structure after all shifts and reduces.

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