Compute the first grammar analysis: nullable nonterminals.
What to build
A program that finds every nonterminal that can derive the empty string.
Requirements
- Nonterminals are the heads of the rules; every other symbol is a terminal;
εalone is an empty body. - Print the nullable nonterminals sorted and separated by spaces, or
none.
Input
Line 1: r. Then r lines A -> body | body, symbols separated by spaces.
Output
One line.
Constraints
r ≤ 20.
Example
Input:
5
E -> T E'
E' -> + T E' | ε
T -> F T'
T' -> * F T' | ε
F -> ( E ) | id
Output:
E' T'
Why it works
Nullability depends on other nonterminals' nullability, so repeating until nothing changes finds all of them.
Examples
Example 1 · Input
5 E -> T E' E' -> + T E' | ε T -> F T' T' -> * F T' | ε F -> ( E ) | id
Expected output
E' T'
Example 2 · Input
3 S -> A B c A -> a | ε B -> b | ε
Expected output
A B
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
A rule makes its head nullable when every symbol in its body is a nullable nonterminal (an ε body counts).
Hint 2
Repeat over all rules until nothing new becomes nullable.
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()
changed = True
while changed:
changed = False
for head, bodies in grammar.items():
if head not in nullable and any(all(s in nullable for s in body) for body in bodies):
nullable.add(head)
changed = True
print(" ".join(sorted(nullable)) if nullable else "none")