上下文无关文法（CFG）与句法分析

小象实战讲义 · 自然语言处理

在前面的学习中，我们主要关注了词的表示（向量化）和文本的概率模型。然而，自然语言不仅仅是词的集合，它拥有内在的结构。一个句子的含义不仅取决于其中的单词，更取决于这些单词如何通过语法规则组合在一起。本节课，我们将开启对语言结构——句法的探索。我们将学习上下文无关文法（Context-Free Grammar, CFG） 这一形式化工具，它能够精确地描述句子的构成规则，并为我们后续学习概率句法分析和更复杂的语言模型奠定基础。

💡 核心导读

• 什么是上下文无关文法？ 理解 CFG 作为一种形式化语法，如何用四元组 (N, Σ, R, S) 来定义一门语言。
• 从规则到句法树： 学习如何根据 CFG 的规则，将一个句子“解析”成一棵结构化的句法树，这个过程称为 Parsing。
• 歧义性挑战： 认识到自然语言的复杂性——同一个句子可能对应多棵合法的句法树，即存在结构歧义。
• 从 CFG 到 PCFG： 初步了解如何为 CFG 规则赋予概率，从而量化不同句法树的可能性，为解决歧义问题铺路。

1. 句法分析：为什么需要结构？

在自然语言处理中，将文本转化为向量是许多任务的基础。然而，仅仅将句子视为词的序列（或词袋）会丢失大量关键信息。例如：

• “狗咬人”和“人咬狗”的词袋表示可能相似，但含义截然相反。
• “我看见了一个拿着望远镜的女孩”这句话中，“拿着望远镜”是修饰“女孩”还是“看见”这个动作？不同的理解对应不同的句法结构。

句法分析（Parsing） 的目标正是揭示这种内在结构。它通过一套预定义的语法规则，将线性的词序列组织成层次化的树状结构，明确各个成分（如名词短语、动词短语）之间的修饰和组合关系。这种结构化的表示是理解句子语义、进行机器翻译、信息抽取等高级任务的重要前提。

2. 上下文无关文法（CFG）的形式化定义

上下文无关文法是描述语言结构最基础、最重要的形式化工具之一。它之所以称为“上下文无关”，是因为每条重写规则的应用只取决于规则左边的非终结符本身，而不依赖于它周围的上下文。

一个 CFG 由一个四元组 $(N, \Sigma, R, S)$ 定义：

1. $N$：非终结符（Non-terminal Symbols）集合

   • 这些符号代表句子中的语法成分或范畴，它们不会最终出现在生成的句子中，而是中间变量。
   • 例如：S（句子），NP（名词短语），VP（动词短语），PP（介词短语），DT（限定词），NN（名词），VB（动词）等。

2. $\Sigma$：终结符（Terminal Symbols）集合

   • 这些符号是语言中实际的词汇，是句法树的“叶子节点”。
   • 例如："the", "dog", "ate", "bone", "with" 等。

3. $R$：规则（Rules）或产生式（Productions）集合

   • 每条规则定义了如何将一个非终结符重写（展开）为一串由终结符和非终结符组成的序列。
   • 形式为：$X \rightarrow Y_1 Y_2 ... Y_n$，其中 $X \in N$，$Y_i \in (N \cup \Sigma)$。
   • 例如：S -> NP VP， NP -> DT NN， NN -> "dog"。

4. $S$：开始符号（Start Symbol）

   • 这是一个特殊的非终结符，代表整个句子的起点。通常就是 S。

类比理解：可以将非终结符（$N$）视为编程中的“变量”，将终结符（$\Sigma$）视为具体的“值”。语法规则（$R$）则定义了如何将这些变量逐步替换、展开，最终得到由具体值（单词）组成的句子。

3. CFG 实例：一个英语片段语法

让我们通过一个具体的例子来理解 CFG 如何工作。以下定义了一个简化的英语片段语法：

• 非终结符 $N$: {S, NP, VP, PP, DT, NN, VB, IN, ...}
• 终结符 $\Sigma$: {"the", "a", "dog", "cat", "man", "woman", "telescope", "saw", "ate", "sleeps", "with", "in", …}
• 开始符号 $S$: S
• 规则 $R$ (部分):

  S   -> NP VP          # 句子由名词短语和动词短语构成
  NP  -> DT NN          # 名词短语由限定词和名词构成
  NP  -> NP PP          # 名词短语后可以接介词短语进行修饰
  VP  -> VB             # 动词短语可以就是一个动词（不及物）
  VP  -> VB NP          # 动词短语由动词和名词短语构成（及物）
  VP  -> VP PP          # 动词短语后可以接介词短语进行修饰
  PP  -> IN NP          # 介词短语由介词和名词短语构成
  DT  -> "the" | "a"    # 限定词
  NN  -> "dog" | "cat" | "man" | "woman" | "telescope"
  VB  -> "saw" | "ate" | "sleeps"
  IN  -> "with" | "in"

3.1 生成句子与最左推导

使用 CFG 可以“生成”合法的句子。过程从开始符号 S 出发，不断选择匹配的规则，用规则的右边替换左边的非终结符，直到所有符号都变为终结符。一种标准的展开方式是最左推导（Leftmost Derivation），即每次都替换当前字符串中最左边的非终结符。

以生成句子 "the dog sleeps" 为例：

1. S (起始)
2. NP VP (应用规则 S -> NP VP)
3. DT NN VP (应用规则 NP -> DT NN，替换最左边的 NP)
4. "the" NN VP (应用规则 DT -> "the")
5. "the" "dog" VP (应用规则 NN -> "dog")
6. "the" "dog" VB (应用规则 VP -> VB)
7. "the" "dog" "sleeps" (应用规则 VB -> "sleeps")

3.2 句法树（Parse Tree）

推导过程可以更直观地表示为一棵句法树。叶子节点是终结符（单词），内部节点是非终结符（语法范畴），子节点由父节点通过一条语法规则展开而来。

句子 "the dog sleeps" 的句法树如下：

        S
       / \
      NP   VP
     /  \    \
    DT   NN   VB
    |    |    |
   the  dog sleeps

这棵树清晰地展示了句子结构：一个名词短语 NP (“the dog”) 作为主语，加上一个动词短语 VP (“sleeps”) 作为谓语。

4. 句法歧义：一个关键挑战

自然语言是充满歧义的。CFG 在解析句子时，一个核心挑战就是结构歧义：同一个词序列可能对应多棵符合语法的句法树，导致不同的语义解释。

经典的例子是介词短语附着歧义（Prepositional Phrase Attachment Ambiguity）。考虑句子：

The man saw the dog with the telescope.

这个句子至少有两种合理的句法分析：

解析树1（PP附着于NP）：理解为“男人看见了那只带着望远镜的狗”。

          S
         / \
        NP        VP
       /  \      /  \
      DT   NN   VB    NP
      |    |    |    /  \
     The  man  saw NP    PP
                  /  \   / \
                 DT  NN IN NP
                 |   |   | / \
                the dog with DT NN
                            |  |
                           the telescope

在这种解析中，介词短语 "with the telescope" 修饰的是紧邻的名词短语 "the dog"。

解析树2（PP附着于VP）：理解为“男人用望远镜看见了那只狗”。

          S
         / \
        NP        VP
       /  \      /  \
      DT   NN   VP    PP
      |    |   /  \   / \
     The  man VB   NP IN NP
               |   / \  | / \
              saw DT NN with DT NN
                  |  |      |  |
                 the dog   the telescope

在这种解析中，介词短语 "with the telescope" 修饰的是动词短语 "saw the dog"，表示动作的方式。

这两种解析在语法上都是合法的，但语义不同。人类会根据常识（“狗通常不会拿望远镜”）更倾向于第二种解释。对于计算机而言，如何从多个可能的解析中选择最合理的一个，是句法分析必须解决的问题。这引出了我们对概率上下文无关文法（PCFG） 的需求——通过为每条语法规则赋予概率，我们可以计算每棵句法树的整体概率，从而选择概率最高的那棵作为最可能的解析。

5. 从 CFG 到 PCFG 的展望

基本的 CFG 无法区分上述两种解析的优劣。为了解决歧义问题，我们引入概率上下文无关文法（Probabilistic CFG, PCFG）。在 PCFG 中，每一条规则 $X \rightarrow \gamma$ 都关联一个概率 $q(X \rightarrow \gamma)$，表示在给定父节点为 $X$ 的条件下，展开为 $\gamma$ 的可能性。所有以 $X$ 为左部的规则概率之和为1。

一棵句法树 $t$ 的概率是其所有应用规则概率的乘积： $$P(t) = \prod_{i=1}^{n} q(\text{rule}_i)$$

对于有歧义的句子，我们可以分别计算每棵候选句法树的概率，选择概率最大的作为输出。概率 $q$ 通常从已标注句法树的大规模语料库（树库）中统计估计得到。这样，PCFG 就能将句法分析从一个纯粹的“是否合法”的判断，转变为一个“可能性多大”的量化评估，为消歧提供了数学基础。我们将在下一节深入探讨 PCFG 及其高效的解析算法（如 CKY 算法）。

📝 动手练一练

1. 概念辨析：根据本节定义的简化英语 CFG，判断以下推导过程或陈述是否正确。 a) 从开始符号 S 出发，应用规则 S -> NP VP 和 NP -> DT NN 后，得到的字符串是 DT NN VP。 b) 终结符（如 "dog"）可以出现在句法树的内部节点上。 c) 句子 "the cat ate" 在该语法下是合法的。 d) 结构歧义只发生在句子特别长和复杂的时候。

2. 手动解析：使用本节给出的简化 CFG 规则，尝试为句子 "a woman saw a dog" 绘制一棵句法树。写出对应的最左推导步骤。

          S
         / \
        NP        VP
       /  \      /  \
      DT   NN   VB    NP
      |    |    |    /  \
      a  woman  saw DT   NN
                   |     |
                   a    dog

本章小结

本节我们引入了自然语言处理中分析句子结构的基础工具——上下文无关文法（CFG）。我们学习了其形式化定义 (N, Σ, R, S)，并通过实例理解了如何用 CFG 生成句子、进行最左推导以及构建句法树。更重要的是，我们认识到了自然语言句法分析的核心挑战：结构歧义。同一个句子可能对应多棵合法的句法树，这为单纯基于规则的 CFG 带来了选择困难。为了解决这个问题，我们预览了概率上下文无关文法（PCFG）的基本思想，即通过为语法规则赋予概率来量化不同解析的可能性，为下一节深入学习 PCFG 及高效解析算法做好了准备。

📋 行动清单

• 理解 CFG 四元组中每个元素的含义，并能用自己的话解释“非终结符”和“终结符”的区别。
• 给定一个简单的 CFG 和句子，能够手动写出其最左推导步骤或绘制句法树。
• 明确“结构歧义”的概念，并能用“介词短语附着歧义”的例子说明其如何导致不同的语义理解。

—— 小象教研组