📚 课程目录第4章语法分析基础

4、语法分析基础：上下文无关文法（CFG）、推导与归约、语法树（AST）的概念，以及二义性文法的处理

语法分析是编译器的第二个核心阶段，其任务是将词法分析产生的序列，按照源语言的语法规则组织成一棵结构化的语法树。如果说词法分析解决的是“单词拼写是否正确”，那么语法分析解决的就是“句子结构是否合法”。本章将深入剖析上下文无关文法（CFG）的形式化定义、推导与归约的逆过程、抽象语法树（AST）的构建逻辑，以及二义性文法的判定与消除策略。理解这些基础概念，是后续实现递归下降解析器或 LR 系列解析器的前提。

4.1 上下文无关文法（CFG）的形式化定义与作用

上下文无关文法（Context-Free Grammar, CFG）是描述程序设计语言语法结构的数学工具。它之所以被称为“上下文无关”，是因为在推导过程中，任何非终结符的替换规则（产生式）都可以独立应用，不依赖于该符号在句子中出现的上下文环境。这与自然语言中“动词变位取决于主语人称”这类上下文相关规则形成鲜明对比。

一个 CFG 由四元组 G = (V, T, P, S) 构成，其中：

V（非终结符集合）：表示语法成分的抽象符号，如表达式（E）、项（T）、因子（F）。它们可以被进一步展开。
T（终结符集合）：词法分析器输出的类型，如 ID、NUM、+、*、(、)。它们不可再分。
P（产生式集合）：形如 A → α 的规则，其中 A ∈ V，α 是由终结符和非终结符组成的任意串（可为空串 ε）。
S（开始符号）：文法中最大的语法成分，通常代表“程序”或“语句序列”。

以经典的四则运算表达式文法为例：

E → E + T   // 加法规则
E → T       // 传递规则
T → T * F   // 乘法规则
T → F       // 传递规则
F → ( E )   // 括号表达式
F → id      // 标识符或数字

在这个文法中，V = {E, T, F}，T = {+, *, (, ), id}，S = E。该文法能够生成所有合法的算术表达式，例如 id + id * id。CFG 的核心价值在于：它用有限的规则集合描述无限的语言集合，为编译器提供了可机械执行的语法判定依据。

经验提醒：在设计文法时，应确保每个非终结符都有实际意义，避免产生“死循环”规则（如 A → A 且无终止条件）。同时，产生式的数量不宜过多，否则会显著增加解析器的复杂度。通常建议将文法控制在 20-50 条产生式之间，便于维护和调试。

4.2 推导与归约：语法分析的两种视角

推导（Derivation）和归约（Reduction）是语法分析的两个互逆过程。理解它们，是掌握自顶向下和自底向上解析算法的关键。

4.2.1 推导：从开始符号到句子

推导是从文法的开始符号 S 出发，反复将某个非终结符替换为其产生式右部的过程。当所有非终结符都被替换为终结符时，得到的符号串称为该文法的一个句子。根据替换顺序的不同，推导分为：

最左推导：每次替换最左边的非终结符。自顶向下解析器（如递归下降）模拟最左推导过程。
最右推导：每次替换最右边的非终结符。自底向上解析器（如 LR 分析器）模拟最右推导的逆过程。

以表达式 id + id * id 为例，最左推导过程如下：

E ⇒ E + T        // 用 E → E + T 替换最左的 E
  ⇒ T + T        // 用 E → T 替换最左的 E
  ⇒ F + T        // 用 T → F 替换最左的 T
  ⇒ id + T       // 用 F → id 替换最左的 F
  ⇒ id + T * F   // 用 T → T * F 替换最左的 T
  ⇒ id + F * F   // 用 T → F 替换最左的 T
  ⇒ id + id * F  // 用 F → id 替换最左的 F
  ⇒ id + id * id // 用 F → id 替换最左的 F

每一步推导都对应语法树的一次“生长”。推导序列的长度等于语法树中内部节点的数量。

4.2.2 归约：从句子回到开始符号

归约是推导的逆过程：从输入的终结符串开始，反复将某个与产生式右部匹配的子串替换为该产生式的左部非终结符。如果最终能归约到开始符号 S，则输入串是合法的句子。归约过程中最关键的概念是句柄（Handle）——它是当前句型中与某个产生式右部匹配、且归约后仍能继续归约到 S 的最左简单短语。

继续使用上述例子，自底向上的归约过程（最右推导的逆过程）为：

id + id * id   // 输入串
⇐ F + id * id  // 用 F → id 归约最右的 id
⇐ T + id * id  // 用 T → F 归约 F
⇐ E + id * id  // 用 E → T 归约 T
⇐ E + F * id   // 用 F → id 归约 id
⇐ E + T * id   // 用 T → F 归约 F
⇐ E + T * F    // 用 F → id 归约 id
⇐ E + T        // 用 T → T * F 归约 T * F
⇐ E            // 用 E → E + T 归约 E + T

归约过程实际上是在构建一棵“自底向上”生长的语法树。LR 分析器通过维护一个状态栈和输入缓冲区，不断执行“移进”（将输入符号压栈）和“归约”（将栈顶的句柄替换为非终结符）操作。

对比维度	推导（Derivation）	归约（Reduction）
方向	从开始符号到句子（自顶向下）	从句子到开始符号（自底向上）
核心操作	非终结符展开	句柄识别与替换
对应解析器	递归下降、LL(1)	LR(0)、SLR(1)、LR(1)、LALR(1)
关键数据结构	调用栈（递归函数）	状态栈 + 分析表
错误检测时机	预测失败时立即报错	移进/归约冲突时延迟报错

4.3 语法树与抽象语法树（AST）

语法树（Parse Tree / Concrete Syntax Tree, CST）是推导过程的图形化表示，它完整记录了推导的每一步。CST 的叶子节点是终结符，内部节点是非终结符。然而，CST 包含大量对后续编译阶段无用的信息，例如括号、逗号、分号等辅助符号，以及冗余的传递规则节点（如 E → T → F）。

抽象语法树（Abstract Syntax Tree, AST）则是对 CST 进行压缩和抽象后的结果。AST 只保留对语义分析、中间代码生成有意义的节点，去除了语法糖和辅助符号。例如，表达式 id + id * id 的 AST 如下：

      +
     / \
    id  *
       / \
      id  id

在 AST 中，运算符作为内部节点，操作数作为子节点。括号表达式 (E) 在 AST 中不会产生额外节点，因为括号只是改变运算优先级，而优先级已经通过树的层级结构体现。AST 的设计原则是：保留语义，去除语法。

构建 AST 的时机通常在语法分析过程中。对于递归下降解析器，每个非终结符对应的解析函数返回该语法成分的 AST 节点；对于 LR 解析器，则在归约动作中创建节点并连接子节点。AST 节点的设计通常采用“变体”模式（如 C 语言的 union 或 C++ 的继承体系），以支持不同类型的表达式和语句。

  实战建议：在自制编译器中，建议直接构建 AST 而非 CST。虽然 CST 更完整，但 AST 能显著减少内存占用和后续遍历的复杂度。例如，对于赋值语句 x = y + 1，AST 只需三个节点（赋值节点、变量节点、加法节点），而 CST 可能包含 10 个以上节点（包括分号、等号、括号等）。在实现时，可以先用 CST 验证文法正确性，再逐步优化为 AST。

4.4 二义性文法的判定与处理策略

如果一个文法对同一个句子可以生成两棵不同的语法树（或存在两个不同的最左推导），则该文法是二义性（Ambiguous）的。二义性对编译器是致命的：它导致解析器无法确定正确的语义，可能产生不同的中间代码或执行结果。

4.4.1 二义性的典型来源

运算符优先级未定义：如文法 E → E + E | E * E | id，句子 id + id * id 可以解释为 (id+id)*id 或 id+(id*id)。
悬空 else（Dangling-else）：如 if_stmt → if (expr) stmt | if (expr) stmt else stmt，嵌套 if 语句中 else 的归属不明确。
左递归与结合性：如 E → E - E，句子 id - id - id 可解释为 (id-id)-id 或 id-(id-id)。

4.4.2 处理二义性的三种策略

策略一：改写文法，消除二义性。通过引入新的非终结符来强制优先级和结合性。例如，将上述二义性文法改写为：

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

这样，+ 的优先级低于 *，且两者都是左结合的。改写后的文法是无二义性的，但代价是产生式数量增加，解析效率略有下降。

策略二：使用优先级与结合性声明。许多解析器生成器（如 Yacc/Bison）允许在文法中直接声明运算符的优先级和结合性，而不必改写文法。例如：

%left '+' '-'    // 左结合，优先级低
%left '*' '/'    // 左结合，优先级高
%right '^'       // 右结合，优先级最高

生成器在遇到移进-归约冲突时，会根据优先级声明自动选择动作。这种方法简洁高效，但要求开发者对冲突解决机制有深入理解。

策略三：在语义分析阶段处理。对于某些二义性（如悬空 else），可以在语法分析时暂时接受，然后在语义分析阶段根据上下文规则进行修正。但这种方法风险较高，容易引入隐蔽的错误，不推荐在自制编译器中使用。

风险提示：二义性文法并不总是“错误”的。有些语言特性（如 C 语言的类型转换 (type)expr 与函数调用 (expr)）天然存在二义性，需要解析器结合符号表信息进行消解。在自制编译器中，建议优先采用“改写文法”策略，因为它最直观、最可控。只有在文法规模过大、改写成本过高时，才考虑使用优先级声明。

4.5 案例拆解：表达式文法的二义性消除与 AST 构建

下面通过一个完整的案例，演示如何从二义性文法出发，逐步构建无二义性文法并生成 AST。假设我们需要为一个简单的计算器语言设计语法分析器，支持加、减、乘、除和括号。

初始二义性文法：

E → E + E | E - E | E * E | E / E | ( E ) | num

该文法对 1 + 2 * 3 存在两棵语法树，无法确定运算顺序。

改写后的无二义性文法：

E   → E + T | E - T | T
T   → T * F | T / F | F
F   → ( E ) | num

改写后，+ 和 - 优先级低于 * 和 /，且所有运算符均为左结合。现在，1 + 2 * 3 只能推导为一棵语法树：1 + (2 * 3)。

AST 节点设计（C 语言风格）：

typedef enum { NODE_NUM, NODE_ADD, NODE_SUB, NODE_MUL, NODE_DIV } NodeType;

typedef struct ASTNode {
    NodeType type;
    int value;          // 仅 NODE_NUM 使用
    struct ASTNode* left;
    struct ASTNode* right;
} ASTNode;

递归下降解析器核心代码（片段）：

ASTNode* parse_E() {
    ASTNode* node = parse_T();
    while (current_ == '+' || current_ == '-') {
        NodeType op = (current_ == '+') ? NODE_ADD : NODE_SUB;
        match(current_);
        ASTNode* right = parse_T();
        node = make_node(op, node, right);
    }
    return node;
}

ASTNode* parse_T() {
    ASTNode* node = parse_F();
    while (current_ == '*' || current_ == '/') {
        NodeType op = (current_ == '*') ? NODE_MUL : NODE_DIV;
        match(current_);
        ASTNode* right = parse_F();
        node = make_node(op, node, right);
    }
    return node;
}

测试结果：输入 1 + 2 * 3，生成的 AST 为：

后续遍历该 AST 即可生成正确的后缀表达式或三地址码。该案例表明，通过合理的文法改写，可以彻底消除二义性，且 AST 的构建过程与文法结构高度一致。

4.6 常见误区与总结复盘

在学习和实现语法分析时，初学者常犯以下错误：

混淆语法树与 AST：语法树包含所有语法细节，AST 只保留语义信息。在调试时，应先打印语法树验证文法正确性，再转换为 AST。
忽视左递归的消除：递归下降解析器无法处理左递归文法（如 E → E + T），会导致无限递归。必须改写为右递归或使用循环结构。
过度依赖优先级声明：虽然 Yacc 等工具支持优先级声明，但过度使用会使文法难以阅读和维护。建议在文法层面明确优先级。
忽略错误恢复：语法分析不仅要识别合法输入，还要在遇到错误时给出清晰提示并尝试恢复。至少应实现“恐慌模式”（跳过直到同步标记）。

总结复盘：本章的核心知识链路为：CFG 形式化定义 → 推导/归约过程 → 语法树/AST 构建 → 二义性消除。掌握这条链路后，你就能理解大多数解析器的工作原理。在下一阶段，我们将深入 LL(1) 文法的判定与预测分析表的构造，这是实现手写递归下降解析器的理论基础。建议读者动手实现一个支持四则运算的解析器，并尝试扩展支持变量和赋值语句，以加深对本章概念的理解。