第72集：上下文无关文法回顾

学习目标

掌握上下文无关文法的基本概念和组成部分
理解产生式规则的表示和应用
掌握推导的基本概念和方法（最左推导、最右推导）
理解语法树的构建过程
认识歧义性问题及其解决方法

一、上下文无关文法的基本概念

上下文无关文法（Context-Free Grammar, CFG）是描述程序设计语言语法的有力工具，它由美国语言学家 Noam Chomsky 在 1956 年提出，是形式语言理论的重要组成部分。

文法的定义

一个上下文无关文法 G 由以下四个部分组成：

终结符集合（Terminal Symbols）：记为 T，是语言的基本符号，对应词法分析器生成的 Token
非终结符集合（Non-Terminal Symbols）：记为 N，是表示语法结构的符号
开始符号（Start Symbol）：记为 S，是文法的初始符号，属于 N
产生式集合（Productions）：记为 P，是形如 A → α 的规则，其中 A ∈ N，α ∈ (N ∪ T)*

示例：简单算术表达式文法

G = (N, T, S, P)
其中：
N = {E, T, F}  // 非终结符：表达式、项、因子
T = {+, *, (, ), id}  // 终结符：运算符、括号、标识符
S = E  // 开始符号：表达式
P = {  // 产生式集合
    E → E + T
    E → T
    T → T * F
    T → F
    F → (E)
    F → id
}

二、产生式规则

产生式是上下文无关文法的核心，它定义了非终结符如何被替换为其他符号串。

产生式的表示

产生式的一般形式为：

A → α

其中：

A 是一个非终结符（左部）
α 是由终结符和非终结符组成的符号串（右部）

产生式的简写

当一个非终结符有多个产生式时，可以简写为：

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

例如，上述算术表达式文法的产生式可以简写为：

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

产生式的应用

产生式的应用是指用产生式的右部替换左部的过程。例如，应用产生式 E → E + T 可以将 E 替换为 E + T。

三、推导过程

推导是通过应用产生式规则，从开始符号逐步替换为终结符串的过程。

直接推导

如果存在产生式 A → α，并且有符号串 β = γAδ，那么应用该产生式后得到 β' = γαδ，记为 β ⇒ β'，称为直接推导。

推导序列

如果存在一个直接推导序列 β₀ ⇒ β₁ ⇒ ... ⇒ βₙ，那么称从 β₀ 可以推导出 βₙ，记为 β₀ ⇒* βₙ。

最左推导与最右推导

最左推导（Leftmost Derivation）

在每一步推导中，总是选择最左边的非终结符进行替换。记为 β₀ ⇒ₗₘ βₙ。

示例：对于表达式 id + id * id 的最左推导

E ⇒ₗₘ E + T ⇒ₗₘ T + T ⇒ₗₘ F + T ⇒ₗₘ id + T ⇒ₗₘ id + T * F ⇒ₗₘ id + F * F ⇒ₗₘ id + id * F ⇒ₗₘ id + id * id

最右推导（Rightmost Derivation）

在每一步推导中，总是选择最右边的非终结符进行替换。记为 β₀ ⇒ᵣₘ βₙ。

示例：对于表达式 id + id * id 的最右推导

E ⇒ᵣₘ E + T ⇒ᵣₘ E + T * F ⇒ᵣₘ E + T * id ⇒ᵣₘ E + F * id ⇒ᵣₘ E + id * id ⇒ᵣₘ T + id * id ⇒ᵣₘ F + id * id ⇒ᵣₘ id + id * id

句型与句子

句型：如果 S ⇒* α，其中 α ∈ (N ∪ T)*，则称 α 是文法 G 的一个句型
句子：如果 S ⇒* α，其中 α ∈ T*（仅由终结符组成），则称 α 是文法 G 的一个句子

四、语法树

语法树（Syntax Tree）是推导过程的图形表示，它直观地展示了句子的语法结构。

语法树的定义

语法树是一棵有向树，满足以下条件：

根节点：标记为文法的开始符号 S
内部节点：标记为非终结符
叶节点：标记为终结符或 ε（空串）
边：如果一个内部节点 A 有子节点 X₁, X₂, ..., Xₙ，则存在产生式 A → X₁X₂...Xₙ

语法树的构建

以表达式 id + id * id 为例，其语法树构建过程如下：

    E
   / | \
  E  +  T
  |     / | \
  T    T  *  F
  |    |     |
  F    F     id
  |    |
  id   id

语法树与推导的关系

每棵语法树对应多个推导过程（最左推导、最右推导等）
不同的推导过程可能对应同一棵语法树
语法树忽略了推导的顺序，只关注最终的结构

短语、直接短语和句柄

短语：语法树中某个子树的叶节点组成的符号串
直接短语：语法树中某个简单子树（高度为2）的叶节点组成的符号串
句柄：最左直接短语，是自底向上分析中的归约对象

示例：对于表达式 id + id * id

短语：id, id, id, id * id, id + id * id
直接短语：id, id, id, id * id
句柄：最左边的 id

五、歧义性问题

歧义性是上下文无关文法的一个重要问题，它会导致同一个句子有多个不同的语法树。

歧义性的定义

如果一个文法 G 存在至少一个句子，该句子有两棵或两棵以上不同的语法树，则称 G 是歧义的（Ambiguous）。

歧义性示例

考虑以下表达式文法：

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

对于句子 id + id * id，存在两棵不同的语法树：

语法树 1（先计算加法）：

    E
   / | \
  E  +  E
  |     / | \
  id   E  *  E
       |     |
       id    id

语法树 2（先计算乘法）：

    E
   / | \
  E  *  E
  / | \
 E  +  E  |
 |     |  id
 id    id

歧义性的问题

语义不明确：不同的语法树可能对应不同的语义解释
分析困难：歧义性会导致语法分析器无法确定正确的分析路径
代码生成问题：不同的语法树可能生成不同的目标代码

歧义性的解决方法

重写文法：通过引入新的非终结符和产生式，消除歧义性
优先级规则：为运算符指定优先级，解决运算顺序问题
结合性规则：为运算符指定结合性（左结合或右结合），解决连续运算的顺序问题

示例：消除上述表达式文法的歧义性

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

这样，id + id * id 就只有唯一的语法树，对应先计算乘法后计算加法的语义。

六、上下文无关文法的分类

根据 Chomsky 层级，上下文无关文法属于 2 型文法，位于正则文法（3 型）和上下文有关文法（1 型）之间。

Chomsky 层级

0 型文法（无限制文法）：最一般的文法，没有任何限制
1 型文法（上下文有关文法）：产生式形式为 αAβ → αγβ，其中 γ ≠ ε
2 型文法（上下文无关文法）：产生式形式为 A → α，其中 A 是单个非终结符
3 型文法（正则文法）：产生式形式为 A → aB 或 A → a（右线性），或 A → Ba 或 A → a（左线性）

上下文无关文法的表达能力

可以描述嵌套结构（如括号匹配）
可以描述递归结构（如表达式、函数定义）
无法描述需要上下文信息的结构（如变量声明与使用的一致性）

七、代码示例：文法的表示与推导

下面是一个使用 Python 表示上下文无关文法并进行推导的简单示例：

class Grammar:
    def __init__(self, non_terminals, terminals, start_symbol, productions):
        self.non_terminals = non_terminals  # 非终结符集合
        self.terminals = terminals          # 终结符集合
        self.start_symbol = start_symbol    # 开始符号
        self.productions = productions      # 产生式字典：{非终结符: [产生式右部列表]}
    
    def get_productions(self, symbol):
        """获取指定非终结符的所有产生式"""
        return self.productions.get(symbol, [])
    
    def is_non_terminal(self, symbol):
        """判断是否为非终结符"""
        return symbol in self.non_terminals
    
    def is_terminal(self, symbol):
        """判断是否为终结符"""
        return symbol in self.terminals
    
    def leftmost_derivation(self, target):
        """最左推导示例（简化版）"""
        print(f"最左推导: {self.start_symbol} ⇒* {target}")
        # 实际实现需要更复杂的算法
        # 这里仅作为示例
        print("E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ id + T ⇒ id + T * F ⇒ id + F * F ⇒ id + id * F ⇒ id + id * id")
    
    def rightmost_derivation(self, target):
        """最右推导示例（简化版）"""
        print(f"最右推导: {self.start_symbol} ⇒* {target}")
        # 实际实现需要更复杂的算法
        # 这里仅作为示例
        print("E ⇒ E + T ⇒ E + T * F ⇒ E + T * id ⇒ E + F * id ⇒ E + id * id ⇒ T + id * id ⇒ F + id * id ⇒ id + id * id")

# 定义算术表达式文法
if __name__ == "__main__":
    # 非终结符
    non_terminals = {'E', 'T', 'F'}
    
    # 终结符
    terminals = {'+', '*', '(', ')', 'id'}
    
    # 开始符号
    start_symbol = 'E'
    
    # 产生式
    productions = {
        'E': ['E + T', 'T'],
        'T': ['T * F', 'F'],
        'F': ['(E)', 'id']
    }
    
    # 创建文法对象
    grammar = Grammar(non_terminals, terminals, start_symbol, productions)
    
    # 测试
    print("文法信息:")
    print(f"非终结符: {grammar.non_terminals}")
    print(f"终结符: {grammar.terminals}")
    print(f"开始符号: {grammar.start_symbol}")
    print("产生式:")
    for nt, prods in grammar.productions.items():
        print(f"{nt} → {' | '.join(prods)}")
    
    print("\n推导示例:")
    target = "id + id * id"
    grammar.leftmost_derivation(target)
    print()
    grammar.rightmost_derivation(target)

八、自测题

上下文无关文法由哪四个部分组成？
什么是产生式规则？请举例说明。
最左推导和最右推导的区别是什么？
什么是语法树？它与推导有什么关系？
什么是歧义性文法？如何解决歧义性问题？
请为以下句子构建语法树：(id + id) * id
上下文无关文法在 Chomsky 层级中属于第几型文法？它与正则文法有什么区别？

九、总结与展望

本集回顾了上下文无关文法的基本概念、产生式规则、推导过程、语法树构建以及歧义性问题。上下文无关文法是语法分析的基础，它为我们提供了一种形式化的方法来描述程序设计语言的语法结构。

在接下来的几集中，我们将学习：

消除左递归：解决自顶向下分析中的左递归问题
提取左公因子：解决自顶向下分析中的回溯问题
递归下降分析器：一种自顶向下的语法分析方法
LL(1) 分析表构造：基于预测的自顶向下分析算法

这些内容将帮助我们理解和实现各种语法分析器，为构建完整的编译器打下坚实的基础。

十、参考资料

《编译原理》（龙书）- Alfred V. Aho 等
《现代编译原理》（虎书）- Andrew W. Appel
《形式语言与自动机》- John E. Hopcroft 等
《编译器设计》- Keith D. Cooper 等
上下文无关文法 - 维基百科