Shift-reduce parsing in Compiler Design - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to identify the action performed in shift-reduce parsing when the next input symbol is pushed onto the stack.

Compiler Design

action = "[1]"  # This action pushes the next input symbol onto the stack

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

Aerror

Breduce

Caccept

Dshift

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing shift with reduce action.

In shift-reduce parsing, the shift action means pushing the next input symbol onto the stack.

2fill in blank

medium

Complete the code to represent the reduce action in shift-reduce parsing, which replaces a handle on the stack with a non-terminal.

Compiler Design

action = "[1]"  # This action replaces a handle on the stack with a non-terminal

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

Ashift

Breduce

Caccept

Dreject

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up reduce with shift or accept.

The reduce action replaces a recognized handle on the stack with the corresponding non-terminal symbol.

3fill in blank

hard

Fix the error in the code to correctly identify the accept action in shift-reduce parsing when the input is fully parsed.

Compiler Design

if stack == ['S'] and input == []:
    action = "[1]"  # Parsing is complete and successful

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

Aaccept

Breduce

Cshift

Derror

Attempts:

3 left

💡 Hint

Common Mistakes

Using shift or reduce instead of accept at the end.

The accept action indicates that the input has been successfully parsed and the stack contains the start symbol.

4fill in blank

hard

Fill both blanks to complete the code that checks if the top of the stack matches a handle and then performs the reduce action.

Compiler Design

if stack[-[1]:] == handle:
    stack = stack[:-[2]] + [non_terminal]  # Perform reduce by replacing handle

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

Alen(handle)

B1

C0

Dlen(stack)

Attempts:

3 left

💡 Hint

Common Mistakes

Using fixed numbers like 1 instead of handle length.

To reduce, we check if the top of the stack matches the handle of length len(handle) and then remove that many symbols before pushing the non-terminal.

5fill in blank

hard

Fill all three blanks to complete the code that performs a shift-reduce parsing step: shifting the next input symbol, checking for a handle, and reducing if found.

Compiler Design

stack.append(input[0])  # Shift next symbol
input = input[1:]
if stack[-[1]:] == [2]:
    stack = stack[:-[3]] + [non_terminal]  # Reduce handle to non-terminal

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

Alen(handle)

Bhandle

Dinput

Attempts:

3 left

💡 Hint

Common Mistakes

Using input instead of handle for comparison.

Incorrect slicing lengths.

The code shifts the next input symbol onto the stack, then checks if the top of the stack matches the handle, and if so, reduces it by replacing the handle with the non-terminal.

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