4. 语法分析：上下文无关文法、抽象语法树(AST)的构建

好，咱们继续往下走。词法分析把源代码切成了一个个 token 流，就像把一整句话拆成了单词。那下一步呢？语法分析要干的事，就是检查这些单词能不能组成一句“通顺的话”。

说白了，语法分析要回答两个问题：“这代码的语法结构对不对？” 和 “它的结构长什么样？”。前者靠的是上下文无关文法，后者产出的就是抽象语法树（AST）。

4.1 上下文无关文法：语法规则的“宪法”

你想想看，我们怎么定义“一段合法的 C 语言 if 语句”？总不能靠直觉吧。得有一套严格的规则。这套规则，就是上下文无关文法（Context-Free Grammar, CFG）。

我刚开始学编译原理时，觉得这东西特别抽象。后来在写一个简单的脚本语言解析器时，才真正体会到它的威力。没有 CFG，你根本没法跟计算机说清楚“什么样的代码才算对”。

CFG 由四个部分组成：

• 终结符（Terminal）：就是词法分析产出的 token，比如 if、else、int、+、; 这些。它们是规则的“叶子”，不能再展开。
• 非终结符（Non-terminal）：可以继续展开的语法成分，比如 statement、expression、declaration。
• 产生式（Production）：核心！它定义了一个非终结符如何由其他终结符和非终结符组成。比如：if_statement → 'if' '(' expression ')' statement。
• 开始符号（Start Symbol）：整个文法的入口，通常是 translation_unit（翻译单元）。

举个例子，一个简单的表达式文法：

expression → term
expression → expression '+' term
term → factor
term → term '*' factor
factor → 'number'
factor → '(' expression ')'

这个文法能推导出 3 + 5 * 2 这样的表达式。注意，它天然就体现了乘法的优先级——term 先处理乘法，expression 再处理加法。我在项目中遇到过有人把优先级写反了，结果 1 + 2 * 3 被解析成了 (1 + 2) * 3，那 bug 找得叫一个痛苦。

4.2 推导与语法树：从规则到结构

有了文法，我们就可以“推导”出代码的结构。推导的过程，就是把开始符号一步步展开，直到全部变成终结符。

比如推导 3 + 5 * 2：

1. expression
2. expression '+' term
3. term '+' term
4. factor '+' term
5. 'number' '+' term （这里 number 是 3）
6. 'number' '+' term '*' factor
7. ... 最终得到 '3' '+' '5' '*' '2'

这个推导过程，如果画成树，就是一棵语法分析树（Parse Tree）。它完整记录了每一步的展开，包含了所有非终结符节点。

但说实话，语法分析树太“啰嗦”了。里面有很多中间节点（比如 term、factor），对后续的语义分析和代码生成来说，这些信息是多余的。所以我们真正需要的是——抽象语法树。

4.3 抽象语法树（AST）：去芜存菁

AST 跟语法分析树最大的区别在于：它只保留对语义有意义的节点。括号、分号、中间的非终结符，这些在 AST 里都被“压缩”掉了。

比如 3 + 5 * 2 的 AST 大概长这样：

    '+'
   /   \
 '3'   '*'
       /   \
     '5'   '2'

你看，没有 term、factor 这些中间节点，只有操作符和操作数。结构清晰，直接反映了运算的优先级和结合性。

下面我用 SVG 画一张图，帮你把词法分析、语法分析、AST 的关系串起来：

4.4 构建 AST 的两种策略

实际写解析器时，构建 AST 主要有两条路：

策略	原理	优点	缺点
自顶向下（递归下降）	从开始符号出发，递归调用各个非终结符对应的函数，匹配 token 并构建节点。	实现直观，代码结构跟文法几乎一一对应。调试方便。	需要处理左递归（得改写文法）。
自底向上（LR 系列）	从 token 流开始，逐步“规约”成非终结符，最终归约到开始符号。	能处理更复杂的文法，效率高。适合工具生成（如 yacc/bison）。	实现复杂，出错信息难读。手写几乎不可能。

我个人习惯手写递归下降解析器。为什么？因为可控。我在项目中遇到过用 yacc 生成的解析器，遇到语法错误时，报错信息是 syntax error，完全不知道哪里错了。换成手写的递归下降，我可以在每个解析函数里精确地输出 “期望 ')'，但遇到 ';'” 这样的信息，调试体验天差地别。

4.5 一个简单的递归下降解析器示例

咱们来看一段伪代码，感受一下怎么构建 AST：

// 解析表达式：处理加减
ExprNode* parse_expression() {
    ExprNode* left = parse_term();  // 先解析 term
    while (current_token == '+' || current_token == '-') {
        Token op = current_token;
        advance();  // 吃掉操作符
        ExprNode* right = parse_term();
        // 构建二元运算节点
        left = new BinaryExprNode(op, left, right);
    }
    return left;
}

// 解析项：处理乘除
ExprNode* parse_term() {
    ExprNode* left = parse_factor();
    while (current_token == '*' || current_token == '/') {
        Token op = current_token;
        advance();
        ExprNode* right = parse_factor();
        left = new BinaryExprNode(op, left, right);
    }
    return left;
}

// 解析因子：数字或括号表达式
ExprNode* parse_factor() {
    if (current_token == NUMBER) {
        ExprNode* node = new NumberNode(current_token.value);
        advance();
        return node;
    } else if (current_token == '(') {
        advance();  // 吃掉 '('
        ExprNode* node = parse_expression();
        if (current_token != ')') {
            error("期望 ')'");
        }
        advance();  // 吃掉 ')'
        return node;
    } else {
        error("意外的 token");
    }
}

你看，每个函数对应一个非终结符，函数内部按产生式规则匹配 token，匹配到了就构建对应的 AST 节点。这就是递归下降的核心思想。

4.6 语法错误的处理

嗯，这里要特别提一下。语法分析不仅要能解析正确的代码，还得能优雅地处理错误的代码。我见过太多编译器在遇到第一个语法错误时就崩溃退出，用户体验极差。

常用的错误恢复策略有：

• 恐慌模式（Panic Mode）：遇到错误时，跳过 token 直到遇到一个“同步标记”（比如 ;、}）。然后继续解析。这是最简单也最实用的方法。
• 短语级别恢复：尝试对当前输入做局部修正，比如补一个缺失的分号。
• 错误产生式：在文法里显式地加入常见的错误模式，让解析器能识别并给出友好提示。

我曾经在写一个 C 语言子集的解析器时，用了恐慌模式。当解析器发现 if (x 后面没有 ) 时，它会一直跳过 token 直到遇到 ) 或 ;，然后报错 "第 10 行：缺少 ')'"。这样解析器能继续检查后面的代码，一次编译报出所有错误，而不是改一个错才能看到下一个。

4.7 小结

语法分析是编译器的“骨架”。上下文无关文法给了我们定义语言结构的工具，而 AST 则是这个结构在内存中的高效表示。从词法分析到语法分析，我们完成了从“字符序列”到“结构化树”的转变。

下一阶段，语义分析就要在这棵树上做文章了——检查类型、绑定作用域、验证语义约束。但那是后话。先把 AST 建好，这是所有后续工作的基础。

---