Sherfiter's wiki for fun

第 5 章 · AST 与语法制导翻译

第 3、4 章的解析器边解析边求值(算了一下表达式),那其实是「解释器」的做法。编译器要做的是把树保留下来:解析的产物是抽象语法树(AST),后续所有阶段(语义分析、优化、代码生成)都围绕这棵树工作。本章讲 AST 的设计取舍、语法制导翻译(边解析边构造树/生成代码的框架)、以及遍历 AST 的基本姿势。

5.1 AST:语法树刨去无用细节

解析树(parse tree,含文法每一步推导)很啰嗦,AST 是它的瘦身版:去掉纯语法的括号、去掉单链的传递节点,保留语义结构。2 + 3 * 4 的 AST:

     +
    / \
   2   *
      / \
     3   4

注意乘法是加法的孩子:树的形状直接编码了优先级和结合性,这就是为什么解析阶段要按优先级嵌套规则。AST 的 C 定义:

typedef enum { ND_NUM, ND_ADD, ND_MUL, ND_NEG } NodeKind;
typedef struct Node {
    NodeKind kind;
    int value;              // ND_NUM 专用
    struct Node *lhs, *rhs; // 二元运算的两个孩子
} Node;

Node *new_add(Node *l, Node *r) {
    Node *n = calloc(1, sizeof(Node));
    n->kind = ND_ADD; n->lhs = l; n->rhs = r;
    return n;
}

设计取舍两问:一元运算(负号)用专节点还是特殊标记;if 这类变长结构用孩子数组还是固定 lhs/mid/rhs。没有标准答案,clang 的 AST 类有几百个节点类(继承体系),迷你编译器用一个 enum + 通用结构就够,「够用且可扩展」是分界线。

5.2 语法制导翻译:在文法上挂动作

语法制导定义(SDD) = 文法 + 每条产生式配的语义动作(继承文法符号的「属性」)。bison 的 $$ = $1 + $3 就是它:产生式 expr → expr + expr 的动作取两个孩子的属性算出父属性。三类经典应用:

  • 求值型(第 3、4 章做过):属性是数值,自底向上合成;
  • 建树型(本章):动作改成 new_add($1, $3),属性是 AST 指针;
  • 生成型(第 7 章):动作直接吐三地址码。

「继承属性 vs 综合属性」是理论重点:综合属性自底向上算(孩子的值算父亲的),继承属性自顶向下传(父亲给孩子环境信息,比如类型声明作用域)。L 属性文法(一次深度优先遍历能算完所有属性)是实践的可计算边界,记住名字和直觉即可。

5.3 递归下降建树:动手版

把第 3 章的解析器改造成建 AST(不求值):

Node *parse_expr(void) {          // expr → term (+ term)*
    Node *n = parse_term();
    while (lookahead == T_PLUS) {
        advance();
        n = new_add(n, parse_term());   // 左结合:树向左长
    }
    return n;
}

左结合的验证:1+2+3 的树必须是 +(+(1,2),3) 而不是 +(1,+(2,3))(结合性不同,求值顺序和减除法的结果都不同)。遍历求值验证树的正确性:

int eval(const Node *n) {
    switch (n->kind) {
        case ND_NUM: return n->value;
        case ND_ADD: return eval(n->lhs) + eval(n->rhs);
        case ND_MUL: return eval(n->lhs) * eval(n->rhs);
    }
}

注意 eval 本身就是解释器的雏形:对 AST 的后序遍历求值。编译器和解释器共享 AST,分家在后半程(第 10 章)。

5.4 AST 之后:树的后序遍历就是代码生成

编译器各阶段对 AST 的操作高度模式化:递归下降遍历,后序处理。因为「先处理孩子、再处理自己」恰好对应「先算操作数、再算运算」。第 7 章生成三地址码、第 10 章生成汇编,都是同一个遍历骨架:

void gen(const Node *n) {          // 伪码:每章会具体化
    switch (n->kind) {
        case ND_NUM: emit_load(n->value); break;
        case ND_ADD: gen(n->lhs); gen(n->rhs); emit_add(); break;
    }
}

这个骨架是本课实验的心脏,值得背下来。顺带把「树遍历的栈深度」和第 8 章(运行时栈帧)连上:递归遍历深 AST 会爆栈,真实编译器用显式栈迭代或限制 AST 深度(表达式嵌套限制)。

常见错误

  • 右结合写成左结合(或反之)。减法、除法验证:AST 形状对不对,拿 10-4-3 跑。
  • 括号信息丢了就以为错了。AST 本来就不存括号(优先级已编码进树形),存括号反而错。
  • 节点内存泄漏。AST 节点 calloc 后没人 free;编译器是短命程序可以靠进程退出回收,长命服务(LSP 语言服务器)就必须管,对应第 8 章存储管理的自管与 GC 之争。
  • 错误位置的属性丢了。建树时没记每个节点的源码行列号,后面报错只能给文件级信息;建树顺手记位置是便宜的远见。

练习

  1. 动手:把第 3 章解析器改成建 AST,支持 -、/、一元负号;打印树(缩进缩出层次),用 10-4-3 和 -2*3 验证结合性。
  2. 动手:写 print_ast 的 DOT 输出(Graphviz),把 AST 画成图,后面的章节都用它调试。
  3. 手算:对 a = b * (c + d) 画出 AST(带赋值节点),标出哪部分是「语句节点」哪部分是「表达式节点」,想想 AST 里语句和表达式要不要分家。
  4. 思考:语法制导翻译把「语义动作」粘在文法上,好处是就地、紧凑;代价是文法和语义耦合(改文法要改动作)。对比第 7 章「解析完独立遍历 AST 生成代码」的两段式,从「文法复用、错误处理、团队协作」三个角度评价两种组织方式。
豫ICP备2026027944号