第73集：消除左递归

学习目标

• 理解左递归的概念和类型
• 掌握左递归对自顶向下分析的影响
• 学会消除直接左递归的方法
• 学会消除间接左递归的方法
• 通过示例演练巩固消除左递归的技巧

一、左递归的概念

左递归是上下文无关文法中的一种现象，指的是一个非终结符可以通过一步或多步推导，最终推导出以自身开头的符号串。

左递归的定义

如果存在推导过程：

A ⇒* Aα

其中 A 是一个非终结符，α 是一个符号串，则称文法中存在关于 A 的左递归。

左递归的类型

左递归分为两种类型：

1. 直接左递归：存在产生式 A → Aα，其中 α ∈ (N ∪ T)*
2. 间接左递归：存在推导 A ⇒ Bα ⇒ ... ⇒ Aβ，其中 B 是其他非终结符

二、左递归对自顶向下分析的影响

自顶向下分析（如递归下降分析）是从开始符号出发，尝试通过最左推导匹配输入串。左递归会导致自顶向下分析器陷入无限循环。

问题示例

考虑以下具有直接左递归的文法：

E → E + T | T
T → T * F | F
F → (E) | id

当使用递归下降分析器分析表达式时，对于产生式 E → E + T，分析器会：

1. 调用 E 的分析函数
2. 再次调用 E 的分析函数（因为最左非终结符是 E）
3. 无限循环...

为什么会出现无限循环？

自顶向下分析器在处理左递归产生式时，会不断地递归调用自身，而没有消耗任何输入符号，导致无限循环。

三、消除直接左递归

直接左递归是最常见的左递归形式，可以通过改写产生式的方法来消除。

消除方法

对于直接左递归的产生式：

A → Aα₁ | Aα₂ | ... | Aαₘ | β₁ | β₂ | ... | βₙ

其中 βᵢ 都不以 A 开头，可以改写为：

A → β₁A' | β₂A' | ... | βₙA'
A' → α₁A' | α₂A' | ... | αₘA' | ε

示例：消除表达式文法的直接左递归

原始文法：

E → E + T | T
T → T * F | F
F → (E) | id

消除直接左递归后：

E → TE'
E' → + TE' | ε

T → FT'
T' → * FT' | ε

F → (E) | id

消除过程解析

以 E 的产生式为例：

1. 识别直接左递归：E → E + T
2. 分离非左递归产生式：E → T
3. 应用消除规则：
   • E → TE'（β 是 T）
   • E' → + TE' | ε（α 是 + T）

四、消除间接左递归

间接左递归比直接左递归更复杂，需要通过一系列步骤来消除。

消除步骤

1. 排序非终结符：将非终结符排序为 A₁, A₂, ..., Aₙ
2. 消除间接左递归：对每个 i 从 1 到 n：
   • 对每个 j 从 1 到 i-1：
     • 将 Aᵢ 的产生式中的 Aⱼ 替换为 Aⱼ 的所有产生式右部
   • 消除 Aᵢ 产生式中的直接左递归
3. 化简结果：移除多余的产生式

示例：消除间接左递归

考虑以下具有间接左递归的文法：

S → Aa | b
A → Ac | Sd | ε

步骤 1：排序非终结符

选择排序：S, A

步骤 2：消除间接左递归

处理 i=1（S）：

• j 从 1 到 0，无操作
• S 无直接左递归，保持不变

处理 i=2（A）：

• j=1（S）：将 A 产生式中的 S 替换为 S 的产生式右部
  • 原产生式：A → Ac | Sd | ε
  • 替换后：A → Ac | Aad | bd | ε
• 消除 A 的直接左递归：
  • 应用规则：A → (bd | ε)A', A' → (c | ad)A' | ε
  • 简化后：A → bdA' | A', A' → cA' | adA' | ε

步骤 3：化简结果

最终文法：

S → Aa | b
A → bdA' | A'
A' → cA' | adA' | ε

可以进一步化简为：

S → Aa | b
A → (bd | ε)A'
A' → (c | ad)A' | ε

五、完整示例：消除左递归演练

示例 1：消除直接左递归

原始文法：

E → E + T | E - T | T
T → T * F | T / F | F
F → (E) | id

消除过程：

1. 处理 E 的产生式：

   • 直接左递归：E → E + T | E - T
   • 非左递归产生式：E → T
   • 消除后：E → TE', E' → + TE' | - TE' | ε

2. 处理 T 的产生式：

   • 直接左递归：T → T * F | T / F
   • 非左递归产生式：T → F
   • 消除后：T → FT', T' → * FT' | / FT' | ε

3. F 的产生式无左递归，保持不变

最终文法：

E → TE'
E' → + TE' | - TE' | ε

T → FT'
T' → * FT' | / FT' | ε

F → (E) | id

示例 2：消除间接左递归

原始文法：

A → Bc | d
B → Ae | f
C → Ce | g

消除过程：

1. 排序非终结符：A, B, C

2. 处理 A：无直接左递归，保持不变

3. 处理 B：

   • 替换 A：B → (Bc | d)e | f → B → Bce | de | f
   • 消除直接左递归：B → (de | f)B', B' → ceB' | ε

4. 处理 C：

   • 消除直接左递归：C → gC', C' → eC' | ε

最终文法：

A → Bc | d
B → (de | f)B'
B' → ceB' | ε
C → gC'
C' → eC' | ε

六、消除左递归的注意事项

1. 保持语言不变：消除左递归后，文法应生成与原文法相同的语言
2. 注意 ε 产生式：消除左递归可能会引入 ε 产生式，需要确保分析器能够正确处理
3. 处理所有左递归：确保消除所有形式的左递归，包括直接和间接左递归
4. 化简结果：消除左递归后，可能会产生多余的产生式，需要进行化简
5. 考虑语义动作：如果产生式带有语义动作，消除左递归时需要保持语义动作的正确性

七、代码示例：检测左递归

下面是一个简单的 Python 代码，用于检测文法中的左递归：

class GrammarAnalyzer:
    def __init__(self, productions):
        """
        初始化文法分析器
        productions: 字典，键为非终结符，值为产生式右部列表
        """
        self.productions = productions
        self.non_terminals = set(productions.keys())
    
    def has_direct_left_recursion(self, non_terminal):
        """
        检测直接左递归
        """
        for prod in self.productions.get(non_terminal, []):
            # 检查产生式右部是否以非终结符开头
            if prod and prod[0] == non_terminal:
                return True
        return False
    
    def has_left_recursion(self):
        """
        检测是否存在左递归（直接或间接）
        使用 Floyd-Warshall 算法检测可达性
        """
        # 构建非终结符列表
        nt_list = list(self.non_terminals)
        nt_count = len(nt_list)
        
        # 创建可达性矩阵
        # reach[i][j] 表示 nt_list[i] 是否可以推导出以 nt_list[j] 开头的符号串
        reach = [[False] * nt_count for _ in range(nt_count)]
        
        # 初始化直接推导
        for i, A in enumerate(nt_list):
            for prod in self.productions.get(A, []):
                if not prod:
                    continue
                # 找到第一个非终结符
                for symbol in prod:
                    if symbol in self.non_terminals:
                        j = nt_list.index(symbol)
                        reach[i][j] = True
                        break
        
        # Floyd-Warshall 算法计算传递闭包
        for k in range(nt_count):
            for i in range(nt_count):
                for j in range(nt_count):
                    reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])
        
        # 检查是否存在左递归
        for i in range(nt_count):
            if reach[i][i]:
                return True, nt_list[i]
        return False, None
    
    def eliminate_direct_left_recursion(self, non_terminal):
        """
        消除直接左递归
        返回新的产生式
        """
        if not self.has_direct_left_recursion(non_terminal):
            return {non_terminal: self.productions.get(non_terminal, [])}
        
        # 分离左递归和非左递归产生式
        left_recursive = []
        non_left_recursive = []
        
        for prod in self.productions.get(non_terminal, []):
            if prod and prod[0] == non_terminal:
                left_recursive.append(prod[1:])  # 移除左递归部分
            else:
                non_left_recursive.append(prod)
        
        # 生成新的非终结符
        new_nt = non_terminal + "'"
        
        # 构建新产生式
        new_productions = {}
        
        # 非终结符的新产生式
        if non_left_recursive:
            new_productions[non_terminal] = [prod + new_nt for prod in non_left_recursive]
        else:
            new_productions[non_terminal] = [new_nt]  # 处理只有左递归的情况
        
        # 新非终结符的产生式
        new_productions[new_nt] = [prod + new_nt for prod in left_recursive]
        new_productions[new_nt].append('')  # 添加 ε 产生式
        
        return new_productions

# 测试示例
if __name__ == "__main__":
    # 测试直接左递归
    productions1 = {
        'E': ['E+T', 'T'],
        'T': ['T*F', 'F'],
        'F': ['(E)', 'id']
    }
    
    analyzer = GrammarAnalyzer(productions1)
    print("测试 1: 直接左递归")
    print(f"E 有直接左递归: {analyzer.has_direct_left_recursion('E')}")
    print(f"T 有直接左递归: {analyzer.has_direct_left_recursion('T')}")
    print(f"F 有直接左递归: {analyzer.has_direct_left_recursion('F')}")
    
    # 消除 E 的直接左递归
    new_prods = analyzer.eliminate_direct_left_recursion('E')
    print("\n消除 E 的直接左递归后:")
    for nt, prods in new_prods.items():
        print(f"{nt} → {' | '.join(prods if prods else ['ε'])}")
    
    # 测试间接左递归
    productions2 = {
        'S': ['Aa', 'b'],
        'A': ['Ac', 'Sd', '']
    }
    
    analyzer2 = GrammarAnalyzer(productions2)
    print("\n测试 2: 间接左递归")
    has_recursion, nt = analyzer2.has_left_recursion()
    print(f"是否存在左递归: {has_recursion}")
    if has_recursion:
        print(f"左递归非终结符: {nt}")