Compilers: Which nonterminals can vanish?

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")

Lesson: FIRST and FOLLOW sets →