Sherfiter's wiki for fun

第 3 章 · 自顶向下语法分析

语法分析是编译器前端的脊梁:token 流进来,语法树出去。本章讲最容易理解、也是手写编译器实际首选的方案:自顶向下的递归下降 / LL(1)。它的优美在于「文法规则和代码一一对应」:每条文法规则就是一个函数,读完这章你手写一个表达式解析器只需要半小时。上位知识:上下文无关文法(CFG)、FIRST/FOLLOW 集、左递归的消除。

3.1 上下文无关文法:语法的 DSL

文法用产生式描述语言结构:

expr    → expr + term | term          (表达式 = 表达式+项,或就是一个项)
term    → term * factor | factor
factor  → ( expr ) | NUM

符号约定:左边是非终结符(结构名),右边出现的全大写/引号是终结符(token),| 表示或。这套文法是「上下文无关」的:每条规则只看左边的结构名,不看周围(上下文),「类型上下文相关的检查」(第 6 章)不在这一层。

一个反直觉的坑藏在上面例子里:左递归。expr → expr + term 的第一项是 expr 自己,递归下降解析器会写 parse_expr 里先调 parse_expr,无限递归当场爆炸。修法是改写成右递归(配合优先级):

expr  → term expr'
expr' → + term expr' | ε        (ε 是空串)

教科书对这道改写有机械算法,手写解析器的实操记忆是:优先级越高的运算放越深层的规则(乘法在 term,加法在 expr),天然解决结合性与优先级。

3.2 递归下降:文法即代码

递归下降解析器,每条产生式一个函数,直接到近乎暴力:

// 解析 factor → ( expr ) | NUM
int parse_factor(void) {
    if (lookahead == T_LP) {          // 吃掉 '('
        advance();
        int v = parse_expr();          // 递归进入表达式
        expect(T_RP);                  // 必须看到 ')'
        return v;
    }
    if (lookahead == T_NUM) { int v = num_val; advance(); return v; }
    error("expected factor");
    return 0;
}

// 解析 term → factor ( * factor )*
int parse_term(void) {
    int v = parse_factor();
    while (lookahead == T_MUL) { advance(); v *= parse_factor(); }
    return v;
}

// 解析 expr → term ( + term )*
int parse_expr(void) {
    int v = parse_term();
    while (lookahead == T_PLUS) { advance(); v += parse_term(); }
    return v;
}

(这个版本顺手做了求值;第 5 章会改成「建 AST 而不求值」,那才是编译器。)

lookahead(向前看一个 token)+ expect(匹配不上就报错)就是全部基础设施。这套代码的可读性是杀手级优点:文法即文档,改文法就是改函数。

3.3 LL(1):什么时候这个方案够用

LL(1) = 从左到右扫描(L)、最左推导(L)、向前看 1 个 token(1)。LL(1) 文法的判据:对每个非终结符的每个产生式选择,用 FIRST 集(能出现在产生式开头的终结符集合)和 FOLLOW 集(能紧跟其后的终结符集合)判别,两两不相交,则无歧义、可确定性选择。

拿到文法先算 FIRST/FOLLOW 再判 LL(1),是考试的固定题型;工程的对应动作是「看到文法有两个产生式共用前缀(公共前缀因子),提取公因子或改写」。比如 stmt → if ... | if ... else ... 的悬空 else 问题,靠 FOLLOW 集的约定解决(else 归最近的 if,语言标准规定)。

不满足 LL(1) 的典型情况两种:左递归(改写可解)和需要多看几个 token(LL(k) 或改用 LR)。这也是「为什么大编译器的解析器很多手写递归下降」的答案:手写时可以自由加 lookahead、用语义信息辅助判断,比死板的表驱动灵活,clang 的解析器就是手写递归下降。

3.4 表驱动版:预测分析表

递归下降的「程序化」对应物是预测分析表:行是非终结符,列是终结符,格子里填「该用哪条产生式」。运行时用显式栈模拟递归:

栈:    [expr' term $]      输入:2 + 3 * 4 $
读 NUM,表[term][NUM] = term → factor
压入 factor ...逐步模拟递归下降的每一步

表驱动版的好处是「文法变了重算表就行」,坏处是可读性归零。教学重点在「手工填写 LL(1) 预测分析表」这一步,它强迫你真正算清 FIRST/FOLLOW。工程上手写递归下降更常见,表驱动留给自动生成器(LLgen、ANTLR 的 LL(*) 变体)。

3.5 错误恢复:parse 崩了别慌

用户写错代码是常态,解析器要能报一个错并继续找下一个错(而不是报一个就罢工)。LL(1) 的经典恢复策略:panic mode——在出错点把输入流跳到 FOLLOW 集(当前结构的「合法出口」)再继续,配合「期待 X 却见到 Y」的详细报错。clang 恢复式解析做得极好(一行代码报出多个错),是产品力的一部分。

常见错误

  • 文法里留了左递归。栈溢出,报错位置在无限递归深处;先改写文法再写代码。
  • ε(空产生式)处理遗漏。expr' 不匹配 + 时应当直接返回(吃掉零个),写成报错就把合法程序判死了。
  • 优先级放错层。2 + 3 * 4 想等于 20 的,查一下乘法是不是放在更深的规则里。
  • 错误恢复只报一个错。第一个错误后直接 exit,用户改一个错跑一次,体验灾难;学 panic mode。

练习

  1. 动手:把 3.2 的解析器扩展到支持减法和除法(含优先级与左结合),用 10 - 4 - 3 验证结果是 3 而不是 9。
  2. 手算:对文法 S → (L) | a,L → L,S | S,求 FIRST/FOLLOW,判断是否 LL(1),并写出预测分析表。
  3. 动手:实现「括号配对检查器」:文法 S → (S) | [S] | {S} | ε,用递归下降,报错时给出「期待什么、在哪里」。
  4. 思考:悬空 else(if a if b s else s,else 归谁)在文法层面有歧义,但所有语言都「规定」归最近的 if。从「文法歧义 vs 语义约定」的角度,思考 LL(1) 判定失败是否必然意味着语言有歧义,以及编译器作者在这种场合的裁量权。
豫ICP备2026027944号