编译器 — 从头到尾亲手打造一门小语言
작은 언어 '미니' 를 렉서·파서·의미 분석·트리 인터프리터·바이트코드 VM·최적화·x86-64 코드 생성·레지스터 할당과 GC 까지 직접 만들고, 모듈마다 만든 것이 다음 모듈의 입력이 됩니다. 채점기는 적어 낸 답이 아니라 여러분의 구현을 무작위 프로그램으로 돌려 기준 구현과 대조하고, 코드 생성은 실제로 구워 실행합니다. 끝에서는 gcc·clang 의 -O0/-O2 어셈블리와 LLVM IR 을 같은 눈으로 읽어, 실무 컴파일러가 무엇을 하는지 숫자로 확인합니다.
고급 · 레슨 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)