Hotdry.
归档
compiler-design

五项目实战功能性编译器：词法分析到虚拟机全流程

分五个渐进项目，从lexer/tokenizer到VM interpreter，构建功能性编译器，提供工程参数、优化清单与测试要点。

构建编译器是计算机科学的核心技能之一，传统教程往往从零开始编写完整前端和后端，导致学习曲线陡峭。一种高效方法是采用 “五项目渐进式” 结构：每个项目聚焦单一阶段，独立可测试，最终组合成完整编译器。该方法强调增量开发，便于调试和理解，支持简单函数式语言（如支持 let、if、while 的基本表达式）。

项目 1: Lexer/Tokenizer（词法分析器）

观点：词法分析是编译起点，将源代码字符串拆解为 token 流，是性能瓶颈之一。高效 lexer 需支持正则匹配与状态机。

证据：使用有限状态自动机（FSM）实现，缓冲区预读减少 IO。参数建议：缓冲区大小 4KB，回退栈深度 32，避免无限循环。

落地清单：

  • 定义 Token 类型：enum {Number, Ident, Op, Keyword, EOF}。
  • 实现 next_token ()：while 循环扫描 char，switch 处理状态（如数字积累）。
  • 测试参数：输入 1000 行代码，目标 < 1ms/token；监控：token 计数、错误率 < 0.1%。
  • 回滚策略：遇非法 char 抛 LexError，位置记录行 / 列。

示例伪代码（Rust 风格）：

fn next_token(&mut self) -> Token {
    self.skip_whitespace();
    match self.ch {
        '0'..='9' => self.read_number(),
        'a'..='z' => self.read_ident(),
        _ => self.read_op(),
    }
}

优化：预分配 Vec，容量 1024。

项目 2: Recursive Descent Parser（递归下降解析器）

观点：RD 解析适合 LL (1) 文法，手写易懂，支持左递归消除。构建抽象语法树（AST）为后续优化奠基。

证据：预测表驱动，错误恢复用同步集。参数：递归深度限 256，防栈溢出。

落地清单：

  • 文法定义：Expr -> Term ((+|-) Term)；Term -> Factor ((|/) Factor)* 等。
  • 实现 parse_expr () 等函数，peek_token () 预览。
  • 测试：覆盖率 > 90%，panic 率 0；参数：节点池复用，初始容量 512。
  • 监控：解析时间 < 5ms/100 节点，AST 验证遍历检查类型一致。

示例：

fn parse_expr(&mut self) -> Expr {
    let mut left = self.parse_term();
    while self.peek().kind == Plus {
        let op = self.next();
        let right = self.parse_term();
        left = BinOp::new(left, op, right);
    }
    left
}

风险限：不支持二义文法，用优先级表解决。

项目 3: Optimizer Passes（优化器多遍）

观点：优化分 IR 阶段，多遍 pass：常量折叠、死代码消除、公共子表达式消除（CSE）。目标减小 20-50% 代码大小。

证据：数据流分析为基础，前向 / 后向 pass。“优化器通过多遍遍历 IR，消除冗余计算。”

落地清单：

  • IR 表示：SSA 形式，便于分析。
  • Pass 顺序：1. 常量折叠；2. 死码消除；3. 内联（限深度 5）。
  • 参数：迭代上限 10 遍，收敛阈值变化 < 1%；内存限 1MB/pass。
  • 测试：基准套件（如 fib (30)），速度提升 > 2x；回滚：保存优化前 IR。

示例常量折叠：

if let (Const(a), Const(b), Add) = (&left.kind, &right.kind, &op.kind) {
    BinOp::Const(a + b)
}

项目 4: IR to Bytecode Codegen（中间表示到字节码生成）

观点：字节码平台无关，紧凑高效。Codegen 线性扫描 IR，生成 opcodes。

证据：栈机模型，opcodes 如 LOAD, ADD, JMP。参数：栈深度限 64，指令缓冲 8KB。

落地清单：

  • 定义 Bytecode：Vec，enum Instr {Load(u32), Add, Jump(usize)}。
  • emit () 函数：遍历 AST/IR，递归生成。
  • 测试：反汇编验证，执行匹配优化前；大小 < 源代码 50%。
  • 优化：跳转表压缩，常量池。

示例：

fn codegen_expr(&mut self, expr: &Expr) {
    match expr {
        Number(n) => self.emit(Instr::Load(*n)),
        BinOp(left, Add, right) => {
            self.codegen_expr(left);
            self.codegen_expr(right);
            self.emit(Instr::Add);
        }
    }
}

项目 5: VM Interpreter（虚拟机解释器）

观点：栈式 VM 简单可靠，支持 GC。解释字节码，运行程序。

证据：大循环 fetch-decode-execute。参数：帧栈深度 32，GC 阈值堆 80% 满。

落地清单：

  • VM 状态：pc, stack: Vec, frames。
  • run()：while pc < len { match fetch() { Add => pop2 add push } }
  • GC：标记 - 清除，根从栈 / 全局。
  • 测试：fib (35)<1s，内存 < 10MB；监控：指令计数，分支预测命中率 > 90%。

示例：

loop {
    let instr = self.fetch();
    match instr {
        Instr::Add => {
            let b = self.pop();
            let a = self.pop();
            self.push(a + b);
        }
        Instr::Halt => break,
    }
}

工程化参数与监控

全链路：pipeline 串联，错误传播用 Result。构建工具：Cargo workspaces，一项目一 crate。测试框架： criterion 基准，proptest 属性。部署：wasm 目标浏览器 demo。

风险：栈溢出（限递归），浮点精度（用 f64）。回滚：每个项目 snapshot git tag。

资料来源

  1. Kmicinski 系列：“Build a Compiler in Five Projects”。
  2. HN 讨论：https://news.ycombinator.com/（近期热门）。

此结构已在实践中验证，适合自学或教学。通过参数调优，可落地生产级 toy compiler。（约 1250 字）

查看归档