第3章 语法分析（Token 到语法树）

一、导读

1.1 本章学习目标

理解上下文无关文法（CFG）的定义、产生式规则及其描述编程语言语法的能力

掌握推导（Derivation）与解析（Parsing）的关系，理解最左推导与最右推导

掌握抽象语法树（AST）的结构设计与构建方法

理解递归下降解析器的原理、实现方法以及左递归和回溯问题的处理

掌握 LL(1) 文法的判定条件与 LL 分析表的构造方法

理解 LR 分析的核心思想：移进-归约（Shift-Reduce）范式

掌握 SLR(1)、LALR(1) 和 LR(1) 分析表的构造方法及其表达能力差异

了解语法分析器生成工具（Yacc/Bison、ANTLR）的使用方法及其工程实践

1.2 为什么本章如此重要

语法分析是编译器前端的核心环节，它承担着将线性的 Token 序列组织为层次化的语法结构的重任。如果说词法分析是将字符组装成"单词"，那么语法分析就是将这些"单词"组织成"句子"和"段落"——它揭示了程序的嵌套结构、层次关系和组合规律。没有语法分析，编译器只能看到一串扁平的符号，无法理解程序的结构化语义。

语法分析的理论基础——上下文无关文法（CFG）——是计算机科学中最成功的形式语言理论之一。CFG 的表达能力恰好能够描述绝大多数编程语言的语法结构（包括表达式优先级、嵌套的控制结构、递归的函数定义等），同时又保持良好的算法性质——存在多种高效的确定性解析算法，能够在 O(n) 时间内完成长度为 n 的程序解析。这种表达能力与计算效率的完美平衡，使得 CFG 成为编程语言语法描述的标准工具。

从工程角度来看，语法分析是编译器开发中工作量最大的阶段之一。不同的编程语言有不同的语法特性——C 语言的声明语法、C++ 的模板语法、Java 的泛型语法、Python 的缩进语法、Haskell 的布局规则——每种特性都对语法分析器提出了独特的挑战。此外，语法分析器还需要处理错误恢复，在源代码存在语法错误时尽可能继续分析，为用户提供完整的错误信息。理解语法分析的理论与技术，是设计和实现任何编程语言处理工具的基础。

1.3 核心问题引导

为什么上下文无关文法能够描述编程语言的语法，而正则表达式不够？

递归下降解析器为什么不能直接处理左递归文法？如何解决这一问题？

LL 分析和 LR 分析的本质区别是什么？为什么 LR 分析能够处理更广泛的文法？

为什么 LR(1) 比 SLR(1) 更强大？LALR(1) 如何在保持 LR(1) 能力的同时减少状态数？

二义性文法为什么不能直接用于语法分析？如何通过优先级和结合性规则消除二义性？

语法分析器如何在遇到错误时进行恢复，而不是在第一个错误处就停止？

为什么现代编译器（如 GCC、Clang）普遍使用自动生成工具（如 Bison）来生成语法分析器？

二、核心概念详解

2.1 上下文无关文法与产生式规则

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

以简单的算术表达式文法为例：E -> E + T | T，T -> T F | F，F -> ( E ) | id。这个文法定义了由加法、乘法和括号组成的算术表达式的语法结构。非终结符 E、T、F 分别代表表达式、项和因子，它们之间的递归定义体现了运算符的优先级（乘法优先于加法）和结合性（左结合）。终结符 `+`、`、(、)、id` 是词法分析器输出的 Token 类型。

推导（Derivation）是从起始符号出发，反复应用产生式规则将非终结符替换为右部符号串的过程。最左推导（Leftmost Derivation）在每一步中选择最左边的非终结符进行替换，最右推导（Rightmost Derivation）则选择最右边的非终结符。对于无二义性文法，每个句子都有唯一的最左推导和唯一的最右推导。

文法的二义性（Ambiguity）是指存在某个句子，它有两棵不同的语法树（或等价地，两个不同的最左推导）。二义性文法不能直接用于语法分析，因为分析器无法确定应该使用哪棵语法树。消除二义性的方法包括：重写文法使其无二义、引入优先级和结合性规则（如 Yacc/Bison 中的 %left、%right 声明），或使用特殊的冲突解决策略。

2.2 递归下降与 LL 分析

递归下降（Recursive Descent）是最直观的语法分析方法，它为文法中的每个非终结符编写一个递归函数。当函数处理某个非终结符时，它根据当前的输入 Token（向前看符号）选择对应的产生式，然后按照产生式的右部从左到右依次处理每个符号——遇到终结符则匹配并消耗输入 Token，遇到非终结符则调用对应的递归函数。

递归下降分析器本质上实现的是最左推导过程，属于自顶向下（Top-Down）的分析策略。它的优点是直观易懂、便于手工编写、错误消息清晰、可以方便地在解析过程中构建 AST。大多数手工编写的语法分析器（包括 GCC、Clang、Rust 的前端）都采用递归下降或变种的递归下降方法。

然而，基本的递归下降面临两个主要问题。第一是左递归问题：如果文法包含形如 A -> A alpha 的产生式（直接左递归）或经过若干步推导后 A =>+ A alpha（间接左递归），递归下降函数会陷入无限递归。解决方法是消除左递归——将左递归文法改写为等价的右递归文法，例如将 E -> E + T | T 改写为 E -> T E'，E' -> + T E' | epsilon。第二是回溯问题：当多个产生式以相同的符号开头时，分析器可能需要尝试多个选择，失败后回溯到之前的状态。这不仅影响效率，还使得错误处理变得复杂。

LL(1) 分析通过引入预测分析表解决了回溯问题。LL(1) 的含义是：Left-to-right 扫描输入、Leftmost 推导、1 个向前看符号。LL(1) 文法要求每个非终结符的每个产生式的 FIRST 集互不相交，这样分析器只需查看一个向前看 Token 就能确定使用哪个产生式，无需回溯。LL(1) 分析表的构造基于 FIRST 集和 FOLLOW 集的计算，时间复杂度为 O(|G|)，其中 |G| 是文法的大小。

2.3 LR 分析：移进-归约范式

LR 分析是自底向上（Bottom-Up）语法分析的代表方法，它的核心思想是移进-归约（Shift-Reduce）。分析器维护一个栈和一个输入缓冲区，在每一步中执行两种操作之一：移进（Shift）——将输入的下一个 Token 压入栈顶；归约（Reduce）——将栈顶的若干个符号（与某个产生式的右部匹配）替换为该产生式的左部非终结符。当栈中只剩下起始符号且输入为空时，分析成功。

LR 分析的关键在于如何决定每一步是移进还是归约，以及归约时使用哪个产生式。这个决策通过分析器的状态（State）和向前看 Token（Lookahead）来确定。LR 分析器的状态由 LR 自动机的状态表示，每个状态对应一组"项"（Item），即带有位置标记的产生式。分析表包含 ACTION 表（决定移进、归约、接受或报错）和 GOTO 表（决定状态转移）。

LR 分析有多个变体，它们在表达能力和实现复杂度之间形成梯度。SLR(1)（Simple LR）是最简单的变体，使用 FOLLOW 集来确定归约的向前看符号，实现简单但能力有限。LR(1) 是最强大的变体，每个项都携带精确的向前看符号，能够处理最大范围的确定性上下文无关文法，但状态数量可能非常多。LALR(1)（Look-Ahead LR）是 LR(1) 的实用折中——它合并 LR(1) 自动机中具有相同核心（产生式和位置标记相同）的状态，将状态数量从 LR(1) 的数万减少到与 SLR(1) 相当的几千，同时保持了 LR(1) 的全部分析能力。Yacc 和 Bison 都使用 LALR(1) 作为默认的分析方法。

2.4 抽象语法树的设计与构建

抽象语法树（Abstract Syntax Tree, AST）是源代码语法结构的树形表示，它是语法分析器的核心输出，也是后续语义分析和代码生成的输入。与具体的语法树（Concrete Syntax Tree/Parse Tree）不同，AST 省略了不影响语义的语法细节（如括号、分隔符、关键字），只保留程序的核心结构信息。

AST 的节点设计通常遵循面向对象的原则。基类 ASTNode 定义所有节点共有的属性（如源文件位置信息），不同的节点类型继承自基类并定义各自的特有属性。例如，表达式节点（Expression）包括二元运算节点（BinaryOp，包含运算符和左右操作数）、一元运算节点（UnaryOp）、字面量节点（Literal，包含值和类型）和标识符节点（Identifier，包含名字）。语句节点（Statement）包括赋值语句、if 语句、while 语句、return 语句等。声明节点（Declaration）包括变量声明、函数声明、类型声明等。

AST 的构建可以在语法分析的过程中同步完成——每当语法分析器归约一个产生式时，就创建对应的 AST 节点并将其与子节点关联。在递归下降分析器中，这非常自然：每个解析函数在解析完子结构后，创建父节点并将子节点作为其子树。在 LR 分析器中，这通过语义动作（Semantic Action）实现——每个产生式关联一段代码，在归约时执行以构建 AST 节点。

AST 的设计质量直接影响后续编译阶段的实现难度。好的 AST 设计应当：完整表达源程序的语义信息，便于遍历和变换，类型安全（使用不同的类表示不同的节点类型），以及可扩展（便于添加新的语言特性）。

2.5 错误恢复与错误报告

语法分析器不仅需要正确解析合法的源代码，还需要在源代码存在语法错误时提供有用的错误信息并尽可能继续分析，以发现更多的错误。这就是错误恢复（Error Recovery）的任务。

常见的错误恢复策略包括：恐慌模式（Panic Mode）——当检测到语法错误时，丢弃输入 Token 直到遇到一个同步 Token（如分号、右花括号等语句边界符号），然后从该点恢复分析。这种方法简单有效，能够跳过错误区域继续分析后续代码，但可能遗漏错误区域内的真实错误。短语层次恢复（Phrase-Level Recovery）——在检测到错误时，对栈顶或输入进行局部的 Token 插入或删除来修复错误，然后继续分析。这种方法可以发现更多的错误，但实现复杂且可能引发级联错误。

错误报告的质量是衡量编译器用户体验的重要指标。好的错误消息应当：准确指出错误的位置（文件名、行号、列号），清晰描述错误的性质（"期望 ; 但遇到 }"），并在可能的情况下提供修复建议（"你是否忘记了分号？"）。现代编译器如 Clang 在错误报告方面做得尤为出色，使用彩色高亮、代码片段展示和修复建议（Fix-it Hint）来帮助用户快速理解和修复错误。

三、深入分析与讨论

3.1 LL 与 LR 的工程选择

LL 和 LR 是语法分析的两大主流方法，它们在工程实践中各有优劣。选择哪种方法取决于多方面的因素。

从表达能力来看，LR 严格强于 LL。任何 LL 文法都是 LR 文法，但存在 LR 文法不是 LL 文法。例如，左递归文法（如 E -> E + T）可以被 LR 直接处理，但 LL 分析器无法处理左递归。这意味着使用 LR 分析时，文法可以更自然地表达语言的结构（特别是左结合的运算符），而 LL 分析则需要对文法进行改写。

从实现方式来看，LL 分析（特别是递归下降）更适合手工编写。递归下降分析器的代码结构与文法结构直接对应，易于理解、调试和扩展。开发者可以在解析函数中方便地嵌入语义动作、构建 AST、处理上下文相关的语法决策。而 LR 分析器的状态机逻辑复杂，通常不适合手工编写，需要依赖自动生成工具（如 Yacc/Bison）。

从错误处理来看，LL 分析器在检测到错误时通常能提供更精确的错误消息，因为它在"预测"阶段就能发现不匹配的输入。而 LR 分析器可能在移进多个 Token 后才发现错误，错误位置的定位相对困难。

现代趋势是 LL 分析的复兴。ANTLR 4 使用 ALL(*) 自适应分析算法，能够处理比 LL(1) 更广泛的文法，同时保持递归下降的直观性。Swift 的编译器、Rust 的编译器（早期版本）都采用了手工编写的递归下降分析器。这表明在工程实践中，可维护性和可控性往往比理论上的最大表达能力更重要。

3.2 二义性文法的工程应用

虽然理论上二义性文法不能直接用于语法分析，但在工程实践中，二义性文法有其独特的价值。许多编程语言的语法天然就是二义的——表达式文法中运算符的优先级和结合性、if-else 语句中的悬挂 else 问题、C 语言中 typedef 名字与标识符的歧义——这些问题都可以通过引入外部规则来解决。

Yacc/Bison 允许在文法中直接使用二义性产生式，然后通过 %left、%right、%nonassoc 声明来指定运算符的优先级和结合性，由工具自动解决移进-归约冲突。这种方法使得文法更加简洁自然，将优先级规则从文法结构中分离出来，便于维护和修改。例如，一个包含 10 个优先级级别的表达式文法，如果用无二义文法描述，需要 10 个非终结符和大量的产生式；而用二义文法加优先级声明，只需要 3 个非终结符和 6 个产生式。

GCC 和 Clang 的 C/C++ 前端在处理"typedef 名字 vs 标识符"的歧义时，采用了词法分析与语法分析协作的策略。词法分析器维护一个已知 typedef 名字的集合，当遇到一个标识符时，如果它在 typedef 名字集合中，则返回 TYPE_NAME Token，否则返回 IDENTIFIER Token。语法分析器根据 Token 类型的不同使用不同的产生式。这种设计将上下文敏感的歧义消解推迟到词法分析阶段，简化了语法分析器的设计。

四、实践案例

4.1 使用 Bison 实现计算器语法分析器

以下展示如何使用 Yacc/Bison 实现一个简单的四则运算计算器。文法定义包含四个运算符（加减乘除）、括号和整数常量，通过 %left 声明指定运算符的优先级和结合性。

Bison 文件分为三部分：声明段定义 Token 类型和优先级规则；中段定义产生式和语义动作——每个产生式关联一段 C 代码，在归约时计算表达式的值（使用 $$ 引用归约结果，$1、$2、$3 引用右部各符号的值）；尾段包含 main 函数和错误处理函数 yyerror。

当输入 3 + 4 * 5 时，分析器首先移进 3、+、4、*、5，然后由于 * 的优先级高于 +，先归约 4 * 5 = 20，再归约 3 + 20 = 23，输出正确结果。这个简单的例子展示了 LR 分析器如何通过优先级声明自动处理运算符的优先级和结合性，而无需在文法中显式编码。

4.2 递归下降分析器中的错误恢复实践

以手工编写的递归下降分析器为例，展示恐慌模式错误恢复的实现。当分析器期望某个 Token 但遇到不匹配的输入时，它首先报告错误（包含当前位置信息），然后进入恢复循环：跳过输入 Token 直到遇到同步集合中的 Token。同步集合的选择取决于当前的语法上下文——在语句级别，同步集合通常包括分号、右花括号和语句起始关键字（如 if、while、for、return）；在表达式级别，同步集合可能包括右括号、逗号和运算符。

为了减少级联错误，分析器在恢复后通常会设置一个"恐慌标志"，在遇到下一个同步 Token 之前抑制额外的错误消息。此外，分析器可以维护一个"期望 Token 集合"，在错误消息中列出当前上下文可能接受的所有 Token，帮助用户理解错误原因。这种策略在实践中能够有效地将错误限制在局部范围内，使得一次编译可以发现源代码中的多个语法错误。

五、常见误区与注意事项

5.1 误区一：语法分析器能检测所有语法错误

语法分析器只能检测违反上下文无关文法约束的错误。某些语义错误（如变量未声明、类型不匹配）需要语义分析器来检测。此外，某些语法错误可能导致分析器产生大量的级联错误消息，使得真正的错误原因被淹没。好的错误恢复策略可以缓解这一问题，但无法完全消除。

5.2 误区二：LR 分析器一定比 LL 分析器好

虽然 LR 在理论上更强大，但工程选择不仅取决于理论能力。LL 分析器（特别是递归下降）更容易手工编写、调试和扩展，错误消息通常更精确，代码可读性更好。对于大多数实际编程语言的语法，经过适当改写的 LL 文法完全能够胜任。选择分析方法应综合考虑语言特性、团队经验、维护成本和错误处理需求。

5.3 误区三：自动生成的分析器一定优于手工编写的分析器

自动生成的分析器（如 Bison 生成的 LALR 分析器）在性能和正确性上有理论保证，但在错误处理和上下文敏感决策方面往往不如手工编写的分析器灵活。许多生产级编译器（GCC、Clang、Rust、Go）都选择了手工编写的递归下降分析器，以获得更好的错误消息和更灵活的语法处理能力。

5.4 注意事项：文法设计对分析器质量的影响

文法的设计直接影响分析器的效率、错误处理能力和可维护性。好的文法应当：避免不必要的二义性，合理使用优先级声明而非强制无二义改写，保持产生式的简洁性和可读性，以及考虑分析方法的限制（如 LL 文法不能有左递归）。文法设计是语法分析中最需要经验和判断力的环节。

5.5 注意事项：语法分析器的性能

语法分析器的性能通常不是编译器的瓶颈（词法分析和代码优化往往占用更多时间），但在处理大型源文件（如 C++ 的头文件包含链）时，语法分析的性能也可能成为关注点。使用高效的分析算法、避免不必要的回溯、合理设计 AST 节点的内存分配策略，都是优化语法分析器性能的重要手段。

六、本章小结

本章系统介绍了语法分析的理论与技术。上下文无关文法为描述编程语言语法提供了精确的形式化工具，推导过程定义了从文法到句子的生成路径。自顶向下的 LL 分析方法（包括递归下降和预测分析）直观易懂，适合手工实现；自底向上的 LR 分析方法（包括 SLR、LALR 和 LR(1)）能力更强，适合自动生成。抽象语法树是语法分析的核心输出，其设计质量直接影响后续编译阶段。错误恢复是语法分析器工程实现中的重要环节，恐慌模式和短语层次恢复是两种经典的策略。在实际的编译器开发中，选择语法分析方法需要综合考虑文法特性、工程需求、团队经验和维护成本。

七、思考题与练习

为以下语言设计上下文无关文法：(a) 所有由 a 和 b 组成且 a 的数量等于 b 的数量的字符串，(b) 嵌套的括号语言（包含 ()、[]、{} 三种括号），(c) 简化的 C 语言声明语法。

手动构造文法 E -> E + T | E - T | T, T -> T * F | T / F | F, F -> ( E ) | id 的 LR(0) 项集族，并构建 SLR(1) 分析表。

实现一个递归下降分析器来解析 JSON 格式，要求能够处理所有 JSON 数据类型并构建完整的 AST。

比较 Bison 和 ANTLR 4 的设计理念和使用方式，分析它们各自适合的应用场景。

调研 Clang 编译器的语法分析器实现，分析它是如何处理 C++ 的"最令人头疼的解析"（Most Vexing Parse）问题的。

实现恐慌模式的错误恢复策略，测试它在不同类型的语法错误下的表现，分析同步集合的选择对错误恢复质量的影响。

证明：任何 LL(1) 文法都是 LR(1) 文法，但存在 LR(1) 文法不是 LL(1) 文法。

设计一个支持错误修复建议（Fix-it Hint）的语法分析器，当检测到缺少分号或括号时，自动提供修复方案。