Run the LL(1) loop with a fixed table.
What to build
A program that parses a string of brackets with an explicit stack and the table for S → ( S ) S | ε.
Requirements
- Start with the stack [$, S]. Match terminals; expand S using the table.
- Print
accept, orerror at token Kwhere K is the position of the token being looked at (the end counts as n + 1).
Input
One line of ( and ) characters (possibly empty).
Output
One line.
Constraints
At most 60 characters.
Example
Input:
(())()
Output:
accept
Why it works
The table chooses the rule from the next token, and the stack remembers what is still expected, so one left-to-right pass decides the input.
Examples
Example 1 · Input
(())()
Expected output
accept
Example 2 · Input
(()
Expected output
error at token 4
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Grammar S → ( S ) S | ε. Table: M[S, (] = ( S ) S; M[S, )] = ε; M[S, $] = ε.
Hint 2
Count tokens from 1; the end marker $ is token n + 1.
Solution
Show one correct solution (try it yourself first)
table = {("S", "("): ["(", "S", ")", "S"], ("S", ")"): [], ("S", "$"): []}
tokens = list(input().strip()) + ["$"]
stack = ["$", "S"]
i = 0
result = None
while result is None:
top, a = stack.pop(), tokens[i]
if top == a:
if a == "$":
result = "accept"
i += 1
elif top == "S" and (top, a) in table:
stack.extend(reversed(table[(top, a)]))
else:
result = f"error at token {i + 1}"
print(result)