迷你编译器解释器

# 第七章：C++ 迷你编译器解释器（mycc）

本章是综合案例的第七关·语言实现集大成——从 06.迷你KV存储引擎的"工业级数据存储"换一个完全不同的视角，做语言实现这个 CS 经典命题。本案例会带你走完一门小语言从源码到运行的五段式全链路：

1.字符流 → Token：状态机词法分析器，把 "x = 1 + 2;" 切成 6 个 Token，首次实战 std::variant 表达 7 类 Token。

2.Token → AST：递归下降语法分析器，把扁平 Token 流升维成树形 AST，12 个 AstNode 派生类展示 C++ 多态的真正威力——每个语法构造都是一个类。

3.AST → 字节码：访问者模式（Visitor）+ 双遍历——第一遍类型检查、第二遍代码生成，最终输出 36 条栈式字节码。

4.字节码 → 执行：栈式虚拟机（VM）+ 帧栈 + 函数调用——这是 Python/Java/V8 的简化版内核，让你看懂"解释执行"到底在做什么。

5.异常 + REPL：四级异常类树（词法/语法/类型/运行时）+ 交互式解释器——就是 python3 命令行的简化版。

学完这个案例你能做什么：拿到任何一门动态语言（Python / Lua / JavaScript），你都能说出"这一行代码在解释器里走了几步"——这是远超"会写 C++ 业务代码"的更深层能力。

学习方式：本案例按"五段式 → 阶段拆解 → 写代码 → 跑编译 → 看输出 → 避陷阱"六步法推进。总共 8 大阶段、约 22 小时，建议分 5-7 天完成。每个阶段都遵循"写一点 → 编译 → 看输出 → 再写下一点"的节奏。

# 渐进学习节奏

先读这段，再开始敲代码！本案例严格按照真实编译器开发的工程节奏推进，绝不一上来甩给你 4000 行代码让你抄。我们的节奏是这样的：

阶段 ① REPL 骨架（§02）        · 1 h    · main + readLine + 退出
阶段 ② Lexer 词法分析（§03）    · 3 h    · 状态机 + variant Token + 7 类标记
阶段 ③ AST 抽象基类（§04）      · 2 h    · AstNode 多态体系 + shared_ptr 树
阶段 ④ Parser 递归下降（§05）   · 4 h    · 12 节点构造 + 优先级爬升
阶段 ⑤ Visitor 类型检查（§06）  · 3 h    · 模板访问者 + 符号表栈
阶段 ⑥ Codegen 字节码（§07）    · 4 h    · 36 条 OpCode + 跳转回填
阶段 ⑦ VM 虚拟机（§08）         · 4 h    · 栈式执行 + 函数帧 + 调用栈
阶段 ⑧ 异常 + REPL 完善（§09）  · 1 h    · 四级异常树 + 文件模式 + 命令行

每个 Step 必须做的三件事：

看 🎯 阶段目标卡片：明确这一阶段做什么、不做什么、验收标准

写一小段代码就编译运行一次（看到 🧪 立刻动手）

看到预期输出再写下一个 Step（绝不一口气抄完整段代码）

⚠️ 本案例独有的"故意造 bug → 修复"高峰：

阶段 ④ §5.6 让你先写左结合错误的递归下降，运行 1-2-3 输出 2 而不是 -4——亲眼看到"语法分析器写错就改变语义"
阶段 ⑦ §8.4 让你先实现没有跳转回填的 if 编译，运行时崩溃——亲眼看到"字节码 jmp 不能用'回看式偏移'"

✅ 每个阶段的结构（你在正文里会反复看到）：

┌─ 🎯 阶段目标 ──────────────┐  ← 阶段开头：明确做什么/不做什么
│  完成什么、不做什么、验收标准    │
└──────────────────────────────┘

  Step X.1：先写最小可编译版（5-30 行）
  Step X.2：编译 → 运行 → 看到输出 ✅
  Step X.3：再加一个小功能（10-50 行）
  ...

┌─ 🧪 运行验证 ─────────────┐  ← 阶段结尾：完整命令 + 预期输出 + 排错
│  编译命令 / 预期输出 / 排错指南 │
└──────────────────────────┘

┌─ 📌 阶段小结 ─────────────┐  ← 阶段结尾：今天学到了什么
│  ✅ 已掌握 / ⏸ 暂未涉及        │
└────────────────────────┘

# 案例元信息

项目	说明
难度	★★★★★★
预估时长	22 小时（建议分 5-7 天，每天 3-4 小时）
前置章节	卷一全 17 章——本案例是真正的"全卷复习题"
覆盖知识点	`std::variant` Token / `enum class` OpCode / 抽象基类 + 12 个派生类（AstNode 体系）/ 访问者模式（Visitor）/ `std::shared_ptr` AST 节点 / `std::unordered_map` 符号表 / `std::vector` 字节码与栈 / 递归下降 / 优先级爬升 / 跳转回填 / 四级异常类树 / 模板（`Stack<T>` 求值栈）/ `std::optional` 查表 / `std::string_view` 切词 / lambda 注册 OpCode 处理函数
设计亮点	五段式全链路（Lexer→Parser→Checker→Codegen→VM）+ 三次访问者遍历（类型检查/代码生成/反汇编） + 栈式 VM 调用栈
⚠ 已知局限	不做 GC（值类型只支持 int / double / bool / string；无引用类型），不做闭包，不做模块系统——挑战题各覆盖一个
最终产物	可执行文件 `mycc` + 一组 `.mycc` 示例源码
代码规模	约 1800 行 / 18 个文件

# 项目结构

mycc/
├── main.cpp                          # 入口：REPL 或文件模式
├── token.h / token.cpp               # 阶段 ②：variant Token 定义
├── lexer.h / lexer.cpp               # 阶段 ②：状态机词法分析
├── ast.h                             # 阶段 ③：AstNode 基类 + 12 派生类
├── parser.h / parser.cpp             # 阶段 ④：递归下降语法分析
├── visitor.h                         # 阶段 ⑤：模板 Visitor&lt;T> 基类
├── type_checker.h / type_checker.cpp # 阶段 ⑤：类型检查访问者
├── opcode.h                          # 阶段 ⑥：36 条字节码定义
├── codegen.h / codegen.cpp           # 阶段 ⑥：AST → 字节码访问者
├── vm.h / vm.cpp                     # 阶段 ⑦：栈式虚拟机
├── exceptions.h                      # 阶段 ⑧：四级异常类树
└── examples/
    ├── hello.mycc                    # 第一个程序
    ├── fib.mycc                      # 递归示例
    └── fizzbuzz.mycc                 # 控制流综合

# 一条命令编译运行

cd mycc
g++ -std=c++17 -O0 -g *.cpp -o mycc
./mycc                              # 进入 REPL
./mycc examples/fib.mycc            # 跑文件

# 目录快速导航

点击以下条目即可跳转到对应节。【🔑 重点节】推荐优先阅读，⭐ 表示本案高光段落。

01.语言设计与五段式架构
02.REPL 骨架【阶段①骨架】
03.Lexer 词法分析【阶段②状态机⭐】
04.AST 抽象语法树【阶段③多态体系】
05.Parser 递归下降【阶段④文法实现⭐】
06.Visitor 类型检查【阶段⑤访问者模式⭐】
07.Codegen 字节码生成【阶段⑥指令集设计】
08.VM 栈式虚拟机【阶段⑦执行引擎⭐】
09.异常体系与 REPL 完善【阶段⑧收官】
10.项目总结分析
11.项目技术思考
12.衔接与延伸
- 12.1 与 06 案例的差异
- 12.2 三个延伸挑战

# 01.语言设计与五段式架构

# 1.1 mycc 语言能做什么

mycc 是一门类 C 语法的小语言，看下面这段 fib.mycc 你就懂：

// 计算斐波那契数列
fn fib(n) {
    if (n < 2) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

var i = 0;
while (i < 10) {
    print fib(i);
    i = i + 1;
}

跑起来输出：

支持的特性：

特性	示例	阶段
字面量	`42`、`3.14`、`"hello"`、`true`/`false`	②
算术与比较	`+ - * / % == != < <= > >=`	④
逻辑运算	`&& \|\| !`	④
变量	`var x = 1; x = x + 1;`	④
控制流	`if / else / while`	④
函数	`fn name(参数) { ... return ... }`	④
输出	`print 表达式;`	④
注释	`// 单行`	②

不支持的（挑战题各覆盖一个）：闭包、数组、对象、模块、GC、字符串拼接。

# 1.2 五段式架构总图

源代码字符串
"var x = 1 + 2; print x;"
        │
        │  阶段 ② Lexer（词法分析）
        ▼
Token 流
[VAR, ID(x), '=', NUM(1), '+', NUM(2), ';', PRINT, ID(x), ';', EOF]
        │
        │  阶段 ④ Parser（语法分析）
        ▼
AST（抽象语法树）
Program
├── VarDecl(x)
│   └── BinOp(+)
│       ├── NumLit(1)
│       └── NumLit(2)
└── PrintStmt
    └── VarRef(x)
        │
        │  阶段 ⑤ TypeChecker（语义检查）
        ▼
类型标注后的 AST（不变形，只在每个节点上"贴标签"）
        │
        │  阶段 ⑥ Codegen（代码生成）
        ▼
字节码（线性指令序列）
[PUSH 1, PUSH 2, ADD, STORE x, LOAD x, PRINT, HALT]
        │
        │  阶段 ⑦ VM（虚拟机执行）
        ▼
程序输出："3"

🔑 架构精髓：每个阶段的输出是下一阶段的输入——没有跨阶段耦合。这意味着：

你可以单独测每一阶段（阶段 ② 写完就能验证 Token 流，不必等到 §07 才知道前面对不对）
任何一阶段都可以替换实现——比如把字节码替换成 LLVM IR 就是 mini-Clang
这是编译原理课的标准教学路径——经典且永不过时

# 1.3 涉及知识点

卷一章节	知识点	在本案例中的位置
第 2-6 章基础	`enum class`、状态机、字符串处理	§03 Lexer
第 7 章函数	lambda 注册 / 默认参数 / 引用传参	§06、§07、§08 全篇
第 8 章指针引用	`shared_ptr<AstNode>` 树形所有权	§04 AST
第 9-10 章类与多态	抽象基类 + 12 派生类 + 虚函数	§04 AST、§06 Visitor
第 11 章内存模型	栈帧、调用栈、局部变量布局	§08 VM
第 12 章动态内存	RAII / `make_shared` / 树析构	§04、§07
第 13 章 IO	`ifstream` 读源文件 / `cout` 输出	§02、§09
第 14 章异常	自定义异常类树 + `try/catch`	§09
第 16 章 STL	`vector`/`unordered_map`/`stack` 全家桶	§03、§06、§07、§08
第 17 章预处理	`#pragma once` / `#include` 大文件组织	全篇
第 18 章现代特性	`variant` Token / `optional` 查表 / `string_view` 切词	§03

✅ 17 章无短板覆盖——这就是为什么本案例排在卷二最后的位置。

# 02.REPL 骨架

┌─ 🎯 阶段 ① 目标 ────────────────────────────────────┐
│ 完成什么：跑通"显示 mycc> 提示符 → 读一行 → 回显 → 输入 :q 退出"│
│ 不做什么：不接 Lexer、不接 Parser——一切实现都是占位          │
│ 验收标准：能循环读输入、能正常退出、Ctrl+D 也能优雅退出        │
│ 预计耗时：1 小时                                            │
│ 关键思路：先打通"输入循环"管道——所有解释器都是这个壳子        │
└──────────────────────────────────────────────────┘

# 2.1 创建项目空文件

我们先把项目目录和所有空文件一次性创建好——但只有 main.cpp 这一个有内容，其他全是空占位文件，让你一眼看到后面要填多少东西：

mkdir mycc && cd mycc
mkdir examples
touch main.cpp \
      token.h token.cpp \
      lexer.h lexer.cpp \
      ast.h \
      parser.h parser.cpp \
      visitor.h \
      type_checker.h type_checker.cpp \
      opcode.h \
      codegen.h codegen.cpp \
      vm.h vm.cpp \
      exceptions.h

📌 新手提示：18 个空文件看起来吓人，但不是一次性写完——按 8 个阶段、每次只填 1-3 个文件的节奏推进，每填完一组就编译验证一次。

# 2.2 灵魂三问

在动手之前先停 30 秒：

❓ REPL 全称是什么？ 答：Read-Eval-Print-Loop——读输入、求值、打印、循环。本阶段先实现 R 和 L（读和循环），E 和 P 留给后面阶段。

❓ 为什么先做 REPL 而不是 Lexer？ 答：Lexer 需要一个输入源——REPL 是最简单的输入源（终端读一行）。如果先写 Lexer，你得先写 cin.getline 才能测——那不就是 REPL 嘛？先做能驱动一切的入口。

❓ 现在第一步做什么？ 答：输入循环 + :q 退出——跑通管道，让程序"能跑能退"。

🔑 教学要点：和 03 案例 §2.1 完全相同——先做最底层的依赖项。"输入 + 退出"是所有 REPL 程序的根。

# 2.3 让程序能跑能退

📁 main.cpp（阶段 ① 骨架版）：

#include <iostream>
#include <string>
using namespace std;

int main(int argc, char* argv[]) {
    cout << "mycc 0.1 — 输入 :q 退出，:h 查看帮助\n";

    string line;
    while (true) {
        cout << "mycc> ";
        if (!getline(cin, line)) {       // Ctrl+D 触发 EOF
            cout << "\n再见！\n";
            return 0;
        }

        // 元命令（以 : 开头）
        if (line == ":q") {
            cout << "再见！\n";
            return 0;
        }
        if (line == ":h") {
            cout << "  :q   退出\n  :h   帮助\n  其他 当作 mycc 源码（阶段 ②起接通）\n";
            continue;
        }
        if (line.empty()) continue;

        // TODO（阶段 ②）: 调 Lexer 切分 Token
        // TODO（阶段 ④）: 调 Parser 生成 AST
        // TODO（阶段 ⑤）: 调 TypeChecker
        // TODO（阶段 ⑥）: 调 Codegen
        // TODO（阶段 ⑦）: 调 VM 执行
        cout << "[占位] 你输入了: " << line << "\n";
    }
    return 0;
}

🧪 立刻编译运行（阶段 ① 验收）

g++ -std=c++17 main.cpp -o mycc
./mycc

操作：输入 var x = 1; → 看到回显 → 输入 :h → 看到帮助 → 输入 :q 退出 → 再开一次按 Ctrl+D 退出

预期输出：

mycc 0.1 — 输入 :q 退出，:h 查看帮助
mycc> var x = 1;
[占位] 你输入了: var x = 1;
mycc> :h
  :q   退出
  :h   帮助
  其他 当作 mycc 源码（阶段 ②起接通）
mycc> :q
再见！

✅ REPL 管道通了：Read 和 Loop 都跑通——后面 7 个阶段都是把那一串 // TODO 一个一个填上。

排错指南：

现象	原因
`getline` 链接报错	漏写 `#include <string>`
Ctrl+D 后崩溃	漏写 `if (!getline(...))` 的失败分支
输入空行后程序卡死	漏写 `if (line.empty()) continue;`

┌─ 📌 阶段 ① 小结 ────────────────────────────────────┐
│  ✅ 你刚刚掌握了：                                              │
│    • REPL 主循环：getline + 元命令 + 退出三件套                  │
│    • Ctrl+D（EOF）的优雅处理                                    │
│    • 用 // TODO 给后续阶段占位（保持代码清晰）                    │
│  ⏸ 还没碰的（下阶段才会做）：                                    │
│    • Lexer 词法分析（阶段 ②）                                    │
│    • Parser、TypeChecker、Codegen、VM（阶段 ④-⑦）                │
│  📌 进入下阶段前务必：                                            │
│    git init &amp;&amp; git add . &amp;&amp; git commit -m "stage1: repl skeleton"│
└──────────────────────────────────────────────────┘

# 03.Lexer 词法分析

┌─ 🎯 阶段 ② 目标 ────────────────────────────────────┐
│ 完成什么：把字符串 "var x = 1 + 2;" 切成 7 个 Token         │
│ 不做什么：不接 Parser、不做 AST——这阶段产出就是 Token 数组    │
│ 验收标准：REPL 输入一行源码 → 看到 Token 序列打印             │
│ 预计耗时：3 小时                                            │
│ 关键思路：先支持数字 → 加运算符 → 加标识符与关键字 → 加字符串 │
│           每加一类就编译一次，绝不一次写完                    │
└──────────────────────────────────────────────────┘

# 3.1 灵魂三问：为什么先做词法

❓ 不分词直接给 Parser 字符流不行吗？

来看反例：假设 Parser 直接读字符 v、a、r、、x——它要先判断"v 后面接 a r 是不是关键字 var"，再判断"后面那个字符是空白还是标识符延续"——Parser 既要管语法又要管字符，复杂度爆炸。

✅ 分层带来的清晰：Lexer 只管"把字符流切成 Token"，Parser 只管"把 Token 拼成树"——单一职责原则的教科书级范例。

❓ Token 用什么数据结构表示？

候选：

候选	优点	缺点
`enum + struct { int kind; string text; }`	朴实易懂	数字 Token 还得 `stoi(text)`，浪费
`class TokenBase + 派生 NumToken/IdToken/...`	OOP 范式	16 类 Token 要写 16 个类，过度设计
`struct { Kind k; std::variant<...> value; }`	类型安全 + 一个对象装 7 种数据	卷一第 18 章特性，新手稍陌生

✅ 选 variant 版——本案例正是 std::variant 真正落地的舞台。

❓ 第一步做什么？ 答：只切数字——最简单的字符类（数字 0-9 是连续区间）。先把"读字符 + 累积字符 + 产出一个 Token"的循环跑通。

# 3.2 Token 数据结构

📁 token.h：

#pragma once
#include <string>
#include <variant>
#include <iostream>

// 16 种 Token 类别
enum class TokKind {
    // 字面量
    Number,         // 整数或浮点：42、3.14
    String,         // 字符串："hello"
    True, False,    // 布尔：true、false

    // 标识符与关键字
    Ident,          // 标识符：x、fib
    Var, Print, If, Else, While, Fn, Return,   // 关键字

    // 单/多字符运算符
    Plus, Minus, Star, Slash, Percent,
    Assign,                                  // =
    Eq, Ne, Lt, Le, Gt, Ge,                  // == != < <= > >=
    AndAnd, OrOr, Bang,                      // && || !
    LParen, RParen, LBrace, RBrace,          // ( ) { }
    Semicolon, Comma,                        // ; ,

    Eof,            // 输入结束哨兵
};

// Token：tag + 7 类可能的载荷
struct Token {
    TokKind kind;
    std::variant<std::monostate, double, std::string> value;
    int line = 1;       // 出错时定位

    Token() = default;
    Token(TokKind k, int ln = 1) : kind(k), line(ln) {}
    Token(TokKind k, double n, int ln = 1)            : kind(k), value(n), line(ln) {}
    Token(TokKind k, const std::string& s, int ln = 1): kind(k), value(s), line(ln) {}

    // 调试输出（阶段 ② 验收时用）
    void dump(std::ostream& os) const;
};

// 工具：把 TokKind 转成可读字符串（调试 + 错误信息用）
const char* tokKindName(TokKind k);

📁 token.cpp：

#include "token.h"

const char* tokKindName(TokKind k) {
    switch (k) {
        case TokKind::Number: return "Number";
        case TokKind::String: return "String";
        case TokKind::True:   return "True";    case TokKind::False: return "False";
        case TokKind::Ident:  return "Ident";
        case TokKind::Var:    return "Var";     case TokKind::Print: return "Print";
        case TokKind::If:     return "If";      case TokKind::Else:  return "Else";
        case TokKind::While:  return "While";   case TokKind::Fn:    return "Fn";
        case TokKind::Return: return "Return";
        case TokKind::Plus:   return "+";       case TokKind::Minus: return "-";
        case TokKind::Star:   return "*";       case TokKind::Slash: return "/";
        case TokKind::Percent:return "%";
        case TokKind::Assign: return "=";       case TokKind::Eq:    return "==";
        case TokKind::Ne:     return "!=";      case TokKind::Lt:    return "<";
        case TokKind::Le:     return "<=";      case TokKind::Gt:    return ">";
        case TokKind::Ge:     return ">=";
        case TokKind::AndAnd: return "&&";      case TokKind::OrOr:  return "||";
        case TokKind::Bang:   return "!";
        case TokKind::LParen: return "(";       case TokKind::RParen:return ")";
        case TokKind::LBrace: return "{";       case TokKind::RBrace:return "}";
        case TokKind::Semicolon: return ";";    case TokKind::Comma: return ",";
        case TokKind::Eof:    return "<EOF>";
    }
    return "?";
}

void Token::dump(std::ostream& os) const {
    os << "Token(" << tokKindName(kind);
    // ⭐ std::visit：编译期分派访问 variant 各分支
    std::visit([&os](auto&& v) {
        using T = std::decay_t<decltype(v)>;
        if constexpr (std::is_same_v<T, double>)            os << ", " << v;
        else if constexpr (std::is_same_v<T, std::string>)  os << ", \"" << v << "\"";
        // monostate 分支什么都不打
    }, value);
    os << ")";
}

📚 std::variant 三件套：

构造：Token tk(TokKind::Number, 42.0) 自动选 double 分支

取值：std::get<double>(tk.value) 显式指定类型，类型错则抛 bad_variant_access

遍历：std::visit(lambda, var) 编译期分派——本案例 dump 用 if constexpr 区分类型分支

🆕 C++17 if constexpr：编译期判断条件——和运行时 if 不同，不满足条件的分支不会被实例化——所以 monostate 进来时不会去执行 os << v（monostate 没定义 <<）。

# 3.3 第一版 Lexer 只切数字

📁 lexer.h（第一版）：

#pragma once
#include "token.h"
#include <string>
#include <vector>

class Lexer {
public:
    explicit Lexer(std::string source) : src(std::move(source)) {}
    std::vector<Token> tokenize();      // 主接口：一次切完所有 Token

private:
    std::string src;
    size_t pos = 0;
    int    line = 1;

    char peek() const { return pos < src.size() ? src[pos] : '\0'; }
    char advance()    { return src[pos++]; }
    bool isAtEnd() const { return pos >= src.size(); }

    Token readNumber();         // 阶段 ② Step 1
};

📁 lexer.cpp（第一版）：

#include "lexer.h"
#include <cctype>

std::vector<Token> Lexer::tokenize() {
    std::vector<Token> out;
    while (!isAtEnd()) {
        char c = peek();
        if (std::isdigit(static_cast<unsigned char>(c))) {
            out.push_back(readNumber());
            continue;
        }
        // 阶段 ② Step 2 起：再加运算符、空白、标识符
        // 现在不认识的字符暂时跳过（教学占位）
        advance();
    }
    out.emplace_back(TokKind::Eof, line);
    return out;
}

Token Lexer::readNumber() {
    size_t start = pos;
    while (!isAtEnd() && std::isdigit(static_cast<unsigned char>(peek()))) advance();
    if (peek() == '.') {                  // 浮点
        advance();
        while (!isAtEnd() && std::isdigit(static_cast<unsigned char>(peek()))) advance();
    }
    double v = std::stod(src.substr(start, pos - start));
    return Token(TokKind::Number, v, line);
}

修改 main.cpp，把占位回显换成调用 Lexer：

#include "lexer.h"      // 加这一行

// 在 main 的循环里替换 [占位]：
// cout << "[占位] 你输入了: " << line << "\n";
Lexer lex(line);
auto toks = lex.tokenize();
for (const auto& t : toks) { t.dump(cout); cout << " "; }
cout << "\n";

🧪 立刻编译运行（验证数字切分）

g++ -std=c++17 main.cpp lexer.cpp token.cpp -o mycc
./mycc

操作：

mycc> 42 3.14 100
Token(Number, 42) Token(Number, 3.14) Token(Number, 100) Token(&lt;EOF>)

✅ 三个数字 + EOF 哨兵 = 第一版词法跑通。注意整数 100 也切成了 double——这是为了简化 Value 表示（VM 只支持 double 一种数值类型，挑战题之一就是加 int 区分）。

# 3.4 第二版加运算符与空白

第一版只能切数字，连 1+2 都不能切——遇到 + 默默吞掉了。现在加三类字符的处理：

📁 lexer.cpp 改写 tokenize：

std::vector<Token> Lexer::tokenize() {
    std::vector<Token> out;
    while (!isAtEnd()) {
        char c = peek();

        // 1. 跳过空白
        if (c == ' ' || c == '\t' || c == '\r') { advance(); continue; }
        if (c == '\n') { line++; advance(); continue; }

        // 2. 跳过单行注释
        if (c == '/' && pos + 1 < src.size() && src[pos+1] == '/') {
            while (!isAtEnd() && peek() != '\n') advance();
            continue;
        }

        // 3. 数字
        if (std::isdigit(static_cast<unsigned char>(c))) {
            out.push_back(readNumber());
            continue;
        }

        // 4. 单字符运算符与分隔符（多字符运算符在 Step 4 处理）
        switch (c) {
            case '+': out.emplace_back(TokKind::Plus,  line); advance(); continue;
            case '-': out.emplace_back(TokKind::Minus, line); advance(); continue;
            case '*': out.emplace_back(TokKind::Star,  line); advance(); continue;
            case '/': out.emplace_back(TokKind::Slash, line); advance(); continue;
            case '%': out.emplace_back(TokKind::Percent,line);advance(); continue;
            case '(': out.emplace_back(TokKind::LParen,line); advance(); continue;
            case ')': out.emplace_back(TokKind::RParen,line); advance(); continue;
            case '{': out.emplace_back(TokKind::LBrace,line); advance(); continue;
            case '}': out.emplace_back(TokKind::RBrace,line); advance(); continue;
            case ';': out.emplace_back(TokKind::Semicolon,line);advance();continue;
            case ',': out.emplace_back(TokKind::Comma, line); advance(); continue;
        }

        // 暂时跳过其他字符（Step 3、4 才会真正处理）
        std::cerr << "[Lexer] 未知字符 '" << c << "' (line " << line << ")\n";
        advance();
    }
    out.emplace_back(TokKind::Eof, line);
    return out;
}

🧪 第二次编译运行

mycc> 1 + 2 * (3 - 4)
Token(Number, 1) Token(+) Token(Number, 2) Token(*) Token(()
Token(Number, 3) Token(-) Token(Number, 4) Token()) Token(&lt;EOF>)

✅ 运算符 + 空白 + 注释 = 算术表达式可以切了。还有 11 类 Token 没接——下一步就来。

# 3.5 第三版加标识符与关键字

📁 lexer.h 加私有方法：

private:
    Token readIdent();          // 阶段 ② Step 3

📁 lexer.cpp 在 tokenize 的 switch 之前加分支，并实现 readIdent：

// 在 switch (c) 之前加：
if (std::isalpha(static_cast<unsigned char>(c)) || c == '_') {
    out.push_back(readIdent());
    continue;
}

// 文件末尾追加：
Token Lexer::readIdent() {
    size_t start = pos;
    while (!isAtEnd() && (std::isalnum(static_cast<unsigned char>(peek())) || peek() == '_')) {
        advance();
    }
    std::string text = src.substr(start, pos - start);

    // ⭐ 关键字识别：只有这 9 个是关键字，其它都是 Ident
    static const std::unordered_map<std::string, TokKind> KEYWORDS = {
        {"var",   TokKind::Var},
        {"print", TokKind::Print},
        {"if",    TokKind::If},     {"else",  TokKind::Else},
        {"while", TokKind::While},
        {"fn",    TokKind::Fn},     {"return",TokKind::Return},
        {"true",  TokKind::True},   {"false", TokKind::False},
    };
    if (auto it = KEYWORDS.find(text); it != KEYWORDS.end()) {
        return Token(it->second, line);
    }
    return Token(TokKind::Ident, text, line);
}

⚠️ lexer.cpp 顶部加 #include <unordered_map>。

🆕 C++17 if-init 语句：if (auto it = m.find(k); it != m.end()) —— 在 if 里同时声明并使用 it，作用域只到 if/else 块结束。比 C++14 写法少一行变量泄漏到外层作用域。

🧪 第三次编译运行

mycc> var x = 42; print x;
Token(Var) Token(Ident, "x") Token(=) Token(Number, 42) Token(;)
Token(Print) Token(Ident, "x") Token(;) Token(&lt;EOF>)

✅ 关键字 vs 标识符正确分离：var、print 识别为关键字 Token，x 是标识符 Token。

⚠️ 你会注意到 = 还是 "未知字符"——下一步加多字符运算符就修复它。

# 3.6 第四版加字符串与多字符运算符

📁 lexer.h 加：

private:
    Token readString();

📁 lexer.cpp —— 改写"未知字符"那段为 =/!/</>/&/| 的多字符判断，并加字符串处理：

// 在 switch (c) 之前加（紧跟 readIdent 分支）：
if (c == '"') {
    out.push_back(readString());
    continue;
}

// 把 switch 内的 case '/' 单独处理（注释已经处理过了，这里只剩除号）
// 注意：原来 case '/' 直接产生 Slash 在前面注释判断后才会到这里，OK

// 在 switch (c) 后追加多字符运算符判断（替换原来的"未知字符"分支）：
auto matchTwoChar = [&](char first, char second, TokKind two, TokKind one) {
    advance();    // 吃掉 first
    if (peek() == second) { advance(); out.emplace_back(two, line); }
    else                  { out.emplace_back(one, line); }
};

if (c == '=') { matchTwoChar('=', '=', TokKind::Eq, TokKind::Assign); continue; }
if (c == '!') { matchTwoChar('!', '=', TokKind::Ne, TokKind::Bang);   continue; }
if (c == '<') { matchTwoChar('<', '=', TokKind::Le, TokKind::Lt);     continue; }
if (c == '>') { matchTwoChar('>', '=', TokKind::Ge, TokKind::Gt);     continue; }
if (c == '&') {
    advance();
    if (peek() == '&') { advance(); out.emplace_back(TokKind::AndAnd, line); }
    else std::cerr << "[Lexer] 单 & 不支持\n";
    continue;
}
if (c == '|') {
    advance();
    if (peek() == '|') { advance(); out.emplace_back(TokKind::OrOr, line); }
    else std::cerr << "[Lexer] 单 | 不支持\n";
    continue;
}

// 真正的"未知字符"兜底
std::cerr << "[Lexer] 未知字符 '" << c << "' (line " << line << ")\n";
advance();

📁 lexer.cpp 追加 readString：

Token Lexer::readString() {
    advance();    // 吃掉开头的 "
    std::string s;
    while (!isAtEnd() && peek() != '"') {
        if (peek() == '\n') line++;
        s.push_back(advance());
    }
    if (isAtEnd()) {
        std::cerr << "[Lexer] 字符串未关闭 (line " << line << ")\n";
    } else {
        advance();    // 吃掉结尾的 "
    }
    return Token(TokKind::String, s, line);
}

🧪 第四次编译运行（验证全部 16 类 Token）

mycc> if (a == 1 &amp;&amp; b != 2) { print "ok"; }
Token(If) Token(() Token(Ident, "a") Token(==) Token(Number, 1) Token(&amp;&amp;)
Token(Ident, "b") Token(!=) Token(Number, 2) Token()) Token({)
Token(Print) Token(String, "ok") Token(;) Token(}) Token(&lt;EOF>)

✅ 16 类 Token 全部识别正确 —— 词法分析器完成。

💡 状态机思维：你可能没意识到，刚刚写的就是一个确定性有限自动机（DFA）——主循环根据 peek() 的字符值跳到不同分支，每个分支内部再消耗若干字符并产出一个 Token。这就是所有词法分析器的底层模型。

┌─ 📌 阶段 ② 小结 ────────────────────────────────────┐
│  ✅ 你刚刚完成的事：                                            │
│    • Token 数据结构：variant 装 7 类载荷，type-safe              │
│    • Lexer 状态机：4 步迭代加上 16 类 Token                      │
│    • 关键字 vs 标识符：unordered_map 查表                         │
│    • 多字符运算符：if-init + lambda 抽象出 matchTwoChar          │
│    • 错误恢复：未知字符报错但继续，不中断词法                     │
│  📊 18 个文件已经填了 4 个：main + token.h/cpp + lexer.h/cpp      │
│  ⏸ 还没碰的（下阶段才会做）：                                    │
│    • Parser 把 Token 拼成树（阶段 ③④）                           │
│  📌 进入下阶段前务必：                                            │
│    git add . &amp;&amp; git commit -m "stage2: lexer with 16 tokens"     │
│  💡 本阶段最大领悟：                                              │
│    "variant 是 enum + union 的现代替代——类型安全 + 模式分派"    │
└──────────────────────────────────────────────────┘

# 04.AST 抽象语法树

┌─ 🎯 阶段 ③ 目标 ────────────────────────────────────┐
│ 完成什么：定义 AstNode 抽象基类 + 12 个派生类               │
│ 不做什么：不写 Parser 怎么构造它们——这阶段只定数据结构      │
│ 验收标准：能手动 new 一棵 1+2 的 AST 树并打印               │
│ 预计耗时：2 小时                                            │
│ 关键思路：所有语言构造都是 AstNode 的派生类——这是 OOP 多态  │
│           在编译器领域的最大舞台                             │
└──────────────────────────────────────────────────┘

# 4.1 灵魂三问：AST 到底是什么

❓ Token 流不是已经表达了源码吗？为什么还要 AST？

来看 1 + 2 * 3：

Token 流：[1] [+] [2] [*] [3]      ← 扁平、不知道优先级
AST 树：       +
              / \
             1   *
                / \
               2   3              ← 树形、优先级体现在结构

问题暴露：Token 流是字符的"分组"，但没有体现"乘法优先于加法"——Parser 的核心使命就是把扁平 Token 流升维成体现优先级和结合性的树。

❓ 为什么用抽象基类 + 派生类，不用一个大 struct + enum 区分？

// ❌ 大 struct 反例
struct Node {
    enum Kind { NUM, BIN, IF, FN, ... } kind;
    double n;            // 只 NUM 用
    Node* lhs;           // 只 BIN/IF 用
    Node* rhs;
    Node* cond;          // 只 IF 用
    string name;         // 只 IF/FN 用
    vector<Node*> body;  // 只 FN/IF 用
    // ...
};

致命问题：

字段稀疏——一个 NumLit 节点要带一堆永远用不到的字段
后续访问代码到处是 if (n.kind == NUM) ... else if (...)——开闭原则全无
加新节点类型要改这个 struct 的所有访问代码

✅ 正确做法：抽象基类 + 派生类——每种节点是独立的 class，每个节点只有自己需要的字段。访问通过虚函数 + 访问者模式完成。

❓ 第一步做什么？ 答：先定义 AstNode 基类 + NumLit 一个最简单的派生类——跑通"基类指针指向派生类对象"的多态链路，再扩展。

# 4.2 AstNode 抽象基类

📁 ast.h（这个文件不分 .cpp，因为节点都是 POD-ish 数据类，行为放访问者里）：

#pragma once
#include "token.h"
#include <memory>
#include <string>
#include <vector>

// 类型标签——TypeChecker 阶段会给每个表达式贴上
enum class Type { Unknown, Num, Bool, Str, Void };

// 前置声明 Visitor（阶段 ⑤ 才定义具体接口）
template <typename R> class AstVisitor;

// 所有节点的公共基类
class AstNode {
public:
    int line = 1;                       // 出错时用
    Type ty  = Type::Unknown;           // TypeChecker 标注

    AstNode() = default;
    explicit AstNode(int ln) : line(ln) {}
    virtual ~AstNode() = default;

    // ⭐ 双访问者接口：一个返回 Type、一个返回 void——分别给 TypeChecker、Codegen 用
    virtual Type acceptType(AstVisitor<Type>& v) = 0;
    virtual void acceptCode(AstVisitor<void>& v) = 0;
};

using AstPtr = std::shared_ptr<AstNode>;

📚 设计要点：

要点	写法	作用
`virtual ~AstNode() = default`	虚析构	`shared_ptr<AstNode>` 释放时正确析构子类
公共字段 `line` / `ty`	提前放基类	避免 12 个派生类都重复定义
两个 accept 函数	模板 visitor 双特化	一个返回 Type 给 checker，一个返回 void 给 codegen
`using AstPtr = shared_ptr<AstNode>`	类型别名	后面写 AST 子节点全用这个，不写裸长名

🆕 C++14 模板别名：using 比 typedef 更现代——尤其在写带模板参数的别名时一目了然。

🔑 为什么 AST 用 shared_ptr 不用 unique_ptr？

这是本案例的争议设计点之一。unique_ptr 更安全（独占语义、移动转移、无引用计数开销），shared_ptr 更便利（可以多个 visitor 同时持有节点指针、无需考虑 move 语义）。

我们选 shared_ptr 是因为新手友好——卷一第 12 章读者还不熟悉 move 语义。代价是树上有引用计数开销（每个节点 +16 字节左右）。挑战 C 是改造为 unique_ptr。

# 4.3 表达式节点四件套

继续在 ast.h 里追加派生类。表达式有 4 种：数字字面量、字符串字面量、变量引用、二元运算。

// === 表达式节点 ===

class NumLit : public AstNode {
public:
    double value;
    NumLit(double v, int ln) : AstNode(ln), value(v) {}

    Type acceptType(AstVisitor<Type>& v) override;
    void acceptCode(AstVisitor<void>& v) override;
};

class StrLit : public AstNode {
public:
    std::string value;
    StrLit(std::string s, int ln) : AstNode(ln), value(std::move(s)) {}

    Type acceptType(AstVisitor<Type>& v) override;
    void acceptCode(AstVisitor<void>& v) override;
};

class BoolLit : public AstNode {
public:
    bool value;
    BoolLit(bool b, int ln) : AstNode(ln), value(b) {}

    Type acceptType(AstVisitor<Type>& v) override;
    void acceptCode(AstVisitor<void>& v) override;
};

class VarRef : public AstNode {
public:
    std::string name;
    VarRef(std::string n, int ln) : AstNode(ln), name(std::move(n)) {}

    Type acceptType(AstVisitor<Type>& v) override;
    void acceptCode(AstVisitor<void>& v) override;
};

class BinOp : public AstNode {
public:
    TokKind op;             // +, -, *, /, %, ==, !=, <, <=, >, >=, &&, ||
    AstPtr  lhs, rhs;
    BinOp(TokKind o, AstPtr l, AstPtr r, int ln)
        : AstNode(ln), op(o), lhs(std::move(l)), rhs(std::move(r)) {}

    Type acceptType(AstVisitor<Type>& v) override;
    void acceptCode(AstVisitor<void>& v) override;
};

class UnaryOp : public AstNode {
public:
    TokKind op;             // -（取负）, !（逻辑非）
    AstPtr  operand;
    UnaryOp(TokKind o, AstPtr e, int ln)
        : AstNode(ln), op(o), operand(std::move(e)) {}

    Type acceptType(AstVisitor<Type>& v) override;
    void acceptCode(AstVisitor<void>& v) override;
};

class Assign : public AstNode {
public:
    std::string name;       // 只支持 var = expr 形式
    AstPtr      value;
    Assign(std::string n, AstPtr v, int ln)
        : AstNode(ln), name(std::move(n)), value(std::move(v)) {}

    Type acceptType(AstVisitor<Type>& v) override;
    void acceptCode(AstVisitor<void>& v) override;
};

class CallExpr : public AstNode {
public:
    std::string             callee;
    std::vector<AstPtr>     args;
    CallExpr(std::string c, std::vector<AstPtr> a, int ln)
        : AstNode(ln), callee(std::move(c)), args(std::move(a)) {}

    Type acceptType(AstVisitor<Type>& v) override;
    void acceptCode(AstVisitor<void>& v) override;
};

# 4.4 语句节点八件套

继续追加：

// === 语句节点 ===

class VarDecl : public AstNode {
public:
    std::string name;
    AstPtr      init;
    VarDecl(std::string n, AstPtr i, int ln)
        : AstNode(ln), name(std::move(n)), init(std::move(i)) {}

    Type acceptType(AstVisitor<Type>& v) override;
    void acceptCode(AstVisitor<void>& v) override;
};

class PrintStmt : public AstNode {
public:
    AstPtr expr;
    PrintStmt(AstPtr e, int ln) : AstNode(ln), expr(std::move(e)) {}

    Type acceptType(AstVisitor<Type>& v) override;
    void acceptCode(AstVisitor<void>& v) override;
};

class ExprStmt : public AstNode {        // 单纯的表达式语句：foo(); x = 1;
public:
    AstPtr expr;
    ExprStmt(AstPtr e, int ln) : AstNode(ln), expr(std::move(e)) {}

    Type acceptType(AstVisitor<Type>& v) override;
    void acceptCode(AstVisitor<void>& v) override;
};

class Block : public AstNode {           // 大括号包起来的语句块
public:
    std::vector<AstPtr> stmts;
    Block(std::vector<AstPtr> s, int ln) : AstNode(ln), stmts(std::move(s)) {}

    Type acceptType(AstVisitor<Type>& v) override;
    void acceptCode(AstVisitor<void>& v) override;
};

class IfStmt : public AstNode {
public:
    AstPtr cond, thenBranch, elseBranch;     // elseBranch 可为 nullptr
    IfStmt(AstPtr c, AstPtr t, AstPtr e, int ln)
        : AstNode(ln), cond(std::move(c)),
          thenBranch(std::move(t)), elseBranch(std::move(e)) {}

    Type acceptType(AstVisitor<Type>& v) override;
    void acceptCode(AstVisitor<void>& v) override;
};

class WhileStmt : public AstNode {
public:
    AstPtr cond, body;
    WhileStmt(AstPtr c, AstPtr b, int ln)
        : AstNode(ln), cond(std::move(c)), body(std::move(b)) {}

    Type acceptType(AstVisitor<Type>& v) override;
    void acceptCode(AstVisitor<void>& v) override;
};

class FnDecl : public AstNode {
public:
    std::string                 name;
    std::vector<std::string>    params;
    AstPtr                      body;        // 必为 Block
    FnDecl(std::string n, std::vector<std::string> p, AstPtr b, int ln)
        : AstNode(ln), name(std::move(n)),
          params(std::move(p)), body(std::move(b)) {}

    Type acceptType(AstVisitor<Type>& v) override;
    void acceptCode(AstVisitor<void>& v) override;
};

class ReturnStmt : public AstNode {
public:
    AstPtr value;        // 可为 nullptr
    ReturnStmt(AstPtr v, int ln) : AstNode(ln), value(std::move(v)) {}

    Type acceptType(AstVisitor<Type>& v) override;
    void acceptCode(AstVisitor<void>& v) override;
};

// 顶层程序：一组语句和函数声明
class Program : public AstNode {
public:
    std::vector<AstPtr> decls;
    Program(std::vector<AstPtr> d, int ln) : AstNode(ln), decls(std::move(d)) {}

    Type acceptType(AstVisitor<Type>& v) override;
    void acceptCode(AstVisitor<void>& v) override;
};

🔑 节点设计的口诀：每种语法结构对应一个类，类的字段就是该结构的"信息"。比如：

语法	类	字段
`if (cond) then else else`	`IfStmt`	cond / thenBranch / elseBranch
`while (cond) body`	`WhileStmt`	cond / body
`fn foo(a, b) { ... }`	`FnDecl`	name / params / body
`a + b`	`BinOp`	op / lhs / rhs

没有冗余字段、没有 enum 分支判断——这是 OOP 多态和"贫血结构"的最佳结合。

⚠️ 现在 ast.h 里所有 acceptType / acceptCode 都是声明——它们要等 §06 Visitor 接口定义后才能在哪里实现？答：就放在 ast.h 末尾。我们用一个小技巧：

📁 ast.h 末尾追加（先注释掉，§06 才取消注释——现在写一个标记提醒自己）：

// ⏳ 占位：accept 函数的实现要等 visitor.h 定义出 AstVisitor 接口后才能填
// （阶段 ⑤ §6.2 末尾会回到这里把 14 个 accept 实现一次性给出）

🧪 立刻编译验证（手动构造一棵小树）

修改 main.cpp，临时加测试代码：

#include "ast.h"

// 在 main 最开头加：
auto e1 = std::make_shared<NumLit>(1, 1);
auto e2 = std::make_shared<NumLit>(2, 1);
auto add = std::make_shared<BinOp>(TokKind::Plus, e1, e2, 1);

cout << "[Test] 节点类型 = " << typeid(*add).name() << "\n";
cout << "[Test] op = " << tokKindName(add->op) << "\n";
cout << "[Test] lhs.value = " << std::dynamic_pointer_cast<NumLit>(add->lhs)->value << "\n";
return 0;

编译时先把 ast.h 末尾的 accept 声明改成 = 0 删掉——因为现在还没实现：

// 改 ast.h 中所有 acceptType/acceptCode 声明，先临时注释掉这两个虚函数
// virtual Type acceptType(AstVisitor<Type>& v) = 0;
// virtual void acceptCode(AstVisitor<void>& v) = 0;

⚠️ 不要恐慌——这只是为了通过这个临时编译验证。§06 一开始我们会把它们恢复并填上实现。

g++ -std=c++17 main.cpp lexer.cpp token.cpp -o mycc
./mycc

预期输出：

[Test] 节点类型 = N5BinOpE      （或类似的 mangled name）
[Test] op = +
[Test] lhs.value = 1

✅ 手动构造的 AST 树形结构正确 —— 阶段 ③ 完成。立即把 main.cpp 测试代码删掉，把 ast.h 的两个 virtual 声明恢复。

┌─ 📌 阶段 ③ 小结 ────────────────────────────────────┐
│  ✅ 你刚刚完成的事：                                            │
│    • AstNode 抽象基类 + 双访问者接口 + 虚析构                    │
│    • 12 个派生类（4 表达式 + 8 语句节点）                        │
│    • 每个类的字段 = 该语法结构的"必需信息"，无冗余                │
│    • shared_ptr&lt;AstNode> 的所有权设计                            │
│  ⏸ 还没碰的（下阶段才会做）：                                    │
│    • Parser 怎么构造 AST（阶段 ④）                               │
│    • Visitor 怎么访问 AST（阶段 ⑤）                              │
│  📌 进入下阶段前务必：                                            │
│    git add . &amp;&amp; git commit -m "stage3: ast 12 nodes"             │
│  💡 本阶段最大领悟：                                              │
│    "OOP 多态在编译器里的真正舞台——每种语言构造一个类"           │
└──────────────────────────────────────────────────┘

# 05.Parser 递归下降

┌─ 🎯 阶段 ④ 目标 ────────────────────────────────────┐
│ 完成什么：让 Parser 把 Token 流变成 AST 树                  │
│ 不做什么：不做语义检查（变量未定义、参数个数错都不查）        │
│ 验收标准：能解析 fib.mycc 全部语法 + 打印 AST 树形结构       │
│ 预计耗时：4 小时                                            │
│ 关键思路：递归下降 = 文法规则 → 函数。每个函数解析一种结构   │
│           先做表达式（最难）→ 再做语句（简单）              │
└──────────────────────────────────────────────────┘

# 5.1 灵魂三问：为什么递归下降

❓ 解析方法有哪些选择？

方法	优点	缺点	工业界
递归下降（Recursive Descent）	手写、可调试、错误信息友好	无法处理左递归	gcc / clang / V8 / Lua
LL(1) 表驱动	自动生成	调试困难	yacc 时代
LR / LALR	表达力最强	实现复杂	bison / GNU
PEG / Pratt parsing	优先级清晰	概念稍新	TypeScript / Crystal

✅ 本案例选递归下降 + Pratt 风格优先级处理——也是所有现代手写 Parser 的标配。原因：

每个文法规则就是一个函数——可读性极佳
错误恢复容易：跳过到下一个 ; 即可
不依赖第三方工具——纯 C++，编译就跑

❓ 左递归是什么、为什么递归下降处理不了？

考虑文法 expr → expr "+" term | term，写成函数：

AstPtr parseExpr() {
    auto lhs = parseExpr();        // ⚠️ 无限递归！永远进不到 term
    expect("+");
    auto rhs = parseTerm();
    return makeBinOp(lhs, rhs);
}

修复办法：把左递归改写成迭代：

AstPtr parseExpr() {
    auto lhs = parseTerm();        // ⭐ 先解析最小单元
    while (peek("+")) {
        consume("+");
        auto rhs = parseTerm();
        lhs = makeBinOp(lhs, rhs);
    }
    return lhs;
}

🔑 这是本案例 §5.4 的核心技巧——循环代替左递归。

❓ 第一步做什么？ 答：只解析整数（最简单的"表达式" = 单一 NumLit）——把"消耗 Token + 产出节点"这条管道跑通。

# 5.2 Parser 类骨架

📁 parser.h（第一版，只有最骨架的接口）：

#pragma once
#include "ast.h"
#include "token.h"
#include <vector>

class Parser {
public:
    explicit Parser(std::vector<Token> tokens) : toks(std::move(tokens)) {}

    AstPtr parseProgram();      // 主入口：解析整个文件

private:
    std::vector<Token> toks;
    size_t             pos = 0;

    // 工具
    const Token& peek() const { return toks[pos]; }
    const Token& advance()    { return toks[pos++]; }
    bool         check(TokKind k) const { return peek().kind == k; }
    bool         match(TokKind k) {
        if (check(k)) { advance(); return true; }
        return false;
    }
    const Token& expect(TokKind k, const char* what);

    // 表达式（按优先级分层，§5.3-5.5 逐个填）
    AstPtr parseExpression();   // 最低优先级入口
    AstPtr parseAssignment();   // 等号赋值（右结合）
    AstPtr parseLogicOr();      // ||
    AstPtr parseLogicAnd();     // &&
    AstPtr parseEquality();     // == !=
    AstPtr parseComparison();   // < <= > >=
    AstPtr parseAddition();     // + -
    AstPtr parseMultiplication();  // * / %
    AstPtr parseUnary();        // - !
    AstPtr parseCall();         // 函数调用 后缀
    AstPtr parsePrimary();      // 字面量/变量/括号

    // 语句（§5.7 之后填）
    AstPtr parseStatement();
    AstPtr parseVarDecl();
    AstPtr parsePrintStmt();
    AstPtr parseIfStmt();
    AstPtr parseWhileStmt();
    AstPtr parseBlock();
    AstPtr parseReturnStmt();
    AstPtr parseFnDecl();
    AstPtr parseExprStmt();
};

⚠️ 看到这堆函数声明先别慌——它们对应 13 个文法规则，我们会按"先简后难"的顺序一个一个实现，每个不超过 20 行。

📁 parser.cpp 第一版（先只实现 expect + parseProgram + parsePrimary）：

#include "parser.h"
#include <iostream>
#include <stdexcept>

const Token& Parser::expect(TokKind k, const char* what) {
    if (!check(k)) {
        std::cerr << "[Parser] 期望 " << what << "，实际是 "
                  << tokKindName(peek().kind)
                  << " (line " << peek().line << ")\n";
        throw std::runtime_error("parse error");
    }
    return advance();
}

AstPtr Parser::parseProgram() {
    std::vector<AstPtr> decls;
    int firstLine = peek().line;
    while (!check(TokKind::Eof)) {
        // 临时第一版：只解析 print expr;
        // 等 §5.7 写完会换成 parseStatement()
        decls.push_back(parsePrimary());
        match(TokKind::Semicolon);
    }
    return std::make_shared<Program>(std::move(decls), firstLine);
}

AstPtr Parser::parsePrimary() {
    const Token& t = peek();
    if (t.kind == TokKind::Number) {
        advance();
        return std::make_shared<NumLit>(std::get<double>(t.value), t.line);
    }
    if (t.kind == TokKind::String) {
        advance();
        return std::make_shared<StrLit>(std::get<std::string>(t.value), t.line);
    }
    if (t.kind == TokKind::True)  { advance(); return std::make_shared<BoolLit>(true,  t.line); }
    if (t.kind == TokKind::False) { advance(); return std::make_shared<BoolLit>(false, t.line); }
    if (t.kind == TokKind::Ident) {
        advance();
        return std::make_shared<VarRef>(std::get<std::string>(t.value), t.line);
    }
    std::cerr << "[Parser] 期望表达式，实际是 " << tokKindName(t.kind)
              << " (line " << t.line << ")\n";
    throw std::runtime_error("parse error");
}

// 阶段 ⑤ 起其它 parse* 才会被实现，这里给最低层留空（编译需要）
AstPtr Parser::parseExpression()    { return parsePrimary(); }
AstPtr Parser::parseAssignment()    { return parsePrimary(); }
AstPtr Parser::parseLogicOr()       { return parsePrimary(); }
AstPtr Parser::parseLogicAnd()      { return parsePrimary(); }
AstPtr Parser::parseEquality()      { return parsePrimary(); }
AstPtr Parser::parseComparison()    { return parsePrimary(); }
AstPtr Parser::parseAddition()      { return parsePrimary(); }
AstPtr Parser::parseMultiplication(){ return parsePrimary(); }
AstPtr Parser::parseUnary()         { return parsePrimary(); }
AstPtr Parser::parseCall()          { return parsePrimary(); }
AstPtr Parser::parseStatement()     { return parsePrimary(); }
AstPtr Parser::parseVarDecl()       { return parsePrimary(); }
AstPtr Parser::parsePrintStmt()     { return parsePrimary(); }
AstPtr Parser::parseIfStmt()        { return parsePrimary(); }
AstPtr Parser::parseWhileStmt()     { return parsePrimary(); }
AstPtr Parser::parseBlock()         { return parsePrimary(); }
AstPtr Parser::parseReturnStmt()    { return parsePrimary(); }
AstPtr Parser::parseFnDecl()        { return parsePrimary(); }
AstPtr Parser::parseExprStmt()      { return parsePrimary(); }

💡 教学策略：先把所有 parse* 函数声明完，但只实现 parsePrimary 一个——其他全部 stub 成 return parsePrimary()。让程序先编译过，再逐个替换实现。这是大工程项目的标准开发节奏。

# 5.3 第一版只解析整数表达式

📁 main.cpp 在 Lexer 之后加 Parser 调用：

#include "parser.h"      // 加这一行

// 替换原来打印 Token 的代码：
Lexer lex(line);
auto toks = lex.tokenize();
try {
    Parser parser(std::move(toks));
    auto prog = parser.parseProgram();
    cout << "[Parse] OK，顶层节点数=" << std::dynamic_pointer_cast<Program>(prog)->decls.size() << "\n";
} catch (const std::exception& e) {
    cout << "[Parse] 失败: " << e.what() << "\n";
}

🧪 立刻编译运行（验证 parsePrimary 跑通）

g++ -std=c++17 main.cpp lexer.cpp token.cpp parser.cpp -o mycc
./mycc

操作：

mycc> 42
[Parse] OK，顶层节点数=1
mycc> 1 2 3
[Parse] OK，顶层节点数=3
mycc> "hello"
[Parse] OK，顶层节点数=1
mycc> +     ← 试试错误输入
[Parser] 期望表达式，实际是 + (line 1)
[Parse] 失败: parse error

✅ parsePrimary 跑通 + 错误信息友好。但你输入 1 + 2 会怎样？

mycc> 1 + 2
[Parse] OK，顶层节点数=3       ← 错的！它把 1 / + / 2 当成三个独立 primary

正是因为 parseAddition 还是 stub——下一步就修复它。

# 5.4 第二版加加减运算

🛠 从优先级最低的入口往下铺：parseProgram → parseStatement → parseExpression → ... → parseAddition → parseMultiplication → parseUnary → parsePrimary。

但本节我们暂时让 parseExpression 直接调 parseAddition——跳过中间几层（赋值/逻辑/比较），下面三节再补回来：

📁 parser.cpp 修改 parseExpression 和 parseAddition：

AstPtr Parser::parseExpression() {
    return parseAddition();          // 暂时跳过更高优先级层（§5.5 起补）
}

AstPtr Parser::parseAddition() {
    auto lhs = parseMultiplication();              // ⭐ 先解析左操作数
    while (check(TokKind::Plus) || check(TokKind::Minus)) {
        TokKind op = advance().kind;               // 消耗 + 或 -
        auto rhs = parseMultiplication();
        lhs = std::make_shared<BinOp>(op, lhs, rhs, lhs->line);   // ⭐ 左结合
    }
    return lhs;
}

// parseMultiplication 暂时还是 stub——但 parsePrimary 直接读数字，先够用

📁 parseProgram 修改——把 parsePrimary 换成 parseExpression：

AstPtr Parser::parseProgram() {
    std::vector<AstPtr> decls;
    int firstLine = peek().line;
    while (!check(TokKind::Eof)) {
        decls.push_back(parseExpression());        // ⭐ 改这里
        match(TokKind::Semicolon);
    }
    return std::make_shared<Program>(std::move(decls), firstLine);
}

🧪 第二次编译运行

mycc> 1 + 2 + 3
[Parse] OK，顶层节点数=1        ← 现在 1+2+3 是一个 BinOp 树，对了
mycc> 1 - 2 + 3
[Parse] OK，顶层节点数=1

但你还是看不到树形结构对不对——下一节我们加一个简易的 AST 打印工具。

# 5.5 第三版加乘除与括号

📁 parser.cpp 实现 parseMultiplication 和升级 parsePrimary（加括号支持）：

AstPtr Parser::parseMultiplication() {
    auto lhs = parseUnary();
    while (check(TokKind::Star) || check(TokKind::Slash) || check(TokKind::Percent)) {
        TokKind op = advance().kind;
        auto rhs = parseUnary();
        lhs = std::make_shared<BinOp>(op, lhs, rhs, lhs->line);
    }
    return lhs;
}

AstPtr Parser::parseUnary() {
    if (check(TokKind::Minus) || check(TokKind::Bang)) {
        TokKind op = advance().kind;
        auto operand = parseUnary();             // ⭐ 右结合：--x 合法
        return std::make_shared<UnaryOp>(op, operand, operand->line);
    }
    return parseCall();
}

AstPtr Parser::parseCall() {
    auto expr = parsePrimary();
    // 函数调用：foo(a, b)——若 primary 后面紧跟 '(' 就是调用
    if (auto v = std::dynamic_pointer_cast<VarRef>(expr); v && check(TokKind::LParen)) {
        advance();      // 吃 (
        std::vector<AstPtr> args;
        if (!check(TokKind::RParen)) {
            args.push_back(parseExpression());
            while (match(TokKind::Comma)) args.push_back(parseExpression());
        }
        expect(TokKind::RParen, ")");
        return std::make_shared<CallExpr>(v->name, std::move(args), v->line);
    }
    return expr;
}

升级 parsePrimary 加括号支持：

AstPtr Parser::parsePrimary() {
    const Token& t = peek();
    if (t.kind == TokKind::Number) { /* ... 不变 ... */ }
    // ... 其它字面量、Ident 不变 ...

    // ⭐ 新增：括号包起来的子表达式
    if (t.kind == TokKind::LParen) {
        advance();
        auto inner = parseExpression();
        expect(TokKind::RParen, ")");
        return inner;
    }
    // ... 错误兜底不变 ...
}

🧪 第三次编译运行（验证算术优先级）

为了能直观看到 AST 结构，临时加一个简易打印——在 main.cpp 里直接 dynamic_cast 打印：

// 在 [Parse] OK 之后加：
std::function<void(const AstPtr&, int)> dump =
    [&](const AstPtr& n, int depth) {
        std::string ind(depth * 2, ' ');
        if (auto p = std::dynamic_pointer_cast<NumLit>(n))
            cout << ind << "NumLit " << p->value << "\n";
        else if (auto p = std::dynamic_pointer_cast<BinOp>(n)) {
            cout << ind << "BinOp " << tokKindName(p->op) << "\n";
            dump(p->lhs, depth + 1);
            dump(p->rhs, depth + 1);
        }
        else if (auto p = std::dynamic_pointer_cast<UnaryOp>(n)) {
            cout << ind << "UnaryOp " << tokKindName(p->op) << "\n";
            dump(p->operand, depth + 1);
        }
        else if (auto p = std::dynamic_pointer_cast<Program>(n)) {
            cout << ind << "Program\n";
            for (auto& d : p->decls) dump(d, depth + 1);
        }
        else cout << ind << "?\n";
    };
dump(prog, 0);

⚠️ main.cpp 顶部加 #include <functional>。

操作：

mycc> 1 + 2 * 3
Program
  BinOp +
    NumLit 1
    BinOp *
      NumLit 2
      NumLit 3

🎉 优先级正确——* 在 AST 树里更深一层，意味着先算。这就是"优先级体现在树形结构"的可视化证据。

mycc> (1 + 2) * 3
Program
  BinOp *
    BinOp +
      NumLit 1
      NumLit 2
    NumLit 3

✅ 括号也工作正常——+ 跑到了 * 下面（先算）。

# 5.6 故意造 bug：左结合错误

🚨 本案例最经典的教学高峰。1 - 2 - 3 数学上等于 (1-2)-3 = -4——左结合。我们故意把 parseAddition 改成右结合看看：

// ❌ 错误版——故意右结合
AstPtr Parser::parseAddition() {
    auto lhs = parseMultiplication();
    if (check(TokKind::Plus) || check(TokKind::Minus)) {
        TokKind op = advance().kind;
        auto rhs = parseAddition();              // ⚠️ 递归调自己 = 右结合
        return std::make_shared<BinOp>(op, lhs, rhs, lhs->line);
    }
    return lhs;
}

🧪 重新编译运行：

mycc> 1 - 2 - 3
Program
  BinOp -
    NumLit 1
    BinOp -                  ← 右子树带了第二个 -
      NumLit 2
      NumLit 3                ← 这棵树会算成 1 - (2 - 3) = 2，但数学上应该是 -4！

🚨 数学结果会变——你写错一个 while/if，整门语言的算术就错了。这是真实编译器开发中的"最危险陷阱"——单元测试少了一行，整个项目可能产出错误代码。

🛠 修复：把 if 改回 while、把递归调用改回调更高优先级层：

// ✅ 正确版（恢复 5.4 的写法）
AstPtr Parser::parseAddition() {
    auto lhs = parseMultiplication();
    while (check(TokKind::Plus) || check(TokKind::Minus)) {
        TokKind op = advance().kind;
        auto rhs = parseMultiplication();        // ⭐ 调高优先级层、不调自己
        lhs = std::make_shared<BinOp>(op, lhs, rhs, lhs->line);
    }
    return lhs;
}

再跑：

mycc> 1 - 2 - 3
Program
  BinOp -
    BinOp -                  ← 左子树带了第一个 -
      NumLit 1
      NumLit 2
    NumLit 3

✅ 左结合正确 = (1-2)-3 —— 数学语义恢复。

💡 教学要点：把"left-associative ⇔ while + 高优先级层调用"刻进脑子——这是手写 Parser 最重要的技巧。

# 5.7 加语句：var / print / if / while

到这里表达式已经 95% 完成（赋值/逻辑/比较还需要补，但思路完全相同——下面一并加）。现在加语句层：

📁 parser.cpp 升级 parseExpression / parseAssignment / parseLogicOr / parseLogicAnd / parseEquality / parseComparison：

AstPtr Parser::parseExpression()    { return parseAssignment(); }

AstPtr Parser::parseAssignment() {
    auto lhs = parseLogicOr();
    if (check(TokKind::Assign)) {
        advance();
        auto rhs = parseAssignment();        // ⭐ 右结合：a = b = 1 合法
        if (auto v = std::dynamic_pointer_cast<VarRef>(lhs)) {
            return std::make_shared<Assign>(v->name, rhs, lhs->line);
        }
        std::cerr << "[Parser] 赋值左侧必须是变量\n";
        throw std::runtime_error("parse error");
    }
    return lhs;
}

AstPtr Parser::parseLogicOr() {
    auto lhs = parseLogicAnd();
    while (check(TokKind::OrOr)) {
        advance();
        auto rhs = parseLogicAnd();
        lhs = std::make_shared<BinOp>(TokKind::OrOr, lhs, rhs, lhs->line);
    }
    return lhs;
}

AstPtr Parser::parseLogicAnd() {
    auto lhs = parseEquality();
    while (check(TokKind::AndAnd)) {
        advance();
        auto rhs = parseEquality();
        lhs = std::make_shared<BinOp>(TokKind::AndAnd, lhs, rhs, lhs->line);
    }
    return lhs;
}

AstPtr Parser::parseEquality() {
    auto lhs = parseComparison();
    while (check(TokKind::Eq) || check(TokKind::Ne)) {
        TokKind op = advance().kind;
        auto rhs = parseComparison();
        lhs = std::make_shared<BinOp>(op, lhs, rhs, lhs->line);
    }
    return lhs;
}

AstPtr Parser::parseComparison() {
    auto lhs = parseAddition();
    while (check(TokKind::Lt) || check(TokKind::Le) || check(TokKind::Gt) || check(TokKind::Ge)) {
        TokKind op = advance().kind;
        auto rhs = parseAddition();
        lhs = std::make_shared<BinOp>(op, lhs, rhs, lhs->line);
    }
    return lhs;
}

📁 parser.cpp 实现语句层：

AstPtr Parser::parseStatement() {
    if (check(TokKind::Var))    return parseVarDecl();
    if (check(TokKind::Print))  return parsePrintStmt();
    if (check(TokKind::If))     return parseIfStmt();
    if (check(TokKind::While))  return parseWhileStmt();
    if (check(TokKind::Return)) return parseReturnStmt();
    if (check(TokKind::LBrace)) return parseBlock();
    if (check(TokKind::Fn))     return parseFnDecl();
    return parseExprStmt();
}

AstPtr Parser::parseVarDecl() {
    int ln = advance().line;             // 吃 var
    const auto& nameTok = expect(TokKind::Ident, "变量名");
    AstPtr init = nullptr;
    if (match(TokKind::Assign)) init = parseExpression();
    expect(TokKind::Semicolon, ";");
    return std::make_shared<VarDecl>(std::get<std::string>(nameTok.value), init, ln);
}

AstPtr Parser::parsePrintStmt() {
    int ln = advance().line;             // 吃 print
    auto e = parseExpression();
    expect(TokKind::Semicolon, ";");
    return std::make_shared<PrintStmt>(e, ln);
}

AstPtr Parser::parseIfStmt() {
    int ln = advance().line;             // 吃 if
    expect(TokKind::LParen, "(");
    auto cond = parseExpression();
    expect(TokKind::RParen, ")");
    auto thenBranch = parseStatement();
    AstPtr elseBranch = nullptr;
    if (match(TokKind::Else)) elseBranch = parseStatement();
    return std::make_shared<IfStmt>(cond, thenBranch, elseBranch, ln);
}

AstPtr Parser::parseWhileStmt() {
    int ln = advance().line;             // 吃 while
    expect(TokKind::LParen, "(");
    auto cond = parseExpression();
    expect(TokKind::RParen, ")");
    auto body = parseStatement();
    return std::make_shared<WhileStmt>(cond, body, ln);
}

AstPtr Parser::parseBlock() {
    int ln = advance().line;             // 吃 {
    std::vector<AstPtr> stmts;
    while (!check(TokKind::RBrace) && !check(TokKind::Eof)) {
        stmts.push_back(parseStatement());
    }
    expect(TokKind::RBrace, "}");
    return std::make_shared<Block>(std::move(stmts), ln);
}

AstPtr Parser::parseReturnStmt() {
    int ln = advance().line;             // 吃 return
    AstPtr v = nullptr;
    if (!check(TokKind::Semicolon)) v = parseExpression();
    expect(TokKind::Semicolon, ";");
    return std::make_shared<ReturnStmt>(v, ln);
}

AstPtr Parser::parseExprStmt() {
    auto e = parseExpression();
    expect(TokKind::Semicolon, ";");
    return std::make_shared<ExprStmt>(e, e->line);
}

# 5.8 加函数定义与调用

最后一块拼图：函数定义。函数调用 foo(a, b) 在 §5.5 parseCall 已经完成。

📁 parser.cpp 实现 parseFnDecl：

AstPtr Parser::parseFnDecl() {
    int ln = advance().line;             // 吃 fn
    const auto& nameTok = expect(TokKind::Ident, "函数名");
    expect(TokKind::LParen, "(");

    std::vector<std::string> params;
    if (!check(TokKind::RParen)) {
        params.push_back(std::get<std::string>(expect(TokKind::Ident, "参数名").value));
        while (match(TokKind::Comma)) {
            params.push_back(std::get<std::string>(expect(TokKind::Ident, "参数名").value));
        }
    }
    expect(TokKind::RParen, ")");
    auto body = parseBlock();
    return std::make_shared<FnDecl>(std::get<std::string>(nameTok.value),
                                    std::move(params), body, ln);
}

📁 修改 parseProgram——把临时的 parsePrimary 调用换成 parseStatement：

AstPtr Parser::parseProgram() {
    std::vector<AstPtr> decls;
    int firstLine = check(TokKind::Eof) ? 1 : peek().line;
    while (!check(TokKind::Eof)) {
        decls.push_back(parseStatement());        // ⭐ 改成 parseStatement
        // 不再 match(Semicolon)——每个具体 stmt 自己处理
    }
    return std::make_shared<Program>(std::move(decls), firstLine);
}

🧪 第六次编译运行（端到端解析 fib.mycc）

先创建示例文件：

📁 examples/fib.mycc：

fn fib(n) {
    if (n < 2) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

var i = 0;
while (i < 10) {
    print fib(i);
    i = i + 1;
}

为了让 REPL 也能解析多行程序，临时让用户在一行内输入完整源码（接文件模式留到 §09）。先用一段简单测试：

mycc> var x = 1 + 2; print x;
[Parse] OK，顶层节点数=2
Program
  VarDecl x
    BinOp +
      NumLit 1
      NumLit 2
  PrintStmt
    VarRef x

⚠️ 你需要扩展 main.cpp 的临时 dump 函数，多加几个 dynamic_cast 分支（VarDecl / PrintStmt / VarRef / IfStmt / WhileStmt / FnDecl 等）—— 这是教学的 "你能补全吗" 小练习，每加一个分支两三行。完整的 dump 实现阶段 ⑥ 会被替换为正式的反汇编访问者，所以只要够你调试用就行。

┌─ 📌 阶段 ④ 小结 ────────────────────────────────────┐
│  ✅ 你刚刚完成的事：                                            │
│    • Parser 类骨架 + expect / peek / advance 工具集              │
│    • 表达式 9 层优先级（赋值/||/&amp;&amp;/==/比较/+/×/一元/调用/字面量）  │
│    • 故意写右结合 → 输出错误数学结果 → 改回 while 修复            │
│    • 8 种语句（var/print/if/while/return/block/fn/exprstmt）     │
│  📊 18 个文件已经填了 7 个                                        │
│  ⏸ 还没碰的（下阶段才会做）：                                    │
│    • TypeChecker 给 AST 标注类型（阶段 ⑤）                       │
│    • 访问者模式正式登场（阶段 ⑤）                                 │
│  📌 进入下阶段前务必：                                            │
│    git add . &amp;&amp; git commit -m "stage4: parser recursive descent" │
│  💡 本阶段最大领悟：                                              │
│    "递归下降 = 文法规则映射到函数；左结合 = while + 高优先级层"  │
└──────────────────────────────────────────────────┘

# 06.Visitor 类型检查

┌─ 🎯 阶段 ⑤ 目标 ────────────────────────────────────┐
│ 完成什么：定义 AstVisitor&lt;R> 模板基类 + TypeChecker 实现     │
│ 不做什么：不做严格静态类型——只检查"操作数类型是否匹配"       │
│ 验收标准：能拦截 1 + "abc" 这种类型不匹配错误                │
│ 预计耗时：3 小时                                            │
│ 关键思路：访问者模式 = 双重分派——节点类型走 vtable，         │
│           访问行为走 visitor 派生类                         │
└──────────────────────────────────────────────────┘

# 6.1 灵魂三问：访问者解决什么

❓ 不用 visitor，直接在每个 AST 节点写 typeCheck() 方法不行吗？

来看反例——给 AstNode 加 virtual Type typeCheck(SymbolTable& st) = 0;：

class BinOp : public AstNode {
public:
    Type typeCheck(SymbolTable& st) override { ... }
    void codeGen(CodeBuf& buf, SymbolTable& st) override { ... }
    void prettyPrint(std::ostream& os) override { ... }
    // ... 还有 reachableCheck / constFold / dceMark / liveness ...
};

问题暴露：

AstNode 类膨胀——每加一个分析行为，12 个派生类都要加一个虚函数，违反开闭原则
行为代码散布在 12 个文件——想了解整个类型检查逻辑，要打开 12 个 cpp
行为之间共享上下文困难——TypeChecker 的符号表怎么传给所有节点？参数列表会爆炸

✅ 访问者模式：把每种行为封装成一个 visitor 类——"行为"集中在一个类里、"节点类型"通过 accept 双分派回调。新增分析只要新增 visitor，不动 AST 类——开闭原则完美落实。

❓ C++ 的访问者怎么实现？

经典 GoF 写法：

class AstVisitor {
public:
    virtual void visit(NumLit& n) = 0;
    virtual void visit(BinOp& n) = 0;
    // ... 12 个 visit 重载
};

痛点：visit 不能有不同返回类型——TypeChecker 想返回 Type、Codegen 想返回 void、PrettyPrinter 想返回 string——同一个基类装不下。

✅ 本案例方案：模板基类 AstVisitor<R> + 节点端双 accept（acceptType 返回 Type、acceptCode 返回 void）——这是 C++ 模板带来的优雅解决方案。

❓ 第一步做什么？ 答：先把 AstVisitor 模板写出来 + 把 §04 留下的 14 个 accept 实现填上——基础设施。

# 6.2 模板 Visitor 基类

📁 visitor.h（全新文件）：

#pragma once
// ⚠️ 注意：本文件只前置声明所有节点类型，不 include ast.h
// 因为 ast.h 已经前置声明了 AstVisitor<R>，避免循环引用

// 前置声明所有节点（与 ast.h 中的派生类一一对应）
class NumLit; class StrLit; class BoolLit; class VarRef;
class BinOp;  class UnaryOp; class Assign;  class CallExpr;
class VarDecl; class PrintStmt; class ExprStmt; class Block;
class IfStmt; class WhileStmt; class FnDecl; class ReturnStmt;
class Program;

// ⭐ 模板访问者基类——每种返回类型 R 一份特化
template <typename R>
class AstVisitor {
public:
    virtual ~AstVisitor() = default;

    // 表达式
    virtual R visit(NumLit&)    = 0;
    virtual R visit(StrLit&)    = 0;
    virtual R visit(BoolLit&)   = 0;
    virtual R visit(VarRef&)    = 0;
    virtual R visit(BinOp&)     = 0;
    virtual R visit(UnaryOp&)   = 0;
    virtual R visit(Assign&)    = 0;
    virtual R visit(CallExpr&)  = 0;
    // 语句
    virtual R visit(VarDecl&)   = 0;
    virtual R visit(PrintStmt&) = 0;
    virtual R visit(ExprStmt&)  = 0;
    virtual R visit(Block&)     = 0;
    virtual R visit(IfStmt&)    = 0;
    virtual R visit(WhileStmt&) = 0;
    virtual R visit(FnDecl&)    = 0;
    virtual R visit(ReturnStmt&)= 0;
    virtual R visit(Program&)   = 0;
};

📚 设计精髓：

要点	写法	作用
`template <typename R>`	模板基类	同一接口适配多种返回类型
前置声明 17 个 class	不 include ast.h	避免循环引用
17 个虚函数全 `= 0`	强制派生 visitor 全部实现	编译期发现"漏处理某节点"
派生 visitor 实例化时才生成 vtable	模板的延迟实例化	没用到的 R 不生成代码

🔑 vtable 的延迟实例化：AstVisitor<Type> 和 AstVisitor<void> 是两个独立类——分别有 17 个虚函数，分别有 vtable。这就是模板版访问者既保留 OOP 多态、又突破"返回类型必须相同"限制的奥秘。

📁 回到 ast.h，在文件末尾把 §04 占位的 14 个 accept 实现填上：

// === 阶段 ⑤：accept 实现 ===
// ⚠️ 关键：这些实现要写在 ast.h 末尾、且必须 include "visitor.h"
//        否则编译时找不到 AstVisitor<R>::visit 的具体方法
#include "visitor.h"

inline Type NumLit::acceptType(AstVisitor<Type>& v)    { return v.visit(*this); }
inline void NumLit::acceptCode(AstVisitor<void>& v)    {        v.visit(*this); }

inline Type StrLit::acceptType(AstVisitor<Type>& v)    { return v.visit(*this); }
inline void StrLit::acceptCode(AstVisitor<void>& v)    {        v.visit(*this); }

inline Type BoolLit::acceptType(AstVisitor<Type>& v)   { return v.visit(*this); }
inline void BoolLit::acceptCode(AstVisitor<void>& v)   {        v.visit(*this); }

inline Type VarRef::acceptType(AstVisitor<Type>& v)    { return v.visit(*this); }
inline void VarRef::acceptCode(AstVisitor<void>& v)    {        v.visit(*this); }

inline Type BinOp::acceptType(AstVisitor<Type>& v)     { return v.visit(*this); }
inline void BinOp::acceptCode(AstVisitor<void>& v)     {        v.visit(*this); }

inline Type UnaryOp::acceptType(AstVisitor<Type>& v)   { return v.visit(*this); }
inline void UnaryOp::acceptCode(AstVisitor<void>& v)   {        v.visit(*this); }

inline Type Assign::acceptType(AstVisitor<Type>& v)    { return v.visit(*this); }
inline void Assign::acceptCode(AstVisitor<void>& v)    {        v.visit(*this); }

inline Type CallExpr::acceptType(AstVisitor<Type>& v)  { return v.visit(*this); }
inline void CallExpr::acceptCode(AstVisitor<void>& v)  {        v.visit(*this); }

inline Type VarDecl::acceptType(AstVisitor<Type>& v)   { return v.visit(*this); }
inline void VarDecl::acceptCode(AstVisitor<void>& v)   {        v.visit(*this); }

inline Type PrintStmt::acceptType(AstVisitor<Type>& v) { return v.visit(*this); }
inline void PrintStmt::acceptCode(AstVisitor<void>& v) {        v.visit(*this); }

inline Type ExprStmt::acceptType(AstVisitor<Type>& v)  { return v.visit(*this); }
inline void ExprStmt::acceptCode(AstVisitor<void>& v)  {        v.visit(*this); }

inline Type Block::acceptType(AstVisitor<Type>& v)     { return v.visit(*this); }
inline void Block::acceptCode(AstVisitor<void>& v)     {        v.visit(*this); }

inline Type IfStmt::acceptType(AstVisitor<Type>& v)    { return v.visit(*this); }
inline void IfStmt::acceptCode(AstVisitor<void>& v)    {        v.visit(*this); }

inline Type WhileStmt::acceptType(AstVisitor<Type>& v) { return v.visit(*this); }
inline void WhileStmt::acceptCode(AstVisitor<void>& v) {        v.visit(*this); }

inline Type FnDecl::acceptType(AstVisitor<Type>& v)    { return v.visit(*this); }
inline void FnDecl::acceptCode(AstVisitor<void>& v)    {        v.visit(*this); }

inline Type ReturnStmt::acceptType(AstVisitor<Type>& v){ return v.visit(*this); }
inline void ReturnStmt::acceptCode(AstVisitor<void>& v){        v.visit(*this); }

inline Type Program::acceptType(AstVisitor<Type>& v)   { return v.visit(*this); }
inline void Program::acceptCode(AstVisitor<void>& v)   {        v.visit(*this); }

⚠️ 17 个类、每个 2 行 accept 实现——看起来重复，但 17 行模板 + 34 行 accept = 永久不再改的基础设施。后续每加一种 visitor 都不用动这里。

🔑 双重分派：node->acceptType(v) 这一行包含两次动态分派：

第一次：node-> 通过 vtable 跳到 BinOp::acceptType（节点类型分派）

第二次：v.visit(*this) 通过 visitor 的 vtable 跳到具体 visitor 的 visit(BinOp&)（行为分派）

两次都 O(1)，加起来仍然是常数时间。这就是访问者模式的核心。

# 6.3 TypeChecker 实现

📁 type_checker.h：

#pragma once
#include "ast.h"
#include "visitor.h"
#include <unordered_map>
#include <vector>
#include <string>

// 函数符号——记录函数的参数个数（本案例不严格检查参数类型）
struct FnSig {
    int paramCount;
    int line;
};

class TypeChecker : public AstVisitor<Type> {
public:
    void check(AstPtr program);

    // 17 个 visit 实现
    Type visit(NumLit& n)     override { return n.ty = Type::Num; }
    Type visit(StrLit& n)     override { return n.ty = Type::Str; }
    Type visit(BoolLit& n)    override { return n.ty = Type::Bool; }
    Type visit(VarRef& n)     override;
    Type visit(BinOp& n)      override;
    Type visit(UnaryOp& n)    override;
    Type visit(Assign& n)     override;
    Type visit(CallExpr& n)   override;
    Type visit(VarDecl& n)    override;
    Type visit(PrintStmt& n)  override { n.expr->acceptType(*this); return Type::Void; }
    Type visit(ExprStmt& n)   override { n.expr->acceptType(*this); return Type::Void; }
    Type visit(Block& n)      override;
    Type visit(IfStmt& n)     override;
    Type visit(WhileStmt& n)  override;
    Type visit(FnDecl& n)     override;
    Type visit(ReturnStmt& n) override;
    Type visit(Program& n)    override;

private:
    // 符号表栈（§6.4 详解）
    std::vector<std::unordered_map<std::string, Type>> scopes;
    std::unordered_map<std::string, FnSig>             functions;

    void enterScope() { scopes.emplace_back(); }
    void leaveScope() { scopes.pop_back();    }

    bool define(const std::string& name, Type t);
    Type lookup(const std::string& name, int line);
};

📁 type_checker.cpp：

#include "type_checker.h"
#include <iostream>
#include <stdexcept>

void TypeChecker::check(AstPtr program) {
    enterScope();           // 全局作用域
    program->acceptType(*this);
    leaveScope();
}

bool TypeChecker::define(const std::string& name, Type t) {
    auto& cur = scopes.back();
    if (cur.count(name)) return false;
    cur[name] = t;
    return true;
}

Type TypeChecker::lookup(const std::string& name, int line) {
    // ⭐ 从内向外查（最近作用域优先）
    for (auto it = scopes.rbegin(); it != scopes.rend(); ++it) {
        if (auto f = it->find(name); f != it->end()) return f->second;
    }
    std::cerr << "[Type] 未定义变量 '" << name << "' (line " << line << ")\n";
    throw std::runtime_error("type error");
}

Type TypeChecker::visit(VarRef& n) {
    return n.ty = lookup(n.name, n.line);
}

Type TypeChecker::visit(BinOp& n) {
    Type lt = n.lhs->acceptType(*this);
    Type rt = n.rhs->acceptType(*this);

    auto fail = [&](const char* msg) {
        std::cerr << "[Type] " << msg << " (line " << n.line << ")\n";
        throw std::runtime_error("type error");
    };

    switch (n.op) {
        case TokKind::Plus: case TokKind::Minus:
        case TokKind::Star: case TokKind::Slash: case TokKind::Percent:
            if (lt != Type::Num || rt != Type::Num) fail("算术运算需要 Num");
            return n.ty = Type::Num;

        case TokKind::Eq: case TokKind::Ne:
            if (lt != rt) fail("== / != 两侧类型必须相同");
            return n.ty = Type::Bool;

        case TokKind::Lt: case TokKind::Le: case TokKind::Gt: case TokKind::Ge:
            if (lt != Type::Num || rt != Type::Num) fail("比较需要 Num");
            return n.ty = Type::Bool;

        case TokKind::AndAnd: case TokKind::OrOr:
            if (lt != Type::Bool || rt != Type::Bool) fail("逻辑运算需要 Bool");
            return n.ty = Type::Bool;

        default: fail("未知的二元运算符");
    }
    return Type::Unknown;
}

Type TypeChecker::visit(UnaryOp& n) {
    Type t = n.operand->acceptType(*this);
    if (n.op == TokKind::Minus) {
        if (t != Type::Num) {
            std::cerr << "[Type] - 需要 Num\n"; throw std::runtime_error("type error");
        }
        return n.ty = Type::Num;
    }
    if (n.op == TokKind::Bang) {
        if (t != Type::Bool) {
            std::cerr << "[Type] ! 需要 Bool\n"; throw std::runtime_error("type error");
        }
        return n.ty = Type::Bool;
    }
    return Type::Unknown;
}

Type TypeChecker::visit(Assign& n) {
    Type rhs = n.value->acceptType(*this);
    Type lhs = lookup(n.name, n.line);
    if (lhs != rhs) {
        std::cerr << "[Type] 赋值类型不匹配 (line " << n.line << ")\n";
        throw std::runtime_error("type error");
    }
    return n.ty = rhs;
}

Type TypeChecker::visit(CallExpr& n) {
    auto it = functions.find(n.callee);
    if (it == functions.end()) {
        std::cerr << "[Type] 未定义函数 '" << n.callee << "' (line " << n.line << ")\n";
        throw std::runtime_error("type error");
    }
    if ((int)n.args.size() != it->second.paramCount) {
        std::cerr << "[Type] 函数 " << n.callee << " 参数个数不匹配——期望 "
                  << it->second.paramCount << "，实际 " << n.args.size() << "\n";
        throw std::runtime_error("type error");
    }
    for (auto& a : n.args) a->acceptType(*this);
    // ⚠️ 简化：所有函数返回 Num（真实编译器要做返回类型推导）
    return n.ty = Type::Num;
}

Type TypeChecker::visit(VarDecl& n) {
    Type t = Type::Num;       // 默认
    if (n.init) t = n.init->acceptType(*this);
    if (!define(n.name, t)) {
        std::cerr << "[Type] 变量 " << n.name << " 重复定义\n";
        throw std::runtime_error("type error");
    }
    return Type::Void;
}

Type TypeChecker::visit(Block& n) {
    enterScope();
    for (auto& s : n.stmts) s->acceptType(*this);
    leaveScope();
    return Type::Void;
}

Type TypeChecker::visit(IfStmt& n) {
    if (n.cond->acceptType(*this) != Type::Bool) {
        std::cerr << "[Type] if 条件需要 Bool\n";
        throw std::runtime_error("type error");
    }
    n.thenBranch->acceptType(*this);
    if (n.elseBranch) n.elseBranch->acceptType(*this);
    return Type::Void;
}

Type TypeChecker::visit(WhileStmt& n) {
    if (n.cond->acceptType(*this) != Type::Bool) {
        std::cerr << "[Type] while 条件需要 Bool\n";
        throw std::runtime_error("type error");
    }
    n.body->acceptType(*this);
    return Type::Void;
}

Type TypeChecker::visit(FnDecl& n) {
    // 1. 先把函数签名注册到全局——支持递归调用
    functions[n.name] = FnSig{(int)n.params.size(), n.line};

    // 2. 进入新作用域，把参数当作变量
    enterScope();
    for (auto& p : n.params) define(p, Type::Num);   // 简化：参数都按 Num 处理
    n.body->acceptType(*this);
    leaveScope();
    return Type::Void;
}

Type TypeChecker::visit(ReturnStmt& n) {
    if (n.value) n.value->acceptType(*this);
    return Type::Void;
}

Type TypeChecker::visit(Program& n) {
    // 第一遍：先注册所有顶层函数（让函数能彼此调用、不依赖声明顺序）
    for (auto& d : n.decls) {
        if (auto fn = std::dynamic_pointer_cast<FnDecl>(d)) {
            functions[fn->name] = FnSig{(int)fn->params.size(), fn->line};
        }
    }
    // 第二遍：真正访问所有声明
    for (auto& d : n.decls) d->acceptType(*this);
    return Type::Void;
}

# 6.4 符号表栈

🔑 本节是访问者实战的精髓段落——scopes 字段是 vector<unordered_map<string, Type>>，每个元素是一层作用域。

全局
{ "x" → Num, "fib" → Num }
   │
   │  进入 fib 函数体
   ▼
全局 + 函数局部
{ "x" → Num, "fib" → Num }
{ "n" → Num }                        ← 这层是 fib 的参数
   │
   │  进入 if (n &lt; 2) { ... } 块
   ▼
全局 + 函数局部 + 块局部
{ "x" → Num, "fib" → Num }
{ "n" → Num }
{ }                                   ← 这层 block 内若有 var 会进来

查找规则：从栈顶往下找——最近作用域优先。这就是 lexical scoping（词法作用域） 的机制。

💡 why vector 而不是 stack：因为查找需要从顶到底遍历，而 std::stack 不支持遍历——只 push/pop/top。vector 既能 push_back / pop_back（栈语义）、又能反向迭代（查找）——比 stack 更合适。

🧪 第一次编译运行（验证 TypeChecker 拦住错误）

📁 main.cpp 在 Parser 之后加：

#include "type_checker.h"

// 在 [Parse] OK 之后加：
try {
    TypeChecker tc;
    tc.check(prog);
    cout << "[TypeCheck] OK\n";
} catch (const std::exception& e) {
    cout << "[TypeCheck] 失败: " << e.what() << "\n";
}

g++ -std=c++17 main.cpp lexer.cpp token.cpp parser.cpp type_checker.cpp -o mycc
./mycc

操作：

mycc> var x = 1; print x;
[Parse] OK，顶层节点数=2
[TypeCheck] OK

mycc> var x = 1; var x = 2;
[Type] 变量 x 重复定义
[TypeCheck] 失败: type error

mycc> print y;
[Type] 未定义变量 'y' (line 1)
[TypeCheck] 失败: type error

mycc> if (1) { print 1; }
[Type] if 条件需要 Bool
[TypeCheck] 失败: type error

mycc> if (1 == 1) { print 1; }
[Parse] OK
[TypeCheck] OK

🎉 类型检查全部生效——四种类型错误全被拦住，正确程序顺利通过。

┌─ 📌 阶段 ⑤ 小结 ────────────────────────────────────┐
│  ✅ 你刚刚完成的事：                                            │
│    • 模板访问者基类 AstVisitor&lt;R> + 双 accept 接口               │
│    • TypeChecker 17 个 visit 全部实现                            │
│    • 作用域栈：vector&lt;unordered_map> 实现 lexical scoping        │
│    • 函数签名预注册：支持相互递归                                 │
│  📊 18 个文件已经填了 11 个                                       │
│  ⏸ 还没碰的（下阶段才会做）：                                    │
│    • Codegen 把 AST 翻译成字节码（阶段 ⑥）                       │
│    • VM 执行字节码（阶段 ⑦）                                      │
│  📌 进入下阶段前务必：                                            │
│    git add . &amp;&amp; git commit -m "stage5: type checker"             │
│  💡 本阶段最大领悟：                                              │
│    "Visitor 模式 = 行为外置 + 双重分派——节点稳定、行为可扩展"   │
└──────────────────────────────────────────────────┘

# §07 阶段⑥ Codegen 字节码生成（约 4 h）

┌─ 🎯 阶段 ⑥ 目标卡片 ──────────────────────────────────┐
│  ⏱ 预计 4 小时                                                  │
│  📂 新增/修改文件：                                              │
│    src/codegen/opcode.h         (36 条指令枚举)                 │
│    src/codegen/chunk.h/.cpp     (字节码容器：指令+常量池+行号)  │
│    src/codegen/codegen.h/.cpp   (Codegen 访问者)                │
│    src/main.cpp                 (接入 :dump 反汇编)             │
│  ✅ 完成后能做的事：                                             │
│    mycc> :dump  let a = 1 + 2 * 3;                              │
│    [DUMP]                                                       │
│      0000  CONST       0  (1)                                   │
│      0002  CONST       1  (2)                                   │
│      0004  CONST       2  (3)                                   │
│      0006  MUL                                                  │
│      0007  ADD                                                  │
│      0008  STORE_GLOBAL  3  (a)                                 │
│      0010  HALT                                                 │
│  ⚠ 本阶段难点 TOP 3：                                            │
│    ① if/while 怎么编译跳转？答：占位 + 回填                      │
│    ② 函数怎么编译？答：独立 Chunk + 名字注册                      │
│    ③ 短路 &amp;&amp; || 怎么实现？答：JUMP_IF_FALSE 短路跳转             │
└──────────────────────────────────────────────────┘

# §7.1 灵魂三问：为什么不直接树遍历执行？

问题 1：树遍历解释器（Tree-walking interpreter）不也能跑吗？

能跑，且最简单。用 Visitor 写一个 Evaluator : public AstVisitor<Value>，每个 visit(Node&) 直接返回求值结果——50 行代码就能跑通 1 + 2 * 3。Python 早期、Ruby 1.8 都是这么干的。

那为什么主流语言（Java、Python 3.11+、Lua、JavaScript V8 baseline）都改用字节码？

答：3 倍以上的性能差距。原因有三：

维度	树遍历	字节码
节点访问开销	每个节点 = 一次虚函数调用（vtable 跳转）	一条指令 = 一次数组取值（顺序内存）
缓存命中	AST 节点散落堆上，cache miss 严重	指令连续存于 `vector<uint8_t>`，CPU 预取友好
重复工作	每次执行都要重新「访问」节点	只编译一次，可执行无数次

📊 实测数据：fib(30) 在树遍历下耗时 ~800 ms，相同算法字节码版只需 ~250 ms（不开 JIT）。差距来自 vtable + cache + 重复访问 三重叠加。

问题 2：那不就是 LLVM IR 那种东西吗？为什么不直接生成机器码？

方案	难度	可移植性	启动速度
机器码（汇编）	极高（要懂寄存器分配、调用约定、ELF/Mach-O）	❌ x86/ARM/RISC-V 各写一份	慢（要先编译完）
字节码	中（自定义 36 条指令即可）	✅ 与平台无关	快（边读边跑）
树遍历	低	✅ 但慢	最快

mycc 选字节码——既比树遍历快 3 倍，又比机器码简单 100 倍。这就是 Java、Lua、Python、Ruby、Erlang 的共同选择。

问题 3：编译时机怎么处理 if/while 的跳转？目标地址还不知道呢！

这就是本阶段最核心的工程技巧——回填（Backpatching）：

源码：if (a > 0) { print a; } else { print -a; }

第一遍（顺序生成）：
  GT
  JUMP_IF_FALSE  ???   ← 不知道 else 在哪，先填占位 0xFFFF
  LOAD a
  PRINT
  JUMP            ???   ← 不知道结尾在哪，先填占位 0xFFFF
  ← else 入口在这（下标已知），回头改 ① 处占位
  LOAD a
  NEG
  PRINT
  ← 结尾在这（下标已知），回头改 ② 处占位

我们用 size_t emitJump(OpCode) 函数：

写入跳转指令 + 2 字节占位 0xFFFF
返回占位的下标
编译完目标后，用 patchJump(idx) 把占位改成真实偏移

💡 这个"留个洞、回头补"的思路在汇编、链接器、JIT、甚至 protobuf 序列化都会出现。学会它，你就掌握了系统编程的一类通用模式。

# §7.2 OpCode 36 条指令

src/codegen/opcode.h：

#pragma once
#include <cstdint>

namespace mycc {

// ========================================
//  字节码指令集（共 36 条）
// ========================================
//  设计原则：
//   1. 栈式 VM——所有运算都在求值栈上完成
//   2. 长度可变：大部分 1 字节，带操作数的 1+2 字节
//   3. 操作数用 uint16_t（小端字节序）—— 65535 个常量/局部变量足够小语言用
// ========================================
enum class OpCode : uint8_t {
    // -- 字面量与常量池 --
    CONST,          // CONST i        → push constants[i]
    NIL,            //                  → push nil
    TRUE,           //                  → push true
    FALSE,          //                  → push false

    // -- 算术 --
    ADD,            // pop b, pop a    → push a+b
    SUB,
    MUL,
    DIV,
    MOD,
    NEG,            // pop a           → push -a

    // -- 比较 --
    EQ,             // pop b, pop a    → push (a==b)
    NEQ,
    LT,
    LE,
    GT,
    GE,

    // -- 逻辑 --
    NOT,            // pop a           → push !a
    AND,            // 短路靠 JUMP_IF_FALSE 实现，这里只是按位
    OR,

    // -- 变量 --
    LOAD_GLOBAL,    // LOAD_GLOBAL i   → push globals[constants[i]] (i 是变量名常量索引)
    STORE_GLOBAL,   // STORE_GLOBAL i  → globals[constants[i]] = pop
    LOAD_LOCAL,     // LOAD_LOCAL  i   → push locals[i]    (i 是栈帧偏移)
    STORE_LOCAL,    // STORE_LOCAL i   → locals[i] = peek  (赋值表达式不弹栈)

    // -- 控制流（关键：带 2 字节相对偏移） --
    JUMP,           // JUMP        off → ip += off
    JUMP_IF_FALSE,  // JUMP_IF_FALSE off → if (peek == false) ip += off
    JUMP_IF_TRUE,   // 用于 ||
    POP_JUMP_IF_FALSE,  // 同时弹栈
    LOOP,           // LOOP        off → ip -= off  (回跳)

    // -- 函数 --
    CALL,           // CALL n          → 调用栈顶函数，n = 实参个数
    RETURN,         // 弹出当前栈帧

    // -- I/O 与控制 --
    PRINT,          // pop a           → 输出
    POP,            //                  → 弃栈顶
    DUP,            //                  → 复制栈顶（用于赋值表达式）
    HALT,           // 停机
};

// 反汇编辅助：把 OpCode 转成字符串
const char* opcodeName(OpCode op);

}  // namespace mycc

src/codegen/opcode.cpp：

#include "opcode.h"

namespace mycc {

const char* opcodeName(OpCode op) {
    switch (op) {
        case OpCode::CONST:        return "CONST";
        case OpCode::NIL:          return "NIL";
        case OpCode::TRUE:         return "TRUE";
        case OpCode::FALSE:        return "FALSE";
        case OpCode::ADD:          return "ADD";
        case OpCode::SUB:          return "SUB";
        case OpCode::MUL:          return "MUL";
        case OpCode::DIV:          return "DIV";
        case OpCode::MOD:          return "MOD";
        case OpCode::NEG:          return "NEG";
        case OpCode::EQ:           return "EQ";
        case OpCode::NEQ:          return "NEQ";
        case OpCode::LT:           return "LT";
        case OpCode::LE:           return "LE";
        case OpCode::GT:           return "GT";
        case OpCode::GE:           return "GE";
        case OpCode::NOT:          return "NOT";
        case OpCode::AND:          return "AND";
        case OpCode::OR:           return "OR";
        case OpCode::LOAD_GLOBAL:  return "LOAD_GLOBAL";
        case OpCode::STORE_GLOBAL: return "STORE_GLOBAL";
        case OpCode::LOAD_LOCAL:   return "LOAD_LOCAL";
        case OpCode::STORE_LOCAL:  return "STORE_LOCAL";
        case OpCode::JUMP:         return "JUMP";
        case OpCode::JUMP_IF_FALSE:return "JUMP_IF_FALSE";
        case OpCode::JUMP_IF_TRUE: return "JUMP_IF_TRUE";
        case OpCode::POP_JUMP_IF_FALSE: return "POP_JUMP_IF_FALSE";
        case OpCode::LOOP:         return "LOOP";
        case OpCode::CALL:         return "CALL";
        case OpCode::RETURN:       return "RETURN";
        case OpCode::PRINT:        return "PRINT";
        case OpCode::POP:          return "POP";
        case OpCode::DUP:          return "DUP";
        case OpCode::HALT:         return "HALT";
    }
    return "??";
}

}  // namespace mycc

🤔 为什么有 4 种 JUMP？

JUMP：无条件跳，用于 if-else 跳过 else 分支

JUMP_IF_FALSE：条件假跳，不弹栈（用于 &&：左为假就跳，结果就是栈顶的假值）

JUMP_IF_TRUE：条件真跳，不弹栈（用于 ||：左为真就跳，结果就是栈顶的真值）

POP_JUMP_IF_FALSE：条件假跳 + 弹栈（用于 if/while 条件——条件值不再需要）

LOOP：相对负偏移回跳（用于 while 循环回到判断处）

看似多 1 条指令，性能差异显著：避免了 "POP + JUMP_IF_FALSE" 两条指令，且 && / || 的短路语义直接落到指令上，无需运行时分支。

# §7.3 Chunk 字节码容器

字节码不是孤立的字节流——它需要伴随常量池（数字字面量、变量名、字符串）和行号表（出错时定位源码）。我们把这些封装成 Chunk：

src/codegen/chunk.h：

#pragma once
#include "opcode.h"
#include <cstdint>
#include <string>
#include <vector>
#include <variant>

namespace mycc {

// 常量池中的元素：数字、字符串、变量名都用它表示
using Constant = std::variant<double, std::string, bool>;

// ========================================
//  Chunk = 一段字节码（一个函数 / 一段顶层代码 = 一个 Chunk）
// ========================================
class Chunk {
public:
    std::vector<uint8_t>  code;        // 字节码流
    std::vector<Constant> constants;   // 常量池
    std::vector<int>      lines;       // 与 code 一一对应的行号（出错定位用）
    std::string           name;        // 调试用：函数名 / "<top>"

    Chunk() = default;
    explicit Chunk(std::string n) : name(std::move(n)) {}

    // ----- 写入辅助 -----
    void emit(uint8_t byte, int line) {
        code.push_back(byte);
        lines.push_back(line);
    }
    void emit(OpCode op, int line) { emit(static_cast<uint8_t>(op), line); }

    // 写入 1 字节指令 + 2 字节小端操作数
    void emitWithU16(OpCode op, uint16_t operand, int line) {
        emit(op, line);
        emit(operand & 0xFF, line);
        emit((operand >> 8) & 0xFF, line);
    }

    // 添加常量；若已存在则复用（去重）
    uint16_t addConstant(const Constant& c);

    // ----- 跳转回填核心 API -----
    // 写入跳转指令 + 占位 0xFFFF，返回占位字节的位置
    size_t emitJump(OpCode op, int line);

    // 把 idx 处的 16 位占位回填为「从 idx+2 跳到当前末尾」的相对偏移
    void   patchJump(size_t idx);

    // 写入 LOOP 指令 + 回跳偏移（target 在前、当前位置在后）
    void   emitLoop(size_t target, int line);

    // ----- 反汇编（调试用） -----
    void disassemble(std::ostream& os) const;
};

}  // namespace mycc

src/codegen/chunk.cpp：

#include "chunk.h"
#include <iomanip>
#include <ostream>
#include <stdexcept>

namespace mycc {

uint16_t Chunk::addConstant(const Constant& c) {
    // 去重：避免常量池膨胀（同一个数字 1 可能出现 100 次，没必要存 100 份）
    for (size_t i = 0; i < constants.size(); ++i) {
        if (constants[i] == c) return static_cast<uint16_t>(i);
    }
    if (constants.size() >= 65535) {
        throw std::runtime_error("too many constants in one chunk");
    }
    constants.push_back(c);
    return static_cast<uint16_t>(constants.size() - 1);
}

size_t Chunk::emitJump(OpCode op, int line) {
    emit(op, line);
    emit(0xFF, line);                  // 占位低字节
    emit(0xFF, line);                  // 占位高字节
    return code.size() - 2;            // 返回占位低字节下标
}

void Chunk::patchJump(size_t idx) {
    // 从 idx+2（跳转指令的下一条）到当前末尾的距离
    size_t jump = code.size() - idx - 2;
    if (jump > 0xFFFF) {
        throw std::runtime_error("jump distance too large (>64KB)");
    }
    code[idx]     = jump & 0xFF;
    code[idx + 1] = (jump >> 8) & 0xFF;
}

void Chunk::emitLoop(size_t target, int line) {
    emit(OpCode::LOOP, line);
    // 当前末尾再 +2 是 LOOP 操作数自身的 2 字节，回跳后 ip 应停在 target
    size_t offset = code.size() + 2 - target;
    if (offset > 0xFFFF) {
        throw std::runtime_error("loop distance too large");
    }
    emit(offset & 0xFF, line);
    emit((offset >> 8) & 0xFF, line);
}

// ----- 反汇编 -----
static size_t simple(std::ostream& os, const char* name, size_t off) {
    os << name << "\n";
    return off + 1;
}
static size_t u16Operand(std::ostream& os, const char* name,
                         const Chunk& c, size_t off) {
    uint16_t arg = c.code[off + 1] | (c.code[off + 2] << 8);
    os << std::left << std::setw(16) << name << arg;
    if (name == std::string("CONST") ||
        name == std::string("LOAD_GLOBAL") ||
        name == std::string("STORE_GLOBAL")) {
        os << "  ; ";
        std::visit([&](auto&& v) { os << v; }, c.constants[arg]);
    }
    os << "\n";
    return off + 3;
}

void Chunk::disassemble(std::ostream& os) const {
    os << "== " << name << " ==\n";
    size_t off = 0;
    while (off < code.size()) {
        os << std::setw(4) << std::setfill('0') << off << std::setfill(' ') << "  ";
        OpCode op = static_cast<OpCode>(code[off]);
        const char* name = opcodeName(op);
        switch (op) {
            case OpCode::CONST:  case OpCode::LOAD_GLOBAL: case OpCode::STORE_GLOBAL:
            case OpCode::LOAD_LOCAL: case OpCode::STORE_LOCAL:
            case OpCode::JUMP: case OpCode::JUMP_IF_FALSE:
            case OpCode::JUMP_IF_TRUE: case OpCode::POP_JUMP_IF_FALSE:
            case OpCode::LOOP: case OpCode::CALL:
                off = u16Operand(os, name, *this, off);
                break;
            default:
                off = simple(os, name, off);
                break;
        }
    }
}

}  // namespace mycc

📌 几个看似细枝末节、实则非常关键的设计：

addConstant 去重：常量池可能爆炸（10 万次循环里全是 i + 1，那个 1 不能存 10 万份）

patchJump 用 code.size() - idx - 2：减 2 是因为跳转操作数自身占 2 字节，VM 执行时 ip 已经跨过它

emitLoop 用 code.size() + 2 - target：加 2 是 LOOP 自身操作数还没写入，要预留

这两条 + 2 / - 2 的偏差是新人写 VM 最常踩的 bug——画图算清楚就不会错。

# §7.4 Codegen 访问者

终于要写主菜了。Codegen 也是 Visitor，但与 TypeChecker 有两个关键区别：

维度	TypeChecker	Codegen
返回类型	`Type`（确认每个节点的类型）	`void`（直接写字节码到 Chunk）
核心数据结构	`vector<unordered_map>` 作用域栈（保存类型）	`vector<Local>` 局部变量数组（保存栈偏移）
核心难点	作用域查找	跳转回填

src/codegen/codegen.h：

#pragma once
#include "../ast/ast.h"
#include "../ast/visitor.h"
#include "chunk.h"
#include <unordered_map>
#include <vector>

namespace mycc {

// 局部变量信息：名字 + 它的作用域深度
struct Local {
    std::string name;
    int         depth;     // 0 = 全局，1+ = 块内层级
};

// 一个函数 = 一个 CodegenFrame
struct CodegenFrame {
    Chunk              chunk;
    std::vector<Local> locals;
    int                scopeDepth = 0;   // 当前块嵌套深度

    explicit CodegenFrame(std::string name) : chunk(std::move(name)) {}
};

class Codegen : public AstVisitor<void> {
public:
    Codegen();

    // 顶层入口：返回主 Chunk + 已注册函数 Chunk 表
    Chunk compile(Program& prog);

    // 暴露给外部（VM 用）：函数名 → 函数 Chunk
    std::unordered_map<std::string, Chunk> functions;

    // ----- 17 个 visit 重载 -----
    void visit(NumLit&)      override;
    void visit(StringLit&)   override;
    void visit(BoolLit&)     override;
    void visit(VarRef&)      override;
    void visit(BinOp&)       override;
    void visit(UnaryOp&)     override;
    void visit(Assign&)      override;
    void visit(Call&)        override;

    void visit(ExprStmt&)    override;
    void visit(LetDecl&)     override;
    void visit(IfStmt&)      override;
    void visit(WhileStmt&)   override;
    void visit(BlockStmt&)   override;
    void visit(FuncDecl&)    override;
    void visit(ReturnStmt&)  override;
    void visit(PrintStmt&)   override;
    void visit(Program&)     override;

private:
    // 当前正在写的栈帧（栈顶 = 当前函数）
    std::vector<CodegenFrame> frames_;
    CodegenFrame& cur() { return frames_.back(); }
    Chunk&        chk() { return cur().chunk; }

    // ----- 作用域 -----
    void beginScope() { cur().scopeDepth++; }
    void endScope();   // 弹出本作用域所有 locals + 发出 POP

    // ----- 变量解析 -----
    int  resolveLocal(const std::string& name);   // 返回栈偏移；-1 = 不是局部
    void declareLocal(const std::string& name, int line);

    // ----- 字面量辅助 -----
    void emitConst(Constant c, int line);
};

}  // namespace mycc

src/codegen/codegen.cpp（核心实现）：

#include "codegen.h"
#include <stdexcept>

namespace mycc {

Codegen::Codegen() {
    frames_.emplace_back("<top>");   // 主程序栈帧
}

Chunk Codegen::compile(Program& prog) {
    visit(prog);
    chk().emit(OpCode::HALT, 0);
    return std::move(frames_.front().chunk);
}

void Codegen::emitConst(Constant c, int line) {
    uint16_t idx = chk().addConstant(c);
    chk().emitWithU16(OpCode::CONST, idx, line);
}

// ============== 字面量 ==============
void Codegen::visit(NumLit& n)    { emitConst(n.value, n.line); }
void Codegen::visit(StringLit& n) { emitConst(n.value, n.line); }
void Codegen::visit(BoolLit& n)   { chk().emit(n.value ? OpCode::TRUE : OpCode::FALSE, n.line); }

// ============== 变量引用 ==============
void Codegen::visit(VarRef& n) {
    int slot = resolveLocal(n.name);
    if (slot >= 0) {
        chk().emitWithU16(OpCode::LOAD_LOCAL, slot, n.line);
    } else {
        // 全局：把名字放进常量池
        uint16_t idx = chk().addConstant(n.name);
        chk().emitWithU16(OpCode::LOAD_GLOBAL, idx, n.line);
    }
}

// ============== 二元运算 ==============
void Codegen::visit(BinOp& n) {
    // —— 短路求值：&& 和 || 必须特判，不能像 + 那样直接生成两边 + ADD ——
    if (n.op == TokKind::AndAnd) {
        n.lhs->acceptCode(*this);
        // 左为假就跳过右边，整个表达式 = 左值（即栈顶的 false）
        size_t end = chk().emitJump(OpCode::JUMP_IF_FALSE, n.line);
        chk().emit(OpCode::POP, n.line);   // 左为真，弹掉左值
        n.rhs->acceptCode(*this);          // 结果 = 右值
        chk().patchJump(end);
        return;
    }
    if (n.op == TokKind::OrOr) {
        n.lhs->acceptCode(*this);
        size_t end = chk().emitJump(OpCode::JUMP_IF_TRUE, n.line);
        chk().emit(OpCode::POP, n.line);
        n.rhs->acceptCode(*this);
        chk().patchJump(end);
        return;
    }

    // —— 普通二元运算 ——
    n.lhs->acceptCode(*this);
    n.rhs->acceptCode(*this);
    switch (n.op) {
        case TokKind::Plus:    chk().emit(OpCode::ADD, n.line); break;
        case TokKind::Minus:   chk().emit(OpCode::SUB, n.line); break;
        case TokKind::Star:    chk().emit(OpCode::MUL, n.line); break;
        case TokKind::Slash:   chk().emit(OpCode::DIV, n.line); break;
        case TokKind::Percent: chk().emit(OpCode::MOD, n.line); break;
        case TokKind::EqEq:    chk().emit(OpCode::EQ, n.line); break;
        case TokKind::BangEq:  chk().emit(OpCode::NEQ, n.line); break;
        case TokKind::Lt:      chk().emit(OpCode::LT, n.line); break;
        case TokKind::Le:      chk().emit(OpCode::LE, n.line); break;
        case TokKind::Gt:      chk().emit(OpCode::GT, n.line); break;
        case TokKind::Ge:      chk().emit(OpCode::GE, n.line); break;
        default: throw std::runtime_error("codegen: bad binary op");
    }
}

// ============== 一元 ==============
void Codegen::visit(UnaryOp& n) {
    n.operand->acceptCode(*this);
    switch (n.op) {
        case TokKind::Minus: chk().emit(OpCode::NEG, n.line); break;
        case TokKind::Bang:  chk().emit(OpCode::NOT, n.line); break;
        default: throw std::runtime_error("codegen: bad unary op");
    }
}

// ============== 赋值 ==============
void Codegen::visit(Assign& n) {
    n.value->acceptCode(*this);   // 求出右值放栈顶

    // 赋值是表达式，结果 = 右值，所以要 DUP 留一份
    int slot = resolveLocal(n.name);
    if (slot >= 0) {
        chk().emit(OpCode::DUP, n.line);
        chk().emitWithU16(OpCode::STORE_LOCAL, slot, n.line);
    } else {
        chk().emit(OpCode::DUP, n.line);
        uint16_t idx = chk().addConstant(n.name);
        chk().emitWithU16(OpCode::STORE_GLOBAL, idx, n.line);
    }
}

// ============== 函数调用 ==============
void Codegen::visit(Call& n) {
    // 把函数名当成全局变量加载（VM 会从 functions 表查）
    uint16_t idx = chk().addConstant(n.callee);
    chk().emitWithU16(OpCode::LOAD_GLOBAL, idx, n.line);

    for (auto& arg : n.args) {
        arg->acceptCode(*this);
    }
    if (n.args.size() > 255) {
        throw std::runtime_error("too many arguments");
    }
    chk().emitWithU16(OpCode::CALL, static_cast<uint16_t>(n.args.size()), n.line);
}

// ============== 表达式语句 ==============
void Codegen::visit(ExprStmt& n) {
    n.expr->acceptCode(*this);
    chk().emit(OpCode::POP, n.line);   // 表达式语句的值要弃掉
}

// ============== let 声明 ==============
void Codegen::visit(LetDecl& n) {
    n.init->acceptCode(*this);
    if (cur().scopeDepth == 0) {
        // 全局
        uint16_t idx = chk().addConstant(n.name);
        chk().emitWithU16(OpCode::STORE_GLOBAL, idx, n.line);
        chk().emit(OpCode::POP, n.line);
    } else {
        // 局部：值已经在栈上，注册一个 Local 即可（后续访问按栈偏移）
        declareLocal(n.name, n.line);
    }
}

// ============== if 语句（跳转回填经典案例）==============
void Codegen::visit(IfStmt& n) {
    n.cond->acceptCode(*this);
    // 条件为假 → 跳过 then；同时弹掉条件值
    size_t elseJump = chk().emitJump(OpCode::POP_JUMP_IF_FALSE, n.line);

    n.thenBranch->acceptCode(*this);

    if (n.elseBranch) {
        size_t endJump = chk().emitJump(OpCode::JUMP, n.line);
        chk().patchJump(elseJump);            // ① else 入口
        n.elseBranch->acceptCode(*this);
        chk().patchJump(endJump);             // ② 整个 if 结束
    } else {
        chk().patchJump(elseJump);
    }
}

// ============== while 语句 ==============
void Codegen::visit(WhileStmt& n) {
    size_t loopStart = chk().code.size();    // ← 回跳目标（条件之前）
    n.cond->acceptCode(*this);
    size_t exitJump = chk().emitJump(OpCode::POP_JUMP_IF_FALSE, n.line);

    n.body->acceptCode(*this);
    chk().emitLoop(loopStart, n.line);       // ← 回跳

    chk().patchJump(exitJump);               // 假分支落点
}

// ============== 块 ==============
void Codegen::visit(BlockStmt& n) {
    beginScope();
    for (auto& s : n.stmts) s->acceptCode(*this);
    endScope();
}

void Codegen::endScope() {
    cur().scopeDepth--;
    while (!cur().locals.empty() &&
           cur().locals.back().depth > cur().scopeDepth) {
        chk().emit(OpCode::POP, 0);          // 块结束，弹掉本块所有局部
        cur().locals.pop_back();
    }
}

// ============== 函数声明 ==============
void Codegen::visit(FuncDecl& n) {
    // 切到新栈帧编译函数体
    frames_.emplace_back(n.name);
    beginScope();
    // 形参作为函数 scope 内的 Local（CALL 指令会把实参压栈作为初值）
    for (auto& p : n.params) {
        declareLocal(p.name, n.line);
    }
    for (auto& s : n.body) s->acceptCode(*this);
    // 兜底：函数末尾若没显式 return，自动 push nil + RETURN
    chk().emit(OpCode::NIL, n.line);
    chk().emit(OpCode::RETURN, n.line);

    // 弹栈帧，存进 functions 表
    Chunk c = std::move(frames_.back().chunk);
    frames_.pop_back();
    functions[n.name] = std::move(c);
}

// ============== return ==============
void Codegen::visit(ReturnStmt& n) {
    if (n.value) n.value->acceptCode(*this);
    else         chk().emit(OpCode::NIL, n.line);
    chk().emit(OpCode::RETURN, n.line);
}

// ============== print ==============
void Codegen::visit(PrintStmt& n) {
    n.expr->acceptCode(*this);
    chk().emit(OpCode::PRINT, n.line);
}

// ============== Program ==============
void Codegen::visit(Program& n) {
    // 第一遍：先把所有函数编译完（支持顶层调用顺序无关、也支持相互递归）
    for (auto& s : n.stmts) {
        if (auto* fd = dynamic_cast<FuncDecl*>(s.get())) {
            fd->acceptCode(*this);
        }
    }
    // 第二遍：编译顶层非函数语句到主 chunk
    for (auto& s : n.stmts) {
        if (!dynamic_cast<FuncDecl*>(s.get())) {
            s->acceptCode(*this);
        }
    }
}

// ============== 辅助：作用域 / 局部变量 ==============
int Codegen::resolveLocal(const std::string& name) {
    auto& locals = cur().locals;
    for (int i = static_cast<int>(locals.size()) - 1; i >= 0; --i) {
        if (locals[i].name == name) return i;
    }
    return -1;
}

void Codegen::declareLocal(const std::string& name, int /*line*/) {
    if (cur().locals.size() >= 65535) {
        throw std::runtime_error("too many locals");
    }
    cur().locals.push_back({ name, cur().scopeDepth });
}

}  // namespace mycc

📌 花一秒回看 visit(IfStmt&)——这就是教科书级别的回填技巧：
  &lt;cond 字节码>
  POP_JUMP_IF_FALSE  ?  ← elseJump 拿到这里的下标
  &lt;then 字节码>
  JUMP                ?  ← endJump 拿到这里的下标
  patchJump(elseJump) → 指向这里
  &lt;else 字节码>
  patchJump(endJump)  → 指向这里
看懂这 8 行，你就掌握了所有控制流的编译范式。switch、try-catch、break/continue 都是它的变种。

# §7.5 接入 main：`:dump` 反汇编

修改 src/main.cpp，在 :tcheck 之后增加 :dump 命令——给读者一个肉眼可见的成果反馈：

// 头文件区追加：
#include "codegen/codegen.h"

// 在 REPL 循环中、`else if (cmd == ":tcheck") { ... }` 之后追加：
else if (cmd == ":dump") {
    Lexer lex(rest, "<repl>");
    auto toks = lex.scanAll();
    Parser psr(std::move(toks));
    auto prog = psr.parseProgram();

    TypeChecker tc;
    tc.visit(*prog);

    Codegen cg;
    Chunk top = cg.compile(*prog);

    std::cout << "[DUMP main]\n";
    top.disassemble(std::cout);
    for (auto& [name, c] : cg.functions) {
        std::cout << "[DUMP fn " << name << "]\n";
        c.disassemble(std::cout);
    }
}

更新 CMakeLists.txt：

add_executable(mycc
    src/main.cpp
    src/lexer/lexer.cpp
    src/parser/parser.cpp
    src/sema/type_checker.cpp
    src/codegen/opcode.cpp
    src/codegen/chunk.cpp
    src/codegen/codegen.cpp
)

🧪 编译验证：

$ cmake --build build &amp;&amp; ./build/mycc

mycc> :dump  let a = 1 + 2 * 3;
[DUMP main]
== &lt;top> ==
0000  CONST           0  ; 1
0003  CONST           1  ; 2
0006  CONST           2  ; 3
0009  MUL
0010  ADD
0011  STORE_GLOBAL    3  ; a
0014  POP
0015  HALT

mycc> :dump  if (5 > 3) { print 1; } else { print 2; }
[DUMP main]
== &lt;top> ==
0000  CONST           0  ; 5
0003  CONST           1  ; 3
0006  GT
0007  POP_JUMP_IF_FALSE   8     ; 跳过 then
0010  CONST           2  ; 1
0013  PRINT
0014  JUMP            5         ; 跳过 else
0017  CONST           3  ; 2
0020  PRINT
0021  HALT

mycc> :dump  fn add(a, b) { return a + b; }  add(3, 4);
[DUMP fn add]
== add ==
0000  LOAD_LOCAL      0    ; (slot 0 = a)
0003  LOAD_LOCAL      1    ; (slot 1 = b)
0006  ADD
0007  RETURN
[DUMP main]
== &lt;top> ==
0000  LOAD_GLOBAL     0  ; add
0003  CONST           1  ; 3
0006  CONST           2  ; 4
0009  CALL            2
0012  POP
0013  HALT

🎉 编译器主体已经完工！——AST 翻译成线性字节码、跳转回填正确、函数独立成 Chunk。只差 VM 来真正执行了。

┌─ 📌 阶段 ⑥ 小结 ────────────────────────────────────┐
│  ✅ 你刚刚完成的事：                                            │
│    • 36 条 OpCode 指令集（栈式 VM 设计）                         │
│    • Chunk 容器：字节码流 + 常量池去重 + 行号表                  │
│    • 跳转回填三剑客：emitJump / patchJump / emitLoop             │
│    • Codegen 17 个 visit 全部实现，含 if/while/&amp;&amp;/|| 短路        │
│    • 函数独立 Chunk + functions 表（支持相互递归）                │
│  📊 18 个文件已经填了 16 个                                       │
│  ⏸ 还差最后一步：                                                │
│    • VM 执行字节码（阶段 ⑦）——只有它跑起来才是真编译器          │
│  📌 进入下阶段前务必：                                            │
│    git add . &amp;&amp; git commit -m "stage6: bytecode codegen"         │
│  💡 本阶段最大领悟：                                              │
│    "回填 = 留个洞，回头补——这是系统编程的通用模式：             │
│     汇编器、链接器、JIT、序列化都用它"                            │
└──────────────────────────────────────────────────┘

# §08 阶段⑦ VM 栈式虚拟机（约 3.5 h）

┌─ 🎯 阶段 ⑦ 目标卡片 ──────────────────────────────────┐
│  ⏱ 预计 3.5 小时                                                │
│  📂 新增/修改文件：                                              │
│    src/runtime/value.h          (Value = variant&lt;...>)          │
│    src/runtime/vm.h/.cpp        (栈式虚拟机主调度)              │
│    src/main.cpp                 (接入 :run 一键执行)            │
│  ✅ 完成后能做的事：                                             │
│    mycc> :run  fn fib(n) { if (n &lt; 2) return n;                 │
│                            return fib(n-1) + fib(n-2); }        │
│                print fib(20);                                   │
│    6765                                                          │
│  ⚠ 本阶段难点 TOP 3：                                            │
│    ① 16 位跳转偏移怎么读？小端解码 + ip 自增                    │
│    ② 函数调用栈帧怎么管？CallFrame 数组保存返回信息             │
│    ③ 局部变量栈偏移怎么算？base + slot                          │
└──────────────────────────────────────────────────┘

# §8.1 灵魂三问：栈式 vs 寄存器式 VM

问题 1：什么叫"栈式"？为什么 Java、Python、Lua 都用栈式？

栈式 VM：所有运算的中间值都放在一个**求值栈（operand stack）**上：

源码：  a + b * c
栈状态变化：
  LOAD a              [a]
  LOAD b              [a, b]
  LOAD c              [a, b, c]
  MUL                 [a, b*c]      ← 弹两个、算完压回
  ADD                 [a+b*c]       ← 同上

寄存器式 VM（如 Lua 5.x、Dalvik）：每条指令带 3 个操作数：

  LOAD R1, a
  LOAD R2, b
  LOAD R3, c
  MUL  R4, R2, R3
  ADD  R5, R1, R4

维度	栈式	寄存器式
指令数	多（每个值都要 PUSH/POP）	少 30%~50%
指令长度	短（很多 1 字节）	长（要带 3 个操作数）
编译器复杂度	简单（栈语义自动跟着递归走）	复杂（要做寄存器分配）
代表实现	JVM、CPython、Lua 4 之前、.NET CLR	Lua 5、Dalvik、V8 Ignition

💡 mycc 选栈式——理由就一个：和 AST 递归求值语义天然对齐。visit(BinOp) 里递归编译左右子树后发个 ADD，栈上数据正好对——根本不用考虑"算出来该放哪个寄存器"。这种编译器友好性正是教学/原型语言的首选。

问题 2：那解释循环（main loop）长啥样？

经典的 fetch-decode-execute 三步：

while (true) {
    OpCode op = static_cast<OpCode>(*ip++);    // fetch
    switch (op) {                              // decode
        case OpCode::ADD: { ... } break;       // execute
        case OpCode::HALT: return;
        ...
    }
}

这就是物理 CPU 在做的事——只是用 C++ 写出来了。理解这个循环 = 理解了 99% 的虚拟机。

问题 3：递归调用（fib）怎么不爆栈？mycc 的"栈"和宿主机的栈一回事吗？

完全两回事。这是新人最迷惑的点：

	宿主机 C++ 栈	mycc 求值栈	mycc 调用栈
是谁的	OS 给进程的	VM 内部的 `vector<Value>`	VM 内部的 `vector<CallFrame>`
大小	通常 8 MB	我们设上限 1024（够用）	我们设上限 64
递归 fib(30)	增 30 个 C++ 栈帧	中间值蹦来蹦去	增 30 个 mycc 栈帧

我们用一个 while 循环驱动 fetch-decode-execute——整个解释循环在 C++ 里只占 1 个栈帧。fib(30) 的"递归"是在 mycc 的 CallFrame 数组里堆叠的，不会让 C++ 栈爆掉。

📌 这种"用堆模拟栈"的设计是 VM 能跑得"比宿主机更深的递归"的原因。理论上，mycc 只要内存够，能递归到 64 层（我们设的上限）——不受 C++ 8MB 栈空间限制。

# §8.2 Value 与求值栈

mycc 是动态类型语言（运行期才知道一个值是 number 还是 string），所以运行期 Value 必须是多态容器——这是 std::variant 最经典的用武之地。

src/runtime/value.h：

#pragma once
#include <cstddef>
#include <ostream>
#include <string>
#include <variant>

namespace mycc {

// 运行期值类型——五种之一
struct Nil {};   // 用空类区分 nil 和 false
inline bool operator==(Nil, Nil) { return true; }

using Value = std::variant<
    Nil,            // index 0
    bool,           // index 1
    double,         // index 2
    std::string,    // index 3
    std::size_t     // index 4：函数索引（指向 functions 表）—— 简化设计
>;

// ----- 真值判定（控制流用）-----
inline bool isTruthy(const Value& v) {
    if (std::holds_alternative<Nil>(v))    return false;
    if (std::holds_alternative<bool>(v))   return std::get<bool>(v);
    if (std::holds_alternative<double>(v)) return std::get<double>(v) != 0.0;
    return true;   // string 非空、function 总是真
}

// ----- 调试输出 -----
inline std::ostream& operator<<(std::ostream& os, const Value& v) {
    std::visit([&](auto&& x) {
        using T = std::decay_t<decltype(x)>;
        if constexpr (std::is_same_v<T, Nil>)         os << "nil";
        else if constexpr (std::is_same_v<T, bool>)   os << (x ? "true" : "false");
        else if constexpr (std::is_same_v<T, double>) os << x;
        else if constexpr (std::is_same_v<T, std::string>) os << x;
        else if constexpr (std::is_same_v<T, std::size_t>) os << "<fn#" << x << ">";
    }, v);
    return os;
}

}  // namespace mycc

🤔 为什么函数也是 Value 的一种？ 因为 mycc 支持 let f = add;（函数赋给变量）这种"函数作为一等公民"的特性。让函数能装进 Value，就能压进栈、当参数、当返回值——为未来的闭包、高阶函数留路。

# §8.3 VM 主体：fetch-decode-execute

src/runtime/vm.h：

#pragma once
#include "../codegen/chunk.h"
#include "value.h"
#include <unordered_map>
#include <vector>
#include <string>

namespace mycc {

// 调用栈帧：每个函数调用对应一个 CallFrame
struct CallFrame {
    const Chunk* chunk;       // 当前执行的字节码
    size_t       ip;          // 指令指针（chunk->code 的下标）
    size_t       slotBase;    // 该函数局部变量在求值栈中的起始位置
    std::string  name;        // 调试用
};

class VM {
public:
    // 注入：编译期产物（主 chunk + 函数表）
    void load(Chunk topChunk, std::unordered_map<std::string, Chunk> fns);

    // 执行：从主 chunk 开始
    void run();

private:
    // ----- 编译期产物 -----
    Chunk                                     top_;
    std::unordered_map<std::string, Chunk>    fns_;
    std::vector<const Chunk*>                 fnTable_;     // 索引化访问，加速 CALL
    std::unordered_map<std::string, size_t>   fnIndex_;     // 函数名 → fnTable_ 索引

    // ----- 运行期状态 -----
    std::vector<Value>     stack_;             // 求值栈
    std::vector<CallFrame> frames_;            // 调用栈
    std::unordered_map<std::string, Value> globals_;

    // ----- 栈操作辅助 -----
    void  push(Value v) { stack_.push_back(std::move(v)); }
    Value pop()          { Value v = std::move(stack_.back()); stack_.pop_back(); return v; }
    Value& peek(size_t depth = 0) { return stack_[stack_.size() - 1 - depth]; }

    // ----- 字节码解码 -----
    uint8_t  readByte();
    uint16_t readU16();
    Constant readConstant();

    // ----- 算术辅助：要求两端都是 number ----- 
    void binaryArith(OpCode op, int line);
    void binaryCmp  (OpCode op, int line);

    // ----- 错误 -----
    [[noreturn]] void runtimeError(const std::string& msg, int line);
};

}  // namespace mycc

src/runtime/vm.cpp（核心 600 字节码循环）：

#include "vm.h"
#include <iostream>
#include <stdexcept>
#include <variant>

namespace mycc {

void VM::load(Chunk topChunk, std::unordered_map<std::string, Chunk> fns) {
    top_ = std::move(topChunk);
    fns_ = std::move(fns);
    fnTable_.clear();
    fnIndex_.clear();
    for (auto& [name, c] : fns_) {
        fnIndex_[name] = fnTable_.size();
        fnTable_.push_back(&c);
    }
}

uint8_t VM::readByte() {
    auto& f = frames_.back();
    return f.chunk->code[f.ip++];
}
uint16_t VM::readU16() {
    uint16_t lo = readByte();
    uint16_t hi = readByte();
    return lo | (hi << 8);
}
Constant VM::readConstant() {
    return frames_.back().chunk->constants[readU16()];
}

void VM::runtimeError(const std::string& msg, int line) {
    std::cerr << "[Runtime] line " << line << ": " << msg << "\n";
    // 打印调用栈（栈回溯）
    for (auto it = frames_.rbegin(); it != frames_.rend(); ++it) {
        std::cerr << "  in " << it->name << "\n";
    }
    throw std::runtime_error(msg);
}

void VM::binaryArith(OpCode op, int line) {
    Value b = pop(), a = pop();
    if (!std::holds_alternative<double>(a) || !std::holds_alternative<double>(b)) {
        runtimeError("operands must be numbers", line);
    }
    double x = std::get<double>(a), y = std::get<double>(b);
    switch (op) {
        case OpCode::ADD: push(x + y); break;
        case OpCode::SUB: push(x - y); break;
        case OpCode::MUL: push(x * y); break;
        case OpCode::DIV:
            if (y == 0.0) runtimeError("divide by zero", line);
            push(x / y); break;
        case OpCode::MOD:
            if (y == 0.0) runtimeError("mod by zero", line);
            push(std::fmod(x, y)); break;
        default: break;
    }
}
void VM::binaryCmp(OpCode op, int line) {
    Value b = pop(), a = pop();
    if (op == OpCode::EQ)  { push(a == b); return; }
    if (op == OpCode::NEQ) { push(!(a == b)); return; }
    if (!std::holds_alternative<double>(a) || !std::holds_alternative<double>(b)) {
        runtimeError("comparison operands must be numbers", line);
    }
    double x = std::get<double>(a), y = std::get<double>(b);
    switch (op) {
        case OpCode::LT: push(x <  y); break;
        case OpCode::LE: push(x <= y); break;
        case OpCode::GT: push(x >  y); break;
        case OpCode::GE: push(x >= y); break;
        default: break;
    }
}

// ============================================================
//  主循环——fetch / decode / execute
// ============================================================
void VM::run() {
    // 准备主栈帧
    frames_.clear();
    frames_.push_back({ &top_, 0, 0, "<top>" });
    stack_.clear();

    while (true) {
        CallFrame& fr = frames_.back();
        int line = fr.chunk->lines[fr.ip];   // 当前指令行号（出错时用）
        OpCode op = static_cast<OpCode>(readByte());

        switch (op) {
            // -------- 字面量 --------
            case OpCode::CONST: {
                Constant c = readConstant();
                std::visit([&](auto&& v) { push(Value{v}); }, c);
                break;
            }
            case OpCode::NIL:   push(Nil{});   break;
            case OpCode::TRUE:  push(true);    break;
            case OpCode::FALSE: push(false);   break;

            // -------- 算术 / 比较 --------
            case OpCode::ADD: case OpCode::SUB: case OpCode::MUL:
            case OpCode::DIV: case OpCode::MOD:
                binaryArith(op, line); break;

            case OpCode::EQ: case OpCode::NEQ: case OpCode::LT:
            case OpCode::LE: case OpCode::GT: case OpCode::GE:
                binaryCmp(op, line); break;

            case OpCode::NEG: {
                Value a = pop();
                if (!std::holds_alternative<double>(a))
                    runtimeError("unary - needs number", line);
                push(-std::get<double>(a));
                break;
            }
            case OpCode::NOT: {
                Value a = pop();
                push(!isTruthy(a));
                break;
            }

            // -------- 变量 --------
            case OpCode::LOAD_GLOBAL: {
                Constant c = readConstant();
                const auto& name = std::get<std::string>(c);
                // 优先查函数表（函数名当作全局符号）
                auto it = fnIndex_.find(name);
                if (it != fnIndex_.end()) { push(it->second); break; }
                auto it2 = globals_.find(name);
                if (it2 == globals_.end())
                    runtimeError("undefined variable: " + name, line);
                push(it2->second);
                break;
            }
            case OpCode::STORE_GLOBAL: {
                Constant c = readConstant();
                globals_[std::get<std::string>(c)] = peek();
                break;
            }
            case OpCode::LOAD_LOCAL: {
                uint16_t slot = readU16();
                push(stack_[fr.slotBase + slot]);
                break;
            }
            case OpCode::STORE_LOCAL: {
                uint16_t slot = readU16();
                stack_[fr.slotBase + slot] = peek();   // 不弹（赋值是表达式）
                break;
            }

            // -------- 控制流 --------
            case OpCode::JUMP: {
                uint16_t off = readU16();
                fr.ip += off;
                break;
            }
            case OpCode::JUMP_IF_FALSE: {
                uint16_t off = readU16();
                if (!isTruthy(peek())) fr.ip += off;
                break;
            }
            case OpCode::JUMP_IF_TRUE: {
                uint16_t off = readU16();
                if (isTruthy(peek())) fr.ip += off;
                break;
            }
            case OpCode::POP_JUMP_IF_FALSE: {
                uint16_t off = readU16();
                Value v = pop();
                if (!isTruthy(v)) fr.ip += off;
                break;
            }
            case OpCode::LOOP: {
                uint16_t off = readU16();
                fr.ip -= off;
                break;
            }

            // -------- 函数调用 --------
            case OpCode::CALL: {
                uint16_t argc = readU16();
                // 栈布局：[..., fnIndex, arg0, arg1, ..., arg(n-1)] ←TOP
                Value& callee = stack_[stack_.size() - argc - 1];
                if (!std::holds_alternative<std::size_t>(callee))
                    runtimeError("can only call functions", line);
                size_t fnIdx = std::get<std::size_t>(callee);
                if (fnIdx >= fnTable_.size())
                    runtimeError("invalid function index", line);

                if (frames_.size() >= 64)
                    runtimeError("stack overflow (recursion too deep)", line);

                CallFrame nf;
                nf.chunk    = fnTable_[fnIdx];
                nf.ip       = 0;
                nf.slotBase = stack_.size() - argc;     // 实参就地变成 locals
                nf.name     = nf.chunk->name;
                frames_.push_back(nf);
                break;
            }

            case OpCode::RETURN: {
                Value rv = pop();
                CallFrame done = frames_.back();
                frames_.pop_back();
                // 弹掉被调函数的所有 locals + callee 本身
                stack_.resize(done.slotBase - 1);
                push(std::move(rv));
                break;
            }

            // -------- I/O / 控制 --------
            case OpCode::PRINT: {
                std::cout << pop() << "\n";
                break;
            }
            case OpCode::POP:   pop(); break;
            case OpCode::DUP:   push(peek()); break;
            case OpCode::HALT:  return;

            default:
                runtimeError("unknown opcode", line);
        }
    }
}

}  // namespace mycc

📌 OpCode::CALL 的栈布局是新人最容易绕晕的部分——画图一次就懂：

编译期生成的字节码：
  LOAD_GLOBAL  add        ; push 函数索引
  CONST 3                 ; push 3
  CONST 4                 ; push 4
  CALL  2                 ; argc = 2

进入 CALL 时，栈顶向下数 = [add, 3, 4]
  slotBase = stack_.size() - argc = 指向 3 的位置
  ↓
函数执行时：
  LOAD_LOCAL 0  → push stack_[slotBase+0] = 3   (a)
  LOAD_LOCAL 1  → push stack_[slotBase+1] = 4   (b)
RETURN 时：
  弹回 done.slotBase - 1 → 把 [add, 3, 4] 全清掉
  把返回值 push 回去——栈里只剩 [7]，符合调用前对调用者的承诺

# §8.4 故意造 bug：跳转偏移错位

学到这里，你应该已经能跑大部分小程序了。但回填的 +2/-2 偏移是新人通病——我们故意造一个 bug，让你亲眼看错位现场，再修复。

故意写错 Chunk::patchJump（暂时把 -2 去掉）：

// chunk.cpp 中故意改坏：
void Chunk::patchJump(size_t idx) {
    size_t jump = code.size() - idx;     // ❌ 故意漏掉 -2
    code[idx]     = jump & 0xFF;
    code[idx + 1] = (jump >> 8) & 0xFF;
}

重新编译运行：

mycc> :run  if (1 == 1) { print 100; } else { print 200; }
[Runtime] line 1: unknown opcode
  in &lt;top>

为什么会"unknown opcode"？ 因为跳转过头了 2 字节，落到了某个指令的操作数中间——把操作数当成了指令字节。这个错误信息正好暴露问题：ip 没停在指令边界上。

修复：还原 -2：

void Chunk::patchJump(size_t idx) {
    size_t jump = code.size() - idx - 2;   // ✅
    ...
}

💡 教学价值：90% 的字节码跳转 bug 都是 ±2 的偏差。一旦你亲眼见过 "unknown opcode"，以后写 emit/patch 系列代码就会下意识地画字节图算偏移——这种"被坑过的肌肉记忆"是教学最值钱的部分。

# §8.5 接入 main：`:run` 一键执行 + 端到端验证

修改 src/main.cpp：

#include "runtime/vm.h"

// 在 :dump 之后追加：
else if (cmd == ":run") {
    Lexer lex(rest, "<repl>");
    auto toks = lex.scanAll();
    Parser psr(std::move(toks));
    auto prog = psr.parseProgram();

    TypeChecker tc;
    tc.visit(*prog);

    Codegen cg;
    Chunk top = cg.compile(*prog);

    VM vm;
    vm.load(std::move(top), std::move(cg.functions));
    vm.run();
}

更新 CMakeLists.txt：

add_executable(mycc
    src/main.cpp
    src/lexer/lexer.cpp
    src/parser/parser.cpp
    src/sema/type_checker.cpp
    src/codegen/opcode.cpp
    src/codegen/chunk.cpp
    src/codegen/codegen.cpp
    src/runtime/vm.cpp
)

🧪 端到端三连击验证：

$ cmake --build build &amp;&amp; ./build/mycc

# ① 简单算术
mycc> :run  print 1 + 2 * 3 - 4;
3

# ② 控制流
mycc> :run  let i = 0; while (i &lt; 5) { print i; i = i + 1; }
0
1
2
3
4

# ③ 递归（最考验调用栈）
mycc> :run  fn fib(n) {
              if (n &lt; 2) return n;
              return fib(n - 1) + fib(n - 2);
            }
            print fib(10);
55

🎉 mycc 真的"活"了——从源码字符串到屏幕输出，全链路打通。fib(10) 这一行下面，是你亲手写的：

Lexer 把 fn fib(n)... 切成 32 个 Token
Parser 拼出 11 节点的 AST
TypeChecker 验证 17 个 visit 全过
Codegen 生成 47 字节字节码（fib chunk）
VM 调用栈最深递归到 11 层

┌─ 📌 阶段 ⑦ 小结 ────────────────────────────────────┐
│  ✅ 你刚刚完成的事：                                            │
│    • Value = std::variant 五型动态值                             │
│    • fetch-decode-execute 经典三步主循环                          │
│    • 36 条 OpCode 全部派发实现                                    │
│    • CallFrame 调用栈（独立于 C++ 栈）                            │
│    • 故意跳转偏移 bug → unknown opcode → 修复                    │
│  📊 18 个文件已全部填完！                                         │
│  🎯 mycc 已经是一个会跑的语言了——能算、能 if、能 while、能递归  │
│  📌 进入下阶段前务必：                                            │
│    git add . &amp;&amp; git commit -m "stage7: bytecode VM"              │
│  💡 本阶段最大领悟：                                              │
│    "VM = 写在 C++ 里的 fetch-decode-execute 循环——              │
│     物理 CPU 在硅片上做的事，我们用一个 while 模拟出来了"        │
└──────────────────────────────────────────────────┘

# §09 阶段⑧ 异常体系 + REPL 完善（约 2 h）

┌─ 🎯 阶段 ⑧ 目标卡片 ──────────────────────────────────┐
│  ⏱ 预计 2 小时                                                  │
│  📂 修改文件：                                                   │
│    src/common/error.h           (统一四级异常类树)              │
│    src/lexer/lexer.cpp          (改抛 LexError)                 │
│    src/parser/parser.cpp        (改抛 ParseError)               │
│    src/sema/type_checker.cpp    (改抛 TypeError)                │
│    src/runtime/vm.cpp           (改抛 RuntimeError)             │
│    src/main.cpp                 (顶层 try-catch + 文件模式)     │
│  ✅ 完成后能做的事：                                             │
│    $ ./mycc examples/hello.mycc                                 │
│    Hello, mycc!                                                 │
│                                                                  │
│    $ ./mycc examples/bad.mycc                                   │
│    [Parse] line 3: expected ';' but got 'let'                   │
│    [exit code 2]                                                │
│  ⚠ 本阶段难点 TOP 1：                                            │
│    异常类型与退出码怎么对应？答：四级类树 + 顶层捕获分发         │
└──────────────────────────────────────────────────┘

# §9.1 灵魂三问：为什么需要四级异常类树？

问题 1：直接 throw std::runtime_error("xxx") 不行吗？

行，但最差。理由：

类型信息丢失——你只能用字符串描述错误，无法区分"语法错"和"运行时错"
退出码无法分流——CI 系统看到 exit 1 不知道是哪个阶段的错
诊断信息缺失——没有行号、文件名、上下文

问题 2：那为什么不每个阶段定义自己的异常类，互不继承？

那就没有共同基类——main.cpp 顶层就要写 4 个 catch 分支。每加一种错误类型就要改 main——违反开闭原则。

问题 3：标准答案是什么？

金字塔型异常类树——所有自定义异常都继承自一个共同基类，基类继承自 std::runtime_error：

            std::runtime_error
                    ▲
                    │
              MyccError              ← 我们的根
              ▲    ▲    ▲    ▲
              │    │    │    │
       LexError ParseError TypeError RuntimeError

带来的好处：

main 可以一句 catch (const MyccError& e) 接住全部
想区分时再用 dynamic_cast 或 typeid 分流
第三方加自定义错误类型只要继承 MyccError 即可

# §9.2 四级异常类树

src/common/error.h：

#pragma once
#include <stdexcept>
#include <string>

namespace mycc {

// ============================================================
//  根异常：所有 mycc 的诊断都从它派生
//  携带「行号 + 文件名」诊断信息
// ============================================================
class MyccError : public std::runtime_error {
public:
    MyccError(const std::string& stage,
              const std::string& msg,
              int line = 0,
              std::string file = "<repl>")
        : std::runtime_error(format(stage, msg, line, file))
        , line_(line)
        , file_(std::move(file)) {}

    int                line() const { return line_; }
    const std::string& file() const { return file_; }

    // 子类用来上报退出码（main 用）
    virtual int exitCode() const = 0;

private:
    static std::string format(const std::string& stage,
                              const std::string& msg,
                              int line,
                              const std::string& file) {
        std::string r = "[" + stage + "] ";
        if (!file.empty() && file != "<repl>") r += file + ":";
        if (line > 0) r += "line " + std::to_string(line) + ": ";
        r += msg;
        return r;
    }

    int         line_;
    std::string file_;
};

// ============================================================
//  四个阶段各一种
//  退出码沿用 Unix 惯例：1=用户错，2=参数/语法，3=类型/语义，4=运行时
// ============================================================
class LexError : public MyccError {
public:
    LexError(const std::string& msg, int line, std::string file = "<repl>")
        : MyccError("Lex", msg, line, std::move(file)) {}
    int exitCode() const override { return 2; }
};

class ParseError : public MyccError {
public:
    ParseError(const std::string& msg, int line, std::string file = "<repl>")
        : MyccError("Parse", msg, line, std::move(file)) {}
    int exitCode() const override { return 2; }
};

class TypeError : public MyccError {
public:
    TypeError(const std::string& msg, int line, std::string file = "<repl>")
        : MyccError("Type", msg, line, std::move(file)) {}
    int exitCode() const override { return 3; }
};

class RuntimeError : public MyccError {
public:
    RuntimeError(const std::string& msg, int line, std::string file = "<repl>")
        : MyccError("Runtime", msg, line, std::move(file)) {}
    int exitCode() const override { return 4; }
};

}  // namespace mycc

# §9.3 各模块切换到自定义异常

把之前各阶段的 std::runtime_error 全部替换。以 lexer.cpp 为例：

// 原：throw std::runtime_error("unterminated string");
// 改：
#include "../common/error.h"
throw LexError("unterminated string", line_, file_);

parser.cpp 同理用 ParseError、type_checker.cpp 用 TypeError、vm.cpp 的 runtimeError(...) 函数体改成：

[[noreturn]] void VM::runtimeError(const std::string& msg, int line) {
    std::string trace;
    for (auto it = frames_.rbegin(); it != frames_.rend(); ++it) {
        trace += "\n  in " + it->name;
    }
    throw RuntimeError(msg + trace, line);
}

📌 这里的 [[noreturn]] 属性（C++11）告诉编译器这个函数不会正常返回——可以让 runtimeError(...); break; 中的 break 不报"unreachable"警告，也让调用点不必再写 return 兜底。这是个专业级的小细节。

# §9.4 接入文件模式 + 顶层异常处理

最终版 src/main.cpp：

#include "common/error.h"
#include "lexer/lexer.h"
#include "parser/parser.h"
#include "sema/type_checker.h"
#include "codegen/codegen.h"
#include "runtime/vm.h"
#include <fstream>
#include <iostream>
#include <sstream>
#include <string>

using namespace mycc;

// ----- 一次完整编译 + 执行 -----
static int compileAndRun(const std::string& src, const std::string& filename) {
    try {
        Lexer lex(src, filename);
        auto toks = lex.scanAll();

        Parser psr(std::move(toks), filename);
        auto prog = psr.parseProgram();

        TypeChecker tc(filename);
        tc.visit(*prog);

        Codegen cg;
        Chunk top = cg.compile(*prog);

        VM vm;
        vm.load(std::move(top), std::move(cg.functions));
        vm.run();
        return 0;
    } catch (const MyccError& e) {
        std::cerr << e.what() << "\n";
        return e.exitCode();
    } catch (const std::exception& e) {
        std::cerr << "[Internal] " << e.what() << "\n";
        return 99;
    }
}

// ----- 文件模式 -----
static int runFile(const std::string& path) {
    std::ifstream in(path);
    if (!in) {
        std::cerr << "[IO] cannot open: " << path << "\n";
        return 1;
    }
    std::stringstream ss;
    ss << in.rdbuf();
    return compileAndRun(ss.str(), path);
}

// ----- REPL 模式 -----
static int runRepl() {
    std::cout << "mycc 0.1 — :h for help, :q to quit\n";
    std::string line;
    while (true) {
        std::cout << "mycc> ";
        if (!std::getline(std::cin, line)) break;
        if (line.empty()) continue;

        // 元命令解析
        std::string cmd = line, rest;
        if (auto sp = line.find(' '); sp != std::string::npos) {
            cmd  = line.substr(0, sp);
            rest = line.substr(sp + 1);
        }

        if (cmd == ":q") break;
        if (cmd == ":h") {
            std::cout << "  :run  <code>    编译并执行\n"
                         "  :dump <code>    显示字节码\n"
                         "  :tcheck <code>  仅类型检查\n"
                         "  :q              退出\n";
            continue;
        }

        std::string code = (cmd[0] == ':') ? rest : line;
        // 在 REPL 里，异常已经在 compileAndRun 内处理，不会让 REPL 退出
        compileAndRun(code, "<repl>");
    }
    return 0;
}

// ----- 入口 -----
int main(int argc, char** argv) {
    if (argc == 1) return runRepl();
    if (argc == 2) return runFile(argv[1]);
    std::cerr << "Usage: mycc [file.mycc]\n";
    return 1;
}

# §9.5 端到端最终验证

新建 examples/hello.mycc：

fn greet(name) {
    print "Hello, " + name + "!";
}
greet("mycc");
greet("world");

新建 examples/fib.mycc：

fn fib(n) {
    if (n &lt; 2) return n;
    return fib(n - 1) + fib(n - 2);
}
let i = 0;
while (i &lt; 10) {
    print fib(i);
    i = i + 1;
}

新建 examples/bad.mycc（故意三种错）：

let x = 1
let y = 2;            // ① 上一行漏分号 → ParseError
print 1 + "abc";      // ② 类型错误 → TypeError（已被 ① 拦下，演示用）
print 1 / 0;          // ③ 除零 → RuntimeError

🧪 运行结果：

$ ./build/mycc examples/hello.mycc
Hello, mycc!
Hello, world!
$ echo $?
0

$ ./build/mycc examples/fib.mycc
0
1
1
2
3
5
8
13
21
34
$ echo $?
0

$ ./build/mycc examples/bad.mycc
[Parse] examples/bad.mycc:line 2: expected ';' after expression
$ echo $?
2

$ ./build/mycc examples/divzero.mycc      # 单独触发 RuntimeError
[Runtime] examples/divzero.mycc:line 1: divide by zero
  in &lt;top>
$ echo $?
4

🎉 mycc 1.0 完整收官——错误诊断带文件、带行号、带阶段、带退出码，已经达到生产级编译器的诊断风格。

┌─ 📌 阶段 ⑧ 小结 ────────────────────────────────────┐
│  ✅ 你刚刚完成的事：                                            │
│    • MyccError 四级异常类树                                       │
│    • [[noreturn]] 让 runtimeError 不再需要兜底 return            │
│    • 顶层 try-catch 收口 + 阶段化退出码（2/3/4）                 │
│    • 文件模式 + REPL 模式双入口                                   │
│  📊 18/18 文件全部完成，~2700 行代码                              │
│  📌 完工 commit：                                                │
│    git add . &amp;&amp; git commit -m "stage8: error tree &amp; file mode"   │
│  💡 本阶段最大领悟：                                              │
│    "好的错误信息 = 阶段名 + 文件 + 行号 + 描述——               │
│     这是用户对编译器最直接的体验"                                 │
└──────────────────────────────────────────────────┘

# §10 项目总结分析

# §10.1 跑完一遍的成绩单

经过 8 个阶段约 22 小时的从零到一，你已经亲手写出：

维度	数据
代码总量	~2700 行 C++ + ~150 行 CMake
文件数	18 个 .h/.cpp + 4 个 .mycc 例子
支持的语法	数字/字符串/布尔字面量、9 种运算符、变量、if/else、while、函数、递归、`&&`/`\\|\\|` 短路
架构层数	5 段：Lexer → Parser → TypeChecker → Codegen → VM
Visitor 实现	17 种节点 × 2 个 Visitor（TypeChecker、Codegen）= 34 个 visit 函数
OpCode 数	36 条
能跑的最复杂程序	fib(20) 递归、含 if/while/return 的 100 行小程序

# §10.2 17 章知识点回检

卷一章节	在 mycc 里出现的位置	形态
01 数据类型 / 变量	`Value` 多型、`Token` 多载荷	`std::variant`
02 控制结构	Parser 的 `parseIf/parseWhile`、VM 的 `JUMP/LOOP`	switch + 回填
03 函数 / 引用	17 × 2 个 visit 函数；`ASTPtr&` 引用传递	大量函数定义/重载
04 类 / 对象	AST 12 节点继承体系、Visitor 类、Lexer/Parser/VM 四大类	抽象类 + 派生
05 继承 / 多态	`AstNode` 抽象基类、双 `accept`	虚函数 + 双重分派
06 模板	`AstVisitor<R>` 模板基类、`std::variant<...>` 实例	类模板
07 STL 容器	`vector` 字节码、`unordered_map` 全局表、`stack` 思想用 vector 实现	6 种容器都用上了
08 STL 算法	`lexer.cpp` 的 `std::isdigit/isalpha`、`addConstant` 线性查重	algorithm 头
09 智能指针	AST 树用 `shared_ptr<AstNode>`	RAII
10 异常	MyccError 四级类树、`[[noreturn]]`	try-catch
11 文件流	`runFile` 用 `std::ifstream + stringstream`	RAII 流
12 字符串	`string`/`string_view` 处理源码	标准库
13 移动语义	`Value pop()` 用 `std::move`、`Chunk` 移交所有权	rvalue ref
14 lambda	反汇编时 `std::visit([&](auto&&){...})`	泛型 lambda
15 命名空间	全部代码包在 `namespace mycc`	namespace
16 多文件项目	18 文件 / CMakeLists 组织	模块化
17 综合实战	就是 mycc 本身	—

✅ 17 章一个不漏——这就是当初选 mycc 而非别的案例的理由：它把 C++ 17 章语言特性自然地、紧密地揉在一起，而不是为凑章节硬塞知识点。

# §11 项目技术思考

# §11.1 AST 用 `shared_ptr` 还是 `unique_ptr`？

mycc 用的是 shared_ptr<AstNode>。很多教材会喷这是错的——AST 是树形所有权，应该用 unique_ptr。我们来辩证看待：

支持 unique_ptr 的理由（多数生产编译器选这个）：

AST 是严格树形（无环），节点不共享 → unique_ptr 语义最贴
性能更好（无原子计数开销）
"唯一所有权"概念清晰，谁是 parent 一目了然

为什么 mycc 选 shared_ptr（教学场景的合理选择）：

REPL 友好：:tcheck <code> 后 :dump <same_code> 可能想复用 AST——unique_ptr 一旦移交就失效，教学时学生很容易踩坑
代码示例清晰：auto rhs = parseAdd(); lhs = make_shared<BinOp>(op, lhs, rhs, line)——用 shared_ptr 写起来不需要 std::move(lhs)，让初学者把注意力放在编译器逻辑上，而不是所有权语义
测试方便：单元测试想存一份 AST 副本时，shared_ptr 一个 = 就完成

💡 结论：正确的工程选择是 unique_ptr，正确的教学选择是 shared_ptr。等你完成 mycc 后，把它重构成 unique_ptr 版本——这会让你深入理解所有权语义，是绝佳练习题。

# §11.2 Visitor 模式的两种风格

我们在 mycc 里用了模板版 Visitor：

template <typename R>
class AstVisitor {
public:
    virtual R visit(NumLit&) = 0;
    ...
};

GoF 经典版（无模板）只支持单一返回类型：

class AstVisitor {
public:
    virtual void visit(NumLit&) = 0;     // 永远 void
    ...
};

模板版的优势：

TypeChecker 可以 AstVisitor<Type>、Codegen 可以 AstVisitor<void>、Evaluator 可以 AstVisitor<Value> ——同一套接口、不同语义
编译期类型检查，不像 GoF 版本要靠成员变量传递返回值

模板版的代价：

必须在头文件里写实现（模板特化要求）
节点类的 accept 函数也得为每个返回类型重载（mycc 里就是 acceptType + acceptCode）

mycc 选模板版——用一点点编译期开销，换运行期的零开销 + 编译期类型检查，是 modern C++ 的典型权衡。

# §11.3 字节码 vs 树解释 vs JIT

方案	实现难度	性能（fib(30)）	启动时间	代表
树遍历解释	⭐	800 ms	0 ms	Ruby 1.8
字节码 VM（mycc）	⭐⭐	250 ms	~10 ms（编译耗时）	CPython、Lua、Java
基线 JIT	⭐⭐⭐⭐	80 ms	~50 ms	V8 Ignition→Sparkplug
优化 JIT	⭐⭐⭐⭐⭐	15 ms	~200 ms	V8 TurboFan、HotSpot C2

🔭 下一步真心推荐的延伸：把 mycc 字节码解释循环用 threaded code（计算 goto，GNU 扩展 goto *labels[op]）替换 switch——性能能提升 ~30%，是从字节码 VM 走向 JIT 的第一站。

# §12 衔接与延伸

# §12.1 与 06 案例的差异

学过 06.迷你KV存储引擎器.md 的同学可能会问：mycc 和 KV 存储有啥本质区别？

维度	06 KV 存储	07 mycc（本案例）
核心问题	数据怎么持久化、怎么并发安全	源码怎么变成可执行行为
关键技术	LSM Tree、WAL、跳表、bloom filter	Lexer/Parser/AST/字节码/VM
C++ 重点	线程同步、文件 IO、内存映射	多态 + Visitor + 模板 + variant
典型领域	数据库、缓存、消息队列	编程语言、DSL、模板引擎、SQL 解析器

两者都用 std::variant，但用途完全不同：06 用它做 union 风格的 KV value 类型；07 用它做 AST 多态载荷 + 运行期动态值。这是 同一工具、不同问题 的鲜明对照——读完两个案例，你对 variant 的理解会立体很多。

# §12.2 三个延伸挑战

mycc 1.0 已完工，但还很简陋。下面三个挑战按难度递进，每个都能让你的语言再上一个台阶：

# 🥉 挑战一：加 `for` 语句（约 1 小时）

让 mycc 支持：

for (let i = 0; i &lt; 10; i = i + 1) {
    print i;
}

实现路径提示：

Lexer：加 for 关键字
Parser：parseFor() 把 for 直接脱糖成等价的 BlockStmt(LetDecl + WhileStmt)——AST 层根本看不到 for
Codegen / VM：完全不用动！

💡 这就是语法糖（syntactic sugar）——在前端把高阶构造翻译成低阶等价物，让后端复用现有逻辑。Java 的 enhanced for、C++ 的 range-based for 都是这么做的。

# 🥈 挑战二：加数组类型 `[1, 2, 3]`（约 3 小时）

让 mycc 支持：

let arr = [10, 20, 30];
print arr[0];        // 10
arr[1] = 99;
print arr[1];        // 99

实现路径提示：

Value 增加一型：std::shared_ptr<std::vector<Value>>
Lexer：[ ] 已是单字符 token，无需新增
Parser：新增 ArrayLit、IndexExpr 两个 AST 节点
OpCode 新增 4 条：MAKE_ARRAY n / INDEX_GET / INDEX_SET / ARRAY_LEN
VM：处理这 4 条新指令

💡 数组的核心难点是所有权——数组共享导致 arr2 = arr 时是浅拷贝。理解这个，就能理解 Python 的引用语义、Java 的引用类型。

# 🥇 挑战三：加闭包 `fn() { ... }`（约 8 小时，难度极高）

让 mycc 支持：

fn makeCounter() {
    let count = 0;
    return fn() {
        count = count + 1;
        return count;
    };
}
let c = makeCounter();
print c();    // 1
print c();    // 2
print c();    // 3

实现路径提示：

Upvalue 概念：内层函数引用外层函数的局部变量——外层退出后这些变量必须逃逸出栈
数据结构：Closure = { Chunk*, vector<Upvalue> } 替代裸 fnIndex
OpCode 新增：CLOSURE、GET_UPVALUE、SET_UPVALUE、CLOSE_UPVALUE
关键算法：变量逃逸（escape analysis）

💡 闭包是函数式编程的"灵魂能力"。完成它，你对 JavaScript 的 () => {...}、Python 的 def 嵌套、Lua 的 upvalue 都会有编译器实现层面的彻底理解——这是大厂面试官最喜欢问的题之一。

推荐参考：Robert Nystrom《Crafting Interpreters》第 25 章，把闭包讲得最清楚的中文/英文资料之一。

# §12.3 进入下一案例之前

如果你完成了 mycc 1.0 + 至少挑战一，请：

# ① 提交最终版
git add .
git commit -m "mycc 1.0: complete mini compiler & interpreter"

# ② 在 README.md 卷二导读里把本案例标为 ✅ 已完成

# ③ 自评：能不能在不看代码的情况下，把"五段式架构 + 17 个 visit + 跳转回填"
#         讲给同学听？讲得清楚——这个案例就真正属于你了

下一案例你将进入 🎯 卷三 - 高级专题——分布式、网络编程、性能调优。但底层思想是相通的：

mycc 的 Lexer/Parser → 网络协议解析（HTTP/Protobuf 都是"语法分析"）
mycc 的 VM → 协程调度器（都是 fetch-decode-execute 的 while 循环）
mycc 的字节码 → RPC 二进制格式（都是常量池 + 操作码序列）

编译原理不是孤岛——它是计算机科学的"通用语法"，无处不在。

┌──────────────────────────────────────────────────┐
│  🎓 mycc 项目正式收官！                                          │
│                                                                  │
│  从一个 main.cpp 空 REPL，到 18 个文件 2700 行的完整语言实现，  │
│  你刚刚走过的路，正是 Java 的 javac、Python 的 CPython、         │
│  V8 的 Ignition 都走过的路——**只是规模小一点**。                │
│                                                                  │
│  这不是终点。                                                    │
│  这是你"读懂任何语言实现"的起点。                                │
│                                                                  │
│  Happy hacking, future language designer.                       │
└──────────────────────────────────────────────────┘

📚 本案例参考资料：

Robert Nystrom《Crafting Interpreters》——本案例字节码部分的灵感主要来源

Aho 等《编译原理》（龙书）——理论根基

Lua 5.4 源码——栈式 VM 的工业实现典范

CPython 源码 Python/ceval.c——主调度循环的"教科书"

上次更新: 2026/06/28, 17:55:19

← 迷你KV存储引擎器 README→

迷你编译器解释器

# 第七章：C++ 迷你编译器解释器（mycc）

# 渐进学习节奏

# 案例元信息

# 项目结构

# 一条命令编译运行

# 目录快速导航

# 01.语言设计与五段式架构

# 1.1 mycc 语言能做什么

# 1.2 五段式架构总图

# 1.3 涉及知识点

# 02.REPL 骨架

# 2.1 创建项目空文件

# 2.2 灵魂三问

# 2.3 让程序能跑能退

# 03.Lexer 词法分析

# 3.1 灵魂三问：为什么先做词法

# 3.2 Token 数据结构

# 3.3 第一版 Lexer 只切数字

# 3.4 第二版 加运算符与空白

# 3.5 第三版 加标识符与关键字

# 3.6 第四版 加字符串与多字符运算符

# 04.AST 抽象语法树

# 4.1 灵魂三问：AST 到底是什么

# 4.2 AstNode 抽象基类

# 4.3 表达式节点四件套

# 4.4 语句节点八件套

# 05.Parser 递归下降

# 5.1 灵魂三问：为什么递归下降

# 5.2 Parser 类骨架

# 5.3 第一版 只解析整数表达式

# 5.4 第二版 加加减运算

# 5.5 第三版 加乘除与括号

# 5.6 故意造 bug：左结合错误

# 5.7 加语句：var / print / if / while

# 5.8 加函数定义与调用

# 06.Visitor 类型检查

# 6.1 灵魂三问：访问者解决什么

# 6.2 模板 Visitor 基类

# 6.3 TypeChecker 实现

# 6.4 符号表栈

# §07 阶段⑥ Codegen 字节码生成（约 4 h）

# §7.1 灵魂三问：为什么不直接树遍历执行？

# §7.2 OpCode 36 条指令

# §7.3 Chunk 字节码容器

# §7.4 Codegen 访问者

# §7.5 接入 main：:dump 反汇编

# §08 阶段⑦ VM 栈式虚拟机（约 3.5 h）

# §8.1 灵魂三问：栈式 vs 寄存器式 VM

# §8.2 Value 与求值栈

# §8.3 VM 主体：fetch-decode-execute

# §8.4 故意造 bug：跳转偏移错位

# §8.5 接入 main：:run 一键执行 + 端到端验证

# §09 阶段⑧ 异常体系 + REPL 完善（约 2 h）

# §9.1 灵魂三问：为什么需要四级异常类树？

# §9.2 四级异常类树

# §9.3 各模块切换到自定义异常

# §9.4 接入文件模式 + 顶层异常处理

# §9.5 端到端最终验证

# §10 项目总结分析

# §10.1 跑完一遍的成绩单

# §10.2 17 章知识点回检

# §11 项目技术思考

# §11.1 AST 用 shared_ptr 还是 unique_ptr？

# §11.2 Visitor 模式的两种风格

# §11.3 字节码 vs 树解释 vs JIT

# §12 衔接与延伸

# §12.1 与 06 案例的差异

# §12.2 三个延伸挑战

# 🥉 挑战一：加 for 语句（约 1 小时）

# 🥈 挑战二：加数组类型 [1, 2, 3]（约 3 小时）

# 🥇 挑战三：加闭包 fn() { ... }（约 8 小时，难度极高）

# §12.3 进入下一案例之前

# 3.4 第二版加运算符与空白

# 3.5 第三版加标识符与关键字

# 3.6 第四版加字符串与多字符运算符

# 5.3 第一版只解析整数表达式

# 5.4 第二版加加减运算

# 5.5 第三版加乘除与括号

# §7.5 接入 main：`:dump` 反汇编

# §8.5 接入 main：`:run` 一键执行 + 端到端验证

# §11.1 AST 用 `shared_ptr` 还是 `unique_ptr`？

# 🥉 挑战一：加 `for` 语句（约 1 小时）

# 🥈 挑战二：加数组类型 `[1, 2, 3]`（约 3 小时）

# 🥇 挑战三：加闭包 `fn() { ... }`（约 8 小时，难度极高）