1.py

from collections import defaultdict

epsilon = "''"
eof = "$"

def is_terminal(symbol):
    return symbol.startswith("'")


def is_nonterminal(symbol):
    return not is_terminal(symbol)

def update_changed(a, b):
    if b - a:
        a.update(b)
        return True

    return False


class CFG:
    def __init__(self, rules):
        self.rules = rules
        self.symbols = set()
        self.terminals = set()
        self.nonterminals = set()
        self.productions = defaultdict(set)
        self.consumers = defaultdict(set)

        for rule in rules:
            self.productions[rule[0]].add(rule[1:])
            for symbol in rule[1:]:
                self.consumers[rule[0]].add(symbol)

            for symbol in rule:
                self.symbols.add(symbol)
                if is_terminal(symbol):
                    self.terminals.add(symbol)
                else:
                    self.nonterminals.add(symbol)

        self.start = rules[0][0]
        self.nullables = set()
        self.first_sets = {}
        self.follow_sets = {self.start: {eof}}
        self.update_nullables()
        self.update_follow_sets()

    def nullable(self, X):
        return X in self.nullables

    def update_nullables(self):
        changed = True
        while changed:
            changed = False
            for X in self.nonterminals - self.nullables:
                for production in self.productions[X]:
                    if all(Y in self.nullables for Y in production):
                        changed = True
                        self.nullables.add(X)
                        break

    def first(self, u):
        if u not in self.first_sets:
            new_sets = [u]
            changed = True
            while changed:
                self.first_sets.update({v: set() for v in new_sets})
                new_sets = []
                changed = False

                for v, S in self.first_sets.items():
                    for X in v:
                        if is_terminal(X):
                            changed |= update_changed(S, {X})
                            break

                        for w in self.productions[X]:
                            if w not in self.first_sets:
                                changed = True
                                new_sets.append(w)
                            else:
                                changed |= update_changed(S, self.first_sets[w] - {epsilon})

                        if not self.nullable(X):
                            break

                    # We didn't break, so all symbols were nullable nonterminals. Add epsilon to first set.
                    else:
                        changed |= update_changed(S, {epsilon})

        return self.first_sets[u]

    def follow(self, X):
        return self.follow_sets[X]

    def update_follow_sets(self):
        for nonterminal in self.nonterminals:
            if nonterminal not in self.follow_sets:
                self.follow_sets[nonterminal] = set()

        changed = True
        while changed:
            changed = False
            for rule in self.rules:
                production = rule[1:]
                for i, Y in enumerate(production):
                    if is_terminal(Y):
                        continue

                    if Y not in self.follow_sets:
                        self.follow_sets[Y] = set()
                        changed = True

                    F = self.first(production[i+1:])
                    changed |= update_changed(self.follow_sets[Y], F - {epsilon})
                    if epsilon in F:
                        changed |= update_changed(self.follow_sets[Y], self.follow_sets[rule[0]])