2_上下文无关语言2.1.ZH解释

这段话是本章的引言，旨在承上启下。它首先回顾了前一章（第 1 章）的核心内容，即有限自动机（Finite Automata, FA）和正则表达式（Regular Expressions, RE）。这两个工具是计算理论中用于描述和识别一类被称为正则语言（Regular Languages）的强大工具。

“不同但等效”是一个关键点。有限自动机是一种计算模型，像一台简单的机器，通过状态转移来“读取”并判断一个字符串是否属于某个语言。而正则表达式是一种代数表达式，是一种描述性的文本模式，用来定义一个字符串集合。尽管它们的形式完全不同（一个是机器模型，一个是代数表达式），但它们所能描述的语言集合是完全相同的，这个集合就是正则语言。这就是“等效”的含义。这个等价性是计算理论中的一个基本且重要的结论。

接着，段落指出了有限自动机和正则表达式的局限性。虽然它们可以描述很多有用的语言（例如，电子邮件地址的格式、特定格式的日期等），但它们的能力是有限的。存在一些结构上看起来很简单，但有限自动机无法处理的语言。

这里给出的经典例子是语言 $L = \left\{0^{n} 1^{n} \mid n \geq 0\right\}$。这个语言包含的字符串是由任意数量（包括零）的 '0' 后面跟着相同数量的 '1' 组成的。例如，空字符串 $\varepsilon$ (当 $n=0$ 时)、"01" (当 $n=1$ 时)、"0011" (当 $n=2$ 时)、"000111" (当 $n=3$ 时) 等都属于这个语言。而 "011"、"001"、"10" 等则不属于。

为什么有限自动机无法识别这个语言呢？直观地理解，有限自动机的“记忆力”是有限的。它的记忆力体现在它的状态数量上。要判断一个字符串是否属于 $\left\{0^{n} 1^{n} \mid n \geq 0\right\}$，机器在读完所有的 '0' 之后，必须准确地记住 '0' 的数量 $n$，以便在接下来读取 '1' 时进行匹配。但是，$n$ 可以是任意大的非负整数。一个只有有限个状态的机器，无法存储一个可能无限增长的计数值。这就是有限自动机的根本局限性，这个局限性通常用泵引理（Pumping Lemma for Regular Languages）来形式化地证明。

因此，这段引言的目的是告诉我们，现有的工具（有限自动机和正则表达式）已经不够用了，我们需要一种更强大的方法来描述像 $\left\{0^{n} 1^{n} \mid n \geq 0\right\}$ 这样更复杂的语言。这为引入本章的主角——上下文无关文法——埋下了伏笔。

这段话正式引入了本章的核心概念——上下文无关文法（Context-Free Grammar, CFG）。在上一段指出有限自动机的局限性之后，这里直接给出了解决方案。

“更强大的语言描述方法”是对上下文无关文法的一个定位。这里的“强大”是形式化的，意味着由上下文无关文法所能描述的语言集合（即上下文无关语言）是正则语言集合的一个超集。也就是说，所有正则语言都可以用上下文无关文法来描述，但上下文无关文法还能描述一些非正则语言，比如上一段提到的 $\left\{0^{n} 1^{n} \mid n \geq 0\right\}$。

接下来解释了上下文无关文法之所以“强大”的关键在于它能够描述“递归结构”。递归（Recursion）是指一个结构或规则的定义中包含了它自身的引用。在语言中，递归结构表现为“一个短语类型可以包含同类型的更小的短语”。例如，一个算术表达式可以由两个更小的算术表达式通过加号连接而成。 ( (3 + 4) * 5 ) 就是一个例子，外层的表达式包含了内层的 (3 + 4)。这种能够自我嵌套的特性，正是上下文无关文法所擅长描述的，也是有限自动机无法处理的。

最后，段落提到了上下文无关文法的实用性——“在各种应用中都很有用”。这表明上下文无关文法不仅仅是一个理论工具，它在实际中有着广泛的应用。这为后面详细介绍其应用场景（如人类语言学和编程语言编译）做了引子。

这段话介绍了上下文无关文法的第一个重要应用领域：自然语言处理（Natural Language Processing, NLP），特别是其在语言学中的起源。

“最初用于研究人类语言”点明了其历史背景。在计算机科学领域之外，语言学家（如诺姆·乔姆斯基）为了形式化地描述人类语言的语法结构，发展了这套理论。

接下来，段落解释了为什么上下文无关文法适合描述人类语言。人类语言的句子不是单词的随意堆砌，而是具有层次化的语法结构。句子由短语构成，短语又由更小的短语或单词构成。这里提到了几个基本的语法单位：“名词”、“动词”、“介词”以及它们构成的“短语”（如名词短语、动词短语）。

核心思想在于这些短语之间的“递归”关系。“名词短语可能出现在动词短语中”，例如，在动词短语“sees the boy”（看见那个男孩）中，“the boy”是一个名词短语。“反之亦然”指的是动词短语也可能出现在名词短语中，虽然这种情况在英语中不那么直接，但可以通过从句等形式实现，例如名词短语“the man who runs fast”（跑得快的男人）中，"who runs fast"起到了修饰作用，其核心是动词"runs"。更典型的例子是，一个名词短语可以包含另一个名词短语，如“the corner of the room”（房间的角落），其中“the room”是内嵌在更大的名词短语里的。

“上下文无关文法帮助我们组织和理解这些关系”是对其作用的总结。通过一套形式化的规则，语言学家可以精确地描述哪些句子是合法的，哪些是不合法的，并且能够揭示句子的内部结构。这种结构化的分析对于理解语言、机器翻译和人机对话等任务至关重要。

这段话介绍了上下文无关文法在计算机科学领域最核心的应用：编程语言。

“编程语言的规范和编译”点出了两个关键环节。

1. 规范 (Specification): 上下文无关文法为编程语言提供了一个精确、无歧义的语法定义。这就像一部语言的“法典”。当我们学习一门新的编程语言（如 Python, Java）时，官方文档中描述的语法规则（比如 if 语句的格式，函数定义的格式）就是基于其上下文无关文法的。这为所有使用者和开发者提供了统一的标准。
2. 编译 (Compilation): 编译是将人类可读的源代码（高级语言）转换成机器可执行的代码（低级语言）的过程。上下文无关文法在编译过程中扮演着至关重要的角色。

段落接着详细阐述了文法在编译过程中的作用。编译器或解释器的设计者首先需要得到该语言的上下文无关文法。这是设计的第一步。

编译器和解释器中有一个核心组件叫解析器（Parser）。解析器的任务是读取源代码字符串，并根据文法规则来分析其语法结构，判断代码是否符合语法。这个过程称为解析（Parsing）或语法分析。如果语法正确，解析器会生成一个数据结构来表示代码的层次化意义，这个结构通常是抽象语法树（Abstract Syntax Tree, AST），它捕捉了代码的运算顺序、依赖关系等。这个“提取程序的意义”的过程是后续生成可执行代码或进行解释执行的基础。

例如，对于代码 a = b + c d，解析器会根据文法中定义的运算符优先级，生成一棵树，表明应该先计算 c d，然后将其结果与 b 相加，最后再将总结果赋值给 a。没有文法和解析器，编译器就无法理解这段代码的真正意图。

最后一段强调了文法的工具价值。“一旦有了上下文无关文法”，构建解析器就变得有章可循。存在许多成熟的理论和算法（如 LL 解析、LR 解析）来指导如何手动编写一个解析器。更方便的是，存在一些“解析器生成器”（Parser Generator）工具，例如 YACC (Yet Another Compiler-Compiler) 或 Bison。你只需要把语言的上下文无关文法作为输入提供给这些工具，它们就能自动生成对应的解析器代码。这极大地简化了编译器和解释器的开发工作。

这段话是整个引言的总结，并预告了本章即将展开的主要内容。

“与上下文无关文法相关的语言集合称为上下文无关语言 (Context-Free Languages, CFLs)。” 这句话给出了一个核心定义。就像由正则表达式描述的语言集合被称为正则语言一样，所有能够被某一个上下文无关文法生成的语言，其集合被称为上下文无关语言。这是一个新的、更庞大的语言类别。

“它们包括所有正则语言以及许多额外的语言。” 这句话阐明了上下文无关语言和正则语言之间的关系。正则语言是上下文无关语言的真子集（Proper Subset）。这意味着：

1. 任何一个正则语言，都必定是一个上下文无关语言。（我们总能为它找到一个上下文无关文法来描述）。
2. 存在一些上下文无关语言，它们不是正则语言（比如 $\left\{0^{n} 1^{n} \mid n \geq 0\right\}$）。

这在形式上确认了上下文无关文法是比有限自动机或正则表达式“更强大”的描述工具。

接下来是本章的内容路线图：

1. “给出上下文无关文法的形式化定义”：前面都是直观描述，接下来要用数学的语言精确定义什么是文法、什么是推导等。
2. “研究上下文无关语言的性质”：这包括探讨这类语言在并、交、补等运算下的封闭性，以及它们的其他特性（例如，是否存在泵引理）。
3. “介绍下推自动机 (Pushdown Automata, PDA)”：这是本章的另一个核心内容。回顾第 1 章，我们有正则表达式（描述工具）和有限自动机（识别机器），它们是等价的。类似地，本章也将为上下文无关文法（描述工具）引入一个与之等价的计算模型——下推自动机。
4. “下推自动机是一类识别上下文无关语言的机器。” 这明确了 PDA 的角色，它是一个识别器，用于判断一个给定的字符串是否属于某个上下文无关语言。
5. “下推自动机很有用，因为它们使我们能够更深入地了解上下文无关文法的力量。” 这说明了引入 PDA 的意义。通过研究一个具体的机器模型，我们可以从另一个角度理解上下文无关语言的内在特性。下推自动机比有限自动机多了一个栈（stack）作为无限的记忆体，正是这个栈结构，使得它能够处理像 $\left\{0^{n} 1^{n} \mid n \geq 0\right\}$ 这样需要计数的语言。研究 PDA 的工作原理，能让我们更深刻地理解为什么上下文无关语言能处理递归和匹配，以及它们的计算能力的边界在哪里。

这一部分开始正式介绍上下文无关文法（CFG）的具体构成。它通过一个非常经典的例子 $G_1$ 来展开说明。

首先，给出了一个名为 $G_1$ 的文法，它包含三条规则：

1. $A \rightarrow 0A1$
2. $A \rightarrow B$
3. $B \rightarrow \#$

然后，对文法的组成要素进行了详细拆解：

1. 规则 (Rules) / 产生式 (Productions): 文法的核心是一系列规则。每一条规则定义了一种“替换”或“生成”的可能性。例如，规则 $A \rightarrow 0A1$ 意味着，当你在构建字符串的过程中遇到符号 $A$ 时，你可以将它替换成字符串 "0A1"。这个过程就像一个转换指令。
2. 箭头 →: 这个符号读作“导出”或“生成”。它分隔了规则的左右两部分。左边是被替换的对象，右边是替换后的结果。
3. 变量 (Variables): 出现在规则左侧的符号被称为变量。它们是文法的“非终结符”（Non-terminals）。你可以把它们看作是构造过程中的“中间产品”或“占位符”。它们不是最终语言字符串的一部分，必须在生成过程中被完全替换掉。按照惯例，变量通常用大写字母表示。在 $G_1$ 中，$A$ 和 $B$ 就是变量。
4. 终结符 (Terminals): 在规则右侧出现的，且不是变量的符号，被称为终结符。它们是构成最终语言字符串的“基本材料”或“字母”。一旦生成，它们就不能再被替换。它们类似于有限自动机的输入字母表。在 $G_1$ 中，0，1 和 # 就是终结符。它们通常用小写字母、数字或特殊符号表示。
5. 开始变量 (Start Variable): 在所有变量中，有一个是特殊的，被称为开始变量。它是一切生成过程的起点。按照惯例，如果没有特别说明，出现在第一条规则左侧的变量就是开始变量。在 $G_1$ 中，$A$ 就是开始变量。

最后，对 $G_1$ 进行了总结：

• 规则: 共 3 条。
• 变量: $A$ 和 $B$。
• 开始变量: $A$。
• 终结符: 0, 1, #。

这一段通过一个实例，清晰地定义了上下文无关文法的四个基本组成部分：变量、终结符、规则和开始变量。这是理解后续所有内容的基础。

这一部分详细描述了如何使用一个文法来生成语言中的字符串，并引入了两个关键概念：推导和分析树。

首先，给出了一个三步走的算法流程，解释了“生成”一个字符串的过程：

1. 初始化: 从开始变量出发。这是所有生成的起点。对于 $G_1$，我们从 $A$ 开始。
2. 迭代替换: 在当前生成的字符串（初始为开始变量）中，选择一个变量。然后，在文法的规则集中，找到一条以这个变量为左侧的规则。将所选变量替换为该规则的右侧内容。这个步骤可以重复进行。选择哪一个变量（如果当前字符串中有多个），以及选择哪一条规则（如果一个变量对应多条规则），都会影响生成的路径和最终结果。
3. 终止: 当生成的字符串中不再含有任何变量，只剩下终结符时，生成过程结束。这个最终的终结符串就是文法所生成的语言中的一个成员。

接着，通过一个具体的例子来演示这个过程。目标是使用文法 $G_1$ 生成字符串 000#111。这个一步步替换的过程被称为推导 (Derivation)。

推导过程的符号是 $\Rightarrow$，读作“一步推导出”。

$A \Rightarrow 0A1$:

• 开始于开始变量 $A$。
• 应用规则 $A \rightarrow 0A1$。将 $A$ 替换为 0A1。

$0A1 \Rightarrow 00A11$:

• 当前字符串是 0A1。其中唯一的变量是 $A$。
• 再次应用规则 $A \rightarrow 0A1$。将中间的 $A$ 替换为 0A1。
• 得到 0 + 0A1 + 1，即 00A11。

$00A11 \Rightarrow 000A111$:

• 当前字符串是 00A11。
• 第三次应用规则 $A \rightarrow 0A1$。
• 得到 00 + 0A1 + 11，即 000A111。

$000A111 \Rightarrow 000B111$:

• 当前字符串是 000A111。
• 现在我们选择应用另一条规则 $A \rightarrow B$。
• 将 $A$ 替换为 $B$，得到 000B111。
• 这一步是递归的终止，转向下一个阶段。

$000B111 \Rightarrow 000\#111$:

• 当前字符串是 000B111。唯一的变量是 $B$。
• 应用规则 $B \rightarrow \#$。
• 将 $B$ 替换为 #，得到 000#111。
• 此时，字符串 000#111 中已没有任何变量。推导结束。

这个序列完整地展示了从开始变量 $A$ 如何一步步生成最终字符串 000#111 的过程。

最后，引入了分析树（Parse Tree）或推导树（Derivation Tree）的概念。它是推导过程的图形化表示，能更直观地展示字符串的语法结构。

• 树根 (Root): 是开始变量（$A$）。
• 内部节点 (Internal Nodes): 是变量（$A, B$）。
• 叶子节点 (Leaves): 是终结符（0, 1, #）或空串 $\varepsilon$。
• 父子关系: 如果有一个规则 $X \rightarrow Y_1 Y_2 \dots Y_k$，那么在树中，节点 $X$ 会有 $k$ 个子节点，从左到右依次是 $Y_1, Y_2, \dots, Y_k$。
• 分析树的产出: 将分析树的所有叶子节点从左到右串联起来，得到的就是被生成的字符串。在图 2.1 中，从左到右读取叶子节点，得到 0 0 0 # 1 1 1。

分析树清晰地展示了字符串的层次结构，例如，000#111 是由一个顶层的 $A$ 结构生成，这个 $A$ 分解为 0、一个子 $A$ 和 1，这个子 $A$ 又同样分解...直到最后通过 $B$ 产生 #。

这段话正式定义了由文法生成的语言，并介绍了一些约定俗成的表示法。

1. 文法生成的语言: 一个文法 $G$ 所生成的语言，记作 $L(G)$，是所有可以从该文法的开始变量出发，经过一系列推导步骤，最终得到的终结符串的集合。换句话说，它是该文法所有可能产出的集合。
2. $L(G_1)$ 的分析: 通过对文法 $G_1$ 进行“实验”（即尝试进行各种可能的推导），我们可以归纳出它生成的语言的模式。
   • 规则 $A \rightarrow 0A1$ 是一个递归规则。每应用一次，就在中间的 $A$ 两侧分别增加一个 '0' 和一个 '1'。如果这个规则被应用 $n$ 次，我们就会得到一个形如 $0^n A 1^n$ 的字符串。
   • 规则 $A \rightarrow B$ 和 $B \rightarrow \#$ 提供了一个终止递归并产生中心符号 # 的方式。
   • 组合起来看：我们首先可以应用 $A \rightarrow 0A1$ 共 $n$ 次（$n \ge 0$），得到 $0^n A 1^n$。然后，应用 $A \rightarrow B$，得到 $0^n B 1^n$。最后应用 $B \rightarrow \#$，得到最终字符串 $0^n \# 1^n$。
   • 由于 $n$ 可以是 0, 1, 2, ...，所以这个文法能够生成 $\left\{0^{n} \# 1^{n} \mid n \geq 0\right\}$ 集合中的所有字符串。例如：
   • $n=0$: $A \Rightarrow B \Rightarrow \#$
   • $n=1$: $A \Rightarrow 0A1 \Rightarrow 0B1 \Rightarrow 0\#1$
   • $n=2$: $A \Rightarrow 0A1 \Rightarrow 00A11 \Rightarrow 00B11 \Rightarrow 00\#11$
   • 因此，我们得出结论：$L(G_1) = \left\{0^{n} \# 1^{n} \mid n \geq 0\right\}$。
3. 上下文无关语言 (CFL) 的定义: 这里给出了上下文无关语言的正式定义。如果一个语言 $L$ 存在一个上下文无关文法 $G$ 能够生成它（即 $L=L(G)$），那么 $L$ 就被称为一个上下文无关语言。这个定义将文法（一种描述工具）和语言（一个字符串集合）联系了起来。
4. 文法缩写: 最后介绍了一个书写惯例，以简化文法的表示。当有多条规则具有相同的左侧变量时，可以将它们合并成一行，用竖线 | 分隔右侧部分。竖线 | 读作“或”。
   • 例如，规则 $A \rightarrow 0A1$ 和 $A \rightarrow B$ 可以合并写成 $A \rightarrow 0A1 \mid B$。
   • 这仅仅是一种语法糖（syntactic sugar），一种简便的写法，它不改变文法的任何数学性质，但使得文法看起来更紧凑、更易读。

这一部分通过一个更复杂、更实际的例子 $G_2$ 来进一步展示上下文无关文法的应用，这次是模拟自然语言——英语的语法。

首先，给出了文法 $G_2$ 的所有规则。

• 变量: 使用尖括号 <...> 括起来的术语，如 <SENTENCE> (句子), <NOUN-PHRASE> (名词短语), <VERB> (动词) 等。这些都是语言学中的语法成分。
• 终结符: 具体的英文单词，如 a, the, boy, touches 等，以及用于分隔单词的空格。
• 规则: 定义了语法成分之间的组合关系。例如：
• <SENTENCE> -> <NOUN-PHRASE><VERB-PHRASE>: 一个句子由一个名词短语（主语）后跟一个动词短语（谓语）构成。
• <NOUN-PHRASE> -> <CMPLX-NOUN> | <CMPLX-NOUN><PREP-PHRASE>: 一个名词短语可以是一个简单的复合名词，也可以是一个复合名词后面跟着一个介词短语（起修饰作用）。这条规则体现了递归潜力，因为介词短语里可能又包含名词短语。
• <CMPLX-VERB> -> <VERB> | <VERB><NOUN-PHRASE>: 一个复合动词可以只是一个动词，也可以是一个动词后面跟着一个名词短语（作宾语）。
• <ARTICLE> -> a | the: 冠词可以是 'a' 或 'the'。这展示了如何定义一个词类。

接下来，对 $G_2$ 的规模进行了统计：10 个变量，27 个终结符（26个字母+空格），18 条规则（通过计算 | 的数量可以得出）。

然后，列举了三个可以通过这个文法生成的句子，展示了该文法的生成能力：

1. a boy sees (一个男孩看见)
2. the boy sees a flower (那个男孩看见一朵花)
3. a girl with a flower likes the boy (一个带着花的女孩喜欢那个男孩)

最后，为了证明这些句子确实是语言 $L(G_2)$ 的成员，详细演示了第一个句子 a boy sees 的推导过程。这个推导从开始变量 <SENTENCE> 出发，一步步应用规则，将变量替换为更小的变量或终结符，最终得到了完全由终结符构成的目标句子。

这个推导过程清晰地展示了句子的语法结构是如何被文法规则逐步构建出来的：

1. 一个句子分解为主语（名词短语）和谓语（动词短语）。
2. 名词短语被具体化为一个复合名词。
3. 复合名词由冠词和名词组成。
4. 冠词和名词被替换为具体的单词 'a' 和 'boy'。
5. 动词短语被具体化为一个复合动词。
6. 复合动词被简化为一个动词。
7. 动词被替换为具体的单词 'sees'。

整个过程就像一个语法分析的逆过程，从最高层的句子结构逐步填充细节，直至生成最终的单词序列。

这一部分从直观描述转向了严格的数学定义，将上下文无关文法及其相关概念形式化。

首先，定义 2.2 将上下文无关文法 (CFG) 定义为一个四元组 $(V, \Sigma, R, S)$。这是一种在数学和计算机科学中常见的定义方式，通过一个元组来精确地规定一个对象的构成要素。

1. $V$ (Variables): 这是一个有限集合，包含了文法中所有的变量（非终结符）。例如，在 $G_1$ 中，$V = \{A, B\}$。有限性是重要的，意味着文法规则是有限的。
2. $\Sigma$ (Terminals): 这是另一个有限集合，包含了所有的终结符（字母表）。关键约束是 $V$ 和 $\Sigma$ 不相交 ($V \cap \Sigma = \emptyset$)，这意味着一个符号不能既是变量又是终结符，二者身份必须明确。在 $G_1$ 中，$\Sigma = \{0, 1, \#\}$。
3. $R$ (Rules): 这是一个有限的规则集合。定义中描述了每条规则的形式：它由一个变量（来自 $V$）和箭头 → 以及一个由变量和终结符混合组成的字符串构成。形式上，$R$ 是 $V \times (V \cup \Sigma)^*$ 的一个有限子集。其中 $(V \cup \Sigma)^*$ 表示由 $V$ 和 $\Sigma$ 中所有符号组成的任意有限长度的字符串集合（包括空串）。在 $G_1$ 中，$R = \{ (A, 0A1), (A, B), (B, \#) \}$。
4. $S$ (Start Variable): 这是开始变量，它必须是 $V$ 集合中的一个成员 ($S \in V$)。它是所有推导的起点。在 $G_1$ 中，$S=A$。

接下来，形式化定义了推导过程：

• 一步推导 (yields): 符号为 $\Rightarrow$。如果有一个字符串 uAv（其中 u 和 v 可以是任何由变量和终结符构成的串，甚至是空串），并且文法中有一条规则 $A \rightarrow w$，那么我们可以应用这条规则将 uAv 转换为 uwv。这个过程被称为 uAv 一步推导出 uwv，记作 $uAv \Rightarrow uwv$。这个定义强调了“上下文无关”的特性：只要有变量 $A$，就可以替换它，而无需关心它的上下文 u 和 v 是什么。

• 多步推导 (derives): 符号为 $\stackrel{*}{\Rightarrow}$。这表示零步或多步推导。我们说 u 推导 v（记作 $u \stackrel{*}{\Rightarrow} v$）有两种情况：

1. $u = v$ (零步推导，任何字符串都可以推导出它自身)。
2. 存在一个推导序列 $u \Rightarrow u_1 \Rightarrow u_2 \Rightarrow \dots \Rightarrow v$。

这个 * 符号是克莱尼星号（Kleene Star）的推广，表示“零次或多次应用”。

最后，基于多步推导，给出了由文法 $G$ 生成的语言 $L(G)$ 的形式化定义：

• $L(G) = \left\{w \in \Sigma^{*} \mid S \stackrel{*}{\Rightarrow} w\right\}$
• 这个语言是一个集合。
• 集合中的成员 $w$ 必须满足两个条件：

1. $w \in \Sigma^{*}$: $w$ 必须是一个完全由终结符组成的字符串（* 表示包括空串）。这意味着推导必须终止，不能留下任何变量。
2. $S \stackrel{*}{\Rightarrow} w$: 必须存在一个从开始变量 $S$ 出发，经过零步或多步推导，能够得到字符串 $w$ 的过程。

这个定义精确、无歧义地界定了上下文无关文法是什么，以及它是如何工作的。

这段话将前面给出的形式化定义应用到之前的两个例子 $G_1$ 和 $G_2$ 上，并阐述了在实际操作中描述一个文法的常用惯例。

首先，它精确地用四元组的形式“翻译”了文法 $G_1$：

• 变量集合 $V$ 是 $\{A, B\}$。
• 终结符集合 $\Sigma$ 是 $\{0, 1, \#\}$。
• 开始变量 $S$ 是 $A$。
• 规则集合 $R$ 就是之前列出的那三条规则 $\{A \rightarrow 0A1, A \rightarrow B, B \rightarrow \#\}$。

这展示了如何将一个写出的文法映射到其形式化定义的四元组上。

接着，它对更复杂的文法 $G_2$ 也做了同样的分析：

• 变量集合 $V$ 被明确列出，包含了所有用尖括号括起来的 10 个语法术语。
• 终结符集合 $\Sigma$ 被描述为所有小写英文字母加上一个空格符号。这里特别解释了空格符号的作用：它是语言的一部分，用来分隔单词，否则生成的句子会是 aboysees 这样的连体词。这强调了终结符可以是任何符号，包括那些不可见的。

然后，引出了一套非常重要的书写惯例。在实践中，每次都写出完整的四元组 $(V, \Sigma, R, S)$ 会非常繁琐。因此，大家约定俗成了一套简化表示法：

1. 只写规则: 我们通常只把规则集合 $R$ 写出来。
2. 推断变量: 凡是出现在任何规则左侧的符号，都被自动识别为变量。
3. 推断终结符: 那些只出现在规则右侧，且不是变量的符号，就被自动识别为终结符。
4. 推断开始变量: 除非特别声明，第一条写出的规则的左侧变量，就被默认为是开始变量。

这套惯例大大简化了文法的书写，使得我们可以仅通过规则列表就能完整地、无歧义地定义一个文法。前面的 $G_1$ 和 $G_2$ 就是按照这个惯例给出的。

这个例子介绍了一个非常经典的上下文无关文法 $G_3$，它用来生成所有正确嵌套括号的字符串。

首先，明确了文法 $G_3$ 的形式化定义：

• 变量 $V = \{S\}$。只有一个变量 $S$。
• 终结符 $\Sigma = \{a, b\}$。
• 开始变量就是 $S$。
• 规则集 $R$ 包含三条规则，通过 | 缩写在一行：$S \rightarrow \mathrm{a} S \mathrm{~b}$, $S \rightarrow S S$, 和 $S \rightarrow \varepsilon$。

接下来分析这三条规则的作用：

1. $S \rightarrow \mathrm{a} S \mathrm{~b}$: 这是一条递归规则，用于嵌套。它表示一个合法的括号串 ($S$)，可以在其外部包裹一层括号 (a 和 b)，形成一个新的、更长的合法括号串。例如，如果 ab 是合法的，那么 a(ab)b 即 aabb 也是合法的。
2. $S \rightarrow S S$: 这也是一条递归规则，用于并列或连接。它表示两个合法的括号串 ($S$) 相邻放置，形成的新字符串也是一个合法的括号串。例如，如果 ab 和 ab 都是合法的，那么它们的连接 (ab)(ab) 即 abab 也是合法的。
3. $S \rightarrow \varepsilon$: 这是基本情况（base case）或终止规则。它表示空串 $\varepsilon$ 本身就是一个合法的括号串。这是所有推导的终点，也是生成最短合法串的方式。

通过这三条规则的组合，可以生成所有形式的合法括号串。

• 嵌套: 通过反复应用 $S \rightarrow \mathrm{a}S\mathrm{b}$ 实现。
• 并列: 通过应用 $S \rightarrow SS$ 实现。
• 结束: 通过应用 $S \rightarrow \varepsilon$ 终止递归。

段落给出了几个 $G_3$ 生成的字符串例子：abab, aaabbb, aababb。

为了帮助理解，段落提出了一个绝佳的类比：将 'a' 想象成左括号 (, 将 'b' 想象成右括号 )。

• $S \rightarrow (S)$: 在一个合法括号串外面加一对括号。
• $S \rightarrow SS$: 将两个合法括号串并列。
• $S \rightarrow \varepsilon$: 空串是合法的。

在这个类比下，$L(G_3)$ 就是所有正确嵌套括号的语言。例如：

• () 对应 ab。
• ()() 对应 abab。
• ((())) 对应 aaabbb。
• (())() 对应 aababb。

最后，再次强调了 ε 规则的重要性，它是递归能够终止的基础。没有它，推导将无限进行下去，无法生成任何有限长度的字符串。

这个例子展示了上下文无关文法在描述编程语言中算术表达式的强大能力，特别是如何利用文法结构来强制实现运算符的优先级和结合性。

首先，给出了文法 $G_4$ 的形式化定义：

• 变量 $V = \{\langle \text{EXPR} \rangle, \langle \text{TERM} \rangle, \langle \text{FACTOR} \rangle\}$。这三个变量分别代表表达式 (Expression)、项 (Term) 和因子 (Factor)。
• 终结符 $\Sigma = \{\mathrm{a}, +, \times, (, )\}$。a 代表一个操作数（比如一个数字或变量），+ 和 × 是运算符，( 和 ) 是括号。
• 开始变量是 $\langle \text{EXPR} \rangle$。
• 规则集分为三组，分别定义了表达式、项和因子：

1. $\langle\mathrm{EXPR}\rangle \rightarrow \langle\mathrm{EXPR}\rangle+\langle\mathrm{TERM}\rangle \mid \langle\mathrm{TERM}\rangle$
   • 一个表达式可以是一个表达式加上一个项，或者直接就是一个项。
   • 这组规则处理加法 +。+ 是左结合的（因为递归的 出现在 + 的左边），并且优先级最低。
2. $\langle\mathrm{TERM}\rangle \rightarrow \langle\mathrm{TERM}\rangle \times\langle\mathrm{FACTOR}\rangle \mid \langle\mathrm{FACTOR}\rangle$
   • 一个项可以是一个项乘以一个因子，或者直接就是一个因子。
   • 这组规则处理乘法 ×。× 是左结合的，它的优先级高于加法，因为一个表达式是由项组成的，而乘法是在项的层次上定义的。要看到加号，你必须先处理完所有的乘法。
3. $\langle\mathrm{FACTOR}\rangle \rightarrow (\langle\mathrm{EXPR}\rangle) \mid \mathrm{a}$
   • 一个因子可以是一个被括号括起来的表达式，或者直接就是一个操作数 a。
   • 这组规则是递归的终点。括号 () 提供了改变默认优先级的机制，因为它允许一个完整的表达式（可以包含加法）出现在一个需要因子的地方。a 是最基本的操作数。

这个三层结构（表达式-项-因子）是编译器设计中用于处理带优先级的表达式的经典文法设计模式。

接着，展示了用这个文法生成的两个字符串 a+a×a 和 (a+a)×a 的分析树。

• 对于 a+a×a:
• 分析树的结构显示，顶层是 + 运算。+ 的左边是一个表达式，最终归结为第一个 a。+ 的右边是一个项，这个项内部是 × 运算 a×a。
• 这棵树的结构强制了 a×a 先被计算（因为它在一个较低的子树 <TERM> 中），其结果再和第一个 a 相加。这正确地反映了乘法优先级高于加法的规则。
• 对于 (a+a)×a:
• 分析树的结构显示，顶层是 × 运算。× 的左边是一个项，这个项最终来自一个因子 (<EXPR>)，即 (a+a)。× 的右边是第二个 a。
• 这棵树的结构强制了括号内的 a+a 先被计算，其结果再和后面的 a 相乘。这正确地反映了括号覆盖默认优先级的规则。

这个例子有力地证明了，一个精心设计的上下文无关文法不仅能定义哪些字符串是合法的，还能通过其推导结构（即分析树的形状）来赋予字符串唯一的、正确的语义解释。

这段话是对例子 2.4 的进一步阐述和总结，旨在强调文法、分析树与编译器工作原理之间的深刻联系。

第一段首先概括了编译器的核心功能：代码转换。然后聚焦于编译过程中的一个关键步骤——解析（Parsing）。

• 解析的目的: “提取待编译代码的含义”。源代码本身只是一串文本字符，编译器需要通过解析来理解这串文本的结构和意图。
• 含义的表示: 分析树（Parse Tree）或其变体抽象语法树（AST）是承载代码含义的关键数据结构。它不是线性的文本，而是层次化的树状结构，能清晰地表示运算的顺序、代码块的嵌套关系等。
• 分析树的来源: 分析树是在特定编程语言的上下文无关文法的框架下构建的。没有文法，就没有构建分析树的依据。
• 预告: 这里提到了后续章节（定理 7.16 和问题 7.22）会讨论具体的解析算法，暗示了这是一个重要且有具体实现方法的主题（例如 CYK 算法或 Earley 算法）。

第二段则将这些通用概念应用回例子 $G_4$。

• $G_4$ 的作用: 明确指出 $G_4$ 就是用来描述编程语言中算术表达式这部分的文法。
• 分析树的“分组”功能: 这是对分析树作用的非常直观的描述。“分组”就是指分析树的子树结构。一个子树将一个运算符和它的操作数“圈”在一起，形成一个独立的计算单元。
• 对 a+a×a 的分析: 分析树将 a×a 圈成一个子树（一个 <TERM>），这个子树整体作为 + 的右操作数。这体现了分组，也即是实现了“先算乘法”。
• 对 (a+a)×a 的分析: 分析树将 a+a 圈在另一个子树里（一个由括号产生的 <FACTOR>），这个子树作为 × 的左操作数。分组顺序发生了颠倒。
• 与编程规则的对应: 这种由文法和分析树强制实现的“分组”，完美地对应了我们在编程时所熟知的两条规则：

1. 标准优先级: 乘法先于加法。
2. 括号覆盖: 括号内的运算最先执行。
   • $G_4$ 的设计意图: 最后总结，$G_4$ 的设计目的就是为了通过其结构来精确地“捕获”这些优先级关系，确保代码被无歧义地理解。

这段话是设计上下文无关文法 (CFG) 这一主题的引言。它首先定性地描述了这项任务的特点和难点，并预告了接下来将要介绍一些有用的设计技巧。

1. 类比与难度:
   • 它将设计 CFG 与之前学习过的设计有限自动机 (FA) 进行了类比，指出两者都需要“创造力”，都不是简单的机械性工作。
   • 紧接着，它做了一个重要的难度对比：“上下文无关文法比有限自动机更难构建”。这为读者设定了合理的预期，承认了这项任务的挑战性。
2. 难度原因分析:
   • 段落给出了一个深刻的解释，说明了为什么设计 CFG 更难。这源于我们人类，特别是受过编程训练的人的思维习惯。
   • “我们更习惯于为特定任务编写机器程序”：设计有限自动机或编写程序，是一种“过程式”或“指令式”的思维。我们思考的是“第一步做什么，第二步做什么，遇到什么情况就转移到哪个状态”。这是一种动态的、描述“如何做”的思维方式。
   • “而不是用文法描述语言”：设计文法，则是一种“声明式”或“描述式”的思维。我们思考的是“一个合法的对象是由哪些部分组成的”，或者“什么样的结构是合法的”。这是一种静态的、描述“是什么”的思维方式。
   • 由于我们的教育和实践更多地倾向于前者，所以转换到后一种思维方式会感觉不自然，从而增加了难度。
3. 提供解决方案:
   • 在指出了困难之后，该段落立即给出了积极的引导：“以下技术……会很有帮助”。这表明，虽然设计 CFG 有挑战，但并非无章可循。存在一些通用的策略和模式可以学习和应用。
   • 这些技术可以“单独或组合使用”，暗示了设计的灵活性，可能需要根据具体问题综合运用多种方法。

这里介绍了设计上下文无关文法 (CFG) 的第一个核心技术：分解与合并，专门用于处理由并集 (Union) 构成的语言。

核心思想: “分而治之” (Divide and Conquer)。

1. 分解 (Divide): 当你面对一个复杂的语言 $L$ 时，首先观察它是否能被看作是几个更简单的语言 $L_1, L_2, \dots, L_k$ 的并集。即 $L = L_1 \cup L_2 \cup \dots \cup L_k$。
2. 解决子问题 (Conquer): 如果可以分解，那么就暂时忽略整个复杂问题，转而为每一个简单的子语言 $L_i$ 单独设计一个 CFG，我们称之为 $G_i$。设 $G_i$ 的开始变量是 $S_i$。
3. 合并 (Combine): 将所有子文法的规则全部放在一起。然后，引入一个新的、全局的开始变量 $S$，并为它添加一条新的规则 $S \rightarrow S_1 | S_2 | \dots | S_k$。这条规则的意思是：“要生成语言 $L$ 的一个字符串，你可以选择去生成 $L_1$ 的一个字符串（从 $S_1$ 开始），或者选择去生成 $L_2$ 的一个字符串（从 $S_2$ 开始），以此类推。”

这个技巧的有效性基于上下文无关语言对于并集运算是封闭的这一性质。也就是说，如果 $L_1$ 和 $L_2$ 都是 CFL，那么它们的并集 $L_1 \cup L_2$ 也必然是 CFL。这个构造性证明本身就提供了设计文法的方法。

例子分析:

• 目标语言: $L = \left\{0^{n} 1^{n} \mid n \geq 0\right\} \cup\left\{1^{n} 0^{n} \mid n \geq 0\right\}$。这个语言包含两种类型的字符串：要么是若干个 '0' 后面跟相同数量的 '1'，要么是若干个 '1' 后面跟相同数量的 '0'。
• 分解:
• $L_1 = \left\{0^{n} 1^{n} \mid n \geq 0\right\}$。
• $L_2 = \left\{1^{n} 0^{n} \mid n \geq 0\right\}$。
• 显然 $L = L_1 \cup L_2$。
• 解决子问题:
• 为 $L_1$ 设计文法 $G_1$。我们已经知道它的递归结构是外部包裹 0 和 1，中心是空串。所以文法是 $S_1 \rightarrow 0S_1 1 \mid \varepsilon$。
• 为 $L_2$ 设计文法 $G_2$。结构完全类似，只是包裹的终结符变成了 1 和 0。所以文法是 $S_2 \rightarrow 1S_2 0 \mid \varepsilon$。
• 合并:
• 将 $G_1$ 和 $G_2$ 的规则放在一起。
• 引入新的开始变量 $S$。
• 添加规则 $S \rightarrow S_1 \mid S_2$。
• 最终文法:

```

S -> S1 | S2

S1 -> 0S1 1 | ε

S2 -> 1S2 0 | ε

```

这个文法的工作方式是：从 $S$ 开始，你第一步必须选择走 $S_1$ 的路径还是 $S_2$ 的路径。一旦选定，比如选了 $S_1$，你就进入了 $L_1$ 的生成模式，之后的所有推导都遵循 $G_1$ 的规则，不可能再跳到 $S_2$ 的规则里去。这样就保证了生成的字符串要么完全符合 $L_1$ 的格式，要么完全符合 $L_2$ 的格式。

这里介绍了设计上下文无关文法 (CFG) 的第二个技术：从确定性有限自动机 (DFA) 进行转换。这个技术专门用于为正则语言构建 CFG。

背景知识: 我们已经知道，所有正则语言都是上下文无关语言。这意味着任何一个可以用 DFA（或 NFA，或正则表达式）描述的语言，都必然存在一个 CFG 可以生成它。本段就提供了一个将 DFA 自动转换为等效 CFG 的算法。

转换算法:

1. 变量映射: 文法的变量和 DFA 的状态一一对应。为 DFA 的每一个状态 $q_i$，创建一个名为 $R_i$ 的变量。这个变量 $R_i$ 的直观含义是：“从状态 $q_i$ 开始，能够识别的字符串的集合”。
2. 转移转换: DFA 的转移函数 $\delta(q_i, a) = q_j$ 表示在状态 $q_i$ 读到输入符号 $a$ 会转移到状态 $q_j$。这个过程被转换成一条 CFG 规则：$R_i \rightarrow a R_j$。这条规则的直观含义是：“要生成一个能从 $q_i$ 开始被识别的字符串，你可以先生成一个 a，然后生成一个能从 $q_j$ 开始被识别的字符串。” 这完美地模拟了 DFA 的一步转移。
3. 接受状态转换: 如果 $q_i$ 是一个接受状态，这意味着机器到达这个状态时，已经读取的字符串是合法的。在 DFA 中，从接受状态开始，如果不再读入任何字符（即读入空串 $\varepsilon$），当前路径是接受的。因此，为每个接受状态 $q_i$ 添加一条规则 $R_i \rightarrow \varepsilon$。这条规则表示“从接受状态 $q_i$ 出发，可以生成空串”，它为推导提供了一个终止点。
4. 开始状态映射: DFA 的开始状态 $q_0$ 对应的变量 $R_0$ 被指定为 CFG 的开始变量。这保证了文法的生成过程是从模拟 DFA 的初始状态开始的。

正确性验证 (直观):

• 考虑 DFA 识别一个字符串 $w = a_1 a_2 \dots a_k$ 的过程。这个过程是一个状态序列：$q_0 \xrightarrow{a_1} q_{i_1} \xrightarrow{a_2} q_{i_2} \dots \xrightarrow{a_k} q_{i_k}$，并且 $q_{i_k}$ 是一个接受状态。
• 在构造出的 CFG 中，这个过程对应一个推导:

$R_0 \Rightarrow a_1 R_{i_1} \Rightarrow a_1 a_2 R_{i_2} \Rightarrow \dots \Rightarrow a_1 a_2 \dots a_k R_{i_k}$。

• 因为 $q_{i_k}$ 是接受状态，所以我们有一条规则 $R_{i_k} \rightarrow \varepsilon$。
• 继续推导：$a_1 a_2 \dots a_k R_{i_k} \Rightarrow a_1 a_2 \dots a_k \varepsilon = w$。
• 这就证明了，任何被 DFA 接受的字符串都可以被这个 CFG 生成。反之亦然。

这个技巧非常强大，因为它将一个可能需要创造力的设计问题，转换为了一个完全机械化的、算法性的转换过程。只要你能为正则语言画出 DFA，就能自动得到它的 CFG。

这里介绍了设计上下文无关文法的第三个，也是最核心的一个技巧：使用递归规则处理关联子串。这个技巧是用来处理那些超越了正则语言能力的、需要“计数”或“匹配”的语言。

1. 问题识别:
   • 首先，要识别出语言的特性。这类语言的字符串通常可以被分成几个部分，其中两个（或多个）部分存在某种“关联”。
   • 最常见的关联是“数量相等”，例如 $\left\{0^{n} 1^{n}\right\}$ 中 '0' 和 '1' 的数量相等。
   • 另一种关联是“逆序匹配”，例如回文语言 $\left\{w w^{R} \mid w \in \{0,1\}^{*}\right\}$，其中后半部分是前半部分的反转。
   • “机器需要记住...无限量信息”是对这种关联的计算挑战的描述。正如之前讨论的，有限自动机的有限状态无法存储一个可能无限增长的计数值 $n$。
2. 解决方案:
   • CFG 通过递归来解决这个问题，而不需要显式的“计数器”。
   • 核心技巧: 使用形如 $R \rightarrow u R v$ 的规则。
   • $R$ 是一个递归调用的变量。
   • u 和 v 是终结符（或终结符串）。
   • 工作原理: 这条规则有一种“同时生长”或“对称生成”的效应。每应用一次，就在递归的变量 $R$ 的两侧同时“种下”u 和 v。
   • $R \Rightarrow uRv$
   • $\Rightarrow u(uRv)v = u^2 R v^2$
   • $\Rightarrow u^2(uRv)v^2 = u^3 R v^3$
   • ... 经过 $n$ 次递归，我们会得到 $u^n R v^n$。
   • 通过这种方式，u 和 v 的数量被文法的递归结构本身隐式地、完美地绑定在了一起，始终保持一致。
   • 最后，只需要一个终止规则（例如 $R \rightarrow \varepsilon$ 或 $R \rightarrow w_0$）来替换掉最后的 $R$，就完成了字符串的生成。
3. 例子回顾:
   • 对于语言 $\left\{0^{n} 1^{n} \mid n \geq 0\right\}$：
   • 关联的子串是 0...0 和 1...1。
   • u 就是 0，v 就是 1。
   • 所以核心规则是 $S \rightarrow 0S1$。
   • 递归的终点是当 $n=0$ 时，此时字符串是空串 $\varepsilon$。所以终止规则是 $S \rightarrow \varepsilon$。
   • 最终文法: $S \rightarrow 0S1 \mid \varepsilon$。

这个技巧是设计非正则 CFL 文法的基石，它直接利用了 CFG 最强大的武器——递归。

这里介绍了设计上下文无关文法的第四个技巧：结构替换式递归。这个技巧用于处理那些一个语法结构可以出现在另一个（或自身）语法结构内部的语言，这是构建复杂层次结构的关键。

1. 问题识别:
   • 这类语言的特点是“一个东西里面可以有另一个东西”。这与第三个技巧的“两端匹配”不同，这里的递归是“整体替换”。
   • 最典型的例子就是算术表达式，如例子 2.4 所示。一个最基本的元素（操作数，如 a）出现的位置，往往可以被一个更复杂的、同类型的结构（一个完整的、带括号的表达式，如 (a+a*b)）所替换。
   • 另一个例子是编程语言中的语句块。一个 if 语句的 then 分支里可以只是一条简单的赋值语句，也可以是另一个完整的 if-else 语句，或者一个 while 循环。
2. 解决方案:
   • 核心技巧: 在文法规则中，将代表“小结构”的符号和代表“大结构”的变量并列作为可选项。
   • 回顾文法 $G_4$ 中的规则 $\langle\mathrm{FACTOR}\rangle \rightarrow (\langle\mathrm{EXPR}\rangle) \mid \mathrm{a}$。
   • a 在这里代表最简单的、原子的结构（一个操作数）。
   • () 代表复杂的、递归的结构。 是整个文法的开始变量，代表了一个可以任意复杂的完整表达式。
   • | “或”符号将这两者并列，意味着：任何需要一个 FACTOR 的地方，你既可以提供一个简单的 a，也可以提供一个用括号括起来的、任意复杂的完整表达式。
   • 通用模式: A -> B | C，其中 B 派生出原子结构，C 派生出包含顶层结构（比如开始变量）的递归结构。
   • 实现效果: "将生成结构的变量符号放置在规则中对应于该结构可能递归出现的位置"。在 $G_4$ 中， 这个代表完整结构的变量，被放置在了 FACTOR 的规则中，也就是一个 a 原本可以出现的位置。

这个技巧是构建具有任意深度嵌套能力的文法的关键，广泛应用于编程语言、数据格式（如 JSON）等领域。

这一部分引入了上下文无关文法中的一个核心问题——二义性 (Ambiguity)。

首先，对二义性进行了直观的定义和解释：

• 现象: 一个文法可以用多种不同的方式生成同一个字符串。
• 后果: 这个字符串会对应多个不同的分析树。因为分析树代表了字符串的结构和含义，所以多个分析树就意味着“多种含义”。
• 危害: 在某些应用中，多种含义是不可接受的。最典型的例子就是编程语言。一个程序 a+bc 必须有唯一确定的计算方式，不能有时解释为 (a+b)c，有时又解释为 a+(b*c)。程序的行为必须是确定的。因此，用于编程语言的文法必须是无二义性的。

接着，给出了两个形式化的术语：

• 二义性推导 (ambiguously derived): 当一个字符串可以被一个文法以多种方式生成（即对应多棵分析树）时，我们说这个字符串是被二义性推导的。
• 二义性文法 (ambiguous grammar): 如果一个文法中至少存在一个字符串可以被二义性推导，那么这个文法本身就被称为二义性文法。

然后，通过一个具体的文法 $G_5$ 来演示二义性。

• 文法 $G_5$: <EXPR> -> <EXPR>+<EXPR> | <EXPR>×<EXPR> | (<EXPR>) | a
• 这个文法看起来很直观，它说一个表达式可以是两个表达式相加，或两个表达式相乘，或括号括起来，或一个 a。
• 问题所在: 这个文法没有规定 + 和 × 的优先级。规则 <EXPR> -> <EXPR>+<EXPR> 和 <EXPR> -> <EXPR>×<EXPR> 处于同一“层级”，推导时可以随意选择先应用哪个。
• 二义性字符串: a+a×a。
• 两个分析树:

1. 第一棵树 (左图): 顶层是 + 节点。这棵树的结构对应于 (a) + (a×a)。它先将 a×a 解析为一个子 ，然后将这个结果与第一个 a 相加。这符合我们期望的乘法优先。
2. 第二棵树 (右图): 顶层是 × 节点。这棵树的结构对应于 (a+a) × (a)。它先将 a+a 解析为一个子 ，然后将结果与第三个 a 相乘。这违反了标准的运算符优先级。

因为文法 $G_5$ 允许为同一个字符串 a+a×a 生成这两棵结构完全不同（即含义完全不同）的分析树，所以 $G_5$ 是一个二义性文法。

这段话是对二义性例子的补充说明和总结，并引出了另一个关于自然语言文法的二义性例子。

第一段，对文法 $G_4$ 和 $G_5$ 进行了直接的对比和定性。

• $G_5$ 的问题: 明确指出 $G_5$ 的根本缺陷在于“没有捕捉到通常的优先级关系”。它把 + 和 × 放在了同等地位，导致解析器在“分组”（构建子树）时可以随意选择，从而产生了二义性。
• $G_4$ 的优点:
• 它生成“完全相同的语言”，即所有合法的算术表达式串。在生成能力上，它和 $G_5$ 是等价的。
• 但是，它对每个合法的字符串，都能生成“唯一的分析树”。
• 结论: 基于以上对比，给出了明确的判定：$G_4$ 是无二义性的 (unambiguous)，而 $G_5$ 是二义性的 (ambiguous)。这强调了对于同一个语言，可能存在好的（无二义性）和坏的（二义性）文法。

第二段，将二义性的概念扩展回自然语言的例子。

• 另一个例子: 指出之前介绍的用于描述英语片段的文法 $G_2$ 也是一个二义性文法。这说明二义性不仅是设计数学表达式文法时的问题，在自然语言处理中也普遍存在。
• 二义性句子: "the girl touches the boy with the flower"。
• 歧义来源: 介词短语 with the flower 到底修饰谁？

1. 修饰 the boy: (the boy with the flower)，男孩带着花。整个句意是：女孩触摸了那个带着花的男孩。
2. 修饰 touches: (touches ... with the flower)，用花来触摸。整个句意是：女孩用花去触摸那个男孩。
   • 两种推导/分析树: 文法 $G_2$ 的规则设计使得这两种解析结构都是合法的，因此可以为这个句子生成两棵不同的分析树，分别对应这两种不同的含义。
   • 留作练习: 文本没有在此处画出这两棵树，而是将其作为一个练习（练习 2.8），让读者亲自去推导和构建分析树，从而更深刻地体会文法规则是如何导致语义二义性的。

这一部分为二义性提供了一个更严格、更便于操作的形式化定义。

首先，它澄清了一个关键点：二义性的本质在于分析树的不同，而不是推导序列的不同。

• 一个字符串可以有很多个推导序列。例如，对于中间字符串 A + B，你可以选择先替换 A，也可以选择先替换 B。这会产生两个不同的推导步骤序列。
• 但是，如果这两种替换顺序最终产生的分析树是完全一样的（即 + 的左右子树分别是 A 和 B 的推导结果），那么这种推导顺序的不同是无关紧要的，不构成二义性。它只是到达同一个“结构”的不同路径而已。
• 二义性的真正问题是，同一个字符串存在结构上不同的分析树。

为了消除这种因推导顺序不同而产生的“假性”多样性，从而能专注于真正的结构性二义性，这里引入了一个标准化的推导方法：最左推导 (Leftmost Derivation)。

• 定义: 在最左推导中，每一步推导都必须替换当前字符串中最左边的那个变量。这是一个严格的规定，使得在每一步，选择哪个变量进行替换是唯一确定的。
• 作用: 通过固定替换顺序，最左推导与分析树之间建立了一一对应的关系。每一棵特定的分析树都唯一对应一个最左推导，反之亦然。
• 因此，判断“一个字符串是否有两棵不同的分析树”这个比较抽象的问题，被转换为了一个更具体、更容易操作的问题：“一个字符串是否有两个不同的最左推导”。

基于最左推导，定义 2.7 给出了二义性的形式化定义：

• 二义性推导: 如果一个字符串 $w$ 在文法 $G$ 中存在两个或更多的、不同的最左推导序列，那么它就是被二义性推导的。
• 二义性文法: 如果一个文法 $G$ 中至少存在一个这样的字符串，那么文法 $G$ 就是二义性的。

这个定义比“多棵分析树”的定义更便于在数学证明或算法中进行判断。

最后，文本回顾了一下，指出在前面（定义 2.2 之前）为 a boy sees 做的推导，实际上就是一个最左推导的例子。

这段话讨论了二义性问题的两种可能结果，并引入了一个新的重要概念：固有二义性语言。

1. 可消除的二义性:
   • “有时，当我们有一个二义性文法时，我们可以找到一个生成相同语言的无二义性文法。”
   • 这是一种“好”情况。它说明二义性是出在我们的文法设计上，而不是语言本身的问题。
   • 例子: 文法 $G_5$ (E -> E+E | EE | ...) 是二义性的，但它生成的算术表达式语言可以通过文法 $G_4$ (E -> E+T, T -> TF, ...) 来无二义性地生成。
   • 这意味着，我们可以通过“重写文法”或“文法转换”的技术来消除二义性。这在编译器设计中是常规操作。
2. 不可消除的二义性:
   • “然而，有些上下文无关语言只能由二义性文法生成。”
   • 这是一种“坏”情况，它揭示了二义性问题的深层本质。这里的二义性根植于语言的内在结构，是其固有属性，无论我们如何巧妙地设计文法，都无法消除。
   • 固有二义性语言 (Inherently Ambiguous Language): 这就是对这类语言的正式命名。一个语言 $L$ 如果是固有二义性的，意味着所有能够生成 $L$ 的上下文无关文法都必然是二义性的。
   • 这个概念非常重要，因为它设定了无二义性解析的边界。对于固有二义性语言，我们无法构建出一个能为其所有字符串提供唯一分析树的 CFG 解析器。
3. 固有二义性语言的例子:
   • 文本给出了一个经典的固有二义性语言的例子：$L = \left\{\mathrm{a}^{i} \mathrm{~b}^{j} \mathrm{c}^{k} \mid i=j \text{ 或 } j=k\right\}$。
   • 这个语言由两部分并集而成：
   • $L_1 = \{a^i b^i c^k \mid i,k \ge 0\}$ (a 和 b 数量相等)
   • $L_2 = \{a^i b^j c^j \mid i,j \ge 0\}$ (b 和 c 数量相等)
   • 二义性的来源: 考虑字符串的形式为 $a^n b^n c^n$。这种字符串既满足 $i=j$ 的条件（属于 $L_1$），也满足 $j=k$ 的条件（属于 $L_2$）。
   • 直观上，一个文法为了生成这个语言，很可能需要一个部分来处理 a-b 的匹配，另一个部分来处理 b-c 的匹配。对于 $a^n b^n c^n$ 这样的字符串，它既可以被“a-b匹配”的逻辑生成（把它看作 $a^n b^n$ 后面跟了 $c^n$），也可以被“b-c匹配”的逻辑生成（把它看作 $a^n$ 后面跟了 $b^n c^n$）。这两种不同的生成逻辑会对应两种不同的分析树，从而导致二义性。
   • 证明一个语言是固有二义性的通常很困难，需要用到上下文无关语言的泵引理的变体或其他高级技术。文本在此处只是提出问题，将证明留作练习。

这一部分引入了一个重要的文法“标准化”形式——乔姆斯基范式 (Chomsky Normal Form, CNF)。

首先，引言部分解释了为什么需要这种范式：

• 目的: “简化形式会很方便”。原始的 CFG 规则形式多样，可以很长，可以混合变量和终结符，这使得设计和分析处理 CFG 的算法变得复杂。
• CNF 的地位: 它是“最简单且最有用的形式之一”。这意味着它在理论和实践中都有很高的价值。
• 用途: “在给出处理上下文无关语言的算法时很有用”。后面章节（第 4 章和第 7 章）将会介绍一些算法，例如，判断一个字符串是否属于某个 CFL 的成员资格算法（如 CYK 算法），或者关于 CFL 的其他性质证明。这些算法的设计通常都假设输入的文法已经是 CNF 形式，因为这种简单的规则形式极大地简化了算法的逻辑。

接着，定义 2.8 给出了乔姆斯基范式的严格定义。一个 CFG 要成为 CNF，它的所有规则（除了一个特殊情况）必须满足以下两种形式之一：

1. $A \rightarrow BC$:
   • 规则的右侧必须是两个变量。不能是一个，不能是三个或更多，也不能是变量和终结符的混合。
   • $A, B, C$ 都是变量。
   • 一个额外的约束是 $B$ 和 $C$ 都不能是开始变量 $S$。这个约束在某些严格的定义中出现，旨在简化某些证明，但并非所有教科书都包含此条。
2. $A \rightarrow a$:
   • 规则的右侧必须是一个终结符。不能是多个终结符，也不能是空串 $\varepsilon$。
   • $A$ 是一个变量，$a$ 是一个终结符。

特殊情况:

• $S \rightarrow \varepsilon$: 如果语言包含空串 $\varepsilon$，那么允许有一条从开始变量 $S$ 直接生成空串的规则。
• 约束: 如果存在 $S \rightarrow \varepsilon$ 这条规则，那么开始变量 $S$ 就不能出现在任何其他规则的右侧。这也是为了简化算法和证明。后面的转换过程会展示如何实现这一点。

总结 CNF 的特点:

• 规则右侧长度: 所有规则（除 $S \rightarrow \varepsilon$）的右侧长度要么是 1（一个终结符），要么是 2（两个变量）。
• 符号类型分离: 变量和终结符不会出现在同一条规则的右侧。要么全是变量，要么全是终结符。
• 无 $\varepsilon$-规则 (基本): 除了可能的 $S \rightarrow \varepsilon$，没有其他规则可以生成空串。
• 无单元规则: 没有形如 $A \rightarrow B$ 的规则。

这种高度规范化的形式，使得分析树的结构也变得非常规整：每个变量节点要么有两个变量子节点，要么有一个终结符子节点。这对于动态规划类的解析算法（如 CYK）来说是完美的基础。

这一部分提出了一个核心定理并概述了其证明思路。

定理 2.9:

• 陈述: “任何上下文无关语言都由乔姆斯基范式中的上下文无关文法生成。”
• 含义: 这个定理的意义非常重大。它说明乔姆斯基范式这种“受限的”文法形式，其生成能力并没有减弱。对于任何一个可以用任意复杂 CFG 描述的语言，我们总能找到一个等价的、但形式上非常简单的 CNF 文法来生成它。
• 推论: 这意味着，当我们要设计一个处理所有 CFL 的通用算法时，我们可以放心地假设输入的文法已经是 CNF 形式。因为如果不是，我们总可以通过一个预处理步骤将它转换成 CNF，而不会改变它所代表的语言。这极大地扩展了 CNF 的实用性。

证明思路 (Proof Idea):

定理的证明是构造性的。它不只是说“存在”一个 CNF 文法，而是给出了一个具体的算法，可以将任何给定的 CFG 转换为等效的 CNF。这个算法分为几个清晰的阶段，每个阶段旨在消除一种不符合 CNF 要求的规则。

1. 阶段 1: 添加新开始变量 (START)
   • 目的: 为了处理语言包含空串 $\varepsilon$ 的情况，并确保开始变量不会出现在任何规则的右侧。这是 CNF 的一个严格要求。
   • 操作: 创建一个全新的开始变量 $S_0$，并添加一条规则 $S_0 \rightarrow S$，其中 $S$ 是原始的开始变量。$S_0$ 成为文法的新起点。如果原始语言包含 $\varepsilon$，通常会在这里处理，比如添加 $S_0 \rightarrow \varepsilon$。
2. 阶段 2: 消除 $\varepsilon$-规则 (TERM)
   • 目的: CNF 中除了 $S_0 \rightarrow \varepsilon$（如果需要），不允许有其他形如 $A \rightarrow \varepsilon$ 的规则。
   • 操作: 找到一条规则 $A \rightarrow \varepsilon$ 并删除它。然后，必须“补偿”因 A 可以消失而带来的影响。具体做法是：在整个文法中，找到所有在右侧包含 $A$ 的规则，对于每一条这样的规则，都添加一个“A消失了”的版本。例如，如果存在规则 $R \rightarrow uAv$，就要添加一条新规则 $R \rightarrow uv$。如果规则是 $R \rightarrow uAvAw$，则需要添加 $R \rightarrow uvAw$, $R \rightarrow uAvw$, 和 $R \rightarrow uvw$ 三个新版本。这个过程需要迭代，直到所有非开始变量的 $\varepsilon$-规则都被消除。
3. 阶段 3: 消除单元规则 (UNIT)
   • 目的: CNF 不允许有形如 $A \rightarrow B$ 的规则，其中右侧只有一个变量。
   • 操作: 找到一条单元规则 $A \rightarrow B$ 并删除它。然后进行“补偿”：找到所有以 $B$ 为左侧的规则，比如 $B \rightarrow w$。为 $A$ 添加一条新规则 $A \rightarrow w$。这样做相当于把 $B$ 的能力“复制”给了 $A$。这个过程也需要迭代，例如，如果 $A \rightarrow B$ 且 $B \rightarrow C$，最终需要把 $C$ 的所有规则都复制给 $A$。
4. 阶段 4: 转换剩余规则 (CLEANUP)
   • 目的: 经过前几个阶段，剩下的规则可能仍然不符合 CNF 的两种形式。例如，可能存在 A -> aBC (混合终结符和变量) 或 A -> BCD (右侧多于两个变量)。
   • 操作:
   • 对于混合终结符和变量的规则，将终结符“外包”出去。例如，对于 A -> aBC，引入一个新变量 $U_a$ 和新规则 $U_a \rightarrow a$，然后将原规则替换为 A -> U_a BC。
   • 对于右侧变量多于两个的规则，进行“二叉化分解”。例如，对于 A -> BCD，引入一个新变量 $A_1$，将原规则分解为两条新规则：A -> B A_1 和 A_1 -> CD。这样，每条规则的右侧都只有两个变量了。

通过这四个阶段的处理，任何一个 CFG 都可以被系统地、算法化地转换为一个生成相同语言的 CNF 文法。

这一部分是定理 2.9 的正式证明，它详细描述了将任意 CFG 转换为 CNF 的四步算法。

第一步：处理开始变量 (START)

• 操作:

1. 引入一个全新的变量 $S_0$。
2. 添加一条新规则 $S_0 \rightarrow S$，其中 $S$ 是原来的开始变量。
3. 将 $S_0$ 设为文法的新开始变量。
   • 目的: 这一步的目的是为了“隔离”开始变量。通过这个操作，新的开始变量 $S_0$ 就绝对不会出现在任何规则的右侧了。这为后续处理（尤其是处理 $S \rightarrow \varepsilon$）铺平了道路，满足了 CNF 关于开始变量的严格要求。语言显然没有改变，因为任何从 $S$ 能推导出的东西，现在都可以从 $S_0$ 经过一步额外推导得到。

第二步：消除 $\varepsilon$-规则 (TERM)

• 目标: 消除所有形如 $A \rightarrow \varepsilon$ 的规则 (除非是 $S_0 \rightarrow \varepsilon$，并且 $S_0$ 不在右侧出现)。
• 算法:

1. 首先，确定所有“可为空的”变量 (nullable variables)。一个变量 $A$ 是可为空的，如果 $A \stackrel{*}{\Rightarrow} \varepsilon$。这可以通过一个迭代算法来找到：初始时，所有有 $A \rightarrow \varepsilon$ 规则的 $A$ 是可为空的；然后，如果存在规则 $B \rightarrow C_1 C_2 \dots C_k$ 并且所有的 $C_i$ 都已经是可为空的，那么 $B$ 也变成可为空的，如此迭代直到没有变化。
2. 对于每一条规则 $R \rightarrow w$，如果 $w$ 中包含一个或多个可为空的变量，那么就要为这条规则创建所有可能的“消失”版本。
3. 详细操作: 遍历所有规则 $R \rightarrow u_1 u_2 \dots u_k$。对于右侧的每个符号 $u_i$，如果它是一个可为空的变量，那么我们就有两种选择：保留它或删除它。我们必须生成包含所有这些选择组合的新规则。例如，规则 $R \rightarrow uAvAw$ 中，如果 $A$ 是可为空的，则需要添加三条新规则：
   • $R \rightarrow uvAw$ (第一个 $A$ 消失)
   • $R \rightarrow uAvw$ (第二个 $A$ 消失)
   • $R \rightarrow uvw$ (两个 $A$ 都消失)
4. 最后，删除所有原始的 $A \rightarrow \varepsilon$ 形式的规则 (除了可能的 $S_0 \rightarrow \varepsilon$)。
   • 特殊情况: 如果在上述过程中，一条规则 $R \rightarrow A$ 因为 $A$ 可为空而需要添加 $R \rightarrow \varepsilon$，那么就添加它。但后续如果 $R$ 的 $\varepsilon$-规则也要被消除，这个过程会继续。这个过程保证了任何可以生成 $\varepsilon$ 的路径都被保留了下来。

第三步：消除单元规则 (UNIT)

• 目标: 消除所有形如 $A \rightarrow B$ 的规则，其中 $A$ 和 $B$ 都是变量。
• 算法:

1. 同样，这是一个迭代过程。对于每个变量 $A$，计算它可以推导出的所有变量的集合（即所有满足 $A \stackrel{*}{\Rightarrow} B$ 的 $B$）。
2. 然后，对于每一对满足 $A \stackrel{*}{\Rightarrow} B$ 的 $(A, B)$，将所有 $B$ 的非单元规则（形如 $B \rightarrow w$，$w$ 不是单个变量）都“复制”给 $A$，即添加规则 $A \rightarrow w$。
3. 简化操作描述: 对于一条单元规则 $A \rightarrow B$，删除它。然后，对于所有以 $B$ 开头的规则 $B \rightarrow u$，添加新规则 $A \rightarrow u$。如果新添加的规则 $A \rightarrow u$ 又是单元规则（比如 $u$ 是一个变量 $C$），则重复此过程，直到没有新的单元规则产生。
4. 最后，删除所有原始的单元规则。
   • 目的: 这保证了任何通过一系列变量传递的推导能力，都被一个直接的规则所取代。

第四步：清理剩余规则 (CLEANUP)

• 目标: 将所有现有规则转换为 $A \rightarrow BC$ 或 $A \rightarrow a$ 的形式。此时，所有规则的右侧长度至少为1（除了 $S_0 \rightarrow \varepsilon$），且不含单元规则。
• 算法分为两部分:

1. 处理混合终端符和变量/长终端符串:
   • 遍历所有规则。如果一条规则 $A \rightarrow w$ 的右侧 $w$ 长度大于1，并且包含任何终结符，那么就为每个这样的终结符 a 创建一个全新的变量 $U_a$ 和一条新规则 $U_a \rightarrow a$。然后，在原规则 $w$ 中，用变量 $U_a$ 替换掉终结符 a。
   • 例如，A -> aB 变为 A -> U_a B 和 U_a -> a。A -> ab 变为 A -> U_a U_b，U_a -> a, U_b -> b。
   • 经过这一步，所有长度大于1的规则右侧都只包含变量。
2. 处理长变量串:
   • 遍历所有规则。如果一条规则形如 $A \rightarrow A_1 A_2 \dots A_k$ 且 $k \ge 3$，则将其分解。
   • 引入一系列新的变量 $N_1, N_2, \dots, N_{k-2}$。
   • 将原规则替换为一组新规则:
   • $A \rightarrow A_1 N_1$
   • $N_1 \rightarrow A_2 N_2$
   • ...
   • $N_{k-2} \rightarrow A_{k-1} A_k$
   • 这就像将一个长链条从左到右断开，每次只保留两个环节。
   • 最终结果: 经过这两部分处理，所有规则都变成了 CNF 的两种标准形式之一。

这个四步过程保证了任何 CFG 都可以被机械地转换为等效的 CNF 文法。

这个例子通过一个完整的、循序渐进的过程，演示了如何将一个给定的文法 $G_6$ 转换为乔姆斯基范式 (CNF)。每一步都严格遵循了前面证明中描述的算法。

初始文法 $G_6$:

```

S -> ASA | aB

A -> B | S

B -> b | ε

```

第 1 步: 添加新开始变量 (START)

• 操作: 引入新变量 $S_0$，添加规则 $S_0 \rightarrow S$。$S_0$ 成为新的开始变量。
• 结果:

```

S0 -> S

S -> ASA | aB

A -> B | S

B -> b | ε

```

• 目的: 隔离开始变量。现在 $S_0$ 不在任何规则的右侧，为后续步骤做好了准备。

第 2 步: 消除 $\varepsilon$-规则 (TERM)

这是一个迭代的过程。

• 第一次迭代 (消除 $B \rightarrow \varepsilon$):
• 可为空变量: $B$ 是可为空的 ($B \rightarrow \varepsilon$)。
• 操作:

1. 找到使用 $B$ 的规则: $A \rightarrow B$ 和 $S \rightarrow aB$。
2. 对于 $S \rightarrow aB$，添加 $B$ 消失的版本: $S \rightarrow a$。
3. 对于 $A \rightarrow B$，添加 $B$ 消失的版本: $A \rightarrow \varepsilon$。
4. 删除 $B \rightarrow \varepsilon$。
   • 结果 (左栏):
   • 第二次迭代 (消除 $A \rightarrow \varepsilon$):
   • 可为空变量: 现在 $A$ 变成可为空的了 ($A \rightarrow \varepsilon$)。
   • 操作:
5. 找到使用 $A$ 的规则: $S \rightarrow ASA$。
6. $S \rightarrow ASA$ 有两个 $A$，所以要添加三个新版本：
   • 第一个 $A$ 消失: $S \rightarrow SA$
   • 第二个 $A$ 消失: $S \rightarrow AS$
   • 两个 $A$ 都消失: $S \rightarrow S$ (这是一个新的单元规则)
7. 删除 $A \rightarrow \varepsilon$。
   • 结果 (右栏):

第 3 步: 消除单元规则 (UNIT)

这也是一个迭代过程。

• 3a. 第一次迭代 (消除 $S \rightarrow S$ 和 $S_0 \rightarrow S$):
• 消除 $S \rightarrow S$: 这是一条无用的规则，直接删除即可。
• 结果 (左栏): S -> ASA | aB | a | SA | AS
• 消除 $S_0 \rightarrow S$:

1. 删除 $S_0 \rightarrow S$。
2. 将所有 $S$ 的规则右侧复制给 $S_0$:

$S_0 \rightarrow ASA | aB | a | SA | AS$

• 结果 (右栏):

```

S0 -> ASA | aB | a | SA | AS

S -> ASA | aB | a | SA | AS

A -> B | S

B -> b

```

• 3b. 第二次迭代 (消除 $A \rightarrow B$ 和 $A \rightarrow S$):
• 消除 $A \rightarrow B$:

1. 删除 $A \rightarrow B$。
2. B 的规则是 B -> b。
3. 添加新规则 $A \rightarrow b$。
   • 中间结果: A -> S | b
   • 消除 $A \rightarrow S$:
4. 删除 $A \rightarrow S$。
5. 将所有 S 的规则右侧 ASA | aB | a | SA | AS 复制给 A。
6. 添加新规则 $A \rightarrow ASA | aB | a | SA | AS$。
   • 最终结果:

第 4 步: 清理剩余规则 (CLEANUP)

• 目标: 将所有规则转换为 $X \rightarrow YZ$ 或 $X \rightarrow x$ 的形式。
• 操作:

1. 处理终结符:
   • 规则 ... -> aB 和 ... -> a 中的 a 需要处理。
   • 引入新变量 U 和规则 $U \rightarrow a$。
   • 将所有 aB 替换为 UB。
   • 将所有单独的 a 保留（因为它已经是 A->a 形式）。
   • B -> b 和 A -> b 中的 b 也已经是 A->a 形式，无需处理。
2. 处理长规则:
   • 规则 ... -> ASA 右侧长度为 3。
   • 引入新变量 A1。
   • 将 ASA 分解为两条规则：... -> A A1 和 $A1 \rightarrow SA$。
3. 组合和整理:
   • 将上述变换应用到 S0, S, A 的所有规则上。
   • S0 的规则 ASA | aB | a | SA | AS 变为:
   • ASA -> A A1
   • aB -> U B
   • a -> a (保留)
   • SA -> S A (已经是 CNF)
   • AS -> A S (已经是 CNF)
   • 对 S 和 A 的规则做同样处理。
   • 最终结果 (如文中所列):

• 关于简化的说明: 文本中提到，严格按照算法，每个终结符都会有一个自己的变量（如 $U_a, U_b$ 等）。但如果多个地方都需要同一个终结符 a，可以复用同一个新变量 U (代表 a)，以使最终文法更简洁。这是一种无伤大雅的优化。