编译原理

编译原理的名声是「难」,我的体验是「被讲难了」。这门课的本质是几个非常朴素的自动化思想(正则、上下文无关文法、不动点)在「把人话翻译成机器话」这个问题上的系统应用。本讲义按「真的写一个编译器」的顺序推进:每章都是那个迷你编译器的一段,第 10 章把它拼完整跑起来。和 jyy 的课一样,我信奉「不做实验的编译原理是文学课」。

十章的地图:前端(词法、语法、语义,02~06)→ 中端(中间表示与优化,07、09)→ 后端(运行时与代码生成,08、10):

• 第 1 章 · 什么是编译器——从 gcc hello.c 的全过程讲起,前端中端后端分工
• 第 2 章 · 词法分析——正则表达式、NFA/DFA、手写一个 tokenizer
• 第 3 章 · 自顶向下语法分析——上下文无关文法、递归下降、LL(1)
• 第 4 章 · 自底向上语法分析——LR 分析、移进归约、为什么工具都用 LR
• 第 5 章 · AST 与语法制导翻译——抽象语法树、边解析边翻译
• 第 6 章 · 语义分析与符号表——类型检查、作用域、那半句「上下文无关」终于兑现
• 第 7 章 · 中间表示与三地址码——IR 的设计哲学、SSA 预告
• 第 8 章 · 运行时存储组织——栈帧、调用约定、GC,和 C 指针课握手
• 第 9 章 · 数据流分析与优化——活跃变量、常量传播、不动点计算
• 第 10 章 · 目标代码生成与迷你编译器实战——把前九章拼成一个能跑的编译器

先修:C 或 Python 任一(实验用)、数据结构(树)、离散数学的自动机部分(第 2 章前可补)。教材配合:《Crafting Interpreters》(手把手,免费在线)、龙书(工具书)、chibicc(读源码)。