第74集：提取左公因子

学习目标

• 理解左公因子的概念和形成原因
• 掌握左公因子对自顶向下分析的影响
• 学会提取左公因子的方法
• 理解提取左公因子对预测分析的重要性
• 通过示例演练巩固提取左公因子的技巧

一、左公因子的概念

左公因子是上下文无关文法中的一种现象，指的是一个非终结符的多个产生式具有相同的前缀。

左公因子的定义

如果一个非终结符 A 有多个产生式：

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

其中 α 是一个非空符号串，βᵢ 是符号串，γ 是不以 α 开头的符号串，则称 α 是这些产生式的左公因子。

左公因子的示例

考虑以下文法：

S → if E then S else S | if E then S | other

这里，前两个产生式 S → if E then S else S 和 S → if E then S 具有左公因子 if E then S。

二、左公因子对自顶向下分析的影响

左公因子会导致自顶向下分析器在选择产生式时出现回溯，从而降低分析效率。

问题示例

考虑以下具有左公因子的文法：

S → if E then S else S | if E then S | other

当使用递归下降分析器分析输入串 if E then S 时，分析器会：

1. 调用 S 的分析函数
2. 尝试第一个产生式 S → if E then S else S
3. 匹配 if E then S 部分
4. 发现下一个 token 不是 else，回溯
5. 尝试第二个产生式 S → if E then S
6. 匹配成功

为什么会出现回溯？

自顶向下分析器在处理具有左公因子的产生式时，无法通过当前输入 token 确定应该选择哪个产生式，只能尝试一个，失败后回溯尝试另一个，这会显著降低分析效率。

三、提取左公因子的方法

提取左公因子是一种文法变换技术，通过改写产生式来消除左公因子，从而避免自顶向下分析中的回溯。

提取方法

对于具有左公因子的产生式：

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

其中 γ 不以 α 开头，可以改写为：

A → αA' | γ
A' → β₁ | β₂ | ... | βₙ

示例：提取条件语句的左公因子

原始文法：

S → if E then S else S | if E then S | other

提取左公因子后：

S → if E then S S' | other
S' → else S | ε

提取过程解析

1. 识别左公因子：if E then S
2. 分离具有左公因子的产生式和其他产生式
3. 应用提取规则：
   • S → if E then S S'（α 是 if E then S）
   • S' → else S | ε（β₁ 是 else S，β₂ 是 ε）

四、提取左公因子的步骤

提取左公因子的过程可以分为以下步骤：

1. 识别左公因子：找出一个非终结符的多个产生式的最长公共前缀
2. 分离产生式：将具有左公因子的产生式与其他产生式分开
3. 构造新产生式：
   • 为原非终结符创建一个新的产生式，使用左公因子作为前缀，后跟一个新的非终结符
   • 为新非终结符创建产生式，右部为原产生式去掉左公因子后的部分
4. 重复处理：对新产生式继续提取左公因子，直到没有左公因子为止

五、示例演练：提取左公因子

示例 1：简单条件语句

原始文法：

S → if E then S else S | if E then S | other

提取过程：

1. 识别左公因子：if E then S
2. 分离产生式：
   • 具有左公因子的产生式：if E then S else S, if E then S
   • 其他产生式：other
3. 构造新产生式：
   • S → if E then S S' | other
   • S' → else S | ε

结果文法：

S → if E then S S' | other
S' → else S | ε

示例 2：赋值语句

原始文法：

A → id = E | id [ E ] = E | id . id = E

提取过程：

1. 识别左公因子：id
2. 分离产生式：所有产生式都具有左公因子 id
3. 构造新产生式：
   • A → id A'
   • A' → = E | [ E ] = E | . id = E

结果文法：

A → id A'
A' → = E | [ E ] = E | . id = E

示例 3：复杂表达式

原始文法：

E → + T E' | - T E' | * T E' | / T E' | T
E' → + T E' | - T E' | * T E' | / T E' | ε

提取过程：

1. 对于 E 的产生式：

   • 识别左公因子：前四个产生式没有公共左公因子，因为它们的第一个符号分别是 +, -, *, /
   • 所以 E 的产生式保持不变

2. 对于 E' 的产生式：

   • 同样，前四个产生式没有公共左公因子
   • 所以 E' 的产生式保持不变

结果文法：与原文法相同

示例 4：多层左公因子

原始文法：

A → a b c d | a b c e | a b f | g

提取过程：

1. 第一次提取：

   • 左公因子：a b
   • 分离产生式：a b c d, a b c e, a b f 和 g
   • 构造新产生式：
     • A → a b A' | g
     • A' → c d | c e | f

2. 第二次提取（对 A'）：

   • 左公因子：c
   • 分离产生式：c d, c e 和 f
   • 构造新产生式：
     • A' → c A'' | f
     • A'' → d | e

结果文法：

A → a b A' | g
A' → c A'' | f
A'' → d | e

六、提取左公因子与预测分析

提取左公因子是构造 LL(1) 分析表的必要步骤之一，它与消除左递归一起，确保文法满足 LL(1) 条件。

LL(1) 文法的条件

一个文法是 LL(1) 的，当且仅当对于每个非终结符 A 和每个终结符 a，最多存在一个产生式 A → α 使得 a 在 FIRST(α) 中，或者当 α ⇒* ε 时，a 在 FOLLOW(A) 中。

提取左公因子对 FIRST 集的影响

提取左公因子可以确保对于每个非终结符 A 和每个终结符 a，最多只有一个产生式 A → α 使得 a 在 FIRST(α) 中，从而避免 LL(1) 分析表中的多重入口。

示例：LL(1) 分析表构造

考虑以下文法：

原文法：

S → if E then S else S | if E then S | other

提取左公因子后：

S → if E then S S' | other
S' → else S | ε

对于 S 的产生式：

• FIRST(if E then S S') = {if}
• FIRST(other) = {other}

对于 S' 的产生式：

• FIRST(else S) = {else}
• FIRST(ε) = ∅，但 FOLLOW(S') 包含 $（输入结束符）

这样，LL(1) 分析表中就不会出现多重入口。

七、提取左公因子的注意事项

1. 保持语言不变：提取左公因子后，文法应生成与原文法相同的语言
2. 注意 ε 产生式：提取左公因子可能会引入 ε 产生式，需要确保分析器能够正确处理
3. 处理多层左公因子：有时需要多次提取左公因子，直到没有左公因子为止
4. 结合消除左递归：提取左公因子通常与消除左递归一起使用，以确保文法满足 LL(1) 条件
5. 考虑语义动作：如果产生式带有语义动作，提取左公因子时需要保持语义动作的正确性

八、代码示例：提取左公因子

下面是一个简单的 Python 代码，用于检测和提取左公因子：

class GrammarTransformer:
    def __init__(self, productions):
        """
        初始化文法转换器
        productions: 字典，键为非终结符，值为产生式右部列表
        """
        self.productions = productions
    
    def find_common_prefix(self, strings):
        """
        找到字符串列表的最长公共前缀
        """
        if not strings:
            return ""
        
        prefix = strings[0]
        for s in strings[1:]:
            while not s.startswith(prefix):
                prefix = prefix[:-1]
                if not prefix:
                    return ""
        return prefix
    
    def has_left_factor(self, non_terminal):
        """
        检测非终结符是否具有左公因子
        """
        prods = self.productions.get(non_terminal, [])
        if len(prods) < 2:
            return False
        
        # 找到所有产生式的最长公共前缀
        prefix = self.find_common_prefix(prods)
        return len(prefix) > 0
    
    def extract_left_factor(self, non_terminal):
        """
        提取非终结符的左公因子
        返回新的产生式
        """
        prods = self.productions.get(non_terminal, [])
        if len(prods) < 2:
            return {non_terminal: prods}
        
        # 找到最长公共前缀
        prefix = self.find_common_prefix(prods)
        if not prefix:
            return {non_terminal: prods}
        
        # 分离具有左公因子和不具有左公因子的产生式
        with_prefix = []
        without_prefix = []
        
        for prod in prods:
            if prod.startswith(prefix):
                with_prefix.append(prod[len(prefix):])
            else:
                without_prefix.append(prod)
        
        # 生成新的非终结符
        new_nt = non_terminal + "'"
        
        # 构建新产生式
        new_productions = {}
        
        # 非终结符的新产生式
        new_prods = []
        if with_prefix:
            new_prods.append(prefix + new_nt)
        new_prods.extend(without_prefix)
        new_productions[non_terminal] = new_prods
        
        # 新非终结符的产生式
        new_productions[new_nt] = with_prefix
        
        return new_productions
    
    def transform(self):
        """
        转换整个文法，提取所有左公因子
        """
        result = {}
        for nt in self.productions:
            transformed = self.extract_left_factor(nt)
            result.update(transformed)
        return result

# 测试示例
if __name__ == "__main__":
    # 测试示例 1：条件语句
    productions1 = {
        'S': ['if E then S else S', 'if E then S', 'other']
    }
    
    transformer = GrammarTransformer(productions1)
    print("测试 1: 条件语句")
    print("原文法:")
    for nt, prods in productions1.items():
        print(f"{nt} → {' | '.join(prods)}")
    
    result1 = transformer.transform()
    print("\n提取左公因子后:")
    for nt, prods in result1.items():
        print(f"{nt} → {' | '.join(prods)}")
    
    # 测试示例 2：赋值语句
    productions2 = {
        'A': ['id = E', 'id [ E ] = E', 'id . id = E']
    }
    
    transformer2 = GrammarTransformer(productions2)
    print("\n测试 2: 赋值语句")
    print("原文法:")
    for nt, prods in productions2.items():
        print(f"{nt} → {' | '.join(prods)}")
    
    result2 = transformer2.transform()
    print("\n提取左公因子后:")
    for nt, prods in result2.items():
        print(f"{nt} → {' | '.join(prods)}")
    
    # 测试示例 3：多层左公因子
    productions3 = {
        'A': ['a b c d', 'a b c e', 'a b f', 'g']
    }
    
    transformer3 = GrammarTransformer(productions3)
    print("\n测试 3: 多层左公因子")
    print("原文法:")
    for nt, prods in productions3.items():
        print(f"{nt} → {' | '.join(prods)}")
    
    # 第一次提取
    result3 = transformer3.transform()
    print("\n第一次提取左公因子后:")
    for nt, prods in result3.items():
        print(f"{nt} → {' | '.join(prods)}")
    
    # 第二次提取
    transformer4 = GrammarTransformer(result3)
    result4 = transformer4.transform()
    print("\n第二次提取左公因子后:")
    for nt, prods in result4.items():
        print(f"{nt} → {' | '.join(prods)}")