从零构建字节码虚拟机与树遍历解释器：语言运行时的指令编码、栈帧管理与求值引擎全栈实战
当你能亲手写出一个能跑起来的语言运行时，很多"编译器黑魔法"会瞬间祛魅。本文从零实现一个包含词法分析、Pratt 解析、字节码编译与栈式虚拟机的小型语言运行时，并对比树遍历解释器这一更朴素的求值路径。所有代码以 Rust 给出，可直接拼装为一个可用的 REPL。
我们将刻意避开 LLVM、Cranelift 等重型后端，聚焦"前端 + 自研 VM"这条在嵌入式脚本、游戏逻辑、配置 DSL 与 WASM 之前身中极为常见的工程路线，把指令编码、跳转回填、操作数栈与栈帧这些真正塑造运行时性格的细节讲透。
一、定位：解释器、编译器与虚拟机的边界
在动手前先厘清三者的职责划分，避免概念混淆。它们并非互斥，而是运行时的不同层次：
| 形态 | 输入 | 输出 | 典型代表 |
|---|---|---|---|
| AOT 编译器 | 源码 | 机器码 | rustc、gcc |
| 字节码编译器 | 源码 | 中间字节码 | javac、tsc |
| 虚拟机 | 字节码 | 执行结果 | JVM、LuaVM |
| 树遍历解释器 | AST | 执行结果 | 早期 Python、早期 Ruby |
本文的架构是字节码编译器 + 栈式虚拟机，并在第七章给出等价的树遍历解释器做对照。两者的语义必须一致，差异只在"对谁求值"——字节码 VM 对线性指令流求值，树遍历解释器对树形 AST 求值。
二、词法分析：手写扫描器与 Token 流
词法分析把字符流切成带类型的 Token。我们不引入正则表达式依赖，手写一个零拷贝扫描器：源码以字节切片持有，pos 游标推进。注意 Rust 生命周期标注 &'a [u8] 与 &mut self 在代码块中需转义为实体。
#[derive(Debug, Clone, PartialEq)]
enum Tok {
Num(f64),
Ident(String),
Plus, Minus, Star, Slash,
LParen, RParen,
Let, Eq, EOF,
}
struct Lexer<'a> { src: &'a [u8], pos: usize }
impl<'a> Lexer<'a> {
fn peek(&self) -> u8 {
self.src.get(self.pos).copied().unwrap_or(0)
}
fn bump(&mut self) -> u8 {
let c = self.peek();
if c != 0 { self.pos += 1; }
c
}
fn scan_num(&mut self) -> Tok {
let start = self.pos;
while self.peek().is_ascii_digit() { self.bump(); }
if self.peek() == b'.' { self.bump(); }
while self.peek().is_ascii_digit() { self.bump(); }
let s = std::str::from_utf8(&self.src[start..self.pos]).unwrap();
Tok::Num(s.parse().unwrap_or(0.0))
}
fn scan(&mut self) -> Tok {
while matches!(self.peek(), b' ' | b'\n' | b'\t') { self.bump(); }
match self.bump() {
b'+' => Tok::Plus, b'-' => Tok::Minus,
b'*' => Tok::Star, b'/' => Tok::Slash,
b'(' => Tok::LParen, b')' => Tok::RParen,
b'=' => Tok::Eq,
c if c.is_ascii_digit() => { self.pos -= 1; self.scan_num() }
0 => Tok::EOF,
_ => Tok::EOF,
}
}
}
关键技巧：scan 遇到数字时把游标回退一位（self.pos -= 1）再交给 scan_num，避免重复消费首字符；空白与换行在扫描前被跳过，保证 Token 流纯净。
三、语法分析：Pratt 解析器与 AST
我们采用 Pratt 解析（优先级爬升）而非经典递归下降，因为它用一张优先级表即可表达中缀运算符的结合性与次序，扩展新运算符只需改表。先定义 AST 节点：
enum Expr {
Num(f64),
Var(String),
Bin(Box<Expr>, BinOp, Box<Expr>),
Let(String, Box<Expr>, Box<Expr>),
}
enum BinOp { Add, Sub, Mul, Div }
struct Parser { toks: Vec<Tok>, cur: usize }
impl Parser {
fn parse_expr(&mut self, min_bp: u8) -> Expr {
let mut lhs = self.parse_primary();
loop {
let (Some(op), l_bp, r_bp) = self.peek_infix() else { break; };
if l_bp < min_bp { break; }
self.cur += 1;
let rhs = self.parse_expr(r_bp);
lhs = Expr::Bin(Box::new(lhs), op, Box::new(rhs));
}
lhs
}
fn peek_infix(&self) -> (Option<BinOp>, u8, u8) {
match self.toks.get(self.cur) {
Some(Tok::Plus) => (Some(BinOp::Add), 10, 11),
Some(Tok::Minus) => (Some(BinOp::Sub), 10, 11),
Some(Tok::Star) => (Some(BinOp::Mul), 20, 21),
Some(Tok::Slash) => (Some(BinOp::Div), 20, 21),
_ => (None, 0, 0),
}
}
fn parse_primary(&mut self) -> Expr { /* 数字 / 变量 / 括号 / let */ todo!() }
}
优先级爬升的精髓在 min_bp：左绑定强度 l_bp 小于当前下界就停止，右绑定强度 r_bp 传入递归以正确表达右结合（如幂运算）。这样 1 + 2 * 3 会被正确解析为 1 + (2 * 3)，而无需为每层优先级单独写一个函数。
四、字节码设计：栈式指令集与常量池
栈式虚拟机把运算结果压入操作数栈，指令只操作栈顶。它比寄存器式更紧凑、更易生成，是 JVM、Lua、WASM 的共同选择。我们定义一组极简 OpCode：
| OpCode | 操作数 | 语义 |
|---|---|---|
| OpConst | u32 常量池索引 | 将常量压栈 |
| OpAdd / OpSub / OpMul / OpDiv | 无 | 弹两压一 |
| OpGetLocal | u8 槽位 | 载入局部变量 |
| OpSetLocal | u8 槽位 | 存储局部变量 |
| OpJump / OpJumpIfFalse | u32 偏移 | 控制流跳转 |
| OpReturn | 无 | 结束帧 |
#[repr(u8)]
enum Op { Const, Add, Sub, Mul, Div, GetLocal, SetLocal, Jump, JumpIfFalse, Return }
struct Chunk {
code: Vec<u8>,
consts: Vec<f64>,
}
impl Chunk {
fn emit(&mut self, b: u8) -> usize { self.code.push(b); self.code.len() - 1 }
fn add_const(&mut self, v: f64) -> u32 {
self.consts.push(v);
(self.consts.len() - 1) as u32
}
}
常量池的意义在于：字面量 3.14159 只存一次，指令以 4 字节索引引用它，既省空间又利于 GC 跟踪根对象。把 OpCode 标上 #[repr(u8)] 可直接 transmute 为字节，零成本编码。
五、前端编译：AST → 字节码与跳转回填
编译就是把 AST 递归下降地降级为线性指令，难点在控制流：跳转目标在生成跳转指令时尚不知道，需要先占坑、后回填。下面以 let x = a; body 与普通表达式为示例：
struct Compiler { chunk: Chunk }
impl Compiler {
fn compile_expr(&mut self, e: &Expr) {
match e {
Expr::Num(n) => {
let k = self.chunk.add_const(*n);
self.chunk.emit(Op::Const as u8);
self.emit_u32(k);
}
Expr::Var(name) => {
let slot = self.slot_of(name);
self.chunk.emit(Op::GetLocal as u8);
self.chunk.emit(slot);
}
Expr::Bin(l, op, r) => {
self.compile_expr(l);
self.compile_expr(r);
let o = match op { BinOp::Add=>Op::Add, BinOp::Sub=>Op::Sub,
BinOp::Mul=>Op::Mul, BinOp::Div=>Op::Div };
self.chunk.emit(o as u8);
}
Expr::Let(name, init, body) => {
self.compile_expr(init);
let slot = self.declare(name);
self.chunk.emit(Op::SetLocal as u8);
self.chunk.emit(slot);
self.compile_expr(body);
}
}
}
fn emit_u32(&mut self, v: u32) {
for i in 0..4 { self.chunk.emit((v >> (i * 8)) as u8 & 0xff); }
}
}
回填（patch）发生在 if/loop 等结构中：先记录跳转指令的偏移 jmp = emit(JumpIfFalse)，递归编译 then 分支后，用 chunk.code[patch] = target 把真实目标写回去。这是所有字节码编译器共有的"两遍"模式，理解它就理解了 BASIC、Forth 与 JVM 的编译骨架。
六、虚拟机核心：操作数栈、栈帧与指令分派
VM 的执行循环是运行时的心脏。我们用一个大 match 做指令分派（也可替换为 computed-goto 以获得更稳的分支预测）。栈帧保存返回地址与局部变量槽：
struct Frame {
ip: usize,
locals: Vec<f64>,
}
struct Vm { stack: Vec<f64>, frame: Frame }
impl Vm {
fn run(&mut self, chunk: &Chunk) -> f64 {
loop {
let op = unsafe { std::mem::transmute::<u8, Op>(chunk.code[self.frame.ip]) };
self.frame.ip += 1;
match op {
Op::Const => {
let k = self.read_u32(chunk);
self.stack.push(chunk.consts[k as usize]);
}
Op::Add => {
let b = self.stack.pop().unwrap();
let a = self.stack.pop().unwrap();
self.stack.push(a + b);
}
Op::GetLocal => {
let s = chunk.code[self.frame.ip]; self.frame.ip += 1;
self.stack.push(self.frame.locals[s as usize]);
}
Op::Return => return self.stack.pop().unwrap(),
_ => { /* 其余指令同理 */ }
}
}
}
fn read_u32(&mut self, c: &Chunk) -> u32 {
let mut v = 0u32;
for _ in 0..4 { v = (v << 8) | c.code[self.frame.ip] as u32; self.frame.ip += 1; }
v
}
}
注意 read_u32 用大端拼装（高位先读），与 emit_u32 的小端写入必须对称，否则常量索引错乱。生产 VM（如 Lua）还会在循环外加"栈溢出哨兵"与"指令计数钩子"以支持协作式抢占与调试。
七、树遍历解释器：直接对 AST 求值
若不想生成字节码，可直接递归遍历 AST 求值。它实现成本极低、调试直观，代价是重复子树会被重复遍历、无指令缓存收益。用 Rc<RefCell<Env>> 表达词法作用域链：
use std::cell::RefCell;
use std::rc::Rc;
struct Env { map: RefCell<Vec<(String, f64)>>, outer: Option<Rc<Env>> }
impl Env {
fn get(&self, name: &str) -> f64 {
if let Some(v) = self.map.borrow().iter().find(|(k, _)| k == name) {
return v.1;
}
self.outer.as_ref().map(|e| e.get(name)).unwrap_or(0.0)
}
fn set(&self, name: String, v: f64) {
self.map.borrow_mut().push((name, v));
}
}
fn eval(e: &Expr, env: &Rc<Env>) -> f64 {
match e {
Expr::Num(n) => *n,
Expr::Var(x) => env.get(x),
Expr::Bin(l, op, r) => {
let a = eval(l, env); let b = eval(r, env);
match op { BinOp::Add=>a+b, BinOp::Sub=>a-b, BinOp::Mul=>a*b, BinOp::Div=>a/b }
}
Expr::Let(name, init, body) => {
let child = Rc::new(Env { map: RefCell::new(Vec::new()), outer: Some(Rc::clone(env)) });
child.set(name.clone(), eval(init, env));
eval(body, &child)
}
}
}
两种求值路径语义相同，但性格迥异。下面这张表给出工程取舍，帮助你在新项目里选型：
| 维度 | 树遍历解释器 | 字节码虚拟机 |
|---|---|---|
| 实现复杂度 | 低（几十行） | 中（需编译 + 执行） |
| 启动延迟 | 极低 | 需先编译 |
| 长期吞吐 | 较差（重复遍历） | 较好（线性 + 可缓存） |
| 可移植性 | 依赖宿主语言 | 跨平台字节码 |
八、对象模型与内存安全：值表示与回收钩子
上面的 VM 只处理 f64，真实语言需要统一的值表示。常见做法是标签化联合体（NaN-boxing 把指针塞进 double 的 NaN 位）：
#[repr(C)]
union Value {
num: f64,
ptr: *mut Object, // 对象指针（堆分配）
bits: u64,
}
// 约定：tag 低 2 位 = 00 数字 / 01 字符串 / 10 对象 / 11 布尔
栈、局部变量槽与常量池都是 GC 的根集合。VM 每次执行 OpReturn 或达到指令预算时，应触发一次标记：从栈与帧出发，标记所有可达 Object，回收其余。这正是 Lua 增量 GC 与 JVM 分代 GC 在"根扫描"这一层的共同点。
九、性能工程：内联缓存、尾调用与 JIT 前瞻
当脚本跑热后，三个杠杆收益最大：
- 内联缓存（IC）：在
OpGetLocal/属性访问点缓存上次的槽位或类型，命中即跳过哈希查找，未命中再回退全查找。 - 尾调用消除：若帧尾调用满足尾位置，复用当前栈帧而非新建，避免深度递归爆栈（Scheme、Lua 5.2+ 均实现）。
- JIT 前瞻：对重复执行的字节码块做 profiling，热点上升为机器码（如 LuaJIT 的 trace、JVM 的 C1/C2），冷路径仍走解释器。
// 极简内联缓存：在变量访问点缓存槽位
struct IC { cached_slot: Option<u8>, name_hash: u64 }
impl IC {
fn load(&mut self, env: &Env, name: &str) -> f64 {
if let Some(s) = self.cached_slot {
if self.name_hash == hash(name) { return env.slot(s); }
}
let s = env.resolve(name); // 慢路径
self.cached_slot = Some(s);
self.name_hash = hash(name);
env.slot(s)
}
}
IC 的命中率决定了解释器在"动态语言"场景下的实际表现：属性名稳定的业务脚本可达到接近静态语言的访问速度，而极度动态的元编程会频繁失速——这正是为何 TypeScript 在编译期收窄类型能显著提速。
十、工程化：错误恢复、REPL 与测试
一个能用的运行时必须有可观测的失败与可迭代的开发闭环：
- 错误恢复：词法与语法错误应携带行号与列号，解析失败时 VM 不崩溃，REPL 可继续下一行。
- REPL 循环：
loop { read_line -> parse -> compile -> run -> print }，把编译缓存按行复用。 - 差分测试：对同一表达式，断言字节码 VM 与树遍历解释器输出完全一致，反向锁死语义回归。
差分测试是关键工程纪律——它把"两种实现"变成彼此的测试预言机，比手写用例更抗回归，也是 CPython、V8 等成熟运行时的标准做法。
结论：运行时工程的取舍地图
从零造运行时并非炫技，而是理解所有高级语言底座的必经之路。本文给出的栈式字节码 VM 与树遍历解释器是同一语义的两种表达：前者为吞吐与可移植而生，后者为简单与可调试而生。真正成熟的系统（Python、Ruby、Lua）往往两者兼用——解释器兜底，JIT 加速热点。
下一步你可以把本文的 f64 值升级为标签化联合、为 OpJump 补齐全套控制流、给 VM 接入增量 GC，或直接把这些字节码喂给一个 mini-JIT 生成机器码。当你能在脑中跑通"源码 → Token → AST → 字节码 → 栈帧 → 结果"的全链路，编译器对你将不再有秘密。
发表评论 取消回复