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 + idon top to E, or a stack that is exactlyidto E; otherwise shift. - Print each action:
shift T,reduce E -> id,reduce E -> E + id, thenacceptorerror.
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)