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 Eonly 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, thenacceptorerror.
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)