Compilers: Shift-reduce with precedence

Resolve shift-reduce conflicts with precedence and associativity.

What to build

A program that parses an expression bottom-up with E → E + E | E * E | ( E ) | id, printing every action.

Requirements

  • Reduce E op E only when the next token is $, ), or an operator whose precedence is not higher than op's.
  • Print shift T, reduce E -> id, reduce E -> ( E ), reduce E -> E + E, reduce E -> E * E, then accept or error.

Input

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

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 -> id
shift *
shift id
reduce E -> id
reduce E -> E * E
reduce E -> E + E
accept

Why it works

Comparing the operator on the stack with the next one decides whether to group now (reduce) or wait (shift), giving precedence and left associativity.

Examples

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

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

Hints

Hint 1

Look for handles in this order: id, then ( E ), then E op E (only if the next token is $, ), or an operator that does not bind tighter).

Hint 2

* binds tighter than +, and both are left-associative.

Solution

Show one correct solution (try it yourself first)
PREC = {"+": 1, "*": 2}
tokens = input().split() + ["$"]
stack, i = [], 0
while True:
    a = tokens[i]
    if stack[-1:] == ["id"]:
        stack[-1:] = ["E"]
        print("reduce E -> id")
    elif stack[-3:] == ["(", "E", ")"]:
        stack[-3:] = ["E"]
        print("reduce E -> ( E )")
    elif len(stack) >= 3 and stack[-1] == "E" and stack[-2] in PREC and stack[-3] == "E" and (a in ("$", ")") or (a in PREC and PREC[a] <= PREC[stack[-2]])):
        print(f"reduce E -> E {stack[-2]} E")
        stack[-3:] = ["E"]
    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 →