Compute what each construct of a grammar can start with.
What to build
A program that prints the FIRST set of every nonterminal.
Requirements
- Print one line per nonterminal, in the order the rules are given:
A: t1 t2 …, terminals sorted, thenεlast if A is nullable.
Input
Line 1: r. Then r lines A -> body | body (symbols separated by spaces; ε is an empty body).
Output
One line per nonterminal.
Constraints
r ≤ 20.
Example
Input:
5
E -> T E'
E' -> + T E' | ε
T -> F T'
T' -> * F T' | ε
F -> ( E ) | id
Output:
E: ( id
E': + ε
T: ( id
T': * ε
F: ( id
Why it works
FIRST is built from the FIRST sets of the symbols that can come first, which a fixed-point loop settles.
Examples
Example 1 · Input
5 E -> T E' E' -> + T E' | ε T -> F T' T' -> * F T' | ε F -> ( E ) | id
Expected output
E: ( id E': + ε T: ( id T': * ε F: ( id
Example 2 · Input
3 S -> A B c A -> a | ε B -> b | ε
Expected output
S: a b c A: a ε B: b ε
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
FIRST of a body: add FIRST of each symbol in turn, stopping at the first one that is not nullable.
Hint 2
Compute nullable and FIRST together, repeating until nothing changes.
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(" | ")]
nullable = set()
first = {a: set() for a in grammar}
changed = True
while changed:
changed = False
for head, bodies in grammar.items():
for body in bodies:
vanishes = True
for s in body:
add = first[s] if s in grammar else {s}
if not add <= first[head]:
first[head] |= add
changed = True
if s not in nullable:
vanishes = False
break
if vanishes and head not in nullable:
nullable.add(head)
changed = True
for head in grammar:
print(f"{head}: " + " ".join(sorted(first[head]) + (["ε"] if head in nullable else [])))