编译器 — 从头到尾亲手打造一门小语言
从词法分析器到 x86-64，亲手做一门小语言
고급 · 课时 30 · 实验 10
课程大纲
编译器做什么 — 先翻译，还是立即执行
- 负责翻译的程序与负责执行的程序 reading
- 让 gcc 中途停下，把计算器做两遍 lab
- 测验：编译器的各个阶段 quiz
词法分析器 — 把字符切成记号，位置一路带到底
- 词法分析器为什么要记住位置 reading
- 做一个记住位置的词法分析器 lab
- 测验：词法分析器 quiz
语法分析器 — 递归下降、Pratt 与错误恢复
- 用两个数字解决优先级 — Pratt 解析 reading
- 做一个带错误恢复的 Pratt 解析器 lab
- 测验：语法分析与错误恢复 quiz
语义分析 — 作用域、名称解析与可知处的类型
- 语法没错，意思却错了 — 语义分析 reading
- 作用域、名称解析与只看可知处的类型检查 lab
- 测验：语义分析 quiz
树遍历解释器 — 环境与闭包
- 随身带着声明时的环境 — 闭包 reading
- 用环境与闭包执行语法树 lab
- 测验：解释器与闭包 quiz
字节码与栈式虚拟机 — 常量池、槽位、跳转回填
- 能在运行前决定的就先决定 — 字节码 reading
- 做一个字节码编译器和栈式虚拟机 lab
- 测验：字节码与栈式虚拟机 quiz
中间表示与优化 — 常量折叠、CFG、支配关系与 SSA
- 结果相同、代价更低的程序 — CFG 与 SSA reading
- 折叠常量、构建 CFG、求出 φ 的位置 lab
- 测验：中间表示与优化 quiz
x86-64 代码生成 — 调用约定与栈帧
- 寄存器、栈帧与 16 字节 — 调用约定 reading
- 翻成 x86-64 并真正编出来 lab
- 测验：代码生成与调用约定 quiz
寄存器分配与垃圾回收 — 线性扫描与 mark-sweep
- 寄存器少、值很多 — 按生命周期分配并回收 reading
- 用线性扫描分配寄存器，再标记与清除 lab
- 测验：寄存器分配与 GC quiz
读懂实战编译器 — 数一数 gcc 与 clang 的输出
- 读懂 -O2 做了什么 reading
- 统计并读懂 gcc 与 clang 的输出 lab
- 测验：读懂实战编译器 quiz
参考文档
- GCC — Options That Control Optimization
- 官方文档 · sourceware.org · as
- System V AMD64 ABI (x86-64 psABI)
- LLVM Language Reference Manual
- 官方文档 · docs.python.org · dis.html
- Pratt — Top Down Operator Precedence (1973)
- Cytron et al. — Efficiently Computing SSA Form (1991)
- Poletto & Sarkar — Linear Scan Register Allocation (1999)