Compilers: FOLLOW sets

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

Lesson: FIRST and FOLLOW sets →