乔姆斯基范式转换为格雷巴赫范式的代码

以下是将乔姆斯基范式（Chomsky Normal Form）转换为格雷巴赫范式（Chomsky Normal Form）的 Python 代码：

def chomsky_to_greibach(grammar):
    """
    将乔姆斯基范式转换为格雷巴赫范式
    """
    new_grammar = {}
    nonterm = list(grammar.keys())

    # Step 1: 将产生式右侧长度大于2的产生式转化为多个产生式
    for nt in nonterm:
        new_grammar[nt] = []
        for prod in grammar[nt]:
            if len(prod) > 2:
                new_nt = nt
                for i in range(1, len(prod)-1):
                    new_nt = new_nt + "_new"
                    new_grammar[new_nt] = [prod[i]]
                new_grammar[nt].append(prod[0] + new_nt)
                new_grammar[new_nt + "_new"].append(prod[-1])
            else:
                new_grammar[nt].append(prod)

    # Step 2: 将产生式右侧长度为2的产生式转化为多个产生式
    for nt in nonterm:
        new_prods = []
        for prod in new_grammar[nt]:
            if len(prod) == 2 and prod[0] in nonterm and prod[1] in nonterm:
                for new_prod in new_grammar[prod[0]]:
                    new_prods.append(new_prod + prod[1])
                for new_prod in new_grammar[prod[1]]:
                    new_prods.append(prod[0] + new_prod)
            else:
                new_prods.append(prod)
        new_grammar[nt] = new_prods

    # Step 3: 将产生式右侧为终结符号的产生式转化为多个产生式
    for nt in nonterm:
        new_prods = []
        for prod in new_grammar[nt]:
            if len(prod) == 2 and prod[0] in nonterm and prod[1] not in nonterm:
                for new_prod in new_grammar[prod[0]]:
                    new_prods.append(new_prod + prod[1])
            else:
                new_prods.append(prod)
        new_grammar[nt] = new_prods

    # Step 4: 将产生式右侧为 ε 的产生式删除
    for nt in nonterm:
        new_prods = []
        for prod in new_grammar[nt]:
            if prod != "ε":
                new_prods.append(prod)
        new_grammar[nt] = new_prods

    # Step 5: 将产生式转化为 A → BC 或 A → a 的形式
    for nt in nonterm:
        new_prods = []
        for prod in new_grammar[nt]:
            if len(prod) > 1:
                new_prods.append(prod[0] + nt + "_new")
                new_grammar[nt + "_new"] = [prod[1:]]
            else:
                new_prods.append(prod)
        new_grammar[nt] = new_prods

    return new_grammar

其中，`grammar` 是一个字典，表示原始的文法，示例代码如下：

grammar = {
    "S": ["AB", "BC"],
    "A": ["BA", "a"],
    "B": ["CC", "b"],
    "C": ["AB", "a"]
}

调用 `chomsky_to_greibach(grammar)` 函数即可将乔姆斯基范式转换为格雷巴赫范式。