Compilers: A complete LL(1) parser

Combine table construction and table-driven parsing into a parser generator.

What to build

A program that builds an LL(1) table from a grammar and parses a list of tokens with it, printing the rules used.

Requirements

  • If the grammar is not LL(1), print only not LL(1).
  • Otherwise print each rule as it is used, A -> body (ε for an empty body), then accept, or error at token K (the end of input is token n + 1).

Input

Line 1: r. Then r lines A -> body | body. Last line: the tokens, separated by spaces (possibly empty).

Output

The rules used, then accept or an error line; or not LL(1).

Constraints

r ≤ 15; at most 40 tokens.

Example

Input:

5
E -> T E'
E' -> + T E' | ε
T -> F T'
T' -> * F T' | ε
F -> ( E ) | id
id + id * id

Output:

E -> T E'
T -> F T'
F -> id
T' -> ε
E' -> + T E'
T -> F T'
F -> id
T' -> * F T'
F -> id
T' -> ε
E' -> ε
accept

Why it works

The rules printed are a leftmost derivation of the input, chosen one token at a time by the table.

Examples

Example 1 · Input
5
E -> T E'
E' -> + T E' | ε
T -> F T'
T' -> * F T' | ε
F -> ( E ) | id
id + id * id
Expected output
E -> T E'
T -> F T'
F -> id
T' -> ε
E' -> + T E'
T -> F T'
F -> id
T' -> * F T'
F -> id
T' -> ε
E' -> ε
accept
Example 2 · Input
1
S -> a b | a c
a b
Expected output
not LL(1)

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

Hints

Hint 1

Build the table as in the previous exercise; if there is a conflict, print not LL(1) and stop.

Hint 2

Parse with the stack [$, start], printing each rule as it is used.

Solution

Show one correct solution (try it yourself first)
grammar = {}
for _ in range(int(input())):
    head, bodies = input().split(" -> ")
    grammar[head] = [[] if b.strip() == "ε" else b.split() for b in bodies.split(" | ")]
tokens = input().split() + ["$"]
start = next(iter(grammar))
nullable, first, follow = set(), {a: set() for a in grammar}, {a: set() for a in grammar}
follow[start].add("$")


def first_of(symbols):
    out = set()
    for s in symbols:
        if s not in grammar:
            return out | {s}, False
        out |= first[s]
        if s not in nullable:
            return out, False
    return out, True


changed = True
while changed:
    changed = False
    for head, bodies in grammar.items():
        for body in bodies:
            f, empty = first_of(body)
            if not f <= first[head]:
                first[head] |= f
                changed = True
            if empty and head not in nullable:
                nullable.add(head)
                changed = True
            for i, s in enumerate(body):
                if s in grammar:
                    rest, rest_empty = first_of(body[i + 1:])
                    new = rest | (follow[head] if rest_empty else set())
                    if not new <= follow[s]:
                        follow[s] |= new
                        changed = True

table, ok = {}, True
for head, bodies in grammar.items():
    for body in bodies:
        f, empty = first_of(body)
        for t in f | (follow[head] if empty else set()):
            if (head, t) in table and table[(head, t)] != body:
                ok = False
            table.setdefault((head, t), body)

if not ok:
    print("not LL(1)")
else:
    stack, i = ["$", start], 0
    while True:
        top, a = stack.pop(), tokens[i]
        if top == a:
            if a == "$":
                print("accept")
                break
            i += 1
        elif top in grammar and (top, a) in table:
            body = table[(top, a)]
            print(f"{top} -> {' '.join(body) or 'ε'}")
            stack.extend(reversed(body))
        else:
            print(f"error at token {i + 1}")
            break

Lesson: LL(1) parsing with a table →