Compilers: FIRST sets

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 [])))

Lesson: FIRST and FOLLOW sets →