整理自 MIT OCW 6.004 Computation Structures（Spring 2017）L11 注解幻灯片。
源网页：11.1 Annotated Slides | Compilers
讲师：Chris Terman。图片直接引用 OCW 原站链接。
L11：编译器（Compilers）
本讲从高级语言出发，对比解释（interpretation）与编译（compilation），再用递归下降模板把 C 表达式/语句翻译成 Beta 汇编；随后拆解现代编译器前端（词法/语法/语义）、中间表示（IR / CFG）与多遍优化，最后做代码生成。
1. 编程语言（Programming Languages）
已学 Beta ISA：对寄存器中的 32 位数据做 datapath 操作，并访存、改 PC；指令由 opcode / 源 / 目的等字段组成 32 位字。汇编一句对应一条指令，程序员自己管寄存器与主存，并把数组访问等拆成 Beta 操作序列。
高级语言用变量与数据结构抽象存储与搬移；用表达式与赋值 = 等紧凑描述本需大量汇编的计算。本讲核心：如何把高级语言程序翻译成可在 Beta 上运行的代码。
2. 高级语言（High-Level Languages）
以欧几里得求 GCD 的 C 代码为例；课程用 C 的简单子集作示例语言。C 由 Dennis Ritchie 在 AT&T Bell Labs 为 Unix 而开发；此后语言不断加入 OOP、新数据结构与控制结构。
用高级语言可不提寄存器、具体指令等 ISA 细节 → 写得更快、更易读、更易维护；类型检查可拦下把字符串赋给数值变量等错误；动态分配等可自动化。因抽象掉具体 ISA，同一源码可移植到不同机器。代价取决于执行策略：解释还是编译。
3. 解释（Interpretation）
在真实机器 M1 上跑解释器，模拟易编程的抽象机 M2：每条 M2 操作由一段 M1 指令序列实现。解释器 + M1 ≡ M2 的一种实现。
常见多层解释：笔记本 x86 跑 Python 解释器 → 加载 SciPy → 一条 SciPy 命令展开为大量 Python 语句 → 每条 Python 再变成数百条 x86。适合一次性计算或探索算法；不必手写全部机器指令。
4. 编译（Compilation）
对需反复执行、愿付前期成本的任务用编译：把高级程序 P2 逐语句翻译成 M1 上的等价程序 P1（并不在翻译时“跑”P2）。做翻译的程序叫编译器（compiler）。
编译一次得 P1，之后直接跑 P1，避免运行时解析源码与多层解释开销。换不同编译器可把同一 P2 落到 M2、M3… 而不改写源码。解释与编译都能改源码、抽象真实机器，且在现代系统中并存。
5. 解释 vs. 编译（Interpretation vs. Compilation）
对语句 x+2：解释器处理时立刻取 x 并加 2；编译器则生成 LD/ADD 等指令，留待以后执行。循环中解释器会反复处理同一语句；编译器只生成指令一次。
| 解释 | 编译 | |
|---|---|---|
| 开销时机 | 执行中反复处理源码 | 一次性编译，执行更快 |
| 类型/操作决策 | 运行时，更灵活 | 编译期，换速度 |
| 开发循环 | 改完即可跑 | compile–run–debug 可能更慢 |
一般编译代码快得多；解释器可按 x 的实际类型改变行为。
6. 编译器（Compilers）
编译器：把高级语言程序翻译成功能等价的机器指令序列（汇编）。先检查良构性：语句是否合法、有无无意义的运算（字符串+整数）、未初始化就用等；并警告浮点转整型可能溢出等。
通过检查后生成高效指令，常重排计算使序列更短更快。现代优化编译器耐心探索替代方案，往往难被手写汇编全面超越。本节先看简单编译策略，再看现代编译器结构。
7. 简单编译策略（A Simple Compilation Strategy）
两主例程：compile_statement 与 compile_expr。源程序是语句序列，反复调前者。关注四类语句：无条件（求一次表达式）、复合（顺序执行子语句）、条件（if：测表达式真则执行 then）、以及迭代（后文 WHILE）。
compile_expr：生成求值表达式并把结果放在某寄存器的代码。表达式含常量、标量/数组变量、赋值、一元/二元运算、过程调用等。复杂算术可拆成一元/二元序列。过程调用留待下讲；其余表达式与语句可直接模板化。
8. compile_expr(expr) → Rx
- 小常量（）：
CMOVE符号扩展进寄存器；过大则存主存再LD。 - 变量：与大常量类似，
LD对应地址。 - 数组访问：元素连续存放；先
compile_expr得下标于 Rx，再乘元素字节数bsize（如int为 4）得字节偏移，LD基址+偏移取元素。 - 赋值：
compile_expr得右值，再ST到左值变量。 - 算术：分别编译操作数到寄存器，再生成对应 ALU 指令。
9. 编译表达式（Compiling Expressions）
例：含减、乘、加的赋值。按赋值模板递归编译 RHS；遇乘则再编译左操作数（减）……直至叶节点（变量/常量）生成 LD/CMOVE，再沿表达式树上返回生成 SUB/MUL/ADD 等。
此即递归下降（recursive descent）：每层表达式更简单，直到叶。相邻指令还可做窥孔优化（peephole）：如 CMOVE 后跟算术常可合并为带常量操作数的单条指令。
10. compile_statement
- 无条件语句：多为赋值或过程调用 → 交给
compile_expr。 - 复合语句：对每个子语句递归
compile_statement；生成代码首尾相接，顺序执行。
11. compile_statement：条件（Conditional）
最简 if：编译 test；若寄存器为 FALSE，分支跳过 THEN 子句代码。完整 if–else 用分支与标签保证：真走 then，假走 else，最后汇合。
编译本质：套用许多小模板，逐步把代码生成拆成更小任务，并用分支把碎片粘成正确控制流。
12. compile_statement：迭代（Iteration）
while 模板类似 if，末尾再分支回测表达式，直到为假。可重组使每轮只需一条 BT（原模板每轮 BF+BR），循环内小优化可累积为大收益。
for 可改写成带更新的 while，再套上述模板。
13. 综合：阶乘（Putting It All Together: Factorial）
把模板套到迭代版阶乘：生成代码可与前述模板一一对应。非最优，但递归下降已够用。
14. 优化：值留在寄存器（Optimization: keep values in regs）
让变量住在专用寄存器而非主存，可少掉大量 LD/ST。例：循环内指令从 10 条减到 4。优化编译器擅长找此类机会。下文改谈更一般的现代编译器流程。
15. 现代编译器解剖（Anatomy of a Modern Compiler）
- 前端 / 分析：检查语法与语义（类型等），把源程序变成机器无关的中间表示（IR）。多语言前端可共享同一 IR。
- 后端 / 综合：先对 IR 做优化（如把与循环下标无关的运算提出循环），再为目标 ISA 生成指令，并做 ISA 相关窥孔优化（如 Beta 上
CMOVE+算术合并）。
16. 前端：词法分析（Frontend Stages: Lexical Analysis）
扫描源文本 → token 序列；空格/制表/换行仅作分隔，扫描后去掉。token 带文件名、行号、列号以便报错。非法 token（如 C 中 3x）在此阶段报错。
17. 前端：语法分析（Frontend Stages: Syntactic Analysis）
解析（parsing）把 token 建成语法树（syntax tree）：操作数挂到一元/二元结点，语句各部件标好角色。树结点标签与前述代码模板对应；深度优先遍历即可按标签选模板——但先还要做语义分析与变换。
18. 前端：语义分析（Frontend Stages: Semantic Analysis）
在语法树上检查语义：如 x = "bananas" 语法合法（左变量、右表达式），但若 x 声明为 int、右为 string，则类型不兼容。查符号表比对类型。完成后：语法树表示语法正确且语义有效的、语言无关的操作序列。
19. 中间表示 IR（Intermediate Representation）
语法树是常用 IR：独立于源语言与目标 ISA；保留运算顺序与分组信息；允许多前端共用一后端。后端可再分：机无关 IR 优化 → 代码生成到目标 ISA。
20. 常用 IR：控制流图（Common IR: Control Flow Graph）
把语法树重组为控制流图（CFG）：结点为基本块（basic block）——以分支结束的赋值/表达式序列；一旦进入块，块内其余操作会连着执行。边表示跳转到哪一块。基本块边界清晰，便于寄存器暂存变量等优化。
21. GCD 的控制流图（Control Flow Graph for GCD）
条件分支块有标 T/F 的两条出边；无条件则单出边。若某块仅一个前驱，可继承前驱关于寄存器中已有 x、y 等知识；多前驱时只能用所有前驱共有的知识。CFG 很像高级 FSM 的状态转移图。
22. IR 优化（IR Optimization）
对 CFG 多遍简单优化，反复直到无进展；简单变换可叠加出复杂效果。例：
- 死代码消除（dead code elimination）：删从未用的赋值、不可达块
- 常量传播（constant propagation）：已知常量的变量用常量替换引用
- 常量折叠（constant folding）：编译期求常量表达式
23. IR 优化示例 I（Example IR Optimizations I）
略造作的源程序及其 CFG：复杂表达式拆成简单二元运算，中间结果用临时名如 _t1。
24. IR 优化示例 II（Example IR Optimizations II）
死代码消除去掉第一块中对 Z 的赋值（后续再赋且中间未用）；发现 X=3 且不再赋值 → 传播常量 3；再常量折叠。
25. IR 优化示例 II（续）（Example IR Optimizations II continued）
更新后的 CFG 再一轮：死代码 → 常量传播 → 常量折叠。
26. IR 优化示例 III（Example IR Optimizations III）
两轮后赋值大减。第三轮：死代码；并可判定条件分支结果 → 删空块或不可达块。
27. IR 优化示例 IV（Example IR Optimizations IV）
IR 明显变小。继续常量传播、折叠、死代码消除。
28. IR 优化示例 IV（续）（Example IR Optimizations IV continued）
直到无更多优化。简单变换反复应用，得到算同一最终 Z 的更小程序。还可加：公共子表达式消除、循环无关代码外提、短循环展开等。
29. 代码生成（Code Generation）
- 为变量分配专用寄存器；不够则部分进内存，必要时
LD/ST - 用模板把赋值/运算译成指令
- 按块发射，加标签与分支
- 重排基本块以尽量消除无条件跳转
- 目标相关窥孔优化
30. 综合 I（Putting It All Together I）
GCD 的原 CFG 与略优化 CFG：主要是常量传播/折叠。顶块关于变量的知识不能简单传到多前驱的 if 块。
31. 综合 II（Putting It All Together II）
为 x、y 专配寄存器；按块生成；重排消除无条件分支。结果已接近人手难再明显改进的质量。
32. 小结（Summary）
编译流水线按序把源码变为高质量汇编：词法 → 语法 → 语义 → IR/CFG 优化 → 代码生成。耐心多遍优化常优于手写汇编；程序员专注功能正确性，细节交给编译器。