用 Rust 写一个解释器：从 Token 到执行，编译原理没那么玄乎
每次看到
1 + 2 * 3被正确算出 7 而不是 9，都觉得理所当然。但从"字符串"到"结果"，中间隔了三道门，每道门的钥匙都不一样。
编译原理在国内被妖魔化得很严重。龙书、虎书、鲸书摆一排，光看书名就劝退一半人。
但真相是：你不需要读完龙书才能写一个解释器。 一个能算 1 + 2 * 3、支持变量赋值、能调函数的 mini 语言，核心代码不超过 400 行。写完之后你会发现，所谓的"编译原理"，80% 是在解决一个很朴素的问题：怎么把一串字符，变成一个能跑的东西。
这篇文章，我们就用 Rust 手搓一个 mini 解释器。不依赖 parser generator，不用 nom，从零开始。
先搞清楚：解释器和编译器有什么区别
这两个词经常被混用，但它们解决的是不同的问题。
编译器（Compiler）：把源代码翻译成另一种语言，然后结束工作。gcc 把 C 翻译成机器码，tsc 把 TypeScript 翻译成 JavaScript。翻译完编译器就走了，执行是别人的事。
解释器（Interpreter）：读源代码，直接执行，不生成中间产物。Python、Ruby、JavaScript（V8 之前）都是这样。你写 print(1+1)，解释器当场就读、当场就算、当场就输出。
编译器：源代码 → [翻译] → 目标代码 → [执行] → 结果
解释器：源代码 → [读一行执行一行] → 结果
但实际的现代语言往往是混合的。Python 其实会先把源代码编译成字节码（bytecode），然后再用虚拟机执行字节码。Java 也是。所以"编译"和"解释"不是非此即彼，而是两个极端，大多数语言在中间某个位置。
我们今天写的解释器，走的是最朴素的路线：读源代码 → 构建 AST → 直接遍历 AST 求值。 这种叫 tree-walking interpreter，是理解编译原理的最佳起点。
整体流程：从字符串到结果，经过三步
不管你写的是编译器还是解释器，核心流程都是三步：
源代码字符串
│
▼
┌─────────┐
│ Lexer │ 词法分析：字符流 → Token 序列
└────┬────┘
│
▼
┌─────────┐
│ Parser │ 语法分析：Token 序列 → AST（抽象语法树）
└────┬────┘
│
▼
┌──────────────┐
│ Interpreter │ 求值：遍历 AST，执行计算
└──────────────┘
│
▼
结果输出
每一步的输出是下一步的输入。我们用一个具体的例子走一遍这个流程。
例子：1 + 2 * 3 是怎么算出 7 的
第一步：Lexer
原始字符串是 1 + 2 * 3，Lexer 从左到右扫描，切成 Token：
'1' ' ' '+' ' ' '2' ' ' '*' ' ' '3'
↓ ↓ ↓
Number(1) Number(2) Number(3)
↓ ↓
Plus Star
输出：[Number(1), Plus, Number(2), Star, Number(3)]
第二步：Parser
Token 序列是一维的，没有优先级信息。如果从左到右算：1 + 2 = 3，再 3 * 3 = 9，结果就错了。
Parser 的核心工作是处理优先级，把一维的 Token 流变成二维的树结构：
+
/ \
1 *
/ \
2 3
乘法节点在内层（更深），所以它先被求值。2 * 3 = 6，然后 1 + 6 = 7。
第三步：Interpreter
遍历这棵树，递归求值：
- 要算
+，先算左子树 →1 - 再算右子树 → 遇到
*，继续递归 *的左子树 →2，右子树 →32 * 3 = 6，返回给+1 + 6 = 7
关键理解：树的结构天然就表达了优先级。 这就是为什么我们需要 Parser——不是为了好看，是为了正确性。
什么是 AST（抽象语法树）
AST 是整个流程的核心数据结构。它是一棵树，每个节点代表程序的一个"结构"：
- 叶子节点：字面量（数字、字符串）、变量名
- 内部节点：运算（加减乘除）、控制流（if/while）、函数调用
let x = 10 + 20; 的 AST 长这样：
Stmt::Let
├── name: "x"
└── value: Expr::BinaryOp
├── op: Add
├── left: Expr::Number(10)
└── right: Expr::Number(20)
为什么叫"抽象"语法树？因为它丢掉了所有不影响语义的东西——空格、换行、注释、分号（分号在某些位置是必须的，但它不参与计算）。只留下程序的结构。
AST 的好处是好遍历。你要算一个表达式的值，递归走一遍树就行了。你要做类型检查，递归走一遍树就行了。你要优化代码（比如把 1 + 2 在编译期直接替换成 3），还是递归走一遍树。
几乎所有语言工具——编译器、解释器、linter、formatter、IDE 补全——核心都是在操作 AST。
我们要造什么
目标是一个能跑这种代码的解释器：
// 变量绑定
let x = 10;
let y = 20;
// 表达式计算
let result = (x + y) * 2;
// 内置函数
print(result); // 输出: 60
// 条件 + 循环
if result > 50 {
print("big");
}
let i = 0;
while i < 3 {
print(i);
i = i + 1;
}语法故意设计得像 Rust，学起来没门槛。但核心机制——词法分析、语法分析、求值——和真正的语言是一样的。
最终效果： 写一个 .mini 文件，用 cargo run -- run test.mini 就能跑。
第一道门：Lexer（词法分析）
为什么需要 Lexer
源代码是字符串。字符串对计算机来说就是一坨字节。你需要先把字符串切成有意义的"词"（Token），后面的步骤才有意义。
let x = 10; 对人类来说一眼就能看出五个词：let、x、=、10、;。但计算机看到的是 l、e、t、 、x、 、=、 、1、0、;。
Lexer 的工作就是：从左到右扫一遍字符流，输出一个 Token 序列。
什么是 Token
Token 是源代码中最小的有意义单位。每个 Token 有一个类型和一个可选的值：
源代码: let x = 10;
Token: ↑ ↑ ↑ ↑ ↑
│ │ │ │ └─ Semicolon
│ │ │ └──── Number(10)
│ │ └─────── Eq
│ └────────── Ident("x")
└────────────── Let
Token 的类型决定了 Parser 怎么处理它。Number(10) 是字面量，可以直接用；Ident("x") 是变量名，需要去环境里查；Let 是关键字，触发变量绑定逻辑。
两个关键概念：前瞻（Lookahead）和关键字 vs 标识符
前瞻：有些 Token 需要"多看一个字符"才能确定。比如 = 和 ==：
看到 '=' 时：
下一个是 '=' → 这是 EqEq（等于比较）
下一个不是 '=' → 这是 Eq（赋值）
Lexer 需要"偷看"下一个字符但不消费它，这叫 lookahead。实现上就是 peek 方法。
关键字 vs 标识符：let、if、while 看起来像标识符（都是字母组成），但它们有特殊含义。处理方式是：先按标识符读完整个单词，然后查表判断它是关键字还是普通标识符。
读到 "let" → 查表 → 关键字 Let
读到 "letx" → 查表 → 没找到 → 标识符 Ident("letx")
这就是为什么关键字不能用作变量名——它们在 Lexer 阶段就被"抢走"了。
定义 Token
#[derive(Debug, Clone, PartialEq)]
pub enum Token {
// 字面量
Number(f64),
String(String),
Bool(bool),
// 标识符和关键字
Ident(String),
Let,
If,
Else,
While,
Fn,
Return,
// 运算符
Plus, // +
Minus, // -
Star, // *
Slash, // /
Percent, // %
Eq, // =
EqEq, // ==
NotEq, // !=
Lt, // <
Gt, // >
LtEq, // <=
GtEq, // >=
And, // &&
Or, // ||
Not, // !
// 分隔符
LParen, // (
RParen, // )
LBrace, // {
RBrace, // }
Comma, // ,
Semicolon, // ;
// 特殊
Eof,
}手写 Lexer
Lexer 的结构很简单：一个 tokenize 方法，核心就是一个大 match。按字符分类处理：
pub struct Lexer {
source: Vec<char>,
pos: usize,
}
impl Lexer {
pub fn tokenize(&mut self) -> Result<Vec<Token>, String> {
let mut tokens = Vec::new();
while self.pos < self.source.len() {
let ch = self.source[self.pos];
match ch {
// 跳过空白
' ' | '\t' | '\r' | '\n' => { self.pos += 1; }
// 单字符 token：直接映射
'+' => { tokens.push(Token::Plus); self.pos += 1; }
'-' => { tokens.push(Token::Minus); self.pos += 1; }
'(' => { tokens.push(Token::LParen); self.pos += 1; }
// ... 其他单字符同理
// 双字符运算符：需要 lookahead
'=' => {
if self.peek() == Some('=') {
tokens.push(Token::EqEq); // ==
self.pos += 2;
} else {
tokens.push(Token::Eq); // =
self.pos += 1;
}
}
// '!'、'<'、'>' 同理，都是 peek 一下判断是单字符还是双字符
// 多字符 token：调用辅助方法
'0'..='9' => { tokens.push(self.read_number()?); }
'"' => { tokens.push(self.read_string()?); }
'a'..='z' | 'A'..='Z' | '_' => { tokens.push(self.read_ident()); }
_ => return Err(format!("unexpected character: '{}'", ch)),
}
}
tokens.push(Token::Eof);
Ok(tokens)
}
fn peek(&self) -> Option<char> {
self.source.get(self.pos + 1).copied()
}
// 读标识符，然后查关键字表
fn read_ident(&mut self) -> Token {
let start = self.pos;
while self.pos < self.source.len()
&& (self.source[self.pos].is_ascii_alphanumeric() || self.source[self.pos] == '_')
{ self.pos += 1; }
let word: String = self.source[start..self.pos].iter().collect();
match word.as_str() {
"let" => Token::Let,
"if" => Token::If,
"while" => Token::While,
"fn" => Token::Fn,
"true" => Token::Bool(true),
_ => Token::Ident(word), // 不是关键字就是标识符
}
}
// read_number、read_string 同理，都是 while 循环读到边界
}核心逻辑就是一个 match，每个分支要么直接产出 Token（单字符），要么调辅助方法读多字符。read_ident 的最后一步是查关键字表——这就是"先读词再判断"的实现。
为什么手写而不用 nom 或 logos？ 手写的好处是完全控制错误信息，你能精确报出"第 3 行第 15 列，遇到意外字符 @"。而且手写一个 lexer 真的不难——核心逻辑就是一个 match。
第二道门：Parser（语法分析）
Token 到 AST
Lexer 给了你一列 Token：[Let, Ident("x"), Eq, Number(10), Semicolon]。但这一列 Token 没有结构。你需要把它变成一棵树（AST，抽象语法树），才能知道"先算乘法再算加法"、"if 的条件是哪个表达式"。
// Token 流：let x = 1 + 2 * 3;
[Let, Ident("x"), Eq, Number(1), Plus, Number(2), Star, Number(3), Semicolon]
// AST：
LetStmt {
name: "x",
value: BinaryOp {
op: Add,
left: Number(1),
right: BinaryOp {
op: Mul,
left: Number(2),
right: Number(3),
}
}
}注意 2 * 3 被包在内层，这保证了乘法先算。这就是 Parser 的核心工作：从一维的 Token 流，构建出二维的树结构，并且正确处理优先级。
语法规则：用 BNF 描述语言
Parser 需要一个"规则"来判断什么样的 Token 序列是合法的。这个规则叫文法（Grammar），通常用 BNF（巴科斯范式）描述。
我们的 mini 语言的表达式文法：
expr → or_expr
or_expr → and_expr ( "||" and_expr )*
and_expr → equality ( "&&" equality )*
equality → comparison ( ("==" | "!=") comparison )*
comparison → addition ( ("<" | ">" | "<=" | ">=") addition )*
addition → multiplication ( ("+" | "-") multiplication )*
multiplication → unary ( ("*" | "/" | "%") unary )*
unary → ( "-" | "!" ) unary | primary
primary → NUMBER | STRING | BOOL | IDENT | IDENT "(" args ")" | "(" expr ")"
每条规则对应一个函数。or_expr 最低优先级，primary 最高优先级。优先级越高的运算符，在越深的层级处理，天然就保证了"先乘除后加减"。
递归下降：为什么这样写 Parser
递归下降（Recursive Descent）是最直观的 Parser 写法。核心思想是：每个文法规则对应一个函数，函数之间互相调用。
parse_expr → parse_or → parse_and → parse_equality → ... → parse_primary
调用链从低优先级到高优先级。当 parse_addition 需要解析一个操作数时，它调用 parse_multiplication（更高优先级），而不是自己处理。这就保证了乘法比加法"绑得更紧"。
左递归的陷阱：如果你写成 expr → expr "+" term，函数会无限递归调用自己。改成 expr → term ( "+" term )*（循环而不是递归）就能避免。这是递归下降 Parser 最常见的坑。
运算符优先级一览
我们的 Parser 处理的优先级层次（从低到高）：
优先级 运算符 结合性
─────────────────────────────────
最低 || 左结合
&& 左结合
== != 左结合
< > <= >= 左结合
+ - 左结合
最高 * / % 左结合
- ! (一元) 右结合
左结合意味着 1 - 2 - 3 算成 (1 - 2) - 3 = -4，而不是 1 - (2 - 3) = 2。实现上，左结合用 while 循环，右结合用递归调用自身。
定义 AST
#[derive(Debug, Clone)]
pub enum Expr {
Number(f64),
String(String),
Bool(bool),
Ident(String),
UnaryOp {
op: UnaryOp,
expr: Box<Expr>,
},
BinaryOp {
op: BinOp,
left: Box<Expr>,
right: Box<Expr>,
},
Call {
func: String,
args: Vec<Expr>,
},
}
#[derive(Debug, Clone)]
pub enum BinOp {
Add, Sub, Mul, Div, Mod,
Eq, NotEq, Lt, Gt, LtEq, GtEq,
And, Or,
}
#[derive(Debug, Clone)]
pub enum UnaryOp {
Neg, Not,
}
#[derive(Debug, Clone)]
pub enum Stmt {
Let {
name: String,
value: Expr,
},
Expr(Expr),
If {
condition: Expr,
then_branch: Vec<Stmt>,
else_branch: Option<Vec<Stmt>>,
},
While {
condition: Expr,
body: Vec<Stmt>,
},
FnDef {
name: String,
params: Vec<String>,
body: Vec<Stmt>,
},
Return(Option<Expr>),
}递归下降 Parser
Parser 的经典写法叫"递归下降"（Recursive Descent）。核心思想是：每个语法规则对应一个函数，函数之间互相调用，形成递归。
表达式的优先级处理是重点。优先级从低到高：
or → and → equality → comparison → addition → multiplication → unary → primary
每一层只处理自己优先级的运算符，把更高优先级的表达式"委托"给下一层。
语句解析负责分发：看到 let 调 parse_let，看到 if 调 parse_if，其他当表达式处理：
fn parse_stmt(&mut self) -> Result<Stmt, String> {
match self.current() {
Token::Let => self.parse_let(),
Token::If => self.parse_if(),
Token::While => self.parse_while(),
Token::Fn => self.parse_fn_def(),
Token::Return => self.parse_return(),
_ => {
let expr = self.parse_expr()?;
self.expect(&Token::Semicolon)?;
Ok(Stmt::Expr(expr))
}
}
}
// 以 let 为例：消费 let → 读变量名 → 消费 = → 解析表达式 → 消费 ;
fn parse_let(&mut self) -> Result<Stmt, String> {
self.advance();
let name = self.expect_ident()?;
self.expect(&Token::Eq)?;
let value = self.parse_expr()?;
self.expect(&Token::Semicolon)?;
Ok(Stmt::Let { name, value })
}表达式解析是核心。每一层结构完全一样，区别只在运算符和下一层调用：
fn parse_expr(&mut self) -> Result<Expr, String> { self.parse_or() }
fn parse_or(&mut self) -> Result<Expr, String> {
let mut left = self.parse_and()?; // 先解析更高优先级的操作数
while self.check(&Token::Or) { // 循环处理当前优先级的运算符
self.advance();
let right = self.parse_and()?;
left = Expr::BinaryOp { // 包装成树节点
op: BinOp::Or, left: Box::new(left), right: Box::new(right),
};
}
Ok(left)
}
// parse_and、parse_equality、parse_comparison、parse_addition 全是同一个模式
// 只有运算符和"下一层调用"不同
fn parse_addition(&mut self) -> Result<Expr, String> {
let mut left = self.parse_multiplication()?;
while matches!(self.current(), Token::Plus | Token::Minus) {
let op = match self.current() {
Token::Plus => BinOp::Add, Token::Minus => BinOp::Sub, _ => unreachable!(),
};
self.advance();
let right = self.parse_multiplication()?;
left = Expr::BinaryOp { op, left: Box::new(left), right: Box::new(right) };
}
Ok(left)
}
fn parse_multiplication(&mut self) -> Result<Expr, String> {
let mut left = self.parse_unary()?; // 最高优先级，委托给 unary
while matches!(self.current(), Token::Star | Token::Slash) {
// ... 同上
}
Ok(left)
}基底：parse_primary 处理叶子节点——数字、字符串、变量名、括号、函数调用。没有更低优先级可以委托了，直接消费 Token：
fn parse_primary(&mut self) -> Result<Expr, String> {
match self.current().clone() {
Token::Number(n) => { self.advance(); Ok(Expr::Number(n)) }
Token::Ident(name) => {
self.advance();
if self.check(&Token::LParen) { // 标识符后面跟 ( → 函数调用
self.advance();
let args = self.parse_args()?;
self.expect(&Token::RParen)?;
Ok(Expr::Call { func: name, args })
} else {
Ok(Expr::Ident(name)) // 否则就是变量引用
}
}
Token::LParen => { // 括号：递归解析内部表达式
self.advance();
let expr = self.parse_expr()?;
self.expect(&Token::RParen)?;
Ok(expr)
}
other => Err(format!("unexpected token: {:?}", other)),
}
}踩坑记录：std::mem::discriminant 是关键。
check 方法需要比较"是不是同一种 Token"，不关心具体值（Number(1.0) 和 Number(2.0) 是同一种）。用 == 比较会因为值不同而失败。std::mem::discriminant 只比较枚举的变体标签，忽略内部数据。
第三道门：求值器（Tree-walking Interpreter）
Tree-walking 是什么意思
Parser 给了我们一棵 AST。求值器的工作就是递归遍历这棵树，遇到节点就执行对应的操作。
eval(BinaryOp { op: Add, left: 1, right: 2 })
→ eval(1) = 1
→ eval(2) = 2
→ 1 + 2 = 3
这就是 "tree-walking"——像走迷宫一样在树上走，走到叶子节点就返回值，走到内部节点就计算。
核心问题：变量存在哪？
执行 let x = 10; 之后，x 被存到哪里了？执行 print(x) 的时候怎么找到它？
答案是环境（Environment）——一个链式的 HashMap。每个作用域有自己的环境，环境之间通过"父指针"串起来：
全局环境: { x: 10, y: 20 }
↑ 父指针
函数环境: { n: 5 }
↑ 父指针
内层块环境: { temp: 100 }
查找变量时，先在当前环境找，找不到就去父环境找，一直找到全局环境。如果全局环境都没有，那就是"未定义变量"错误。
这就是作用域链——几乎所有语言的变量查找都是这个机制。
为什么需要 Box？
AST 节点会递归嵌套：BinaryOp 的 left 可能又是 BinaryOp。Rust 需要知道每个类型的大小，递归类型必须用 Box（堆分配的指针）来打破无限大小的循环。
// 编译失败：Expr 的大小是无限的
enum Expr {
BinaryOp { left: Expr, right: Expr }, // Expr 包含 Expr，无限嵌套
}
// 正确：Box 是一个指针，大小固定
enum Expr {
BinaryOp { left: Box<Expr>, right: Box<Expr> }, // Box<Expr> 大小是 8 字节
}函数调用时发生了什么
函数调用是解释器里最复杂的部分。调用 fibonacci(3) 时：
- 查找函数定义：在环境里找
fibonacci，得到它的参数列表和函数体 - 创建新环境：函数自己的作用域，父环境是定义时的环境（不是调用时的）
- 绑定参数：
n = 3写入新环境 - 执行函数体：在新环境里执行函数体的每条语句
- 处理 return：遇到
return语句，提前退出，返回值给调用者
第 2 步是闭包的关键。如果父环境用的是"调用时"的环境，内层函数就访问不到外层变量。用"定义时"的环境，闭包才能正确捕获。
return 的处理：ControlFlow
函数里遇到 return，需要立即退出整个函数，不只是退出当前循环或 if 块。怎么做到？
用一个枚举来传递"控制信号"：
enum ControlFlow {
None, // 正常执行，继续下一条
Return(Value), // return 了，立即退出函数
}每执行一条语句，都检查返回值。如果是 Return，就一路往上传，直到函数调用的那一层。这模拟了真实语言里的"栈帧弹出"。
环境（Environment）
变量存在哪？答案是一个"环境"——本质上就是栈上的 HashMap 链。每进入一个作用域，就创建一个新环境，父环境是外层的那个。
pub struct Environment {
vars: HashMap<String, Value>,
parent: Option<Box<Environment>>,
}
impl Environment {
// 查找变量：先在当前环境找，找不到就去父环境找
pub fn get(&self, name: &str) -> Option<&Value> {
self.vars.get(name).or_else(|| self.parent.as_ref()?.get(name))
}
// 赋值（x = 20）：如果父环境有这个变量，更新父环境的
pub fn set(&mut self, name: String, value: Value) {
if let Some(parent) = &mut self.parent {
if parent.get(&name).is_some() {
parent.set(name, value); // 递归向上找，直到找到定义处
return;
}
}
self.vars.insert(name, value);
}
// 定义（let x = 10）：只在当前作用域创建
pub fn define(&mut self, name: String, value: Value) {
self.vars.insert(name, value);
}
}set 和 define 的区别：define 只在当前作用域创建新变量；set 递归向上找到变量的定义处再更新。这就是 while 循环里 i = i + 1 能工作的秘密。
求值器
运行时的值用一个枚举表示：
pub enum Value {
Number(f64),
String(String),
Bool(bool),
Fn { params: Vec<String>, body: Vec<Stmt>, env: Environment }, // 闭包：捕获定义时的环境
Null,
}核心：eval_expr 递归求值。 遇到叶子节点直接返回值，遇到运算节点递归计算子节点：
fn eval_expr(&mut self, expr: &Expr) -> Result<Value, String> {
match expr {
// 叶子节点：直接返回
Expr::Number(n) => Ok(Value::Number(*n)),
Expr::Ident(name) => self.env.get(name).cloned()
.ok_or_else(|| format!("undefined variable: {}", name)),
// 二元运算：先算左右子树，再做运算
Expr::BinaryOp { op, left, right } => {
let l = self.eval_expr(left)?;
let r = self.eval_expr(right)?;
self.eval_binop(op, &l, &r)
}
// 函数调用：最复杂的部分
Expr::Call { func, args } => {
if func == "print" { /* 内置函数，直接处理 */ }
let func_val = self.env.get(func).cloned()
.ok_or_else(|| format!("undefined function: {}", func))?;
match func_val {
Value::Fn { params, body, env } => {
// 1. 创建新环境，父环境是定义时的环境（不是调用时的！）
let mut fn_env = Environment::extend(env);
// 2. 绑定参数
for (param, arg) in params.iter().zip(args) {
fn_env.define(param.clone(), self.eval_expr(arg)?);
}
// 3. 在新环境里执行函数体
let mut interp = Interpreter { env: fn_env };
for stmt in &body {
if let ControlFlow::Return(v) = interp.exec_stmt(stmt)? {
return Ok(v); // return 立即退出
}
}
Ok(Value::Null)
}
_ => Err(format!("{} is not a function", func)),
}
}
// ... 其他节点类型
}
}函数调用那三步就是闭包的核心——用定义时的环境，不是调用时的环境。如果换成调用时的环境，内层函数就访问不到外层变量了。
语句执行（exec_stmt）和二元运算（eval_binop）的代码和其他 match 分支结构类似，这里不全部展开。关键模式是：每进入一个块（if/while），就 Environment::extend 创建子环境；每遇到 ControlFlow::Return，就一路往上传退出函数。
串起来：主程序
fn main() {
let args: Vec<String> = std::env::args().collect();
if args.len() < 3 || args[1] != "run" {
eprintln!("Usage: mini run <file>");
std::process::exit(1);
}
let source = std::fs::read_to_string(&args[2])
.expect("failed to read file");
// 词法分析
let mut lexer = Lexer::new(&source);
let tokens = lexer.tokenize().unwrap_or_else(|e| {
eprintln!("Lexer error: {}", e);
std::process::exit(1);
});
// 语法分析
let mut parser = Parser::new(tokens);
let stmts = parser.parse().unwrap_or_else(|e| {
eprintln!("Parser error: {}", e);
std::process::exit(1);
});
// 执行
let mut interp = Interpreter::new();
interp.run(&stmts).unwrap_or_else(|e| {
eprintln!("Runtime error: {}", e);
std::process::exit(1);
});
}写一个测试文件 test.mini：
fn fibonacci(n) {
if n <= 1 {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
let i = 0;
while i < 10 {
print(fibonacci(i));
i = i + 1;
}跑一下：
$ cargo run -- run test.mini
0
1
1
2
3
5
8
13
21
34
能跑斐波那契，说明递归、函数调用、条件判断、循环全部通了。整个解释器核心代码 400 行左右。
进阶：接下来可以做什么
这个 mini 解释器是 tree-walking 的——直接遍历 AST 求值。优点是实现简单，缺点是慢（每次执行都要遍历树结构）。如果想继续深入，有几个方向：
1. Bytecode VM（字节码虚拟机）
把 AST 编译成字节码（一种线性的指令序列），然后用一个虚拟机执行。Python、Lua、Ruby 都是这么做的。
// AST: 1 + 2 * 3
// 字节码：
Push 1
Push 2
Push 3
Mul
Add
字节码比 AST 紧凑得多，cache friendly，而且可以做很多优化（常量折叠、指令合并）。写一个 bytecode VM 是理解 Python/JS 引擎的最好方式。
2. 垃圾回收（GC）
现在我们的 Value::Fn 会 clone 整个环境。真实语言不会这么干——它们用引用计数或者 tracing GC。Rust 的 Rc<RefCell<>> 可以快速原型一个引用计数 GC，但要处理循环引用就得上 Weak 或者写一个 mark-sweep。
3. 类型系统
给 mini 语言加类型检查。在求值之前跑一遍类型推导，报出 1 + "hello" 这种错误。这会用到 unification 算法——和 Haskell/Rust 的类型推导是同一个东西。
4. 用 Rust 的 enum 做 pattern matching
你会发现 Rust 写解释器特别舒服。match expr { Expr::Number(n) => ..., Expr::BinaryOp { op, left, right } => ... } 这种模式匹配，比 Java/Python 里的 if isinstance(expr, Number) 优雅太多。Rust 的穷尽性检查还保证你不会漏掉某个分支——编译器帮你找 bug。
龙书到底要不要读
我的建议：先写代码，再读书。
写完这个 mini 解释器之后，你会发现龙书里的"词法分析"、"语法分析"、"语法制导翻译"这些概念，你已经用过了——只是不知道它们的学术名字。这时候再翻龙书，每个概念都有对应的代码，理解效率翻倍。
龙书真正有价值的是后半部分：优化、代码生成、数据流分析。前半部分——lexer、parser、AST——动手写一遍比看十遍书管用。
如果觉得龙书太厚，推荐两本更友好的：
- 《Crafting Interpreters》（Bob Nystrom）—— 免费在线，用 Java 和 C 写两个完整的解释器，从 tree-walking 到 bytecode VM
- 《Writing An Interpreter In Go》（Thorsten Ball）—— 用 Go 写，但思路可以平移到 Rust，代码量小，节奏快
总结
从字符串到可执行的程序，三道门：
- Lexer：字符 → Token。纯机械扫描，一个
match搞定。 - Parser：Token → AST。递归下降处理优先级，每层一个函数。
- Interpreter：AST → 结果。环境链管理变量，递归遍历求值。
400 行 Rust，一个能跑递归斐波那契的解释器就出来了。没有魔法，没有黑箱。
编译原理不是天书。它是你每天都在用的东西——cargo build 干的就是这三件事，只不过它多了一步"生成机器码"。理解了前三步，第四步只是时间问题。
动手写一个吧。从 1 + 1 开始，加到能跑斐波那契，你会发现——编译原理，原来这么好玩。