语法分析入门：上下文无关文法（CFG），自顶向下与自底向上解析

语法分析，说白了就是让计算机理解你写的代码结构对不对。我刚开始学编译原理时，觉得这玩意儿特别抽象，直到自己动手写了一个解析器，才真正明白它的威力。

咱们今天聊三个核心东西：上下文无关文法（CFG）、两种解析策略（自顶向下 vs 自底向上），以及手写一个递归下降解析器。嗯，我会带着你一步步走，保证你能上手。

1. 上下文无关文法（CFG）—— 语法的“语法”

什么是CFG？你可以把它想象成一套“搭积木”的规则。比如你要描述一个算术表达式：

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

这个规则说：一个表达式（E）可以是一个表达式加一个项（T），或者直接就是一个项。项（T）可以是一个项乘一个因子（F），或者直接就是一个因子。因子（F）可以是括号括起来的表达式，或者一个标识符（比如变量名）。

为什么叫“上下文无关”？ 因为每个非终结符（比如E、T、F）的展开规则，跟它出现在什么位置没关系。你想想看，不管这个E是在括号里还是括号外，它的展开规则都一样。这就叫“上下文无关”。

我在项目中遇到过一个问题：用CFG描述JSON语法时，如果规则写得太复杂，解析器会变得非常慢。后来我简化了规则，把一些嵌套结构拆成多层，性能直接翻倍。

2. 自顶向下 vs 自底向上解析

这两种策略，说白了就是“从根往下找叶子”和“从叶子往上拼成根”的区别。

特性	自顶向下	自底向上
思路	从开始符号出发，尝试匹配输入	从输入符号出发，归约到开始符号
实现难度	简单，适合手写	复杂，通常用工具生成
适用文法	LL(k) 文法（无左递归）	LR(k) 文法（几乎通用）
典型工具	手写递归下降	Yacc、Bison

自顶向下：从根节点开始，根据当前输入符号，选择一条产生式往下展开。如果选错了，就得回溯。我刚开始写解析器时，就踩过这个坑——文法里有左递归，结果递归下降解析器直接栈溢出了。

自底向上：从输入符号开始，不断“归约”——把匹配到的右部替换成左部的非终结符。这个过程有点像拼图，从碎片拼出完整的图案。LR解析器就是典型的自底向上，它用状态机来避免回溯，效率很高。

3. 手写一个简单的递归下降解析器

好了，理论说完了，咱们动手写代码。我选一个最简单的算术表达式解析器，支持加减乘除和括号。

先定义文法（已经去掉了左递归）：

E  → T E'
E' → + T E' | ε
T  → F T'
T' → * F T' | ε
F  → ( E ) | num

注意这里的 ε 表示空串，也就是可以什么都不匹配。这是消除左递归后的标准写法。

接下来是代码。我用的是类C的伪代码，你换成任何语言都行：

// 全局变量：当前token
Token currentToken;

// 解析入口
void parse() {
    currentToken = getNextToken();
    E();
    if (currentToken != EOF) {
        error("语法错误：有多余的token");
    }
}

// E → T E'
void E() {
    T();
    E_prime();
}

// E' → + T E' | ε
void E_prime() {
    if (currentToken == '+') {
        currentToken = getNextToken();
        T();
        E_prime();
    }
    // 否则就是 ε，什么都不做
}

// T → F T'
void T() {
    F();
    T_prime();
}

// T' → * F T' | ε
void T_prime() {
    if (currentToken == '*') {
        currentToken = getNextToken();
        F();
        T_prime();
    }
}

// F → ( E ) | num
void F() {
    if (currentToken == '(') {
        currentToken = getNextToken();
        E();
        if (currentToken != ')') {
            error("缺少右括号");
        }
        currentToken = getNextToken();
    } else if (currentToken == NUM) {
        currentToken = getNextToken();
    } else {
        error("语法错误：期望数字或左括号");
    }
}

你看，每个非终结符对应一个函数，函数里根据当前token选择走哪条路。这就是递归下降解析器的精髓——文法结构和代码结构一一对应。

这个解析器虽然简单，但已经能处理像 3 + 5 * (2 + 4) 这样的表达式了。你想想看，它怎么处理乘法的优先级？因为 T 在 E 里先被调用，而 T 里又先处理 F（因子），所以乘法比加法先绑定，优先级自然就对了。

4. 知识体系总览

为了让你更直观地理解本章的知识结构，我画了一张图：

这张图把本章的三个核心模块串起来了。CFG是基础，解析策略是方法，递归下降解析器是具体实现。三者环环相扣，缺一不可。

嗯，说到这，我想起一个细节：很多初学者会问，为什么递归下降解析器不能处理左递归？其实很简单——左递归会导致函数无限调用自己，永远读不到下一个token。我当年调试这个问题时，盯着栈回溯看了半天才反应过来。

好了，这一章的内容就到这。你如果能把上面的代码跑一遍，再试着扩展一下（比如加上减法、除法），那语法分析这块就算入门了。

可可精品资料库