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), thenaccept, orerror 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
5 E -> T E' E' -> + T E' | ε T -> F T' T' -> * F T' | ε F -> ( E ) | id id + id * id
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
1 S -> a b | a c a b
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