Compilers: A table-driven parser for brackets

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, or error at token K where 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)

Lesson: LL(1) parsing with a table →