Compilers: Shift and reduce a sum

Trace a bottom-up parser for a left-recursive grammar.

What to build

A program that parses tokens with the grammar E → E + id | id by shifting and reducing, printing every action.

Requirements

  • Before reading a token, reduce E + id on top to E, or a stack that is exactly id to E; otherwise shift.
  • Print each action: shift T, reduce E -> id, reduce E -> E + id, then accept or error.

Input

One line of tokens separated by spaces (id and +).

Output

One action per line.

Constraints

At most 40 tokens.

Example

Input:

id + id + id

Output:

shift id
reduce E -> id
shift +
shift id
reduce E -> E + id
shift +
shift id
reduce E -> E + id
accept

Why it works

The parser waits until a whole rule body is on the stack before reducing, which is why left recursion is no problem bottom-up.

Examples

Example 1 · Input
id + id + id
Expected output
shift id
reduce E -> id
shift +
shift id
reduce E -> E + id
shift +
shift id
reduce E -> E + id
accept
Example 2 · Input
id
Expected output
shift id
reduce E -> id
accept

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Check for the handle E + id first, then for a single id at the bottom of the stack, and shift otherwise.

Hint 2

At the end of the input, accept only if the stack is just E.

Solution

Show one correct solution (try it yourself first)
tokens = input().split() + ["$"]
stack, i = [], 0
while True:
    a = tokens[i]
    if stack[-3:] == ["E", "+", "id"]:
        stack[-3:] = ["E"]
        print("reduce E -> E + id")
    elif stack == ["id"]:
        stack = ["E"]
        print("reduce E -> id")
    elif a == "$":
        print("accept" if stack == ["E"] else "error")
        break
    else:
        stack.append(a)
        i += 1
        print("shift", a)

Lesson: Bottom-up parsing: shift and reduce →