第3章语法分析（上下文无关文法） Syntax Analysis

一、导读

1.1 本章学习目标

理解上下文无关文法（CFG）的形式化定义、推导过程和语法树的构建方法

掌握二义性文法的概念、危害及消除二义性的常用策略

深入理解 LL(1) 分析的原理，包括 FIRST/FOLLOW 集的计算和预测分析表的构造

掌握递归下降解析器的手工实现方法及其与 LL(1) 文法的关系

理解 LR 分析的核心思想，掌握 LR(0)、SLR(1)、LALR(1) 和 LR(1) 的区别与联系

学会使用 Yacc/Bison 等语法分析器生成工具编写文法文件并生成解析代码

理解语法错误恢复的主要策略（恐慌模式、短语层次恢复、全局纠正）

1.2 为什么本章如此重要

语法分析是编译过程中最具理论深度和工程挑战性的阶段之一。如果说词法分析解决的是"字符如何组成单词"的问题，那么语法分析解决的就是"单词如何组成合法句子"的问题。编程语言的嵌套结构——if 语句中包含表达式，表达式中包含函数调用，函数调用中包含参数列表——这种递归嵌套的特性正是上下文无关文法所刻画的。

从历史角度看，语法分析理论的发展直接推动了编译器从"手工艺品"走向"工业产品"。1950 年代，编译器开发者手工编写语法分析代码，每种语言都需要从零开始。1960 年代，Knuth 提出 LR 分析理论，使得文法规则可以自动转换为高效的分析器。1970 年代，Yacc 工具的出现让开发者只需编写文法描述，即可自动生成语法分析器。这种自动化极大地降低了编译器开发的门槛，也催生了大量新的编程语言。

今天，语法分析技术的影响已远超编译器领域。配置文件解析（JSON、YAML、TOML）、文档格式处理（HTML、XML）、查询语言实现（SQL、GraphQL）、协议定义（Protocol Buffers、gRPC）——几乎所有需要处理结构化数据的场景都依赖语法分析技术。掌握本章内容，等于掌握了处理一切结构化信息的通用方法论。

1.3 核心问题引导

为什么正则表达式不足以描述编程语言的语法？需要什么更强大的工具？

什么是二义性文法？为什么它对编译器实现有害？如何消除二义性？

LL 分析和 LR 分析的根本区别是什么？各自能处理哪类文法？

为什么 LR 分析比 LL 分析更强大？是否存在 LR 能处理但 LL 不能处理的实际文法？

递归下降解析器为什么容易理解和调试？它的局限性在哪里？

Yacc/Bison 报告"移进-归约冲突"和"归约-归约冲突"时，应该如何处理？

语法分析器遇到错误输入时，如何尽可能多地报告后续错误而非在第一个错误处停止？

二、核心概念详解

2.1 上下文无关文法与推导（约 700 字）

上下文无关文法（Context-Free Grammar, CFG）是一个四元组 G = (V, T, P, S)，其中 V 是非终结符（Nonterminal）的有穷集合，T 是终结符（Terminal）的有穷集合，P 是产生式（Production）的有穷集合，S 是起始符号（Start Symbol）。产生式的形式为 A -> alpha，其中 A 属于 V，alpha 属于 (V 并 T)*，表示非终结符 A 可以被替换为符号串 alpha。

"上下文无关"这个名字的含义是：产生式的应用不依赖于 A 出现的上下文环境。无论在什么位置看到非终结符 A，都可以用 alpha 替换它。这与上下文有关文法（Context-Sensitive Grammar）形成对比，后者的替换规则依赖于 A 的左右上下文。

推导（Derivation）是从起始符号出发，反复应用产生式将非终结符替换为符号串的过程。如果每步推导都替换最左边的非终结符，称为最左推导（Leftmost Derivation）；如果替换最右边的非终结符，称为最右推导（Rightmost Derivation），也称为规范推导（Canonical Derivation）。

例如，考虑一个简单的表达式文法：E -> E + T | T, T -> T F | F, F -> ( E ) | id。句子 `id + id id` 的最左推导过程为：E => E + T => T + T => F + T => id + T => id + T F => id + F F => id + id F => id + id id。

语法分析树（Parse Tree）是推导过程的树形表示：根节点是起始符号，每个内部节点是一个产生式的应用，叶节点是终结符或 epsilon。语法分析树直观地展示了句子的层次结构，是语法分析器的核心输出。

2.2 二义性及其消除（约 600 字）

如果一个文法可以为同一个句子生成两棵或两棵以上不同的语法分析树（等价地，存在两个不同的最左推导），则该文法是二义的（Ambiguous）。二义性对编译器是致命的：不同的语法树对应不同的语义解释，编译器无法确定应该采用哪一种。

经典的二义性案例是表达式文法：E -> E + E | E E | ( E ) | id。句子 `id + id id 可以有两种解析：一种是 (id + id) id`（先加后乘），另一种是 `id + (id id)`（先乘后加）。显然，数学上正确的语义是后者（乘法优先于加法）。

消除二义性的方法有两种。第一种是改写文法，通过引入额外的非终结符来强制优先级和结合性。例如，将上述文法改写为：E -> E + T | T, T -> T * F | F, F -> ( E ) | id。这个新文法是无二义的，它通过分层结构自然地表达了乘法优先于加法、运算符左结合的规则。

第二种方法是使用外部规则（如优先级和结合性声明），保持文法简洁的同时由分析器生成工具解决冲突。Yacc/Bison 就支持 %left、%right、%nonassoc 等声明，允许开发者为运算符指定优先级和结合性，工具在遇到移进-归约冲突时自动根据优先级做出决策。这种方法在实践中更常用，因为它使文法更接近语言的数学定义。

2.3 LL 分析：自顶向下的预测解析（约 700 字）

LL 分析是一种自顶向下（Top-Down）的语法分析方法。第一个 L 表示从左到右扫描输入，第二个 L 表示构造最左推导。LL 分析的核心思想是：从文法的起始符号出发，根据当前输入 Token 和即将展开的非终结符，预测应该使用哪条产生式。

递归下降解析器（Recursive Descent Parser）是 LL 分析最直观的实现方式：为每个非终结符编写一个函数，函数体根据当前 Token 选择对应的产生式，然后递归调用其他非终结符的函数。例如，对于产生式 E -> T {+ T}，对应的函数为：

void E() {
  T();
  while (lookahead == '+') {
    match('+');
    T();
  }
}

递归下降解析器易于理解和调试，但有一个重要前提：文法必须是 LL(1) 的。LL(1) 的要求是：对于每个非终结符 A 的多条候选产生式 A -> alpha | beta，可以通过查看下一个输入 Token（即 1 个 Token 的前瞻）唯一确定应该选择哪条候选。

判断文法是否为 LL(1) 需要计算每个非终结符的 FIRST 集（该非终结符能推导出的所有串的第一个终结符的集合）和 FOLLOW 集（该非终结符在某个句型中后面可能紧跟的终结符的集合）。如果对于 A 的任意两条不同候选 alpha 和 beta，FIRST(alpha) 和 FIRST(beta) 不相交（当 alpha 能推导出 epsilon 时，还需检查 FIRST(beta) 和 FOLLOW(A) 不相交），则文法是 LL(1) 的。

LL(1) 分析器可以用一张预测分析表（Predictive Parsing Table）实现：表的行是非终结符，列是终结符（包括结束标记），表项 M[A, a] 表示当非终结符 A 面临输入 a 时应使用的产生式。如果表中有空项，说明文法不是 LL(1) 的；如果有多个产生式在同一表项中，说明文法有二义性或不是 LL(1) 的。

2.4 LR 分析：自底向上的移进-归约解析（约 800 字）

LR 分析是一种自底向上（Bottom-Up）的语法分析方法。L 表示从左到右扫描输入，R 表示构造最右推导的逆过程。LR 分析的核心思想是：从输入串（叶节点）出发，逐步将符号串归约为非终结符，直到得到起始符号（根节点）。

LR 分析器使用一个栈和一个分析表协同工作。栈中保存已扫描但尚未归约的符号串的前缀，分析表根据栈顶状态和当前输入 Token 决定下一步动作。动作有四种：移进（Shift，将输入 Token 压入栈）、归约（Reduce，用产生式左部的非终结符替换栈顶的右部符号串）、接受（Accept，分析成功完成）和报错（Error，发现语法错误）。

LR 分析的强大之处在于它能识别几乎所有编程语言的结构。LR 分析家族包括多个成员，能力依次增强：

LR(0) 是最基础的变体，它的分析表构造不需要任何前瞻信息。每个状态对应一个"项目集"（Item Set），项目是产生式右部带有一个"点"（标记当前扫描位置）的表示。LR(0) 的局限是容易产生移进-归约冲突和归约-归约冲突。

SLR(1)（Simple LR）通过引入 FOLLOW 集来解决部分冲突：当归约动作和移进动作冲突时，只有当当前输入 Token 属于被归约产生式左部非终结符的 FOLLOW 集时才执行归约。SLR(1) 比 LR(0) 更强大，但仍有一些冲突无法解决。

LR(1) 在 LR(0) 项目的基础上增加了一个前瞻符号，形成 LR(1) 项目 [A -> alpha . beta, a]，表示只有当输入 Token 为 a 时才允许归约。LR(1) 是最强大的，能处理所有确定性上下文无关语言，但状态数可能非常多。

LALR(1)（Look-Ahead LR）是 LR(1) 的实用折中：它合并 LR(1) 中核心项目集相同但前瞻不同的状态，状态数与 LR(0) 相当，但能力接近 LR(1)。Yacc 和 Bison 默认使用 LALR(1) 分析。

LR 分析的实际意义在于，绝大多数编程语言的语法都可以用 LALR(1) 文法描述。Bison 工具接受类 Yacc 格式的文法文件，自动生成 LALR(1) 分析器的 C 代码，极大简化了语法分析器的开发。

三、深入分析与讨论

3.1 LL 与 LR 的能力对比（约 500 字）

LL 和 LR 是语法分析的两大流派，它们的能力范围有明确的包含关系：所有 LL 文法都是 LR 文法，但存在 LR 文法不是 LL 文法。直觉上，LL 分析在"展开"非终结符时就需要预测整个子树的形状，而 LR 分析等到"看完"子树的所有叶节点后才进行归约，因此 LR 拥有更多的信息来做出决策。

一个经典的例子是左递归文法。产生式 A -> A alpha 是左递归的，LL 分析器在展开 A 时会无限递归，因此 LL 分析器无法处理左递归文法。而 LR 分析器先移进 A 的内容，再归约为 A，天然支持左递归。由于表达式的自然文法通常是左递归的（E -> E + T），LL 分析需要改写为右递归形式（E -> T {+ T}），而 LR 分析可以直接使用原始文法。

在实践中，LL 分析器的优势在于易于手工实现和调试（递归下降解析器代码直观），错误信息也更易理解。LR 分析器的优势在于能处理更广泛的文法，且由工具自动生成。现代编译器通常根据场景选择：简单语言或嵌入式 DSL 使用递归下降（LL），复杂语言使用 Bison（LALR/LR）。

3.2 错误恢复策略（约 500 字）

语法分析器遇到错误输入时，不应该立即终止，而应尽可能报告更多的错误。常见的错误恢复策略包括：

恐慌模式（Panic Mode）：发现错误后，丢弃输入 Token 直到遇到一个"同步记号"（Synchronizing Token），如分号、右花括号等语句边界符号。这种方法简单但可能遗漏错误。

短语层次恢复（Phrase-level Recovery）：在错误位置进行局部修正，如插入缺失的分号、删除多余的右括号。这种方法能恢复更多错误，但不当的修正可能导致级联错误（Cascading Errors）。

错误产生式（Error Productions）：在文法中添加专门的错误产生式，如 stmt -> error ';'，使分析器能够识别常见的错误模式并给出针对性的错误信息。

现代编译器通常组合使用多种策略。例如，GCC 在遇到语法错误时，会尝试多种恢复方法，并抑制可能由同一错误引起的级联错误信息，确保输出的错误报告既全面又准确。

3.3 文法设计的美学与实用性（约 400 字）

好的文法设计应当兼顾数学美感和工程实用性。从美学角度，文法应该简洁、对称、易于理解；从工程角度，文法应该适合自动分析（如 LALR(1)），避免不必要的二义性和冲突。

实践中常见的文法设计技巧包括：使用分层结构表达运算符优先级（表达式文法）；将列表结构（如参数列表、语句序列）用递归或迭代方式统一处理；为可选元素（如 else 子句、类型修饰符）设计清晰的产生式。好的文法设计能显著降低语法分析器的复杂度，提高错误信息的质量。

四、实践案例

4.1 案例一：用 Bison 实现计算器语法分析器（约 400 字）

Bison 是 GNU 项目对 Yacc 的兼容替代品，它接受类 Yacc 格式的文法文件并生成 C 语言的 LALR(1) 分析器。一个简单计算器的 Bison 文件核心部分如下：

动作部分为每条产生式指定语义动作：加法产生式的动作为 $$ = $1 + $3（将左右操作数的值相加），数字产生式的动作为 $$ = $1（取数字的字面值）。Bison 自动生成的分析器在归约时执行这些动作，实现了语法分析和简单语义计算的结合。

4.2 案例二：手工实现递归下降解析器（约 400 字）

递归下降解析器是理解 LL 分析的最佳实践方式。以解析简化的 JSON 为例，可以为每种 JSON 值类型编写一个解析函数：

parseValue() 根据当前 Token 决定调用哪个子解析器：遇到 { 调用 parseObject()，遇到 [ 调用 parseArray()，遇到字符串调用 parseString()，遇到数字调用 parseNumber()，遇到 true/false/null 直接返回对应值。parseObject() 循环解析 key: value 对，每对之间用逗号分隔，整体用花括号包围。parseArray() 循环解析元素，用逗号分隔，方括号包围。

这种实现方式代码结构清晰，每个函数对应文法中的一个非终结符，递归调用对应产生式的嵌套结构。调试时可以在每个函数入口打印当前 Token，形成类似调用栈的跟踪信息，非常便于定位语法错误。

五、常见误区与注意事项

5.1 误区一：无二义的文法就是好文法

无二义性只是文法的必要条件，不是充分条件。一个文法可能无二义但不适合 LL 或 LR 分析（例如存在 FIRST/FOLLOW 冲突或移进-归约冲突）。好的文法应该既无二义，又适合目标分析算法处理。

5.2 误区二：LR 分析器能处理一切文法

LR 分析只能处理确定性上下文无关语言（DCFL）。有些无二义文法不是 LR 的（需要查看超过 1 个 Token 的前瞻才能做出决策）。此外，LR 分析器无法处理上下文有关的结构（如 C 语言中类型名和标识符的区分需要符号表信息）。

5.3 误区三：语法分析器应该报告所有错误

语法分析器的错误报告应当"有用"而非"全面"。一个语法错误可能引发多个级联错误信息，反而干扰开发者定位真正的问题。好的编译器会智能地抑制级联错误，并在适当位置恢复分析，确保每个报告的错误都是独立的、有意义的。

5.4 注意事项：左递归与 LL 分析的冲突

左递归是 LL 分析的"天敌"。如果文法包含左递归产生式（如 A -> A alpha），递归下降解析器会无限递归导致栈溢出。将左递归文法转换为 LL(1) 文法需要消除左递归并提取左公因子，这个过程可能使文法变得不直观。在选择分析策略时，需要根据文法特性权衡 LL 和 LR。

六、本章小结

本章系统讲解了语法分析的理论与实践。上下文无关文法为描述编程语言的嵌套结构提供了形式化工具，推导和语法分析树建立了文法与句子结构之间的对应关系。LL 分析采用自顶向下的预测策略，适合手工实现递归下降解析器；LR 分析采用自底向上的移进-归约策略，能处理更广泛的文法类别，是 Yacc/Bison 等工具的理论基础。二义性文法需要通过改写或优先级声明来消除。错误恢复策略使分析器能够在发现错误后继续分析，报告更多独立的错误信息。掌握语法分析技术，是构建编译器前端的核心能力。

七、思考题与练习

为简化的 C 语言声明语法（支持指针、数组、函数指针）编写上下文无关文法，并验证其是否为 LL(1) 或 LR(1)。

计算以下文法所有非终结符的 FIRST 集和 FOLLOW 集：S -> AaBb, A -> a | epsilon, B -> b | epsilon。判断该文法是否为 LL(1)。

手工构造以下文法的 LR(0) 项目集规范族和 SLR(1) 分析表：E -> E + T | T, T -> T * F | F, F -> ( E ) | id。

实现一个递归下降解析器，能够解析并计算包含加减乘除和括号的算术表达式。

用 Bison 编写一个能解析简化 SQL SELECT 语句（支持 SELECT、FROM、WHERE、ORDER BY）的语法分析器。

分析以下文法的二义性：S -> if E then S | if E then S else S | other。给出两种不同的语法树，并说明如何通过优先级规则解决"悬空 else"问题。

比较 Bison 和 ANTLR 的设计哲学和适用场景，说明在什么情况下你会选择其中之一。

调研"Parser Combinator"模式（如 Haskell 的 Parsec、Rust 的 nom），说明它与传统的 LL/LR 分析有何异同。

第3章 语法分析（上下文无关文法） Syntax Analysis