消除左递归python

消除文法中的左递归是一个常见的问题，下面是一种Python实现的方法：

# 定义一个函数，用于消除文法中的左递归
def eliminate_left_recursion(grammar):
    # 获取文法中的所有非终结符
    non_terminals = grammar.keys()
    # 遍历每个非终结符
    for A in non_terminals:
        # 获取A可以推导出的所有产生式
        productions = grammar[A]
        # 将产生式分为左递归和非左递归两类
        left_recursive_productions = []
        non_left_recursive_productions = []
        for production in productions:
            if production[0] == A:
                left_recursive_productions.append(production)
            else:
                non_left_recursive_productions.append(production)
        # 如果存在左递归产生式
        if left_recursive_productions:
            # 新建一个非终结符B
            B = A + "'"
            # 将B加入到文法中
            grammar[B] = []
            # 将非左递归产生式加入到B中
            for production in non_left_recursive_productions:
                grammar[B].append(production + [B])
            # 将B -> ε加入到B中
            grammar[B].append(['ε'])
            # 将左递归产生式改写为非左递归产生式
            for production in left_recursive_productions:
                grammar[A].remove(production)
                grammar[A].append(production[1:] + [B])
                grammar[B].append(production[1:] + [B])
    # 返回消除左递归后的文法
    return grammar

该函数接受一个字典类型的文法作为参数，返回消除左递归后的文法。具体实现过程如下：

1. 遍历每个非终结符A。
2. 获取A可以推导出的所有产生式。
3. 将产生式分为左递归和非左递归两类。
4. 如果存在左递归产生式，则新建一个非终结符B，并将B加入到文法中。
5. 将非左递归产生式加入到B中，并将B -> ε加入到B中。
6. 将左递归产生式改写为非左递归产生式。
7. 返回消除左递归后的文法。