Compilers: Build an LL(1) table

Generate a parse table automatically, and detect grammars that are not LL(1).

What to build

A program that builds the LL(1) table of a grammar, or reports the first conflict.

Requirements

  • If there is no conflict, print one entry per line, A, t: body (ε for an empty body), nonterminals in the order given and terminals sorted, then LL(1).
  • Otherwise print only not LL(1): conflict at A, t for the first conflict met when placing rules in order.

Input

Line 1: r. Then r lines A -> body | body (symbols separated by spaces; ε is an empty body). The first head is the start symbol.

Output

The table and LL(1), or one conflict line.

Constraints

r ≤ 15.

Example

Input:

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

Output:

E, (: T E'
E, id: T E'
E', $: ε
E', ): ε
E', +: + T E'
T, (: F T'
T, id: F T'
T', $: ε
T', ): ε
T', *: * F T'
T', +: ε
F, (: ( E )
F, id: id
LL(1)

Why it works

Each cell says which rule predicts the next token; if one cell needs two rules, a single token cannot decide.

Examples

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

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

Hints

Hint 1

Compute nullable, FIRST and FOLLOW first; then place each rule under FIRST of its body, and under FOLLOW of its head if the body can vanish.

Hint 2

Walk the nonterminals and their rules in the order given, and the terminals sorted, and stop at the first cell that gets a different rule.

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(" | ")]
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 = {}
conflict = None
for head, bodies in grammar.items():
    for body in bodies:
        f, empty = first_of(body)
        for t in sorted(f | (follow[head] if empty else set())):
            if (head, t) in table and table[(head, t)] != body and conflict is None:
                conflict = (head, t)
            table.setdefault((head, t), body)
if conflict:
    print(f"not LL(1): conflict at {conflict[0]}, {conflict[1]}")
else:
    for head in grammar:
        for (h, t) in sorted(k for k in table if k[0] == head):
            print(f"{h}, {t}: {' '.join(table[(h, t)]) or 'ε'}")
    print("LL(1)")

Lesson: LL(1) parsing with a table →