Compute what can come after each construct, the last ingredient of an LL(1) table.
What to build
A program that prints the FOLLOW set of every nonterminal.
Requirements
- The head of the first rule is the start symbol; $ marks the end of the input.
- Print
A: t1 t2 …for each nonterminal in the order given, with the terminals (and $) sorted.
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: $ )
E': $ )
T: $ ) +
T': $ ) +
F: $ ) * +
Why it works
What follows B is whatever starts the rest of the rule, and, if that rest can vanish, whatever follows the rule's head.
Examples
Example 1 · Input
5 E -> T E' E' -> + T E' | ε T -> F T' T' -> * F T' | ε F -> ( E ) | id
Expected output
E: $ ) E': $ ) T: $ ) + T': $ ) + F: $ ) * +
Example 2 · Input
3 S -> A B c A -> a | ε B -> b | ε
Expected output
S: $ A: b c B: c
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Put $ in FOLLOW of the first rule's head; for each B in a body, add FIRST of what follows it, and FOLLOW of the head when the rest can vanish.
Hint 2
You need nullable and FIRST first; then repeat the FOLLOW rules 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(" | ")]
start = next(iter(grammar))
nullable = set()
first = {a: set() for a in grammar}
follow = {a: set() for a in grammar}
follow[start].add("$")
def first_of(symbols):
out = set()
for s in symbols:
if s not in grammar:
out.add(s)
return out, 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
for head in grammar:
print(f"{head}: " + " ".join(sorted(follow[head])))