第六十九 编译器与解释器

程序员用人类能读懂的语言写下意图，CPU 却只认识一串串二进制机器码。把“给人看的“变成“给机器跑的“，就是**编译器（Compiler）和解释器（Interpreter）**的工作。可以说，整个软件世界都建立在这两个程序之上：没有编译器，C、C++、Rust、Go 无从谈起；没有解释器，Python、JavaScript、Shell 也不会存在。

这一章我们将从零开始回答三个问题：编译器与解释器到底差在哪里、一个“翻译器“内部由哪些阶段组成，以及如何用 Rust 亲手写一个能跑的小语言。最后我们会看到一个有意思的事实：Rust 编译器 rustc 本身就是用 Rust 写的，它内部甚至还藏着一个解释器。

一、为什么需要翻译

1.1 机器的语言

CPU 只执行指令：取数、加、比较、跳转。一条“把 rax 和 rbx 相加，结果写回 rax“的指令，在 x86-64 上就是三个字节：

48 01 D8        ; 机器码：add rax, rbx

人当然不该这样写程序，于是有了三层抽象：

从上往下，人写得越来越舒服；从下往上，机器执行得越来越直接。编译器与解释器就是横在中间的那道桥：

   人类可读                         机器可执行
  高级语言源码  ←── 编译器/解释器 ──→  目标代码/动作
     a + b                              add rax, rbx

1.2 翻译的两种时机

同样是翻译，方式可以完全不同。用一个类比最容易理解：

于是就有了两条经典路线：

编译执行：
  源码 ──[编译器]──► 可执行文件 ──[反复执行]──► 结果
                      （翻译只做一次）

解释执行：
  源码 ──[解释器：读取 → 分析 → 执行]──► 结果
                      （每次都重新翻译）

二、编译器与解释器对比

一个经验判断：

追求性能与部署独立性（只发可执行文件，不发源码）选编译；追求灵活、即时反馈（脚本、配置、插件、教学）选解释。

2.1 界线其实很模糊

“编译型语言“和“解释型语言“只是一种方便的简称，现实中绝大多数实现都是混合体：

所以更准确的说法是：语言本身没有“编译/解释“属性，只有“实现“才有。同一个 Python 程序，CPython 靠解释器执行，Cython/Nuitka 则把它编译成本地代码。

2.2 三种执行模式

JIT 是“既要启动快、又要跑得快“的折中：先解释运行，发现某个函数被反复调用（热点），就把它编译成机器码，下次直接跑机器码。代价是预热时间和内存占用，收益是长跑性能。这也是同一门语言在“跑 1 秒的脚本“和“跑 1 小时的服务“上表现差异巨大的原因。

三、编译器的经典流水线

无论编译 C 还是 Rust，编译器内部大体都是这条流水线：

      源程序（字符流）
           │
           ▼
   ┌───────────────┐
   │  词法分析     │  Lexer / Scanner
   └───────┬───────┘
           │ Token 流（关键字、标识符、字面量、运算符）
           ▼
   ┌───────────────┐
   │  语法分析     │  Parser
   └───────┬───────┘
           │ 抽象语法树 AST
           ▼
   ┌───────────────┐
   │  语义分析     │  符号表、类型检查、作用域检查
   └───────┬───────┘
           │ 带类型信息的 AST
           ▼
   ┌───────────────┐
   │  中间代码生成 │  IR：三地址码 / SSA / 字节码 / LLVM IR
   └───────┬───────┘
           │
           ▼
   ┌───────────────┐
   │  优化         │  常量折叠、死代码消除、内联、向量化……
   └───────┬───────┘
           │
           ▼
   ┌───────────────┐
   │  代码生成     │  汇编 / 机器码 / 字节码
   └───────┬───────┘
           │
           ▼
   ┌───────────────┐
   │  汇编与链接   │  Assembler & Linker
   └───────┬───────┘
           │
           ▼
      可执行文件

各阶段的输入、输出与典型错误：

习惯上把前三阶段叫前端（Front End，与源语言相关），中间的 IR 与优化叫中端（Middle End，与语言和目标都无关），代码生成与链接叫后端（Back End，与目标机器相关）。这种划分的意义在于：新增一门语言只需要写前端，新增一种 CPU 只需要写后端，M 种语言 × N 种目标从 M×N 个编译器变成 M+N 个模块。LLVM 就是靠这条思路成为“编译器界的乐高“：C/C++/Rust/Swift 各自写前端，产出 LLVM IR，后端复用同一套优化与代码生成。

顺便说一句：为什么现在的编译器报错这么友好？因为诊断信息本身就是流水线的副产品——每个阶段都知道自己手上的位置信息（行列号）、Token、语法结构，Rust 借用这套信息生成了“带下划线和修改建议“的错误提示；而错误在越靠前的阶段被拦住，用户得到的反馈就越清晰。

四、词法分析：把字符流切成 Token

词法分析（Lexing / Scanning）的任务是把字符流切分成一个个记号（Token）。一个 Token 通常包含三部分：种类（关键字、标识符、数字……）、词素（源码中的原文）、位置（行号列号，用于报错）。

理论上的做法是把每类 Token 描述成正则表达式，再用 Thompson 构造法转成 NFA、子集构造法转成 DFA，最后生成一个状态机自动机来扫描。工程上则常用手写扫描器（更快、错误提示更好）或用工具生成（lex/flex/logos）。两条必须遵守的规则：

1. 最长匹配（maximal munch）：遇到 <= 不能切成 < 和 =，要尽量吞掉最长的合法记号。
2. 优先级：if 既能匹配“标识符“也能匹配“关键字“，保留字优先。

下面是一个手写词法分析器，约 50 行，覆盖了我们的迷你语言（数字、标识符、+ - * / % ( ) = ;）：

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq)]
enum Token {
    Number(f64),
    Ident(String),
    Let,
    Plus,
    Minus,
    Star,
    Slash,
    Percent,
    LParen,
    RParen,
    Assign,
    Semi,
    Eof,
}

fn lex(src: &str) -> Result<Vec<Token>, String> {
    let chars: Vec<char> = src.chars().collect();
    let mut tokens = Vec::new();
    let mut i = 0;

    while i < chars.len() {
        let c = chars[i];
        match c {
            // 跳过空白
            ' ' | '\t' | '\r' | '\n' => i += 1,

            // 数字：连续的数字与小数点，最长匹配
            '0'..='9' | '.' => {
                let start = i;
                while i < chars.len() && (chars[i].is_ascii_digit() || chars[i] == '.') {
                    i += 1;
                }
                let text: String = chars[start..i].iter().collect();
                let n = text.parse::<f64>().map_err(|_| format!("非法数字字面量: {text}"))?;
                tokens.push(Token::Number(n));
            }

            // 标识符或关键字：字母/下划线开头
            c if c.is_alphabetic() || c == '_' => {
                let start = i;
                while i < chars.len() && (chars[i].is_alphanumeric() || chars[i] == '_') {
                    i += 1;
                }
                let text: String = chars[start..i].iter().collect();
                tokens.push(if text == "let" { Token::Let } else { Token::Ident(text) });
            }

            // 单字符运算符与分隔符
            '+' => { tokens.push(Token::Plus); i += 1; }
            '-' => { tokens.push(Token::Minus); i += 1; }
            '*' => { tokens.push(Token::Star); i += 1; }
            '/' => { tokens.push(Token::Slash); i += 1; }
            '%' => { tokens.push(Token::Percent); i += 1; }
            '(' => { tokens.push(Token::LParen); i += 1; }
            ')' => { tokens.push(Token::RParen); i += 1; }
            '=' => { tokens.push(Token::Assign); i += 1; }
            ';' => { tokens.push(Token::Semi); i += 1; }

            _ => return Err(format!("无法识别的字符: {c}")),
        }
    }
    tokens.push(Token::Eof); // 结束标记，让语法分析器有"哨兵"可用
    Ok(tokens)
}
}

对 let a = 3 + 4 * 2; 调用 lex，得到：

[Let, Ident("a"), Assign, Number(3.0), Plus, Number(4.0), Star, Number(2.0), Semi, Eof]

五、语法分析：从 Token 流到语法树

5.1 用文法描述语法

语法规则用文法（Grammar）描述。BNF/EBNF 是最常见的写法，{ } 表示重复 0 次以上，| 表示或：

program   = { statement } ;
statement = "let" ident "=" expr ";" | expr ";" ;
expr      = term  { ("+" | "-") term } ;
term      = unary { ("*" | "/" | "%") unary } ;
unary     = "-" unary | primary ;
primary   = number | ident | "(" expr ")" ;

这里的关键设计是把优先级编码进分层：expr 管加减、term 管乘除模、unary 管负号、primary 管括号和叶子节点。层次越深，优先级越高——这就是“* 比 + 先算“的来历。

5.2 解析方法一览

5.3 抽象语法树（AST）

解析的产物是一棵抽象语法树：只保留结构，丢掉多余的分隔符与括号。用 Rust 的枚举加上 Box，语法树可以写得非常自然：

#![allow(unused)]
fn main() {
#[derive(Debug, Clone)]
enum Expr {
    Number(f64),                      // 字面量
    Var(String),                      // 变量引用
    Unary(char, Box<Expr>),           // 一元运算：-x
    Binary(char, Box<Expr>, Box<Expr>), // 二元运算：a + b
}

#[derive(Debug, Clone)]
enum Stmt {
    Let(String, Expr),                // let x = ...;
    Expr(Expr),                       // 表达式语句
}
}

3 + 4 * 2 会变成：

        Binary('+')
        /        \
   Number(3)   Binary('*')
               /        \
         Number(4)   Number(2)

Box 是必需的：Expr 里要放 Expr，直接内联会让类型大小无限递归，Box 把它变成指针，大小就固定了。

5.4 递归下降解析器

照着文法的层次一节一个函数，就能写出解析器。乘法优先级高于加法，正是因为 parse_expr 先把 term 解析出来再组合：

#![allow(unused)]
fn main() {
struct Parser {
    tokens: Vec<Token>,
    pos: usize,
}

impl Parser {
    fn new(tokens: Vec<Token>) -> Self {
        Parser { tokens, pos: 0 }
    }

    fn peek(&self) -> &Token {
        &self.tokens[self.pos]
    }

    fn bump(&mut self) -> Token {
        let t = self.tokens[self.pos].clone();
        self.pos += 1;
        t
    }

    fn parse_program(&mut self) -> Result<Vec<Stmt>, String> {
        let mut stmts = Vec::new();
        while *self.peek() != Token::Eof {
            stmts.push(self.parse_stmt()?);
        }
        Ok(stmts)
    }

    fn parse_stmt(&mut self) -> Result<Stmt, String> {
        if *self.peek() == Token::Let {
            self.bump();
            let name = match self.bump() {
                Token::Ident(name) => name,
                other => return Err(format!("let 之后期望标识符，得到 {other:?}")),
            };
            if self.bump() != Token::Assign {
                return Err("期望 =".to_string());
            }
            let value = self.parse_expr()?;
            self.expect(Token::Semi)?;
            Ok(Stmt::Let(name, value))
        } else {
            let value = self.parse_expr()?;
            self.expect(Token::Semi)?;
            Ok(Stmt::Expr(value))
        }
    }

    fn expect(&mut self, want: Token) -> Result<(), String> {
        let got = self.bump();
        if got == want {
            Ok(())
        } else {
            Err(format!("期望 {want:?}，得到 {got:?}"))
        }
    }

    // expr := term (("+" | "-") term)*
    fn parse_expr(&mut self) -> Result<Expr, String> {
        let mut left = self.parse_term()?;
        loop {
            let op = match self.peek() {
                Token::Plus => '+',
                Token::Minus => '-',
                _ => break,
            };
            self.bump();
            let right = self.parse_term()?;
            left = Expr::Binary(op, Box::new(left), Box::new(right));
        }
        Ok(left)
    }

    // term := unary (("*" | "/" | "%") unary)*
    fn parse_term(&mut self) -> Result<Expr, String> {
        let mut left = self.parse_unary()?;
        loop {
            let op = match self.peek() {
                Token::Star => '*',
                Token::Slash => '/',
                Token::Percent => '%',
                _ => break,
            };
            self.bump();
            let right = self.parse_unary()?;
            left = Expr::Binary(op, Box::new(left), Box::new(right));
        }
        Ok(left)
    }

    // unary := "-" unary | primary
    fn parse_unary(&mut self) -> Result<Expr, String> {
        if *self.peek() == Token::Minus {
            self.bump();
            let inner = self.parse_unary()?;
            return Ok(Expr::Unary('-', Box::new(inner)));
        }
        self.parse_primary()
    }

    // primary := number | ident | "(" expr ")"
    fn parse_primary(&mut self) -> Result<Expr, String> {
        match self.bump() {
            Token::Number(n) => Ok(Expr::Number(n)),
            Token::Ident(name) => Ok(Expr::Var(name)),
            Token::LParen => {
                let inner = self.parse_expr()?;
                self.expect(Token::RParen)?;
                Ok(inner)
            }
            other => Err(format!("期望表达式，得到 {other:?}")),
        }
    }
}
}

两个值得注意的细节：

• 左递归要消除。文法若写成 expr = expr "+" term，函数会直接递归到栈溢出；改写成 expr = term { ("+"|"-") term }（即“先解析一个 term，再循环吃运算符“）就等价且不会左递归。上面的 loop 正是在做这件事。
• 左结合 vs 右结合。循环里 left = Binary(op, left, right) 让 1 - 2 - 3 解析成 (1 - 2) - 3；若改为递归处理运算符右侧，就变成右结合（=、** 通常是右结合）。

六、语义分析：语法正确不代表意思对

语法分析只管“结构对不对“。x * 2; 语法完全合法，但如果 x 从未声明，程序就是错的——这是语义分析（Semantic Analysis）的职责。

6.1 符号表与作用域

符号表（Symbol Table）记录“名字 → 类型/位置/作用域“，通常用哈希表或树实现。作用域则用链式结构表达：

全局作用域
  ├── fn main
  │     ├── let a
  │     └── 内层块
  │           └── let b     ← 查找 b：从当前层向外层沿链查找

一个极简的“声明检查“就足以体现这一步的原理：

#![allow(unused)]
fn main() {
use std::collections::HashSet;

fn check(expr: &Expr, declared: &HashSet<String>) -> Result<(), String> {
    match expr {
        Expr::Number(_) => Ok(()),
        Expr::Var(name) => {
            if declared.contains(name) {
                Ok(())
            } else {
                Err(format!("使用了未声明的变量 `{name}`"))
            }
        }
        Expr::Unary(_, inner) => check(inner, declared),
        Expr::Binary(_, l, r) => {
            check(l, declared)?;
            check(r, declared)
        }
    }
}
}

6.2 语义分析要做的四件事

Rust 在语义分析上走得比多数语言远：借用检查器（Borrow Checker） 把“悬垂指针、数据竞争“这类传统上属于运行期的问题提前到了编译期。这也是 Rust 没有 GC 却能保证内存安全的关键——详见第六十二“操作系统“与第五十九“软件漏洞“两章。

6.3 同一个式子，不同语言不同语义

语义由语言规范定义，而不是由“数学直觉“决定。最典型的坑是负数除法：

两者都自洽：Rust 的余数符号跟随被除数，Python 的余数符号跟随除数。写编译器的人必须对着规范表逐条实现，这也是“移植代码“最容易出错的地方之一。

七、中间表示与优化

7.1 为什么要再造一层 IR

中间表示（Intermediate Representation，IR）是源程序和目标机器之间的“通用语“。好处是：

• 解耦：前端只关心源语言，后端只关心目标机器，M 种语言 + N 种目标只需 M + N 个模块。
• 便于优化：AST 太“像人话“，机器码太“像机器“；IR 处在合适的抽象层，各种分析（数据流、活跃变量）才好做。
• 便于验证：Rust 的类型检查、借用检查、常量求值都发生在自己的 IR 上。

常见的 IR 形态：

SSA（Static Single Assignment）值得一提：在 SSA 形式下，每个变量只有唯一一次定义，x 被赋两次就拆成 x1、x2，分支汇合处用 φ 函数表示“到底用了哪条路径的值“。这让“某个值从哪来“变成图上的可达性问题，优化和检查都变简单了。

用现成的编译器就能看到自己代码的 IR。以 Rust 为例，一条命令即可让 rustc 打印出各阶段产物：

# 查看 MIR（类型检查、借用检查、常量求值都在这一层）
rustc --emit=mir -O src/main.rs

# 查看 LLVM IR（优化与代码生成的输入）
rustc --emit=llvm-ir -O src/main.rs

# 查看汇编
rustc --emit=asm -O src/main.rs

看 MIR 与 LLVM IR 的差别，是理解“前端关心语义、后端关心机器“最直观的方式。

7.2 常见优化

常量折叠的实现非常直观——递归遍历语法树，只要子节点都是常量就直接算出结果：

#![allow(unused)]
fn main() {
// 常量折叠：若子表达式全是常量，则在编译期直接算出结果
fn fold(expr: Expr) -> Expr {
    match expr {
        Expr::Binary(op, l, r) => {
            let l = fold(*l);
            let r = fold(*r);
            if let (Expr::Number(a), Expr::Number(b)) = (&l, &r) {
                let folded = match op {
                    '+' => Some(a + b),
                    '-' => Some(a - b),
                    '*' => Some(a * b),
                    '/' if *b != 0.0 => Some(a / b),
                    _ => None,
                };
                if let Some(v) = folded {
                    return Expr::Number(v);
                }
            }
            Expr::Binary(op, Box::new(l), Box::new(r))
        }
        Expr::Unary(op, inner) => {
            let inner = fold(*inner);
            if op == '-' {
                if let Expr::Number(n) = inner {
                    return Expr::Number(-n);
                }
            }
            Expr::Unary(op, Box::new(inner))
        }
        other => other,
    }
}
}

对 (2 + 3) * 4 + x * 1 做折叠，(2 + 3) * 4 会变成常量 20，而 x * 1 因为含变量而保持原样：

折叠前: Binary('+', Binary('*', Binary('+', Number(2), Number(3)), Number(4)),
                     Binary('*', Var("x"), Number(1)))
折叠后: Binary('+', Number(20), Binary('*', Var("x"), Number(1)))

优化必须保持语义等价。浮点数不满足结合律（(a+b)+c ≠ a+(b+c)），所以 -O 下编译器不会随意重排浮点运算；整数溢出的行为也要按语言规范处理（Rust 调试模式下直接 panic）。“优化“不是“改写”，边界由语言语义划定。

八、解释器的两种实现路线

解释器怎么执行代码？最常见的两条路线是树遍历和字节码 + 虚拟机。

8.1 树遍历解释器（Tree-Walking Interpreter）

最直接的实现：拿着 AST 递归求值，遇到加法就做加法。几十行就能跑起来，绝大多数“教学语言“和配置引擎都属于这一类。

#![allow(unused)]
fn main() {
use std::collections::HashMap;

fn eval(expr: &Expr, env: &HashMap<String, f64>) -> Result<f64, String> {
    match expr {
        Expr::Number(n) => Ok(*n),
        Expr::Var(name) => env
            .get(name)
            .copied()
            .ok_or_else(|| format!("未定义的变量: {name}")),
        Expr::Unary(op, inner) => {
            let v = eval(inner, env)?;
            match op {
                '-' => Ok(-v),
                _ => Err(format!("未知一元运算符: {op}")),
            }
        }
        Expr::Binary(op, l, r) => {
            let a = eval(l, env)?;
            let b = eval(r, env)?;
            match op {
                '+' => Ok(a + b),
                '-' => Ok(a - b),
                '*' => Ok(a * b),
                '/' => {
                    if b == 0.0 {
                        Err("除以零".to_string())
                    } else {
                        Ok(a / b)
                    }
                }
                '%' => {
                    if b == 0.0 {
                        Err("对零取模".to_string())
                    } else {
                        Ok(a % b)
                    }
                }
                _ => Err(format!("未知二元运算符: {op}")),
            }
        }
    }
}
}

缺点也很明显：每次执行 1 + 2 + 3 都要重新遍历一遍树、走一遍 match 分支，指针跳跃多、缓存不友好。

8.2 字节码解释器（Bytecode VM）

成熟实现的做法是先把 AST 编译成一维指令序列（字节码），再用一个循环派发执行。这样把“结构“一次翻译成“动作“，执行时只需顺序扫描指令：

#![allow(unused)]
fn main() {
#[derive(Debug, Clone)]
enum Instr {
    Push(f64),        // 压入常量
    Load(String),     // 读取变量
    Store(String),    // 写入变量
    Neg,              // 取负
    Add, Sub, Mul, Div, Rem,
    Pop,              // 丢弃栈顶（语句的值）
}

// 编译：后序遍历 AST，先编译操作数，再发出运算指令
fn compile(expr: &Expr, code: &mut Vec<Instr>) {
    match expr {
        Expr::Number(n) => code.push(Instr::Push(*n)),
        Expr::Var(name) => code.push(Instr::Load(name.clone())),
        Expr::Unary(_, inner) => {
            compile(inner, code);
            code.push(Instr::Neg);
        }
        Expr::Binary(op, l, r) => {
            compile(l, code);
            compile(r, code); // 注意顺序：先左后右，栈里就是 [左, 右]
            code.push(match op {
                '+' => Instr::Add,
                '-' => Instr::Sub,
                '*' => Instr::Mul,
                '/' => Instr::Div,
                '%' => Instr::Rem,
                _ => unreachable!(),
            });
        }
    }
}

fn run_vm(code: &[Instr], env: &mut HashMap<String, f64>) -> Result<f64, String> {
    let mut stack: Vec<f64> = Vec::new();

    for instr in code {
        match instr {
            Instr::Push(n) => stack.push(*n),
            Instr::Load(name) => {
                let v = env
                    .get(name)
                    .copied()
                    .ok_or_else(|| format!("未定义的变量: {name}"))?;
                stack.push(v);
            }
            Instr::Neg => {
                let v = stack.pop().ok_or("栈下溢")?;
                stack.push(-v);
            }
            Instr::Pop => {
                stack.pop();
            }
            _ => {
                // 二元运算：弹出右操作数、左操作数，压回结果
                let b = stack.pop().ok_or("栈下溢")?;
                let a = stack.pop().ok_or("栈下溢")?;
                let v = match instr {
                    Instr::Add => a + b,
                    Instr::Sub => a - b,
                    Instr::Mul => a * b,
                    Instr::Div => {
                        if b == 0.0 {
                            return Err("除以零".to_string());
                        }
                        a / b
                    }
                    Instr::Rem => {
                        if b == 0.0 {
                            return Err("对零取模".to_string());
                        }
                        a % b
                    }
                    _ => unreachable!(),
                };
                stack.push(v);
            }
        }
    }
    stack.pop().ok_or_else(|| "字节码为空".to_string())
}
}

对于 a * 10;（假设 a = 11），编译结果是：

指令序列: [Load("a"), Push(10.0), Mul]
栈式求值: Ok(110.0)

三个指令就代替了一次树遍历。这种“后序遍历 + 栈“的编译策略，正是 JVM、CPython、WebAssembly 共同的选择。

8.3 栈式还是寄存器式

字节码虚拟机又分两大流派：

另外还有两个工程技巧值得知道：

• 派发方式决定性能。最朴素的 match/switch 派发每次都要做一次跳转；改用计算跳转（computed goto） 或直接线索化（direct threading），把每个指令的处理地址放进一张表里，能显著减少分支预测失败，性能提升常常是成倍的。
• JIT 的三种流派：方法 JIT（把热点函数整体编译，如 HotSpot 的 C1/C2、V8 的 TurboFan）、追踪 JIT（把热点执行路径连成的线性轨迹编译，如 LuaJIT、PyPy）、模板/copy-and-patch JIT（预先编译好指令模板再拼接，如 CPython 3.13 的实验性 JIT、WebAssembly 运行时）。它们都是“解释器的启动速度 + 编译器的执行速度“的折中产物。

九、完整实现：一个迷你语言的解释器

把前面的零件拼起来：词法分析 → 语法分析 → 语义检查 → 树遍历求值。这个程序能处理变量声明与赋值、四则运算（含取模）、一元负号、括号优先级，并给出可读的错误信息。

待解释的源码：

let a = 3 + 4 * 2;
let b = (3 + 4) * 2;
let c = -a % 5;
let d = a / b;
a + b * c - d;

完整代码（单文件，可直接 rustc interp.rs && ./interp 运行）：

use std::collections::{HashMap, HashSet};

// ---------- 1. 词法分析 ----------

#[derive(Debug, Clone, PartialEq)]
enum Token {
    Number(f64),
    Ident(String),
    Let,
    Plus,
    Minus,
    Star,
    Slash,
    Percent,
    LParen,
    RParen,
    Assign,
    Semi,
    Eof,
}

fn lex(src: &str) -> Result<Vec<Token>, String> {
    let chars: Vec<char> = src.chars().collect();
    let mut tokens = Vec::new();
    let mut i = 0;

    while i < chars.len() {
        let c = chars[i];
        match c {
            ' ' | '\t' | '\r' | '\n' => i += 1,
            '0'..='9' | '.' => {
                let start = i;
                while i < chars.len() && (chars[i].is_ascii_digit() || chars[i] == '.') {
                    i += 1;
                }
                let text: String = chars[start..i].iter().collect();
                let n = text.parse::<f64>().map_err(|_| format!("非法数字字面量: {text}"))?;
                tokens.push(Token::Number(n));
            }
            c if c.is_alphabetic() || c == '_' => {
                let start = i;
                while i < chars.len() && (chars[i].is_alphanumeric() || chars[i] == '_') {
                    i += 1;
                }
                let text: String = chars[start..i].iter().collect();
                tokens.push(if text == "let" { Token::Let } else { Token::Ident(text) });
            }
            '+' => { tokens.push(Token::Plus); i += 1; }
            '-' => { tokens.push(Token::Minus); i += 1; }
            '*' => { tokens.push(Token::Star); i += 1; }
            '/' => { tokens.push(Token::Slash); i += 1; }
            '%' => { tokens.push(Token::Percent); i += 1; }
            '(' => { tokens.push(Token::LParen); i += 1; }
            ')' => { tokens.push(Token::RParen); i += 1; }
            '=' => { tokens.push(Token::Assign); i += 1; }
            ';' => { tokens.push(Token::Semi); i += 1; }
            _ => return Err(format!("无法识别的字符: {c}")),
        }
    }
    tokens.push(Token::Eof);
    Ok(tokens)
}

// ---------- 2. 语法分析：AST ----------

#[derive(Debug, Clone)]
enum Expr {
    Number(f64),
    Var(String),
    Unary(char, Box<Expr>),
    Binary(char, Box<Expr>, Box<Expr>),
}

#[derive(Debug, Clone)]
enum Stmt {
    Let(String, Expr),
    Expr(Expr),
}

struct Parser {
    tokens: Vec<Token>,
    pos: usize,
}

impl Parser {
    fn new(tokens: Vec<Token>) -> Self {
        Parser { tokens, pos: 0 }
    }

    fn peek(&self) -> &Token {
        &self.tokens[self.pos]
    }

    fn bump(&mut self) -> Token {
        let t = self.tokens[self.pos].clone();
        self.pos += 1;
        t
    }

    fn parse_program(&mut self) -> Result<Vec<Stmt>, String> {
        let mut stmts = Vec::new();
        while *self.peek() != Token::Eof {
            stmts.push(self.parse_stmt()?);
        }
        Ok(stmts)
    }

    fn parse_stmt(&mut self) -> Result<Stmt, String> {
        if *self.peek() == Token::Let {
            self.bump();
            let name = match self.bump() {
                Token::Ident(name) => name,
                other => return Err(format!("let 之后期望标识符，得到 {other:?}")),
            };
            if self.bump() != Token::Assign {
                return Err("期望 =".to_string());
            }
            let value = self.parse_expr()?;
            self.expect(Token::Semi)?;
            Ok(Stmt::Let(name, value))
        } else {
            let value = self.parse_expr()?;
            self.expect(Token::Semi)?;
            Ok(Stmt::Expr(value))
        }
    }

    fn expect(&mut self, want: Token) -> Result<(), String> {
        let got = self.bump();
        if got == want {
            Ok(())
        } else {
            Err(format!("期望 {want:?}，得到 {got:?}"))
        }
    }

    // expr := term (("+" | "-") term)*
    fn parse_expr(&mut self) -> Result<Expr, String> {
        let mut left = self.parse_term()?;
        loop {
            let op = match self.peek() {
                Token::Plus => '+',
                Token::Minus => '-',
                _ => break,
            };
            self.bump();
            let right = self.parse_term()?;
            left = Expr::Binary(op, Box::new(left), Box::new(right));
        }
        Ok(left)
    }

    // term := unary (("*" | "/" | "%") unary)*
    fn parse_term(&mut self) -> Result<Expr, String> {
        let mut left = self.parse_unary()?;
        loop {
            let op = match self.peek() {
                Token::Star => '*',
                Token::Slash => '/',
                Token::Percent => '%',
                _ => break,
            };
            self.bump();
            let right = self.parse_unary()?;
            left = Expr::Binary(op, Box::new(left), Box::new(right));
        }
        Ok(left)
    }

    // unary := "-" unary | primary
    fn parse_unary(&mut self) -> Result<Expr, String> {
        if *self.peek() == Token::Minus {
            self.bump();
            let inner = self.parse_unary()?;
            return Ok(Expr::Unary('-', Box::new(inner)));
        }
        self.parse_primary()
    }

    // primary := number | ident | "(" expr ")"
    fn parse_primary(&mut self) -> Result<Expr, String> {
        match self.bump() {
            Token::Number(n) => Ok(Expr::Number(n)),
            Token::Ident(name) => Ok(Expr::Var(name)),
            Token::LParen => {
                let inner = self.parse_expr()?;
                self.expect(Token::RParen)?;
                Ok(inner)
            }
            other => Err(format!("期望表达式，得到 {other:?}")),
        }
    }
}

// ---------- 3. 语义分析：声明检查 ----------

fn check(expr: &Expr, declared: &HashSet<String>) -> Result<(), String> {
    match expr {
        Expr::Number(_) => Ok(()),
        Expr::Var(name) => {
            if declared.contains(name) {
                Ok(())
            } else {
                Err(format!("使用了未声明的变量 `{name}`"))
            }
        }
        Expr::Unary(_, inner) => check(inner, declared),
        Expr::Binary(_, l, r) => {
            check(l, declared)?;
            check(r, declared)
        }
    }
}

// ---------- 4. 树遍历求值 ----------

fn eval(expr: &Expr, env: &HashMap<String, f64>) -> Result<f64, String> {
    match expr {
        Expr::Number(n) => Ok(*n),
        Expr::Var(name) => env
            .get(name)
            .copied()
            .ok_or_else(|| format!("未定义的变量: {name}")),
        Expr::Unary(op, inner) => {
            let v = eval(inner, env)?;
            match op {
                '-' => Ok(-v),
                _ => Err(format!("未知一元运算符: {op}")),
            }
        }
        Expr::Binary(op, l, r) => {
            let a = eval(l, env)?;
            let b = eval(r, env)?;
            match op {
                '+' => Ok(a + b),
                '-' => Ok(a - b),
                '*' => Ok(a * b),
                '/' => {
                    if b == 0.0 {
                        Err("除以零".to_string())
                    } else {
                        Ok(a / b)
                    }
                }
                '%' => {
                    if b == 0.0 {
                        Err("对零取模".to_string())
                    } else {
                        Ok(a % b)
                    }
                }
                _ => Err(format!("未知二元运算符: {op}")),
            }
        }
    }
}

// ---------- 5. 驱动：源码 -> 结果 ----------

fn run(src: &str) -> Result<f64, String> {
    let tokens = lex(src)?;
    let stmts = Parser::new(tokens).parse_program()?;

    // 语义分析：按顺序收集已声明变量，并检查引用的合法性
    let mut declared = HashSet::new();
    for stmt in &stmts {
        match stmt {
            Stmt::Let(name, value) => {
                check(value, &declared)?;
                declared.insert(name.clone());
            }
            Stmt::Expr(e) => check(e, &declared)?,
        }
    }

    // 解释执行
    let mut env = HashMap::new();
    let mut last = 0.0;
    for stmt in &stmts {
        match stmt {
            Stmt::Let(name, value) => {
                let v = eval(value, &env)?;
                env.insert(name.clone(), v);
                last = v;
            }
            Stmt::Expr(e) => last = eval(e, &env)?,
        }
    }
    Ok(last)
}

fn main() {
    let src = r#"
        let a = 3 + 4 * 2;
        let b = (3 + 4) * 2;
        let c = -a % 5;
        let d = a / b;
        a + b * c - d;
    "#;

    match run(src) {
        Ok(v) => println!("结果 = {v}"),
        Err(e) => eprintln!("错误: {e}"),
    }

    // 故意写错，看看错误提示
    for bad in ["1 + ;", "x * 2;", "1 / 0;"] {
        match run(bad) {
            Ok(v) => println!("{bad:>8} => {v}"),
            Err(e) => println!("{bad:>8} => 错误: {e}"),
        }
    }
}

运行结果：

结果 = -3.7857142857142856
   1 + ; => 错误: 期望表达式，得到 Semi
  x * 2; => 错误: 使用了未声明的变量 `x`
  1 / 0; => 错误: 除以零

对照着看这一步步发生了什么：

想把它变成一个字节码解释器，只需把 run 里的 eval(value, &env) 换成“compile 成 Vec<Instr> 再 run_vm“——第 8.2 节的代码可以直接接上去。

如何继续扩展这门语言？四步走，缺一不可：

1. 加 Token（比如 If、While、LBrace、RBrace）；
2. 加 AST 节点（Stmt::If(Expr, Vec<Stmt>, Vec<Stmt>)）；
3. 在 Parser 里加对应的解析函数（parse_if、parse_block）；
4. 在 eval / check 里加对应的分支（注意：if 的条件与分支要单独检查，循环要考虑是否会死循环）。

再往下走，函数调用需要引入栈帧和环境链（局部变量不再是一个 HashMap，而是每层调用一个），闭包则需要捕获环境；这些概念与第三十二“函数“、第二十四“λ演算“两章一脉相承。

十、Rust 编译器生态

Rust 社区几乎把编译原理的每个环节都做了一遍，而且很多工具本身就是用 Rust 写的（这点很像 C 语言：写编译器的语言，往往就是被编译的语言）。

用这些工具，写一个 DSL 的成本可以低到“一个下午“：logos 出 Token 流、chumsky 或 lalrpop 出 AST、自己写几百行求值器，就是一个可用的规则引擎或配置语言。

10.1 关于 rustc 本身

Rust 编译器的几个事实，对照本章的流水线看会很有味道：

• 自举（Bootstrapping）：rustc 是 Rust 写的。编译器从哪来？官方发布一个预编译的编译器（stage0）作为种子，用它编译出 stage1，再用 stage1 编译出正式的 stage2。为了确认自举结果可信，构建系统还会用不同阶段互相编译并比对产物。这就是“鸡生蛋“问题的标准答案。
• 多级 IR：源码先降级成 HIR（高层 IR，保留语法结构），再降级成 MIR（中层 IR，SSA 形式），类型检查、借用检查、常量求值都发生在 MIR 上，最后翻译成 LLVM IR 交给 LLVM 做优化与代码生成。所以 Rust 的编译期也跑着一个解释器：const 表达式由 MIR 解释器直接求值。
• 后端可替换：既然中间隔着 LLVM IR 与 MIR，后端就能换。rustc_codegen_cranelift 用 Cranelift 替代 LLVM，换来更快的编译速度（代价是生成代码略慢）；增加一个 CPU 架构，也主要是写一个后端。
• 目标三元组：<架构>-<厂商>-<系统>-<ABI>，例如 x86_64-unknown-linux-gnu、aarch64-apple-darwin、wasm32-unknown-unknown。交叉编译就是把前端换成“为别的三元组生成代码“。

编译器是“零成本抽象“神话的兑现者：迭代器、Option、泛型在源码层面都是高级抽象，但经过内联与单态化之后，生成的机器码可以与手写循环几乎一致。抽象不花钱，是因为编译器替你花了功夫。

十一、总结与练习

本章小结

练习建议

1. 加语法：给第九节的迷你语言加上 if/else 与 while，注意在词法、AST、解析、求值四处都要动。
2. 加字符串与比较：引入 String 与 <、== 运算符，把 f64 值域扩展成枚举，体会“类型检查“为什么必须放在求值之前。
3. 改成字节码：用第 8.2 节的 compile + run_vm 替换树遍历求值，实现 if 的跳转指令（JumpIfZero、Jump），再对比两种实现的代码量与运行速度。
4. 写个常量折叠并验证正确性：对随机生成的表达式树分别做“折叠后求值“与“直接求值“，断言结果一致——这就是最朴素的编译器测试方法。
5. 看真实的 IR：写一个循环求和函数，用 rustc --emit=mir 与 --emit=llvm-ir 打印出来，观察 -O 前后 MIR 与 LLVM IR 的差异。
6. 借力工具：用 logos 重写第九节的词法分析器，再用 chumsky 或 lalrpop 重写语法分析器，比较手写与生成的代码在可读性、错误提示、性能上的差别。
7. 进阶挑战：实现一个支持函数定义与调用的解释器（需要栈帧与环境链），再试着支持闭包——你会发现“作用域“从静态概念变成了需要在运行时捕获的数据结构。