准备：一个五行的样例

$ cat > demo.c <<'EOF'
int add(int a, int b) {
    int t = a + b * 2;
    return t;
}
EOF

• 用它是因为它一次性包含了后面每一章的引子：标识符与常量（词法，03 章）、运算符优先级（文法与二义性，04 章）、类型与作用域（语义，08 章）、能被强度削减的乘法（优化，11 章）、参数与寄存器（目标代码，12 章）。

四站产物，四条命令

$ clang -fsyntax-only -Xclang -dump-tokens demo.c   # ① token 流   → 03 章
$ clang -fsyntax-only -Xclang -ast-dump \
        -Xclang -ast-dump-filter=add demo.c             # ② 语法树+类型 → 04、08 章
$ clang -S -emit-llvm -o - demo.c                   # ③ 中间代码 IR → 09 章
$ clang -S -o - demo.c                              # ④ 目标汇编   → 12 章

# 用 gcc 的话，对应同一站的开关是：
$ gcc -fdump-tree-gimple-raw -c demo.c   # GIMPLE（gcc 自己的中间表示），相当于 ③
$ gcc -S -o - demo.c                     # 汇编，相当于 ④

• 四份输出依次变短、变陌生：token 流最长最琐碎，AST（抽象语法树）有层次，IR 已看不出源码结构，汇编只剩寄存器和跳转。这个「逐步丢掉源码形态」的过程，就是整本编译原理在做的事——每一步都在为下一步的机械处理铺路，代价是离人越来越远。

① token 流：每行一个「种别 + 词素」

int          'int'      [StartOfLine]      // 关键字，种别不是 identifier
identifier   'add'      [LeadingSpace]     // 相当于课本的 ⟨id, "add"⟩
l_paren      '('
int          'int'
identifier   'a'
comma        ','
...
numeric_constant '2'                       // ⟨num, 2⟩
semi         ';'

• 三件事当场可验证：关键字与标识符已分开、空白和注释一个都不在（所以 a+b 与 a + b 编出来一样）、a <= b 出来的是一个 lessequal 而不是两个符号（最长匹配）。

② AST：优先级以树的形状呈现

Dumping add:
FunctionDecl  add 'int (int, int)'         // 名字 + 完整类型
|-ParmVarDecl  used a 'int'
|-ParmVarDecl  used b 'int'
`-CompoundStmt
  |-DeclStmt
  | `-VarDecl  used t 'int' cinit
  |   `-BinaryOperator 'int' '+'          // 加法在上层
  |     |-ImplicitCastExpr 'int' <LValueToRValue>
  |     | `-DeclRefExpr 'int' lvalue ParmVar 'a'
  |     `-BinaryOperator 'int' '*'        // 乘法在下层 ← 优先级更高
  |       |-ImplicitCastExpr 'int' <LValueToRValue>
  |       | `-DeclRefExpr 'int' lvalue ParmVar 'b'
  |       `-IntegerLiteral 'int' 2
  `-ReturnStmt
    `-ImplicitCastExpr 'int' <LValueToRValue>
      ...                                  // 每行还带 0x… 地址与 <行:列>，这里省掉了

• 「乘法优先于加法」在这里不是一条规则，而是一个形状：a + b * 2 的乘法节点长在加法节点下面，优先级从此变成了树的深度问题（04 章）。
• 顺带看见了语义阶段的产物（08 章）：每个节点都标着类型，变量引用直接连回声明——这些不是语法分析的成果，是语义分析补上的。

四段结构

• 02–06 前端理论最密集：04 章是地基，推导、二义性、文法变换不过关，05、06 就只能背算法；
• 07–09 语义与中间表示：从这里开始产物能直接跑命令看到；
• 10–13 优化与后端：数据流分析、SSA、寄存器分配；
• 14–16 现代议题与动手：第一遍可以跳，回头再补。

同一根时机轴上的几个点

把翻译整个提到执行前，就是编译：先花一整趟把源程序译成目标程序，之后每次运行都直接跑机器码，快，而且有充裕时间做深度优化（C / C++ / Rust）。把翻译推到执行时、逐条边译边跑，就是解释：省掉了先译一遍的等待，启动快、易移植、好调试，代价是每跑一次都要重新理解一遍源码。真正的主流语言大多落在中间：先把源码编成紧凑的字节码交虚拟机解释，再把反复执行的热点在运行时临时编成机器码（JIT，如 JVM、V8）——冷代码省启动、热代码得速度。所谓 AOT（提前编译）与 JIT，无非是把编译放在「部署前」还是「运行时」，仍是这同一根时机轴的两端。

三种时机放一起看

翻译时机：  编译前 ←───────────────→ 运行时

AOT 编译    源码 ──▶ 机器码，之后才运行            gcc / rustc / go
字节码+JIT  源码 ─▶ 字节码 ─(运行时热点)▶ 机器码    JVM / V8 / .NET
解释        源码 ──▶ 边读边执行，不留独立产物      python / bash

三种实现路线，同一根时机轴上的三个点

• 值得单独记的一格是「峰值性能」：JIT 可以比 AOT 更快，因为它掌握 AOT 拿不到的信息——这个虚方法实际只有一个实现、这个分支运行时从不走、这个变量总是整数。代价是这些假设可能失效，于是需要去优化（deoptimization）退回解释执行。「编译早 → 优化信息少，编译晚 → 优化信息多但没时间」是这条轴的核心张力。

三段各管什么、为什么这么切

前端把源代码一路做到中间代码：词法、语法、语义分析都在这里，它认得的是源语言的规则。后端把中间代码落成某台机器的指令：代码生成、寄存器分配、机器相关优化，它认得的是目标机的脾气。中端夹在当中，只在机器无关的 IR 上做优化，谁都不偏袒。这么切的回报是算术级的：要支持 m 种语言、n 种目标机，若前后端搅在一起就得写 m×n 套；有了统一 IR，只需 m 个前端加 n 个后端，m+n 就够——这正是 LLVM 敢让几十种语言共享同一套优化与后端的底气。

m×n 还是 m+n

// 不解耦：每种语言各自下到每种机器 —— m × n 套
C, Go, Rust  ×  x86, ARM, RISC-V   →  3 × 3 = 9 套

// 解耦：都先降到统一 IR，前后端各写一次 —— m + n 个
C  ─┐                       ┌─▶ x86
Go ─┼─▶ 统一 IR ─▶ 机器无关优化 ─┼─▶ ARM
Rust┘                       └─▶ RISC-V
前端 3 个 + 后端 3 个 = 6 个（中间优化还共享）

每一步都是一次形态转换

每个阶段都对同一段程序做一次形态转换，上一阶段的产物恰好是下一阶段的原料：词法分析把字符流切成词法单元(token)流；语法分析把扁平的 token 流搭成有层次的语法树，顺带检查结构合法；语义分析在树上查类型、查作用域，为它加注解；中间代码生成把带注解的树降成机器无关的 IR（如三地址码）；优化在不改变语义的前提下改写 IR，让它更快更小；目标代码生成再把 IR 落成汇编 / 机器码。符号表与错误处理不隶属某一步，而是横贯全程的两条服务线。

示例

// 源语句
position = initial + rate * 60

// 词法分析后的 token 流
<id,position> <=> <id,initial> <+> <id,rate> <*> <60>

// 中间代码（三地址码）
t1 = inttofloat(60)
t2 = id_rate * t1
t3 = id_initial + t2
id_position = t3

十三站旅程（跟着 position = initial + rate * 60 走）

源代码字符流   position = initial + rate * 60   ← 一串字符
    ↓ 词法分析（§03）：正则 + 有限自动机切词
Token 流       ⟨id,position⟩⟨=⟩⟨id,initial⟩⟨+⟩⟨id,rate⟩⟨*⟩⟨60⟩
    ↓ 语法分析（§04–06）：CFG + LL / LR 判断结构
语法树 / AST    =( position, +( initial, *( rate, 60 ) ) )
    ↓ 语义分析（§07–08）：查类型、查作用域、加注解
带类型的 AST    60 是 int → 插入 inttofloat；各 id 登记进符号表
    ↓ 中间代码生成（§09）：降为机器无关的三地址码
IR             t1=inttofloat(60); t2=rate*t1; t3=initial+t2; position=t3
    ↓ 代码优化（§11；运行时环境 §10 为其打底）
优化后 IR       常量折叠、删冗余、循环不变量外提……语义不变、更快
    ↓ 目标代码生成（§12）：指令选择 + 寄存器分配
汇编 / 机器码   mulss / addss …，变量落到寄存器
    ↓ 现代工具链（§13）：LLVM / 链接 / JIT / AOT

两条贯穿全程的分界

• 前端 vs 后端：§03–09 只依赖源语言（换成 C++ 只改这半边），§12 只依赖目标机（换成 ARM 只改那半边），中间靠 IR 解耦——这正是上一张卡说的「m+n 而非 m×n」。
• 正则 vs 文法：词法用正则（数不清括号），语法用 CFG（能数嵌套）——为什么恰好在这里分家，§04 末的「乔姆斯基谱系」会给出全局地图。

一条接力链，各做一件窄事

预处理器先做宏展开、头文件包含、条件编译，吐出来的仍是源程序；编译器把它译成汇编；汇编器再把汇编逐条译成可重定位的机器码；链接器把多个目标文件拼到一起、把彼此的外部引用对上号；最后加载器把成品装入内存、定好最终运行地址。每个工具只做一件窄而确定的事，于是每个都足够简单、能被单独替换——这也引出了下面的问题：编译器为什么不干脆一步到位、直接吐机器码？

一条链，gcc 每步都能单独停下

hello.c
  │ 预处理 cpp    展开宏、#include        gcc -E → hello.i（仍是源码）
  │ 编译   cc1    源码 → 汇编             gcc -S → hello.s
  │ 汇编   as     汇编 → 可重定位机器码    gcc -c → hello.o
  │ 链接   ld     合并 .o、解析外部引用    gcc    → a.out
  ▼ 加载   loader 装入内存、定地址后运行

模子、实物、贴好标签的成品

模式(pattern)是一条规则，规定「什么样的字符串算这一类」，通常用正则写；词素(lexeme)是源程序里真正出现、匹配上某条模式的那段具体字符；词法单元(token)则是词法分析交给语法分析的成品，形如 ⟨种别, 属性值⟩ 的二元组，例如 ⟨id, 指向符号表的指针⟩。一句话串起来：模式是模子，词素是照模子浇出来的实物，token 是给实物贴好标签、供下一站直接取用的封装。

一行源码切成 token

源码：  sum = count + i * 2

lexeme（实物）  token（成品）    pattern（模子·正则）
  sum           ⟨id, ptr⟩       [a-zA-Z]+   ← sum/count/i 三个不同 lexeme…
  =             ⟨assign⟩        =
  count         ⟨id, ptr⟩       [a-zA-Z]+   ← …匹配同一 pattern…
  +             ⟨op, +⟩         [-+*/]
  i             ⟨id, ptr⟩       [a-zA-Z]+   ← …同归一个 token: id
  *             ⟨op, *⟩         [-+*/]
  2             ⟨num, 2⟩        [0-9]+

三种拼法，搭出所有词素模式

正则靠三种最基本的组合描述模式：选择（a|b，二选一）、连接（ab，先 a 后 b）、闭包（a*，重复任意次、含零次）；+ ? [...] 不过是常用简写。再给较长的子表达式起个名字复用（正则定义），就能像搭积木一样拼出「标识符」「浮点数」这类模式。它的表达力刚好够刻画 token 内部的形状——却也止步于此：一旦需要「记住前面出现过什么」，正则就无能为力，这正是下面要点破的边界。

能描述什么、不能描述什么

// 正则定义：给子式命名再复用
digit   → [0-9]
digits  → digit digit*            // 一个以上数字
id      → [a-zA-Z][a-zA-Z0-9]*    // 字母打头
number  → digits (. digits)?      // 整数或小数

能：认出 id、number、<=、字符串字面量…
不能：判断 ((())) 括号是否配对 —— 要「记住还欠几个 )」，正则没有记忆

一台会跳状态的小机器，两副面孔

自动机的运作极简单：读入一个符号，就按转移规则从当前状态跳到下一个状态，读完看是否落在「接受状态」上——所需零件不过是状态、输入符号、转移规则、一个初态和一组接受态。它的两副面孔差在「确不确定」：DFA（确定有限自动机） 每个状态对每个输入至多跳一处、也不许凭空(ε)空转，照着实现就是一张查表，运行时毫不含糊；NFA（非确定有限自动机） 则允许同一输入岔出好几条路、还能走 ε 空转移，描述起来更灵活。关键事实是二者识别的语言完全相同——NFA 便于描述、DFA 便于执行，于是词法工具的固定套路就是「先按正则搭出 NFA，再转成 DFA 去跑」。

同一步：NFA 岔路，DFA 唯一

              读 a        读 b       ε 空跳
NFA  状态 q0  {q0, q1}     {q0}       → q2     ← 一个输入可多个去向
DFA  状态 A   B（唯一）    A（唯一）    无       ← 照表走，绝不含糊

两者识别的语言相同；NFA 好描述、DFA 好执行 ⇒ 套路：正则 → NFA → DFA

NFA / DFA 对照（记住「能力相同、代价不同」）

• 所以工具的固定套路是「正则 → NFA → DFA」：用 NFA 的易构造性，换 DFA 的执行确定性。RE2 那类引擎更进一步——建好线性大小的 Thompson NFA，然后边匹配边惰性生成 DFA 状态，既拿到 DFA 的速度又躲开建表的指数爆炸。

每个算子一种固定拼法，只用 ε 缝合

最小的积木是「单个符号 a」和「ε」各自对应的两态小 NFA；往上三种组合各有一套固定拼法：选择 r|s 新起一个初态、用 ε 岔向两个分支，两分支的终态再用 ε 汇到新终态；连接 rs 把 r 的终态用 ε 接上 s 的初态；闭包 r* 补一条 ε 回边（允许重复）和一条 ε 跳过边（允许零次）。正因为每个算子只添几个状态、几条 ε 边，拼出来的 NFA 规模始终与正则长度成正比，绝不会爆炸。

把 a·b 拼起来

RE = a      →   ①─a→②
RE = b      →   ③─b→④
RE = a·b    →   ①─a→② ⋯ε⋯▶ ③─b→④   // a 的终态 ε 接上 b 的初态

每个算子只加常数个状态 / ε 边  ⇒  NFA 大小 ∝ 正则长度

把「多个可能」打包成「一个确定」

一旦把「此刻可能所处的那一堆 NFA 状态」整体看作 DFA 的单个状态，非确定性就消失了。落实只需两个操作：ε-closure(T) 求出从集合 T 出发、只走 ε 能到达的全部状态；move(T, a) 求出 T 中状态读入 a 后到达的状态集。DFA 的初态就是初始状态的 ε-closure，此后每个新状态都由 ε-closure(move(T, a)) 算出；只要某个集合里含有 NFA 的任一接受态，它就是 DFA 的接受态。

不断寻找「可区分」的证据，直到分不动

做法叫「划分细化」：先把状态粗分成 {接受态} 和 {非接受态} 两组，再反复检查——若同一组里两个状态遇到某个输入被送进了不同的组，就说明它们行为有别，把这一组拆开；如此细分下去，直到再也拆不动，剩下的每一组便是一批真正等价、可以合并成一个的状态。顺带把从初态永远到不了的「不可达状态」、以及到不了任何接受态的「死状态」一并清除，DFA 就压到了最小。

划分细化跑一遍

初分两组：   { 接受态 }  |  { 非接受态 }
细分规则：   同组两状态，若某输入把它们送进不同组 ⇒ 拆开
            s ─a→ 组X，t ─a→ 组Y（X≠Y）⇒ s、t 不等价，分家
… 反复细分，直到没有组还能拆

结果：读任何输入去向都落在同一组的状态（如 B、C）⇒ 合并成一个

为每个位置算出「接下来能轮到谁」

先给正则末尾补一个结束标记、写成 (r)#，再把每个叶子——也就是某个字符出现的位置——编上号。然后自底向上给每个结点算三样东西：nullable（这一部分能否匹配空串）、firstpos（它开头可能是哪些位置）、lastpos（它结尾可能是哪些位置）。由它们推出真正的核心 followpos：某个位置的字符匹配完，紧接着可能轮到哪些位置。有了这张「位置 → 后继位置」的关系表，DFA 的状态就直接是一组位置的集合、转移照 followpos 走——NFA 那一整步被跳了过去。

在语法树上算 followpos

增广：(a|b)*a#      叶子编号： a₁  b₂  a₃  #₄

自底向上算性质：
  a₁: first={1} last={1}      b₂: first={2} last={2}
  (a|b)*: nullable=真, first={1,2}, last={1,2}
followpos（谁匹配完能接谁）：
  1、2 之后 → {1,2,3}      3 之后 → {4}
DFA 状态 = 位置集合，按 followpos 转移，NFA 被跳过

从自动机到扫描器，要补上的几件事

切到哪算一个词？最长匹配原则(maximal munch)：能匹配更长就绝不停在短的，所以 <= 会整体识别成一个 token，而非拆成 < 和 =。关键字怎么办？它们长得和标识符一模一样，通常先把保留字预装进符号表，识别出一个标识符后一查便知，或干脆为它们单列模式。怎么读得快？用双缓冲加哨兵(sentinel)：一次读入一大块、用一个特殊结束符省掉「每读一个字符都判一次是否越界」。至于生成扫描器的体力活，则常交给 Lex / Flex——你写正则规则，它自动吐出上面这套自动机代码。

最长匹配：<= 是一个还是两个

输入： a <= b
          ↑ 扫到 '<' 别急着交，最长匹配：再看下一个是 '='？
          是 → 整体吃成一个 ⟨le, "<="⟩   （不是 ⟨lt⟩⟨assign⟩）

关键字： if 先查「保留字表」→ 命中就是 ⟨if⟩，否则才当 ⟨id⟩
读取：   双缓冲 + 末尾哨兵，省掉每读一字符都判越界

一堆替换规则，靠自我引用描述任意深嵌套

CFG 的骨架简单到只有一样东西：一批产生式，每条形如「某个非终结符 → 一串符号」，例如 E → E + E。非终结符是「待展开的语法成分」（表达式、语句），终结符是最终的词法单元；从开始符号出发反复替换，就生成出合法的程序结构。它强过正则的关键在自我引用：产生式右边可以再度出现左边那个非终结符，于是括号套括号、表达式套表达式的任意深嵌套都描述得了——这正是正则数不清、CFG 数得清的那类结构。而每条产生式的左部只允许是单个非终结符，这个看似不起眼的限制，正是下面『上下文无关』得名的由来。

一条产生式，套出任意深

文法： E → E + E | E * E | ( E ) | id

数清任意深嵌套（正则做不到）：
  ( id + ( id * id ) )
        └── E 里又出现 E，靠产生式右部再现自己 ——「自我引用」

左部永远是单个非终结符（E → …）⇒ 展开与左右无关 = 上下文无关

正着推导，倒着归约

正着用是推导：从开始符号出发，每一步挑一个非终结符、用某条产生式的右部替换它(记作 ⇒)，直到全变成终结符，就生成了一个句子。倒着用是归约：从一串终结符出发，反复把「某条产生式的右部」替换回它的左部，最终收回开始符号——这是自底向上分析的基本动作。每步该展开哪个非终结符是有讲究的：总挑最左边的叫最左推导，总挑最右边的叫最右推导（又称规范推导），这个选择看似随意，却和两类分析法严丝合缝对应。（推导途中那些可能还含非终结符的中间串叫句型；全是终结符的句型才是句子。）

id + id 的一次最左推导

文法： E → E + T | T      T → id

最左推导（每步替换最左非终结符）：
  E ⇒ E + T ⇒ T + T ⇒ id + T ⇒ id + id
归约就是倒着走： id + id ⇒ … ⇒ E

中间的 E+T、T+T 叫「句型」；末尾 id+id 全是终结符，叫「句子」

一句两解，就是二义

分析树把一次推导的层次画出来：根是开始符号，叶子是终结符，中间结点是非终结符。它关心的是句子搭成了什么形状。二义性指同一个句子能画出不止一棵分析树。为什么这一点关键？因为结构决定语义——两棵树意味着两种解释、两种算法、两种结果。最经典的是悬空 else，和没规定优先级的表达式文法（a+b*c 到底先乘还是先加？）。消解办法有两条：要么改写文法把歧义从根上堵死，要么外加优先级、结合性规则替分析器拍板。

a + b * c 的两棵树

文法无优先级： E → E + E | E * E | id
同一句 a + b * c，能画出两棵分析树：

  先乘（对）        先加（错）
     +                 *
    / \               / \
   a   *             +   c
      / \           / \
     b   c         a   b

两棵树 = 两种结构 = 两种结果 ⇒ 这就是二义性（要靠优先级消解）

治两个病：左递归与左公因子

左递归 A → Aα | β：产生式左边第一个符号又是自己，递归下降还没读入任何符号就先调用自己，无限自套。消除的办法是把「先递归后收尾」改写成「先展开后收尾」（见下例），生成的句子集合一模一样。左公因子 A → αβ₁ | αβ₂：两条产生式开头一截相同，分析器光看开头分不清走哪条、只能回溯；提取公因子成 A → αA′, A′ → β₁ | β₂，把「分岔点」推后到能看清为止。至于间接左递归，先把非终结符按序代入、让藏着的直接左递归暴露出来，再照上法消除即可。

示例

// 左递归（不适合递归下降）
E → E + T | T

// 消除后
E  → T E′
E′ → + T E′ | ε

一把尺子：表达力越强，代价越高

四档从强到弱——0 型不加任何限制，要图灵机才认（等于「可计算」的极限）；1 型上下文相关，展开一个符号还得看它左右的邻居；2 型上下文无关，展开与上下文无关、靠下推自动机（本质是一个栈）识别；3 型正规，最弱，有限自动机足矣。四者层层包含：3 ⊂ 2 ⊂ 1 ⊂ 0。编译器只用得着最下面两档——词法用 3 型、语法用 2 型，再往上的表达力用不着、代价还高。至于为什么恰好停在这两档，看下面。

四档能力，编译器只用最下两档

型   限制越松 → 能力越强   识别机器          编译器用途
3    正规（最弱）          有限自动机         ← 词法
2    上下文无关            下推自动机（栈）    ← 语法
1    上下文相关            线性有界自动机
0    无限制（最强）        图灵机
                          包含关系：3 ⊂ 2 ⊂ 1 ⊂ 0

四型一览（表格版，便于窄屏对照）

• 包含关系是 3 ⊂ 2 ⊂ 1 ⊂ 0：越往下限制越严、能力越弱，但性质越好——这正是「最小力量原则」要的东西。

一个非终结符，一个函数

做法是给每个非终结符写一个函数，函数体照着它的产生式走：要匹配终结符就吃掉一个 token，要匹配非终结符就调用对应的函数。你根本不用自己维护分析栈——程序的调用栈就是分析栈；也不用显式建树——函数的调用嵌套就是语法树的形状。正因如此它易手写、报错友好，不少工业编译器的前端就是手写的。代价是它要求文法「够乖」：不能回溯（一步走错，之前已执行的动作收不回来），于是只瞄一个符号就得选定产生式——这正是下面 LL(1) 的要求，也是上一章非先消左递归、提左公因子不可的原因。

文法照着写成函数

文法              对应的递归函数
E  → T E'         parseE()  { parseT(); parseE_(); }
E' → + T E' | ε   parseE_() { if (peek()=='+') { match('+'); parseT(); parseE_(); } }
T  → id           parseT()  { match(id); }

调用栈 = 分析栈；   函数的嵌套调用 = 语法树的形状

一张管「开头」，一张管「后面」

FIRST(α) 收集 α 推导出的串可能的第一个终结符；若 α 能整个推成空，就把 ε 也收进去。FOLLOW(A) 收集各种句型里紧跟在 A 后面的终结符；若 A 能落在句子末尾，就把结束符 $ 收进去。算 FIRST 时遇到能为空的符号，便顺势再看它后面一个；算 FOLLOW 时则顺着产生式 A → αBβ，把 β 的 FIRST 灌给 B，β 若可空再把 A 的 FOLLOW 也灌过去。为什么两条边界偏偏一个含 ε、一个含 $，下面细说。

名字即定义，表格即预先算好的决策

从左(L)到右扫描输入、构造最左(L)推导、只用 1 个向前看符号——一个文法属于 LL(1)，等价于说「站在任何非终结符前，瞄一眼下个符号就能唯一确定该用哪条产生式」。判据正由上一张的两个集合给出：对每对候选 A → α | β，要求 FIRST(α) 与 FIRST(β) 不相交（开头就能区分）；若 β 能推成空，还要求 FIRST(α) 与 FOLLOW(A) 不相交。把这些决策预先算好、填成一张预测分析表 M[A, a]，就能用「一个栈 + 输入串 + 查表」的循环来驱动分析，连递归函数都省了。

三种止损办法

最常用的是恐慌模式：一旦卡住，就往后跳过输入符号，直到撞上一个「同步符号」——常取 FOLLOW 集里的成员，因为那恰是当前结构合法收尾的位置，从那儿重新开始最不容易再乱套。更精细的有短语级恢复（对输入做个局部小修补，比如替你补上漏掉的分号）和出错产生式（把常见的错误写法直接编进文法、专门捕捉并给出针对性提示）。它们的共同点是都不图把程序改正确，只图别让一个错误引发一连串假报警或漏报。

恐慌模式：跳到分号再站起来

输入： int a = ; b = 5;      // '=' 后漏了表达式
              ↑ 出错
恐慌模式：向后跳过 token，直到撞上同步符号 ';'
          → 丢弃出错的残片
          → 从 ';' 之后重新开始，继续检查 b = 5

目的是止损：一次多报几个真错误，而非改对

一个栈、两个动作、一个句柄

它靠一个栈攒住已读进来、尚未归约的符号，每步只在两个基本动作间抉择：移进(shift) 再读一个 token 压栈；归约(reduce) 当栈顶正好凑成某条产生式的右部，就把它替换回左部（另有接受、报错两种收尾）。何时移、何时归，全看栈顶那段「此刻正该归约」的子串——这就是句柄。认准句柄，动作就定了；认错，分析就崩。所谓活前缀，不过是分析途中合法地留在栈里、还没越过句柄右端的那截前缀。整章的核心问题，就是「如何又快又准地认出句柄」。

id + id 的移进-归约

文法： E → E + T | T    T → id       栈 | 剩余输入 | 动作

  $        | id + id $ | 移进
  $ id     |  + id $   | 归约 T→id   ← 句柄 id
  $ T      |  + id $   | 归约 E→T
  $ E      |  + id $   | 移进
  $ E +    |    id $   | 移进
  $ E + id |       $   | 归约 T→id
  $ E + T  |       $   | 归约 E→E+T  ← 句柄 E+T
  $ E      |       $   | 接受

圆点标进度，CLOSURE 与 GOTO 拼状态

一个 LR(0) 项目就是一条产生式加一个圆点，如 A → α·β，圆点标记「已经匹配到哪儿了」。两个操作把项目组织成自动机：CLOSURE——若圆点后面是个非终结符，意味着接下来随时可能开始匹配它，于是把它那些产生式的初始项目（圆点在最左）递归拉进来，凑成一个项目集；GOTO(I, X)——把项目集 I 中「圆点后是 X」的项目的圆点全部右移一格，就得到读入 X 之后到达的新状态。所有项目集连起来，正是一台识别活前缀的 DFA。

只在「后面跟得上」时才归约

LR(0) 不看输入、一律归约，很容易和「其实还该继续移进」撞车。SLR（Simple LR，简单 LR）的补丁是：只有当前输入符号落在 FOLLOW(A) 里时才归约——毕竟归约成 A 之后，A 后面本就只可能跟这些符号，不在其中就说明此刻归约必错。就这一条，便化解掉一部分移进-归约冲突，而构造几乎没变复杂。代价是这个判据偏粗，能力有限，下面正好点破它粗在哪。

看 FOLLOW 决定要不要归约

状态里有归约项 A → α· ，当前输入是 a：
   a ∈ FOLLOW(A) ? ── 是 → 归约（A 后面本就只跟这些符号）
                   └─ 否 → 不归约（此刻归约必错）

例：FOLLOW(T) = {+, $}，遇到归约项 T → id·
   下一个是 +  ⇒ 归约          下一个是 (  ⇒ 不归约

把判据做精，再把表压小

规范 LR(1) 把判据做到极致精确：给每个项目单独绑一个向前看符号，写成 [A → α·β, a]，只在真正合法的后继 a 出现时才归约，比笼统的 FOLLOW 精准得多，能力也最强。可它的项目集分得极细，分析表大到不实用。LALR(1) 是那个恰到好处的折中：把「圆点位置全同、只是向前看符号不同」的状态合并，一举把表压到和 SLR 一个量级，能力却贴近 LR(1)。四者由弱到强依次是 LR(0)、SLR(1)、LALR(1)、LR(1)，而 Yacc / Bison 默认选的正是性价比最高的 LALR(1)。

带向前看的项目 + LALR 合并

LR(1) 项目多带一个向前看符号，比 FOLLOW 精确：
   [ A → α·β , a ]      ← 只在后继真是 a 时才归约

LALR：合并「圆点位置全同、只是向前看不同」的状态
   [A→α· , a]  +  [A→α· , b]   ─合并─▶   [A→α· , a/b]
   表压到 SLR 大小，能力却近 LR(1)  ⇒  Yacc / Bison 默认

两张表驱动，一格两义即冲突

ACTION[s, a] 告诉你在状态 s、看到输入 a 时该移进、归约、接受还是报错；GOTO[s, A] 告诉你归约出非终结符 A 后跳往哪个状态。理想情况每格只有一个动作；一旦某格塞进两个，就是冲突：既能移进又能归约叫移进-归约冲突（悬空 else 是典型），两条产生式都能归约叫归约-归约冲突。冲突未必是文法写错——对着二义文法补一句优先级、结合性声明，往往既消了冲突又缩小了表。真出了错，Yacc / Bison 靠一个保留记号 error 做恐慌式恢复：不断弹栈直到某状态肯接纳 error，再跳过输入到同步符号（如 ;）继续。

两张表 + 一格两义的冲突

          ACTION              GOTO
状态   id    +     $          E    T
 0     s5                      1    2      sN=移进到状态N
 1           s6    acc                     rN=用第N条产生式归约
 2           r2    r2                       acc=接受

冲突 = 一格挤进两个动作：
  悬空 else：同格既能 s（移进 else）又能 r（收尾内层 if）⇒ 移进-归约冲突

好写 vs 更强

LL 自顶向下、构造最左推导、边猜边验，最大的好处是直观——能手写、报错信息友好；坏处是能罩住的文法窄。LR 自底向上、对应最右推导的逆，能力强得多、几乎覆盖所有实用语言，但分析表庞大，通常靠 Yacc / Bison 这类工具生成。实践中能被 LR 接受的文法范围明显比 LL 宽——至于「LR 为什么更强」，下面从「决策推迟得更晚」这个角度说透。

两范式对照

              LL（自顶向下）       LR（自底向上）
推导          最左                 最右的逆
决策时机      早：看开头就押注      晚：整条移进栈上再定
文法能力      较窄                 更广（真包含 LL）
实现          可手写、报错友好      表大，多用工具生成
代表          递归下降、ANTLR       Yacc / Bison

LL 与 LR 的正面对照

• 工业界的选择正在偏向 LL/手写递归下降——不是因为它理论上更强（恰恰更弱），而是因为报错质量和可调试性在真实编译器里比表达力值钱：GCC、Clang、Roslyn（C#）、rustc、V8 的解析器全是手写递归下降。表达力不够就用「加一点前瞻 + 少量特判」补，换来的是能给出人类看得懂的诊断信息。
• 反过来 LR 的主场是你不控制文法的时候：为既有语言写工具、做语法高亮、做代码分析——tree-sitter 用 GLR 就是为了鲁棒地解析各种语言而不必为每种语言手写。

给符号挂属性，让信息沿树流动

做法是给每个文法符号挂上「属性」，再用语义规则让信息顺着分析树流动。流向分两种：综合属性由子结点往上汇总——子表达式的类型决定父表达式的类型，方向自底向上；继承属性由父结点或左兄弟往下、横向传递——一处声明的类型要发给它管辖的每个变量。终结符的属性直接由词法分析给定，所以只有综合属性、没有继承属性。至于什么时候一定算得出、什么时候会卡死，看下面。

一个往上汇总，一个往下分发

// 综合属性 val：自底向上，子决定父
      E.val = 8
     /    |    \
 T.val=3  +  T.val=5      ← 父的 val 由子的 val 算出

// 继承属性 type：自顶向下，一处声明发给多个变量
 int   a ,  b ,  c
  └── type=int ─┴──┴──▶   ← 从声明处横向 / 向下分发给每个 id

两档属性，对应两种「边分析边算」

S-属性定义只用综合属性（纯往上汇总），归约到哪就能算到哪，天然贴合自底向上的 LR。L-属性定义放宽一点，允许继承属性，但限定它只能依赖左边已处理过的符号和父结点——于是从左到右做一遍深度优先遍历也能算完，贴合 LL；S-属性其实就是「没有继承属性」的 L-属性特例。一组规则到底算不算得出，就看它的依赖图有没有环：有环意味着「算 A 得先有 B、算 B 又得先有 A」，找不到起点，无解。

能不能一趟算完

S-属性：只有综合属性（纯往上）→ 归约到哪算到哪，配 LR

L-属性：综合 + 受限继承（继承只依赖左边已处理的符号 / 父）
  A → B C  {C.in = B.val}   ✓ 用左边 B，从左到右一趟能算
  A → B C  {B.in = C.val}   ✗ 要用右边 C，一趟算不了

依赖图无环 ⇒ 可算；有环 ⇒ 无解

动作摆在哪，就在哪一刻执行

位置大有讲究：动作全摆在最右端（后缀 SDT），意味着整条产生式归约完才动手，正好配 S-属性 + LR；动作可插在任意位置，配 L-属性 + LL，递归下降走到哪就调到哪。在 LR 里想执行「中间动作」会有麻烦——它凭空多出一个「必须此刻做点事」的点，扰乱了原本靠向前看做出的移进/归约判断；解决办法是引入一个什么都不匹配的标记(marker)非终结符，把动作合法地「托管」进文法，既保住这个执行点、又不破坏分析。

动作放哪，就在哪一步执行

语义动作 {…} 嵌在产生式的哪个位置，分析走到那就执行：

后缀（动作在最右）  E → E + T { print('+') }    归约完才做 ── 配 LR
中间（动作在中段）  E → E + { m } T { … }        匹配到一半就做 ── 配 LL

LR 里的中间动作会扰乱移进 / 归约 ⇒ 用标记非终结符 M → ε 托管它

只留骨架的那棵树

AST 用综合属性在归约 / 遍历时自底向上搭出来：每凑齐一个子结构，就用 mknode / mkleaf 造一个结点，让属性记住指向它的指针，一层层拼成整棵树。它和忠实记录每步推导的具体语法树(CST)不同——AST 把括号、分号、单产生式这类只为分析服务的结点全部删掉，只留「运算符 + 操作数」的骨架，干净紧凑。若再把重复出现的公共子表达式合并、共享同一个结点，AST 就成了 DAG（有向无环图）。之所以另造这棵树而不直接沿用 CST，下面细说。

CST 塞满语法，AST 只留骨架

a + b * c

具体语法树 CST           抽象语法树 AST
    E                        +
   /|\                      / \
  E + T                    a   *
  |  /|\                       / \
  T T * T                     b   c
（塞满 E/T/单产生式/标点）  （只留运算符 + 操作数）

后续各章加工的都是右边这棵干净的 AST

一本按作用域分层的账

一个名字叫什么、是什么类型、属于哪个作用域、将来落在内存或寄存器的什么位置、（若是函数）带哪些参数——都记在这里。实现上常用哈希表（查得快）或有序表；碰上嵌套作用域，就用一叠符号表（栈）或一条链把内外层串起来：进入一个作用域就压一层新表，退出就弹掉。这样内外层同名的变量各记各的、互不踩踏。至于为什么非按作用域分层不可、以及「先用后声明」的前向引用为何棘手，看下面。

嵌套作用域 = 一叠符号表

int x;              ┌─ 全局表 ── x:int, f:func
void f(int a){      │
  int x;            ├─ f 的表 ── a:int, x:int   ← 遮蔽全局 x
  { int y; … }      ├─ 块的表 ── y:int
}                   └─ 退出块 / 函数就弹掉对应表

进入作用域压一层表、退出弹掉；查名字从栈顶往下找

按文本嵌套定，还是按运行调用链定

有两套规矩：静态（词法）作用域按程序文本的嵌套结构来定，编译期一看便知；动态作用域按运行时的调用链来定，得跑起来才知道（如今少见）。块结构语言遵循「最近嵌套」原则——查一个名字时从当前块往外一层层找，撞上的第一个声明就是它，内层的同名声明会遮蔽外层。为什么现代语言几乎清一色选静态作用域，看下面。

最近嵌套，从里往外

int x = 1;
void f() {
  int x = 2;          // 内层 x 遮蔽外层
  { int x = 3;
    print(x); }       // → 3（最近嵌套：从里往外，撞上第一个）
  print(x);           // → 2
}
静态作用域：绑定由文本嵌套决定，编译期就能钉死

先描述类型，再检查是否对得上

它先要能描述类型：整数、浮点这些基本类型，加上数组、记录、指针、函数这些由基本类型构造出来的复合类型。再检查每处运算的操作数类型对不对得上，检查规则通常写成「前提 → 结论」的推理规则。检查的时机分两种：静态在编译期一次查清、运行时零开销但偏保守；动态拖到运行时才查、更灵活但错误要到执行那一刻才暴露。两者的取舍、以及「强 / 弱类型」这对标签为何含糊，看下面。

类型规则长什么样

规则写成「前提 → 结论」：
    e1 : int    e2 : int
    ─────────────────────      // 两个 int 相加，结果才是 int
        e1 + e2 : int

静态检查：编译期查完，运行时零开销，偏保守
动态检查：运行到那一刻才查，灵活但错误暴露晚

等价、转换、推导

等价：「结构等价」看两个类型长得一不一样，「名字等价」看名字是不是同一个（更严格）。转换：编译器悄悄替你转叫隐式(coercion)、你自己写明叫显式(cast)；小类型塞进大类型叫拓宽(widening)、反过来叫缩窄(narrowing)。推导：不写类型标注、由用法反推，ML / Haskell 的 Hindley-Milner 就靠「合一(unification)」自动补齐全部类型。此外还有重载消解（同名函数该选哪个）与多态（一段代码适配多种类型）。这里最容易埋 bug 的是隐式转换，下面点破。

结构等价 vs 名字等价

type Point = { x:int, y:int }
type Vec   = { x:int, y:int }      // 结构相同、名字不同

结构等价：Point 与 Vec 视为同一类型（长得一样即可）
名字等价：Point 与 Vec 视为不同类型（更严，尊重「特意起不同名」）

隐式转换的坑：long → float 悄悄丢精度，最难查

不是一种东西，而是一道光谱

IR 并非单一形式，而是一道光谱：高级 IR 接近 AST、还留着循环和数组下标；中级是三地址码这类摊平的线性代码；低级已经接近汇编。常见的具体形式有语法树 / DAG、三地址码、SSA、字节码、LLVM IR 等。落在光谱的哪一档并非无关紧要——它直接决定了哪些优化做得动、哪些已经没法做，下面详说。

同一句，三个层次的 IR

a[i] = a[i] + 1

高级 IR   a[i] = a[i] + 1           ← 还留着数组下标
中级 IR   t1 = i * 4                ← 三地址码，摊平
          t2 = a + t1
          *t2 = *t2 + 1
低级 IR   load  r1, [a + i*4]       ← 接近汇编，带寄存器
          add   r1, r1, 1
          store [a + i*4], r1
越往下：高层结构丢得越多，越贴近机器

一步一运算，控制流全显式

基本形态是 x = y op z；此外还有拷贝、无条件 / 条件跳转、函数调用、数组与指针访问等几类。嵌套的复杂表达式怎么办？——引入临时变量 t1、t2… 拆成一步步算（见下例）。控制流也不再靠缩进和嵌套体现，而是显式地用标号(label)加 goto 表达。写起来这么啰嗦是有回报的，下面讲它换来了什么。

示例

// a = b * c + b * c
t1 = b * c
t2 = b * c
t3 = t1 + t2
a  = t3

省空间还是好重排

四元式 (op, arg1, arg2, result) 把结果的临时变量名显式写出，优化时要移动、重排指令都方便。三元式 (op, arg1, arg2) 省掉 result，改用「这条指令的位置编号」来指代它的结果，省空间，却也因此一挪动就全乱。间接三元式 是折中：另加一张「指令指针表」，重排时只动这张表、不碰指令本体。为什么多这一层间接就解决了问题，下面细说。

同一段 TAC，三种存法

a = b * c + d

四元式（带 result）          三元式（用行号指代结果）
 (0) *  b   c   t1           (0) *  b   c
 (1) +  t1  d   t2           (1) +  (0) d      ← "(0)" = 第 0 条的结果
 (2) =  t2      a            (2) =  a  (1)

移动一条指令：四元式改 t1 即可；三元式行号全乱
 ⇒ 间接三元式加一层「指令指针表」，重排只动表

一个变量只赋一次值，汇合处插 φ

做法是给变量按版本重命名，x 每被赋值一次就换个新名 x₁, x₂…。好处立竿见影——数据来源清清楚楚，常量传播、值编号、死代码消除这些数据流优化瞬间变简单。唯一的麻烦在控制流汇合处：if 的两个分支都给 x 赋了值，汇合后该用哪个版本？答案是插一个 φ 函数，放在汇合点、按来路挑对应版本。φ 该放进哪些块最省，由「支配边界」定（见 §11）。φ 究竟是不是一条真指令，下面点破。

看一眼：φ 从哪来

// 原始：两个分支都给 x 赋值
if (a > 0)  x = 1;   else  x = 2;
y = x + 1;                 // 汇合点：该用哪个 x？

// SSA：每次赋值换个新版本号，汇合处插 φ
if (a > 0)  x₁ = 1;  else  x₂ = 2;
x₃ = φ(x₁, x₂);           // φ 按来路挑：左路→x₁、右路→x₂
y₁ = x₃ + 1;              // 往后只认 x₃，来源唯一

一切归结为地址算术

碰到声明，编译器算出每个变量的类型宽度(width)和它在所属存储区里的偏移(offset)，填进符号表备用。碰到数组引用 a[i]，就把它换成一条地址算式 base + index × width；多维数组还要按「行优先」或「列优先」的约定，把下标摊平成一维偏移。碰到记录 / 结构的字段，则按各字段预先算好的偏移定位。为什么这套地址算术值得逐字讲透，下面说。

a[i][j] 怎么变成地址算式

int a[3][4];   访问 a[i][j]（行优先，每元素 4 字节）：

地址 = base(a) + (i * 4 + j) * 4
                  └ i 行、每行 4 个元素 ┘
翻成三地址码：
  t1 = i * 4
  t2 = t1 + j
  t3 = t2 * 4
  t4 = a + t3        // 即 &a[i][j]
地址偏一位，整个访问就落到别的数据上 —— 所以要讲透

算出真值，还是直接编成跳转

数值法老实把真假算成 1 和 0，像算术一样求出一个值。控制流法（跳转代码）则根本不算真假，而是直接把「成立跳这、不成立跳那」编成条件跳转——&& 和 || 天然配这种译法，因为它们短路：左边一旦定局，右边就不必再看。if / while / for 则各有一套标号 + goto 的固定翻译模板。控制流法的精髓全在「跳转目标怎么安排」，下面讲透。

a && b 的短路跳转

if (a < b && c < d) S;   控制流法（不算真假，直接跳）：

         if a < b goto L1      // 左边真，才有必要看右边
         goto Lfalse           // 左边假 → 短路，整个假
    L1:  if c < d goto Ltrue
         goto Lfalse
 Ltrue:  （S 的代码）
Lfalse:  …
&& 的左假出口直接指向整个表达式的假出口 —— 这就是短路

先记账，后补填

典型场景是 if 的假出口要跳到尚不存在的 else 之后。回填的办法就是「先记账、后补填」：先把跳转目标留空，把这些待填的指令攒进一张列表（truelist / falselist / nextlist），等地址确定了再统一填回去。配套只需三个操作——makelist(i) 新建列表、merge 合并两张列表、backpatch(p, i) 把列表 p 里的空目标一次全填成 i。真正烧脑的是嵌套结构里列表怎么合并、怎么往外传，下面说。

走一遍：留空 → 回填

// 生成 if (a < b) 的跳转时，真 / 假出口地址还不知道
100:  if a < b goto ___    // truelist = {100}，目标留空
101:  goto ___             // falselist = {101}，目标留空
        ...                // 接着往下生成代码

// 等真出口 = 102、假出口 = 200 确定后，一次性填回去
backpatch(truelist,  102)  →  100:  if a < b goto 102
backpatch(falselist, 200)  →  101:  goto 200

按生命期分区，按生命期分配

代码区放指令；静态 / 全局区放整个程序期间都在的数据；栈放随函数调用来去的局部数据；堆放手动申请、生命期不定的动态对象。典型布局里栈从高地址往下长、堆从低地址往上长，中间留白供两者伸缩。对应地有三种分配策略：静态分配（编译期就把地址钉死）、栈式分配（随调用压入弹出）、堆分配（运行时按需申请释放）。为什么这三者恰好对应三种生命期、递归又为什么非用栈不可，看下面。

内存分几块，各放什么

高地址 ┌────────────┐
       │    栈       │ ↓ 向下增长（函数调用来去）
       │   ↓    ↑    │
       │    堆       │ ↑ 向上增长（malloc 动态对象）
       ├────────────┤
       │ 静态 / 全局 │   整个程序期间都在
       ├────────────┤
       │   代码      │   指令
低地址 └────────────┘
静态分配 = 地址钉死 ／ 栈 = 随调用压弹 ／ 堆 = 按需申请

一次调用需要的一切，都装在这一块里

帧里装着这次调用需要的一切：返回值、实参、保存的机器状态（寄存器）、局部变量与临时变量，还有两条链——控制链(动态链)和访问链(静态链)。两个指针框住它：帧指针 fp 锚定当前帧的固定基准，栈指针 sp 指向栈顶。调用发生时，调用者与被调者按约定分工：一段调用序列压入参数、保存现场，一段返回序列再把这些拆掉、恢复现场。两条链具体各管什么、为什么绝不能混，看下面。

一帧长什么样

高地址 ↑
  实参、返回值      ← 调用者压入
  返回地址          ← call 指令自动压入
  调用者的 fp       ← 控制链：返回时据此还原上一帧
──────────────  ← fp 帧指针，锚定本帧、偏移固定
  保存的寄存器
  局部变量
  临时变量
──────────────  ← sp 栈指针，指向栈顶
低地址 ↓（栈向下增长）

拷贝，还是共享

值传递(call-by-value) 给拷贝，函数改不动外面的实参。引用传递(call-by-reference) 给路，形参和实参成了同一块存储的两个名字，函数一改、外面跟着变。值-结果(copy-restore) 是「进来先拷一份、返回时再写回去」的折中。名字传递(call-by-name) 最特别：实参每被用到一次就重新求值一次——注意它和「只求值一次并缓存结果」的 call-by-need（惰性求值）不是一回事。抓住「拷贝 vs 共享」这条轴，下面这些差异就都不必硬记了。

改得动外面，还是改不动

void f(int p)  { p = 99; }        // 值传递
int x = 1; f(x);  → x 仍是 1       // 改的是拷贝

void g(int &p) { p = 99; }        // 引用传递
int x = 1; g(x);  → x 变成 99      // p 与 x 是同一块存储的两个名字

分歧只一条：传「值的拷贝」，还是「通往原变量的路」

四种参数传递的对照

• 「传共享」这一行解释了那个最经典的争论：Java/Python 到底是传值还是传引用？答案是传的是「引用的值」——所以 list.append(x) 调用方看得见，而 list = [] 调用方看不见。争论双方各说对了一半，因为他们用的是只有两个词的词汇表。
• 传名是理解宏和惰性求值的钥匙：参数不是先算好再传，而是把表达式本身传过去、用到才算。经典的 Jensen 设备（用传名实现求和）今天看像魔法，但 C 的宏、Haskell 的惰性、React 的「传一个函数而不是传值」都是同一个机制的后代。

顺着定义的嵌套关系往外指

访问链（静态链）的解法是：每个栈帧存一根指针，顺着定义时的嵌套关系指向外层的活动记录；要访问外 k 层，就沿链回溯 k 步——回溯步数正好等于嵌套深度差。嵌套越深回溯越慢，于是又有了 display 表：用一个数组直接按层号索引各层活动记录，一步 O(1) 到位。这套机制在什么语言里用得上、又为什么 C 根本用不着，看下面。

静态链：顺定义往外指

g() {
  int x;                ← 内层要访问它
  h() {
    k() { 用 x }        ← k 定义在 h 里，h 定义在 g 里
  }
}
运行时每帧存一根静态链，顺「定义嵌套」往外指：
  k 帧 ─静态链→ h 帧 ─静态链→ g 帧（在这找到 x）
访问外 2 层 = 沿链走 2 步。C 不许函数嵌套 ⇒ 用不上这套

引用计数 vs 追踪，各有盲区

手动管理容易漏（内存泄漏）或错（悬空指针），于是有了垃圾回收(GC)自动清掉没人再用的对象。主流思路两大类：引用计数给每个对象数「还有几处引用」，归零即回收，简单而即时；追踪式从根出发扫描「还够得着谁」，够不着的即垃圾，包含标记-清扫、标记-整理、复制收集、分代收集等一系列变体。分配本身还要对付内 / 外碎片。各种算法为什么没有一个全能、分别在权衡什么，看下面。

引用计数栽在环上

引用计数：被引用数归 0 就回收
   外部 → A，且 A ⇄ B 互相指
   初始： A.count=2（外部 + B）， B.count=1（来自 A）

删掉外部引用后： A.count=1（B）， B.count=1（A）   ← 都不为 0！
   环里互相撑着，谁都归不了零 —— 循环引用的盲区

追踪式 GC 从根出发扫「还够得着谁」，能识破环，
代价是要在「扫描时暂停(STW)」与「总吞吐」之间权衡

先找单入单出的段，再连成图

基本块是一段「一进必一出、中间绝不跳进跳出」的最大指令序列——控制流一旦进了它的头，就必定顺着执行到它的尾。怎么切？找首指令(leader)：程序第一条、任何跳转的目标、以及任何跳转的下一条，都是新块的开头。把基本块当结点、块间的控制转移当边，连成的图就是控制流图(CFG)，之后所有全局优化都在这张图上做。为什么 leader 规则恰好这么定，看下面。

找 leader，切块，连成 CFG

三地址码（标出 leader）：
  1: t = 0             ← leader（第一条）
  2: if a<b goto 5
  3: t = 1             ← leader（跳转的下一条）
  4: goto 6
  5: t = 2             ← leader（跳转目标 / 也是跳转的下一条）
  6: x = t             ← leader（跳转目标）
切块 B1={1,2} B2={3,4} B3={5} B4={6}
连边成 CFG： B1→B2、B1→B3、B2→B4、B3→B4

四要素定死一个分析，迭代到不动点

任何一个数据流问题都由四样东西定死：方向（沿控制流前向、还是逆流后向）、传递函数（一个基本块 gen 出什么、kill 掉什么）、汇合算子（几条路径交汇时取并集还是交集）、边界条件（入口 / 出口的初值）。经典的三个问题——到达定值、活跃变量、可用表达式——各自的四要素配置都不同。求解办法是沿图反复迭代，直到信息不再变化，即到达不动点(fixpoint)。为什么方向和汇合算子不能随意搭配、初值又必须与之匹配，看下面。

四要素定死一个分析

问题          方向   汇合   传递函数    求的是
到达定值      前向    ∪    gen/kill    之前可能定值了什么
活跃变量      后向    ∪    use/def     之后是否还会用到
可用表达式    前向    ∩    gen/kill    每条路径都算过的表达式

沿 CFG 反复迭代，直到信息不再变化 = 不动点

看得越宽，越离不开数据流分析

局部优化只在单个基本块内做：块内指令必定顺序执行，谁在谁前一目了然，常借一张 DAG 就能消掉冗余。全局优化跨基本块，一条指令的「上一步」可能来自好几个分支、循环还会绕回来，非靠上一张的数据流分析在整张 CFG 上迭代不可。过程间优化(interprocedural) 再跨函数边界，要顾及的路径最多、代价也最高。为什么一跨出基本块就离不开数据流分析，看下面。

块内一眼看穿，跨块要分析

局部（块内）              全局（跨块）
  b = a + 1                L1: t = a + 1
  c = a + 1  ← 同表达式       L2: …（可能来自多个前驱）
  一眼可知 c = b            t 从哪来？要沿 CFG 追

块内顺序执行、谁在谁前一目了然；
跨块有分支 / 回边 ⇒ 只能靠数据流分析在整图上迭代

一箱互相喂球的改写

公共子表达式消除(CSE) 把算过一遍的表达式复用；复制传播、常量传播 / 折叠 把变量替换成它已知的值、能当场算的就当场算；死代码消除(DCE) 删掉永远用不到的计算；代数化简 抹掉 x*1、x+0 这类恒等式；强度削弱 拿便宜运算换贵的（乘法换成加法）；还有函数内联、循环展开。它们看似各管一摊，实则互相制造机会——下面这一点，正是优化真正的学问所在。

一步喂下一步

  x = 3            常量传播 →  y = 3 * 2
  y = x * 2        常量折叠 →  y = 6
  if (y > 100) …   该条件恒假 → 死代码消除，整个分支删掉

一步的产物成了下一步的机会 ⇒ 优化的顺序与轮数本身就是学问

把省下的每一条乘以迭代次数

核心几招：循环不变代码外提(LICM) 把每轮都算出同样结果的计算挪到循环外、只算一次；归纳变量识别加强度削弱，把随循环规律变化的量（如 i*4）改成每轮加一个常数；还有循环展开、循环合并 / 分裂、向量化。这些都要先靠支配关系认出「自然循环」和它的回边。其中 LICM 看着简单，却有个绝不能违背的前提，下面讲。

循环不变量外提（LICM）

优化前：                    LICM 后：
  for (i=0; i<n; i++)         t = a * b;      ← 每轮不变，提到循环外
    x[i] = a * b + i;         for (i=0; i<n; i++)
                                x[i] = t + i;
前提：a*b 每轮真的不变、无副作用、不抛异常
      否则外提就改变了语义 —— 优化只能更快、不能改意思

一个结构事实，撑起 φ 放置、循环识别与 SSA 优化

把支配关系整理成支配树，再算出支配边界（d 的支配力刚好失效的第一批块），就知道 φ 函数该放哪；自然循环也靠它识别——一条回边的头支配其尾，就圈出一个循环。有了 SSA，这些还能撑起更狠的优化：稀疏条件常量传播(SCCP)、全局值编号(GVN)。不过它们常要先做别名 / 指针分析判断两个指针是否指向同一块内存——分析越准，能安全施展的优化越多。为什么 φ 恰好落在支配边界，下面讲透。

支配边界 = φ 该放的地方

CFG：    1
        / \
       2   3      2、3 各给 x 赋一次值
        \ /
         4        ← 汇合点

1 支配所有点；但 4 不被 2 或 3 单独支配
 ⇒ 4 落在 2、3 的「支配边界」上（支配力刚失效、版本头回相遇）
 ⇒ φ 就放在 4： x₃ = φ(x 来自2, x 来自3)

IR 加一份机器模型，正确第一

它吃两样输入：IR，以及一份目标机模型——有哪些寄存器、什么指令集、支持哪些寻址方式、每条指令代价多少。目标是既正确又高效、还得会利用机器的特长。这一步高度机器相关：换一种指令集、一套调用约定、一个内存模型，代码生成就得重写——这正是「后端依赖目标机」那条界线的落点。为什么这一步里正确性要死死压在性能之前，看下面。

IR + 机器模型 → 汇编

输入 IR：    t = a + b
目标机模型： 寄存器 r0–r15、加法 add、各指令代价…
                 ↓ 指令选择 + 寄存器分配
输出汇编：    add r1, r2, r3      （a→r2, b→r3, t→r1）

高度机器相关：换 ISA / 调用约定 / 内存模型就得重写后端
先保证每种 IR 都译得分毫不差，再谈榨性能

用最小代价盖住整棵 IR 树

最朴素的做法是「一个 IR 结点配一条指令」的模板映射；讲究点的把 IR 看成树、用树覆盖——一条复杂指令能一口吃掉一整棵子树。挑法上，最大吞噬(maximal munch) 每步尽量吃最大的一块（和词法分析的「最长匹配」同名同源，只是这里吃的是 IR 子树），而用动态规划能求出全局最小代价、而非只顾眼前最贪。工具化的方案有 BURS（自底向上重写系统）/ 树文法。为什么值得为「挑哪条指令」大费周章，看下面。

同一操作，挑最省的覆盖

IR:  t = a + b*4      同一操作，几种目标指令：

方案 A（3 条）           方案 B（1 条，x86 支持）
  mul t1, b, 4            lea t, [a + b*4]
  add t,  a, t1           ← 一条复杂寻址指令顶三条

用动态规划挑「总代价最小」的覆盖，而非只贪眼前
（与词法「最长匹配」同源，只是这里吃的是 IR 子树）

塞得下就着色，塞不下就溢出

经典办法是图着色：把「同时活跃、不能共用一个寄存器」的变量两两连边，得到干扰图；给它做 k 着色（相邻不同色）恰好对应用 k 个物理寄存器互不冲突地装下所有变量。装不下时就得溢出(spilling)——把某个变量赶回内存、用时再读。常用算法有 Chaitin / Briggs（图着色系）和 JIT 偏爱的线性扫描(linear scan)，它们都以活跃变量 / 活跃区间分析为前提。为什么这问题能化成图着色、以及溢出该挑谁最不亏，看下面。

干扰图 k 着色

变量活跃区间相交 → 干扰图连边：
      a ─── b        a、b、c 两两同时活跃
       ╲   ╱         2 色（=2 个寄存器）染不了 → 需要 3 色
         c
k 着色成功 = k 个寄存器够用；失败 → 溢出一个到内存

溢出谁？别挑循环里反复用的 —— 热路径上反复读写内存最亏

一个重排，一个替换

指令调度靠重排：现代 CPU 流水线执行，若后一条指令要等前一条的结果就会停顿(stall)；调度器在不破坏依赖的前提下调换指令顺序，把互不相干的指令填进这些空档，常用列表调度。窥孔优化靠替换：拿一个小滑动窗口在代码上滑过，一认出「冗余加载、可化简的跳转、能强度削弱的运算」这类固定坏味道，就地换成更省的写法——看不到全局，却便宜又有效。为什么重排的自由度是被数据依赖卡死的，看下面。

重排绕停顿，窥孔换烂招

指令调度（重排绕开停顿）：
  load r1,[x]        load r1,[x]      ← load 后立刻用 r1 会停顿
  add  r2,r1,1   →   mul  r3,r4,r5    ← 插一条无关指令填空档
  mul  r3,r4,r5      add  r2,r1,1
  有数据依赖的两条不能换序，否则算错

窥孔（小窗口就地替换）：
  mov r1,r2; mov r2,r1   →   mov r1,r2      // 删冗余

统一 IR + 可插拔 Pass

它是标准的三段式：各种前端（Clang 等）都把源码降到同一种 LLVM IR，中端在 IR 上优化，后端再降到各目标机。这套 IR 强类型、SSA 形式，有可读文本 / 位码 / 内存三种等价形态。优化被拆成一个个可插拔的 Pass（分析 Pass 与变换 Pass），随意组合成流水线。于是多种前端、多种后端共享同一套中端优化——几百个 Pass 谁都能复用，任意前端配任意后端。它真正的厉害之处不在某个算法，下面点破。

统一 IR，任意前后端拼装

  Clang(C) ─┐                           ┌─▶ x86 后端
  Rust     ─┼─▶ LLVM IR ─▶ 一堆 Pass ─┼─▶ ARM 后端
  Swift    ─┘   (强类型 / SSA)  可插拔组合  └─▶ RISC-V 后端

几百个分析 / 变换 Pass，任意前端配任意后端都能复用
厉害的不是某个算法，而是「统一 IR + 可拼装 Pass」这套架构

运行时编译 vs 提前编译

AOT（提前编译）在部署前把一切编好（GraalVM native-image、Go），运行时零编译开销。JIT（即时编译）把编译推到运行时：先解释字节码，再把反复执行的热点临时编成机器码（JVM HotSpot、V8、.NET）。实践中常用分层编译——解释器加多级 JIT 协作，冷代码省心、热代码逐层提速；按「编译单位」又分 tracing JIT（编热路径）与 method JIT（编整个方法）。JIT 有个 AOT 天生拿不到的本钱，下面讲。

AOT 提前编，JIT 边跑边赌

AOT：部署前编好 ──────▶ 运行（零编译开销）        gcc / go
JIT：先解释 ─(此处总是 int?)▶ 赌是 int，编快路径     V8 / HotSpot
                赌错 ─deopt→ 退回慢路径重来

只有运行时才看得到「程序真跑起来的样子」
所以 JIT 敢做 AOT 做不了的投机优化 —— 这就是它的本钱

用真实运行画像，或更重的数学

PGO（画像引导优化）先拿真实负载跑一遍，用采样或插桩收集一份运行画像——哪条分支热、哪个函数值得内联、代码该怎么摆放——再据此编译。多面体模型(polyhedral) 则用一套精确的数学刻画循环嵌套的依赖关系，支撑激进的循环变换。再往上还有自动向量化(SIMD) 和自动并行化。PGO 的成败全系于一个前提，下面点破，稍不留神它会帮倒忙。

拿真实负载指导编译

① 插桩编译  →  ② 拿真实负载跑一遍，采集画像
                （哪条分支热、哪个函数值得内联、代码怎么摆）
③ 按画像重新编译  →  热路径内联、代码紧凑排布

成败全看：采画像用的输入，像不像日后真实负载？
拿玩具输入采的画像，可能把冷路径当热路径 —— 帮倒忙

对上号，填实地址，装入内存

目标文件按平台有 ELF（可执行与可链接格式，Linux）/ PE（Windows）/ Mach-O（macOS）等格式。链接器做两件事：符号解析（谁定义了 foo、谁引用了 foo，一一对上号）和重定位（把地址填实）。链接分两种：静态链接把库直接并进可执行文件；动态链接把库留到运行时再加载、让多个程序共享一份。最后加载器把成品装入内存、做最终的地址重定位（还含 ASLR 地址空间布局随机化）。两类经典报错从何而来、动态库到底在权衡什么，看下面。

对上号，填地址

a.o：定义 foo、引用 bar        链接器两件事：
b.o：定义 bar、引用 foo          ① 符号解析：foo / bar 对上号
   ───链接───▶ a.out             ② 重定位：把地址填实

两类经典报错都源于「对不上号」：
  没人定义 → undefined reference（未定义符号）
  多人定义 → duplicate symbol（重复符号）
动态库把对号推迟到运行时：省内存，却引入「版本对不上」

静态库 vs 动态库

• 最值得记的是最后一行：静态链接把问题暴露在构建时，动态链接把问题推迟到用户机器上。这就是「依赖地狱」的技术根源，也是 Go 默认静态链接、Docker 镜像流行、以及近年 Rust/Zig 强调静态产物的共同动机——用体积换「构建成功就一定跑得起来」。
• 动态库还有一个静态库没有的能力：运行期按需加载（dlopen）。插件系统、数据库的扩展、浏览器的编解码器全靠它——程序可以加载编译时根本不知道存在的代码。

把枯燥的部分交给生成器

词法交给 Lex / Flex：写好正则规则，它吐出扫描器。语法有两大生成器，正好对应两种分析范式——Yacc / Bison 走自底向上的 LALR(1)，ANTLR 走自顶向下的 ALL(*)。更大的框架如 LLVM、GCC、MLIR 则把后端整套基础设施都备好了。当然也可以手写前端，换来更好的报错和掌控——手写 vs 生成器，各有取舍。而选 Bison 还是 ANTLR，本质上又是在重走那道 LL vs LR 的老题，下面说。

Bison 还是 ANTLR：又是 LL vs LR

词法 Lex / Flex  →  语法生成器  →  分析器代码

  Bison   自底向上 LALR(1)   文法罩得广，冲突报告较难读
  ANTLR   自顶向下 ALL(*)    生成的像手写递归下降，报错友好

选哪个 = 重走「LL 好读 vs LR 更强」这道取舍
理论最终决定了你用起来的手感

阶段对应表

为什么值得编译，而不是运行时解释

• 静态可分析：模板里绝大多数结构在编译期就确定了，把「每次渲染都要重新判断的事」提前算完，是最典型的编译期收益；
• 产物更小：不需要把模板解析器打包进浏览器（Vue 的「运行时 + 编译器」版本比「仅运行时」大一截）；
• 错误提前：拼错标签名、用了不存在的指令，在构建时就能报，而不是等用户点进那个页面。

产物里的三个记号

• _hoisted_1 = { class: "card" }：静态的属性对象被提升到 render 函数外面，每次渲染复用同一个对象，不再重新分配——这就是常量提升在界面上的样子；
• _cache[0] || (_cache[0] = ...)：纯静态的 <p>静态文本</p> 整个节点被缓存，第一次渲染后就不再创建，注释里标着 -1 /* CACHED */；
• patch flag：动态节点带上一个位标记——只有文本会变标 1 /* TEXT */，文本和 class 都会变标 3 /* TEXT, CLASS */。运行时 diff 时看这个数字就知道该比什么，不必逐个属性比对。

这是一种「把分析结果编码进产物」的手法

• patch flag 本质上是编译期算出的数据流信息，用位掩码编码后传给运行时——和本页 09 章讲的活跃变量分析、10 章讲的把分析结果附在 IR 上，是同一套思路；
• 收益也一样：把「每次都要重新判断」变成「一次判断、多次使用」；
• 代价是运行时与编译器强耦合：版本不匹配时产物里的标记含义可能变，这就是「模板编译器版本必须和运行时一致」这条要求的由来。

两种运行时约定

• classic（老写法）：编译成 React.createElement(...)，因此每个用了 JSX 的文件都必须自己 import React——这是很多老代码顶部那行 import 的唯一用途；
• automatic（今天的默认）：编译器自己在文件顶部插入 import { jsx, jsxs } from "react/jsx-runtime"，你不用再手动 import React；同时它把「单个子节点」与「多个子节点」分成 jsx / jsxs 两个函数，让运行时少做一次判断；
• 产物里的 /* @__PURE__ */ 注释是给打包器看的：告诉它这个调用没有副作用，如果结果没人用就可以整段删掉——这是编译器与打包器之间的一个约定协议，也是 tree-shaking 能删掉未使用组件的原因。

JSX 不做的事（常见误解）

• 不做类型检查：那是 TypeScript 的活，esbuild 这类工具只剥语法不查类型；
• 不做静态提升：<p>hi</p> 每次渲染都会重新创建一个对象——这正是 React 侧需要 memo 与 React Compiler 的原因，而 Vue 在模板编译期就顺手做掉了；
• 不认识组件语义：大写开头当变量、小写开头当字符串标签，仅此而已。

三种做法

• ① 扫描生成（Tailwind）：构建时把源码当文本扫一遍，找出所有出现过的类名，只生成这些类的规则。它不是一个 CSS 框架，而是一个以源码为输入的代码生成器；
• ② 作用域哈希（CSS Modules / Vue scoped）：把 .title 改写成 .title_a3f9x（或加上属性选择器），同时把 JS 里的引用一起改。这是一次重命名 + 引用更新，等价于编译器里的符号重整；
• ③ 编译期提取（vanilla-extract / Panda / StyleX）：你用 TypeScript 写样式，构建时求值并抽成静态 CSS 文件，运行时一行样式代码都不剩。

扫描式生成的固有限制

• 它靠文本匹配而不是求值，所以拼出来的类名它看不见："text-" + color 在产物里根本不会生成对应规则；
• 这不是 bug 而是设计——要在构建期知道所有类名，就不能依赖运行时才确定的值；
• 正确写法是把完整类名写成常量映射，让扫描器能原样看到它们。这条限制与本页讲的「静态分析的边界」是同一件事：分析器只能看见语法层面确定的东西。

和 15 章推荐的那几本书什么关系

• Crafting Interpreters、chibicc 这些是好书，但它们是「跟着走完一整本」的承诺——几十个章节、上千行代码，很多人停在第三章。本章反过来：每一级台阶都在一个晚上之内能收工，且都有能跑的产物，做完一级就已经赚到。
• 两者不冲突：本章是那些书的最小骨架版。六级走完再去啃它们，你会发现自己认得里面的每一个数据结构，剩下要学的只是「怎么把它做完整」。
• 选 JavaScript 不是偷懒——零依赖、零构建、报错友好，让你把全部注意力留给编译本身而不是内存管理。语言换成 Python、Go、Rust 都一样，骨架一行不用改。

六级台阶

怎么用这一章

• 先自己写，卡住了再看代码。每张卡的结构都是「目标 → 关键几十行 → 本机跑出来的输出 → 现在你来」，中间那段代码是骨架不是答案，故意留了扩展空间。
• 随时可以停。只做①②就已经拥有一个能画出 AST 的解析器；做到③就有一门能跑的语言；④⑤⑥ 是三个独立的加分项，顺序可换。
• 改坏它比写对它更有价值：把②里 bin 的 while 改成递归调用自己（结合性立刻反过来）、把③的短路分支删掉（d != 0 && 10 / d 当场炸）、把⑤的回填地址算错一格（跳转飞掉）——每一处「坏法」都对应正文里的一条设计理由。

三件必须做对的事

• 最长匹配：扫到 < 别急着交货，先看下一个字符是不是 =——<= 必须整体成为一个 token。代码里就是那句「先试双字符表，再退回单字符」，顺序反了 a <= b 会被切成 < 和 =。
• 保留字表：let、while 和标识符长得一模一样，所以先按标识符规则扫出整个词，再查表决定它的种别——这正是 03 章说的「关键字不是词法层面的特殊形状，而是查表查出来的」。反过来先匹配关键字，letter 会被切成 let + ter。
• 行号：每遇到一个换行就 line++，并把它塞进每个 token。这是全链条唯一还知道行号的地方，漏了它，后面任何一级的报错都只能说「出错了」而说不出在哪。

词法阶段的输出

$ node -e "…" // 对样例程序跑词法
token 数: 38
前 8 个: let id(n) = num(0) ; let id(s) =

// 吞吐（20000 条 print 语句）
60001 个 token，词法 15 ms、语法 8 ms

• 词法比语法慢不是错觉：它逐字符走完了整个源文件，而语法只在 token 数组上走一趟。真实编译器里词法通常也是「便宜但占比不低」的一站，所以才有 03 章那些双缓冲、哨兵的讲究。
• 注释与空白在这一步就没了——把源码里的 a+b 与 a + b 各跑一遍，token 数组一模一样，信息销毁当场可见。

优先级爬升：层号就是优先级

• 把二元运算按优先级从低到高排成一串函数，每层只做一件事：调用下一层，然后循环吃掉本层的运算符。or → and → equality → compare → term → factor → unary → primary 八层，* 比 + 先算，仅仅因为 factor 在 term 的下面一层。
• 这就是 04 章那张 a + b * c 的树：乘法结点更深 = 先求值。你没写任何一条「乘法优先」的规则，优先级是从函数嵌套里长出来的。

循环还是递归，决定结合性

while (ops.includes(peek().k)) {      // 循环 ⇒ 左结合
  l = { t: "Bin", op, l, r: next() };  // 每轮把已有的树塞进左边
}
// 换成 return { t:"Bin", op, l, r: bin(next, ops) } 就成了右结合

• print 20 - 5 - 3; 输出 12（左结合，(20-5)-3）；把上面那句改成递归自调用，同一段源码输出 18（20-(5-3)）——一个字的改动，减法的语义就反了，而两种写法都编译通过、都不报错。
• 这正是 04 章「消除左递归保语言不保树形」那条 pitfall 的现场：文法变换之后照树求值会把 a-b-c 算错，修法就是在循环里用累加器自左向右建树——也就是上面这四行。

报错：一半的工程量在这里

// 本机上的三条报错
let y = ;          → 第 2 行: 表达式里出现意外的 ;
let x = (1 + 2;    → 第 1 行: 期望 )，实际 ;
let x = 1 @ 2;     → 第 1 行: 无法识别的字符 "@"   （这条来自①，词法期就拦下了）

• 三条错分属两个阶段，「报错来自哪一站」本身就是信息——这正是 01 章那张分诊卡的道理，只不过现在是你自己实现的。
• 能说出行号，全靠①在每个 token 上带了 line。这是「早期阶段多存一点元信息、后期阶段就能给出好诊断」的最小样本，也是 05 章说「手写递归下降报错友好」的实际来源。

符号表：先用一个 Map，再谈作用域

• 求值器的全部状态就是一个 Map<名字, 值>。08 章说的「一本按作用域分层的账」，在最简版本里就是一层；等你加了函数或块级作用域，把它换成「一叠 Map + 从栈顶往下查」，那一章的图就完全落地了。
• 查不到就报 未定义变量 zz——注意这是运行期报的。想让它变成编译期错误，就得在求值之前单独走一趟语义分析：那正是 08 章存在的理由，你会亲手感到「多一趟能换来什么」。

短路必须在求值器里特判

case "Bin":
  if (n.op === "&&") return ev(n.l) ? (ev(n.r) ? 1 : 0) : 0;   // 左假 → 右边根本不求值
  if (n.op === "||") return ev(n.l) ? 1 : (ev(n.r) ? 1 : 0);
  const a = ev(n.l), b = ev(n.r);        // ← 其余运算才两边都算

• 把这两行删掉，&& 就会走下面那句「两边都先算」。同一段源码 let ok = 0; if (ok != 0 && missing > 1) { print 1; } else { print 0; }：有短路时正常输出 0，删掉后抛出「未定义变量 missing」——左边明明已经把它挡住了。
• 顺带一个值得记住的坑：用「除以零」来演示短路，在这个宿主上是演示不出来的——JS 里 10 / 0 得 Infinity 而不是报错，取整后成了 0，两版输出一模一样。要验证短路，右操作数必须带一个在本语言里真的会炸的副作用；宿主语言的容忍度会悄悄吃掉你的测试用例，这类「测试其实什么都没测到」在写编译器时格外常见。
• 这就是 09 章那句「短路是语言的语义承诺，不是编译器的优化」——在你自己的求值器里，它是两行必须手写的特判，漏了就是语义 bug，没有任何优化器会替你补上。

三种执行方式的耗时

样例程序（n 从 0 到 9 累加 n*n） → 输出 285
3,000,000 次循环的版本        → 树遍历耗时 约 560~640 ms
                                （这个数字是第⑤级的对照基准，记住它）

为什么必须后序

• 先递归处理子树、再看自己——只有这样，2 * 3 + 4 * 5 里的两个乘法才会先变成 6 和 20，轮到加法时它才看得见「两个常量」。写成前序，加法先看到的是两棵子树，一次也折不动。
• 折叠完成后，If 的条件可能已经是常量——于是顺手做死分支消除：条件恒真就整个换成 then 分支、恒假换成 else，while (0) 直接删掉。这就是「常量传播 → 常量折叠 → 死代码消除」那条链，只不过你是在一趟遍历里同时做完的。

一段四行的源码

let x = 2 * 3 + 4 * 5;
if (1 > 2) { print 111; } else { print x; }
while (0) { print 999; }
print x * (10 - 10) + 7;

折叠前：AST 32 结点  →  编出 50 字节码
折叠后：AST 13 结点  →  编出 17 字节码
输出两版完全一致（26 和 7），语义不变

• 结点少了六成，字节码少了三分之二。注意 x * (10 - 10) 只折到 x * 0 就停了——再往前需要「乘 0 得 0」这条代数化简规则，而它不属于常量折叠。想让 print 那行也折成 7，就得再加一条代数恒等式规则，这正好演示了 11 章「优化技术是一箱互相喂球的改写」。
• 三十行代码换来六成结点，这个投入产出比就是编译器优化的日常：没有哪个 pass 是聪明的，聪明的是它们叠在一起反复跑。

栈式指令集：不用分配寄存器

• 操作数全部走一个栈：CONST 压常量、LOAD/STORE 读写变量槽、ADD 弹两个压一个。选栈式而不是三地址，就是为了跳过寄存器分配——那是 12 章一整章的内容，这一级先绕开（JVM、CPython、Lua 的字节码也都是栈式，理由相同）。
• 变量名在编译期就换成了槽位下标：运行期不再有任何字符串查找，这一步单独就能带来可观的提速——正是 08 章符号表「记录地址/偏移」的最小形态。

跳转靠回填：09 章那张卡的现场

// 编 if 时，还不知道 else 在哪 —— 先填 0 占位，记下位置
ex(n.cond); emit(OP.JZ, 0); const j = code.length - 1;
st(n.then);
code[j] = code.length;      // ← 现在知道了，回头把洞填上

• 先留空、后补填——和 09 章回填卡、01 章重定位说的是同一道工序。写错一格跳转就飞掉，而且不报错，只是结果不对：这是本级最容易调半天的 bug，也是最值得亲手踩一次的。

反汇编出来的字节码

// 反汇编 let a = 1; while (a < 3) { a = a + 1; } print a;
   0  CONST 1        11  LOAD 0
   2  STORE 0        13  CONST 1
   4  LOAD 0         15  ADD
   6  CONST 3        16  STORE 0
   8  LT             18  JMP 4       ← 回边，跳回条件
   9  JZ 20          20  LOAD 0
                     22  PRINT
                     23  HALT

// 300 万次循环的样例程序（同一份 AST，两种执行方式）
树遍历   约 560~640 ms
字节码VM 约 195 ms        ⇒ 加速 约 2.9~3.3 倍，输出完全一致
字节码长度 41 字，常量池 4 项，变量槽 2 个

• 三倍不是上限，也不是什么惊人数字——它买到的是「把每次执行都要做的判断，挪到只做一次的编译期」，这条原则在词法的 DFA、LR 的分析表、正则的预编译里已经出现过三次了。
• 想再快，路子就分两条：继续在 VM 里做（计算跳转 goto、超级指令、内联缓存），或者干脆别解释了——那就是下一级。

生成策略：先别管 SSA

• 每个变量老老实实 alloca 一个栈格，读写全走 load/store——不要试图自己构造 φ 函数。这不是偷懒，而是 LLVM 官方推荐的前端写法：把内存形式交给 mem2reg，它会用 11 章那套支配边界算法替你放 φ，比手写靠谱得多。
• 控制流按 09 章的方式编成基本块 + br：while 拆成 loop.cond / loop.body / loop.end 三块。短路的 && 这里必须真的编成分支并汇合出一个 phi——因为 IR 里没有「短路运算符」这种东西，它只有跳转。

mem2reg 当场生出 φ

$ node llvm.mjs '…样例程序…' > out.ll
$ opt -passes=mem2reg -S out.ll

loop.cond0:                        ; preds = %loop.body1, %entry
  %s.addr.0 = phi i64 [ 0, %entry ], [ %t11, %loop.body1 ]
  %n.addr.0 = phi i64 [ 0, %entry ], [ %t13, %loop.body1 ]
  %t5 = icmp slt i64 %n.addr.0, 10
  …

• 你生成的 IR 里一个 φ 都没有，全是 alloca/load/store；一趟 mem2reg 之后，两个循环变量各得到一个 φ，位置恰好在「两条前驱边汇合处」——09 章的 SSA 卡和 11 章的支配边界卡，在这两行里同时兑现了。

-O2 把整个循环算没了

$ opt -passes='default<O2>' -S out.ll

define noundef i32 @main() {
entry:
  %0 = tail call i32 (ptr, ...) @printf(ptr @.fmt, i64 285)
  ret i32 0
}

$ clang -O2 -S -masm=intel out.ll -o -
main:
  …
  mov  edx, 285          ← 循环整个不见了
  call printf

• 十次迭代的累加被完全在编译期算完：循环消失、变量消失，只剩一个立即数。你写的前端一行优化都没做，这些全部来自那条你白拿的 pass 管线。
• 这也是 01 章那条 pitfall 的实证：想观察真实的优化行为，输入必须是运行期才知道的值。把上界 10 换成从命令行读进来的数，循环就会老老实实留在汇编里。

第一级：15 章的六级台阶（起点在页内）

• 先把 15 章走完：它已经把「词法 → 递归下降 → 求值 → 常量折叠 → 字节码 VM → LLVM IR」六级各写了一个能跑的最小版本，每级一晚上收工。这一级不需要另找教材，也不必等读完全页——读到哪一章就能开工对应的那一级。
• 走完之后再给你的语言加函数与调用：这是 15 章刻意留白、也是收益最大的一次扩展，它会同时逼出参数传递、调用栈、作用域链与返回值约定——10 章运行时环境的内容从此有了体感。

第二级：把语言做完整

• 跟着免费在线书 Crafting Interpreters（《手写解释器》）把 Lox 做完：它是 15 章那条链的「完整版」——闭包、类、垃圾回收、更认真的错误恢复，正是最小骨架里省掉的部分。有了 15 章的底子，这本书会读得快得多。
• 再读 chibicc（Rui Ueyama 的迷你 C 编译器，每个 commit 就是一课）或 LLVM 官方的 Kaleidoscope 教程：前者体会「不靠框架直出汇编」（12 章那些指令选择、寄存器分配得自己来），后者是 15 章第⑥级往下的延伸——换成真正的 LLVM API 而不只是吐 IR 文本。

第三级：进阶读物与方向

• 系统补理论：《Engineering a Compiler》比龙书更工程视角、更好读；龙书当参考书按需查。想深入优化就读 SSA 相关论文与 LLVM 源码，想玩新方向看 MLIR（机器学习编译）。
• 参与真实项目：给 LLVM/GCC 提一个小 patch，或用 tree-sitter 给编辑器写一个语言的语法高亮——都是编译技术的「日常岗位」。