编译器祛魅 (Compiler Demystification)

一个用于理解编译器工作原理的教育性项目。通过从简单到复杂的渐进式实现，让编译器不再神秘。

🎯 项目理念

"编译器祛魅" —— 让编译器从"黑盒"变成"透明盒"。

传统编译器课程往往只关注理论，而本项目通过可视化 + 交互式探索的方式，让你能够：

• 看到 代码如何被解析成 AST
• 追踪 控制流如何转化为 CFG
• 理解 作用域如何在栈上分配
• 观察 代码如何一步步生成汇编指令
• 执行 生成的汇编代码并查看运行时状态

📚 项目结构：多层次的学习路径

项目采用渐进式设计，从简单到复杂，逐层深入：

第一层：表达式解析器（优先级爬升）

位置: bnf/, precedence-climbing/

目标: 理解语法分析的本质

核心思考:

• 如何将文本解析成树结构？
• 运算符优先级如何实现？
• 递归下降 vs 优先级爬升：两种思路的对比

可视化: frontend/src/priority-climbing/

• AST 树可视化
• 栈式执行可视化（单调栈 + 操作数栈）
• 理解优先级爬升算法的数据结构本质

关键洞察: 优先级爬升算法 = 操作符单调递增栈 + 操作数栈。递归实现只是隐式栈，栈式实现让数据结构显式化。

第二层：完整编译器（CFG + 作用域）

位置: cfg/, statements/

目标: 理解控制流和作用域管理

核心思考:

• 如何将线性代码转换为控制流图？
• 基本块（Basic Block）的本质是什么？
• 作用域如何在栈上分配和管理？
• 变量遮蔽（shadowing）如何实现？

设计亮点:

1. Checkpoint 机制: 显式标记作用域边界，将作用域管理与 CFG 结构解耦
2. init 标志: 区分"声明"和"初始化"，正确处理变量遮蔽
3. 快照机制: 在 DFS 遍历中支持作用域状态的回溯

可视化:

• frontend/src/ast-cfg/: AST 和 CFG 的可视化
• frontend/src/stack-scope/: 栈布局和作用域链的可视化

第三层：代码生成与虚拟机

位置: cfg/src/assembly-generator.ts, cfg/src/assembly-vm.ts

目标: 理解代码生成和执行模型

核心思考:

• 如何从 CFG 生成汇编代码？
• 栈帧如何分配和回收？
• 寄存器如何分配？
• 如何优化生成的代码（基本块合并）？

可视化: frontend/src/codegen-vm/

• 汇编代码生成过程可视化
• 虚拟机执行可视化（寄存器、栈、标志位）
• 代码优化前后对比（基本块合并）

第四层：链接器与多文件编译

位置: linker/

目标: 理解链接过程和多文件编译

核心思考:

• 如何将多个源文件编译并链接在一起？
• 静态链接 vs 动态链接：两种链接方式的区别
• 符号解析和地址重定位如何实现？
• 库函数如何被链接到主程序？

设计亮点:

1. 静态链接: 编译时将所有符号解析为地址，生成单一可执行代码
2. 动态链接: 运行时按需加载库函数，支持跨段调用
3. 代码段管理: 每个库文件映射到独立的代码段（1000*N）
4. 符号表管理: 通过 libMap 管理动态加载的函数

可视化: frontend/src/linker/

• 多文件编辑器（主程序和库文件）
• 静态链接过程可视化
• 动态链接过程可视化（代码段分布、函数映射）
• 链接后的汇编代码和执行结果

关键洞察: 链接器是编译器和运行时之间的桥梁。静态链接在编译时完成所有符号解析，而动态链接将符号解析推迟到运行时，提供了更大的灵活性。

第五层：指针与内存管理

位置: pointer/

目标: 理解指针操作和内存间接访问

核心思考:

• 指针的本质是什么？如何表示内存地址？
• 取地址 & 和解引用 * 操作如何实现？
• 间接寻址（Indirect Addressing）在汇编层面如何工作？
• 指针作为函数参数如何传递和修改？

设计亮点:

1. 指针类型系统: 支持 int* 等指针类型声明
2. 间接寻址指令: 扩展 VM 支持 lir（Load Indirect from Register）和 sir（Store Indirect to Register）
3. 地址计算: 通过 lea 指令或手动计算实现取地址操作
4. 多级指针: 支持二级指针、多级指针等复杂场景

技术细节:

• 每个变量占 1 个地址单位（简化设计，便于教学）
• 指针变量存储地址值，通过间接寻址访问目标
• 支持指针作为函数参数，实现引用传递语义

测试用例: pointer/tests/

• test-pointer.txt: 基础指针操作
• test-double-pointer.txt: 二级指针
• test-multi-level-pointer.txt: 多级指针

关键洞察: 指针 = 地址值 + 间接寻址。理解指针的关键是理解"地址"和"值"的区别，以及如何通过地址访问值。

🏗️ 架构设计哲学

1. 模块化与可扩展性

每个模块都是独立的，可以单独理解和使用：

• lexer.ts: 词法分析
• parser.ts: 语法分析
• cfg-generator.ts: CFG 生成
• assembly-generator.ts: 代码生成
• assembly-vm.ts: 虚拟机执行

设计思考:

• 每个模块职责单一，易于理解
• 模块间通过清晰的接口通信
• 可以单独测试每个模块

2. 可视化驱动的学习

核心思想: 代码即文档，可视化即解释。

每个关键概念都有对应的可视化：

• AST: 树形结构可视化
• CFG: 图结构可视化
• 栈布局: 内存布局可视化
• 虚拟机: 执行状态可视化

设计思考:

• 可视化让抽象概念变得具体
• 交互式探索比静态文档更有效
• 实时反馈帮助理解动态过程

3. 渐进式复杂度

项目从最简单的表达式解析开始，逐步增加复杂度：

1. 表达式 → 2. 语句 → 3. 控制流 → 4. 作用域 → 5. 函数 → 6. 代码生成 → 7. 链接 → 8. 指针

设计思考:

• 每一步都建立在前一步的基础上
• 每个新概念都有独立的示例
• 可以随时停下来理解当前层

🎓 学习路径建议

初学者路径

1. 理解表达式解析 (bnf/, precedence-climbing/)

   • 先理解递归下降（BNF）
   • 再理解优先级爬升
   • 最后理解栈式实现（显式数据结构）

2. 探索可视化 (frontend/src/priority-climbing/)

   • 输入表达式，观察 AST
   • 单步执行，观察栈的变化
   • 理解优先级和结合性

3. 理解控制流 (cfg/)

   • 阅读 cfg/docs/ 文档
   • 运行 vm-runner.ts 查看 CFG
   • 在可视化中探索 CFG 结构

4. 理解作用域 (frontend/src/stack-scope/)

   • 观察作用域如何创建和销毁
   • 理解变量遮蔽
   • 追踪栈上的变量分配

5. 理解代码生成 (frontend/src/codegen-vm/)

   • 观察汇编代码的生成过程
   • 理解代码优化（基本块合并）
   • 在虚拟机中执行并观察状态

6. 理解链接过程 (linker/, frontend/src/linker/)

   • 学习静态链接：符号解析和地址重定位
   • 学习动态链接：运行时函数加载和跨段调用
   • 观察多文件编译和链接的完整流程
   • 理解库函数如何被链接到主程序

7. 理解指针操作 (pointer/)

   • 学习指针类型和声明
   • 理解取地址 & 和解引用 * 操作
   • 观察间接寻址在汇编层面的实现
   • 探索指针作为函数参数的使用

进阶路径

1. 深入算法实现

   • 研究 DFS 遍历中的快照机制
   • 理解基本块合并的优化算法
   • 探索寄存器分配策略

2. 扩展功能

   • 添加新的数据类型
   • 实现函数调用
   • 添加更多优化
   • 探索动态链接的优化策略
   • 实现更复杂的指针操作（如指针算术）

🔍 关键设计决策

为什么使用 Checkpoint 机制？

问题: 如何在 CFG 遍历时正确管理作用域？

传统方案: 在 CFG 生成时处理作用域（耦合度高）

我们的方案: Checkpoint 机制

• 在 AST 转换阶段显式标记作用域边界
• CFG 生成时只需识别 Checkpoint 节点
• 作用域管理与 CFG 结构解耦

优势:

• 职责分离：AST 转换负责标记，CFG 生成负责控制流
• 易于理解：作用域边界清晰可见
• 易于调试：可以单独测试作用域管理

为什么使用 init 标志？

问题: 如何区分"已声明但未初始化"和"已初始化"的变量？

传统方案: 只记录声明，不区分初始化

我们的方案: init 标志

• enterScope 时，所有变量 init: false
• int x 或 let x 声明时，init: true
• 查找变量时，只返回 init: true 的变量

优势:

• 正确处理变量遮蔽：内层未初始化的变量不会遮蔽外层已初始化的变量
• 支持 TDZ（Temporal Dead Zone）语义
• 更接近真实编译器的实现

为什么使用快照机制？

问题: 在 CFG 的 DFS 遍历中，如何正确处理分支和回溯时的作用域状态？

传统方案: 每次回溯都重新计算作用域（效率低）

我们的方案: 快照机制

• 进入基本块时保存作用域快照
• 回溯时从快照恢复
• 使用深拷贝确保独立性

优势:

• 正确性：每个分支都有独立的作用域状态
• 效率：不需要重新计算
• 可调试：可以查看任意时刻的作用域状态

为什么支持静态链接和动态链接？

问题: 如何理解链接过程的本质？

静态链接方案:

• 编译时将所有符号解析为地址
• 所有代码合并到单一可执行文件
• 优点：执行效率高，无需运行时查找
• 缺点：可执行文件体积大，库更新需要重新链接

动态链接方案:

• 运行时按需加载库函数
• 通过 libMap 管理函数映射
• 每个库文件映射到独立代码段（1000*N）
• 优点：代码复用，库更新无需重新编译主程序
• 缺点：运行时开销，需要符号解析

我们的实现: 同时支持两种方式，便于对比理解链接的本质。

为什么使用简化的地址单位设计？

问题: 指针操作需要什么样的内存模型？

真实架构: x86 中 int 占 4 字节，需要地址对齐

我们的方案: 每个变量占 1 个地址单位

• 简化地址计算，便于教学
• 所有变量（包括指针）统一处理
• 指针操作仍然正确：地址值 + 间接寻址

优势:

• 教学友好：概念清晰，易于理解
• 实现简单：不需要复杂的对齐计算
• 功能完整：支持所有指针操作场景

关键洞察: 只要地址系统一致，指针操作就能正常工作。简化设计不影响对指针本质的理解。

📖 文档结构

技术文档

• CFG 模块 (cfg/docs/): 系统架构、实现流程、模块说明、基本块理论
• 链接器模块 (linker/docs/): 链接过程说明、符号解析、动态链接实现
• 指针模块 (pointer/docs/): 指针实现说明、间接寻址、VM 扩展

代码示例

• CFG 测试 (cfg/tests/): 复杂的作用域和控制流示例
• 链接器测试 (linker/tests/): 静态链接、动态链接、多文件编译示例
• 指针测试 (pointer/tests/): 基础指针、二级指针、多级指针示例

🚀 快速开始

环境要求

• Bun 运行时

安装依赖

bun install
cd frontend && bun install

运行示例

后端测试

# 运行 CFG 编译器
cd cfg
bun run src/vm-runner.ts tests/grade-check.txt

# 运行链接器（静态链接）
cd ../linker
bun run src/link-runner.ts tests/test-main.txt tests/lib/

# 运行链接器（动态链接）
bun run src/dynamic-link-runner.ts tests/dynamic-link-test.txt tests/lib/

# 运行指针测试
cd ../pointer
bun run src/vm-runner.ts tests/test-pointer.txt

# 运行表达式解析器
cd ..
bun run precedence:stack

前端可视化

cd frontend
bun run dev
# 访问 http://localhost:5173

探索页面

1. 栈式优先级爬升可视化 (/)

   • 表达式解析的栈式可视化

2. AST CFG 测试页面 (/ast-cfg)

   • AST 和 CFG 的可视化
   • 代码高亮和块映射

3. 栈布局可视化 (/stack-scope)

   • 作用域链可视化
   • 栈布局逐步执行

4. 代码生成与虚拟机 (/codegen-vm)

   • 汇编代码生成
   • 代码优化（基本块合并）
   • 虚拟机执行

5. 链接器可视化 (/linker)

   • 多文件编辑器（主程序和库文件）
   • 静态链接过程可视化
   • 动态链接过程可视化（代码段分布、函数映射）
   • 链接后的汇编代码和执行结果

🎯 项目价值

教育价值

• 理论结合实践: 不仅讲解理论，还提供完整实现
• 可视化学习: 抽象概念通过可视化变得具体
• 渐进式学习: 从简单到复杂，循序渐进

技术价值

• 模块化设计: 每个模块都可以独立理解和使用
• 可扩展性: 易于添加新功能
• 可调试性: 每个阶段都有详细的输出

研究价值

• 算法实现: 优先级爬升、DFS 遍历、基本块合并、符号解析
• 数据结构: 单调栈、作用域栈、快照机制、符号表、代码段映射
• 系统设计: 编译器架构、模块划分、接口设计、链接器设计

🤝 贡献

欢迎贡献代码、文档、示例或改进建议！

📄 许可证

MIT License

---

让编译器不再神秘，从理解开始。 🚀