THU Compilers Sample Code Repository

清华大学编译原理课程 —— 样本代码仓库

简介

本仓库基于龙书 (Dragon Book) + Andrew Appel 体系构建，提供 14 个可运行 Python 实现，涵盖 12 章、4 大知识领域。核心亮点：第12章包含一个完整的端到端迷你编译器 (Lexer→Parser→AST→CodeGen→VM)。适合：

• 清华编译原理课程的学习者
• 408/826 计算机考研复习
• 词法/语法/语义分析、IR、优化等概念的动手实践
• 编译器/PL 方向的面试准备

仓库结构 (4 部 12 章)

compilers/
├── Hello.py                              # 仓库入口
│
╔══ Part I: 前端 (01-03) — 词法/语法/AST ═══════════════════════╗
║                                                                  ║
├── 01_introduction/                      # 编译器概述
│   └── compiler_phases.py                #   各阶段流水线演示
│
├── 02_lexical/                           # 词法分析
│   ├── regex_nfa_dfa.py                  #   Regex→NFA→DFA 理论
│   └── lexer.py                          #   手写词法分析器完整实现
│
├── 03_parsing/                           # 语法分析
│   └── recursive_descent.py              #   递归下降 LL(1) 解析器+求值
║                                                                  ║
╚══════════════════════════════════════════════════════════════════╝

╔══ Part II: 语义 (04-06) — AST/类型/IR ════════════════════════╗
║                                                                  ║
├── 04_ast/                               # 抽象语法树
│   └── ast_visitor.py                    #   AST + Visitor/Interpreter 模式
│
├── 05_semantic/                          # 语义分析
│   └── type_checker.py                   #   类型检查 + 符号表(作用域栈)
│
├── 06_intermediate/                      # 中间表示
│   └── three_address_code.py             #   三地址码 + SSA φ函数
║                                                                  ║
╚══════════════════════════════════════════════════════════════════╝

╔══ Part III: 后端 (07-09) — 代码生成/优化/运行时 ═════════════╗
║                                                                  ║
├── 07_codegen/                           # 代码生成
│   └── register_allocation.py            #   图着色寄存器分配
│
├── 08_optimization/                      # 优化
│   └── optimizations.py                  #   常量折叠/传播/死代码消除
│
├── 09_runtime/                           # 运行时
│   └── stack_frame.py                    #   栈帧 + 调用约定(x86-64)
║                                                                  ║
╚══════════════════════════════════════════════════════════════════╝

╔══ Part IV: 高级 (10-12) — JIT/静态分析/迷你编译器 ════════════╗
║                                                                  ║
├── 10_jit/                               # JIT编译
│   └── jit_basics.py                     #   JIT原理 + Python字节码
│
├── 11_static_analysis/                   # 静态分析
│   └── dataflow.py                       #   Liveness数据流分析
│
├── 12_mini_compiler/                     # ★ 完整编译器
│   └── mini_compiler.py                  #   Lex→Parse→AST→CodeGen→VM
║                                                                  ║
╚══════════════════════════════════════════════════════════════════╝

快速开始

python3 Hello.py

# 体验完整编译器流水线
python3 12_mini_compiler/mini_compiler.py
# 输出: Source → Lex → Parse → AST → Bytecode → VM Output

各章核心内容速查

Part	章节	核心内容	关键概念
I	编译器概述	各阶段流水线	前端 vs 后端, IR
I	词法分析	Regex→NFA→DFA + 手写Lexer	Thompson构造, 子集构造
I	语法分析	递归下降 LL(1)	FIRST集, 左递归, 优先级
II	AST	Visitor/Interpreter模式	开闭原则, 双重分派
II	语义分析	类型检查 + 符号表	静态vs动态类型
II	中间表示	三地址码 + SSA	φ函数, LLVM IR
III	代码生成	图着色寄存器分配	干涉图, Spill
III	优化	常量折叠/传播/DCE	优化遍, CSE
III	运行时	栈帧 + 调用约定	x86-64 ABI, prologue/epilogue
IV	JIT	JIT原理 + 字节码	Trace JIT, Method JIT
IV	静态分析	数据流分析(Liveness)	CFG, 不动点迭代
IV	★迷你编译器	Lex→Parse→CodeGen→VM	栈机指令集, 完整流水线

参考资料

• 龙书: Aho, Lam, Sethi, Ullman, Compilers: Principles, Techniques, and Tools, 2nd Edition
• Appel: Modern Compiler Implementation in C/Java/ML
• LLVM: https://llvm.org/docs/

构建说明

本仓库由以下 AI 协作完成：

• 代码架构与实现: Claude (Anthropic)
• 推理引擎: DeepSeek V4 Pro (1M 上下文)

所有代码经人工审查确认，AI 工具仅作为生产力辅助。

许可

MIT License