core.py 文件源码

def post_parse(grammar):
    # Create `G`
    G = DiGraph()
    G.add_nodes_from(grammar.prods)
    for lhs, rhs in grammar.prods.items():
        for tok in rhs:
            if tok in grammar.prods:
                G.add_edge(lhs, tok)

    # DEBUG: from ._debug import Drawer # DEBUG
    # DEBUG: drawer = Drawer(G, grammar.start) # DEBUG

    # Inlining
    for root, _ in list(bfs_edges(G, grammar.start)):
        while True:
            nodes = [d for _, d in bfs_edges(G, root)]
            nodes = [root] + nodes
            edges = []
            for n in nodes:
                edges.extend(G.edges([n]))
            for ns, nd in reversed(edges):
                # DEBUG: drawer.draw(G, (ns, nd)) # DEBUG

                # Skip if `nd` has a self-loop
                if G.has_edge(nd, nd):
                    continue

                # Skip if `C` consists of multiple nodes
                g = G.subgraph(n for n in G.nodes_iter() if n != ns)
                if len(next((c for c in sccs(g) if nd in c))) != 1:
                    continue

                # Update grammar
                expr = []
                alter = Token.alter()
                for tok in grammar.prods[ns]:
                    expr.append(tok)
                    if tok == nd:
                        expr.extend(list(grammar.prods[nd]) + [alter])
                grammar.prods[ns] = Expr(expr)

                # Update G
                G.remove_edge(ns, nd)
                for _, dst in G.edges_iter(nd):
                    G.add_edge(ns, dst)

                # DEBUG: drawer.draw(G) # DEBUG
                break  # Back to `for ns, nd in ...`

            else:
                # DEBUG: drawer.draw(G) # DEBUG
                break  # Back to `for root, _ in ...`

    return {nd for _, nd in G.edges_iter()}  # Unexpanded nonterminals