gistfile1.txt

from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))


def remove_indices(s, indices):
    ret, prev = '', 0
    for i in indices:
        chunk = s[prev:i]
        ret += chunk
        prev = i + 1
    return ret + s[prev:]


def rewrite(sym, prod):
    occurrences = [i for i, v in enumerate(prod) if v == sym]

    for removal in powerset(occurrences):
        yield remove_indices(prod, removal)


def epsilonless_production(prod):
    prod = prod[:]
    try:
        prod.remove('')
    except:
        pass
    return prod


g = {'A': ['aNbNcNd'],
     'N': ['a', '']}

def rewrite_all(sym, grammar):
    iterated_grammar = grammar.copy()
    for nonterminal, production in grammar.iteritems():
        iterated_grammar[nonterminal] = [alt
                                         for rule in production
                                         for alt in rewrite(sym, rule)]
    return iterated_grammar

def remove_epsilons(grammar):
    iterated_grammar = grammar.copy()

    for nonterminal, production in grammar.iteritems():
        epsilon_free = epsilonless_production(production)
        if epsilon_free != production:
            iterated_grammar[nonterminal] = epsilon_free
            iterated_grammar = rewrite_all(nonterminal, iterated_grammar)

    return iterated_grammar