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, thenLL(1). - Otherwise print only
not LL(1): conflict at A, tfor 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
5 E -> T E' E' -> + T E' | ε T -> F T' T' -> * F T' | ε F -> ( E ) | id
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)
1 S -> a b | a c
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)")