2026 春 · 实验班期末考试

编译原理（实验班）
期末一站式复习

覆盖 Lect01-15 全部考点，重点放在 Lect08-15 进阶内容。全部知识点来源课件，结合普通班 2016/2017/2018/2021 真题改编出更贴近实验班难度的练习。

15讲课件
17章节
30自测题
4年真题
📌 关于本站：所有知识点严格来源于实验班课件（Lect01-15）。真题部分来自普通班期末（5 份），仅作题型参照；实验班实际难度更高，因此「期末模拟练习」一节给出了加难版本，并明确标注难度。建议先过一遍课件知识点，再做真题与模拟题。

🎯 实验班期末考试形式（来自 Lect15 复习讲）

考试以大题形式，分「必答题」与「选答题」。
必答题覆盖：自底向上语法分析（LR / SLR / LALR）、语法制导翻译方案（回填思想的三地址代码生成）、运行时环境（非局部数据访问、垃圾回收）、代码优化（公共子表达式提取、死代码消除……）。
选答题覆盖：静态单赋值（Koopa IR）的生成与优化、函数式语言的编译、类型系统与类型检查。

📊 考点权重（基于课件复习讲 + 真题统计）整理推断

必答

LR / SLR / LALR 分析

FOLLOW 集、LR(0) 自动机、ACTION/GOTO 表（去年期末 20 分）

必答

SDT + 回填

三地址代码生成、布尔短路回填、控制流（去年期末 20 分）

必答

运行时 & 优化

访问链 / display、垃圾回收、活跃变量 + 图染色寄存器分配

选答

SSA / 函数式 / 类型

Koopa IR 块参数、闭包转换、类型判断规则与可靠性（各 20 分）

🗺️ 期末考点路线图 整理导图

1

前端速览（Lect01-07）

RE/自动机、LL(1)、CFG、SDD、三地址码——期中已细讲，期末快速回顾

2

LR 分析进阶（Lect11）

项/部分分析状态 → NFA → 子集构造 → LR(0)/SLR/LR(1)/LALR · 必答

3

语义 & IR 进阶（Lect12-13）

S/L 属性的移进-归约实现、标记符号、回填、数组寻址、SSA 生成 · 必答 + 选答

4

运行时 & 代码生成（Lect06-07,14）

访问链/display、垃圾回收、SSA 弦图着色、线性扫描 · 必答 + 选答

5

代码优化（Lect08,14）

DAG、窥孔、数据流分析四要素、四大经典问题 · 必答

6

函数式 & 类型（Lect09-10）

闭包、KNF/ANF/CPS、闭包转换；类型规则、可靠性、多态、递归类型、GADT · 选答

第 1 章 · 前端速览（Lect01-07） 课件 Lect01-07

这部分在期中复习里已详细展开（可点顶部「期中复习」切换查看）。此处仅做期末快速回顾与高频公式速记。

1.1 编译器流水线

源码
→
词法
→
语法
→
语义
→
IR
→
优化
→
代码生成
  • 前端（依赖源语言）：词法、语法、语义；后端（依赖目标机器）：代码生成、机器相关优化。
  • 符号表管理与错误处理贯穿全流程。

1.2 词法：RE → NFA → DFA → 最小化

环节关键点
RE → NFAThompson 构造，引入 $\varepsilon$ 转移
NFA → DFA子集构造（$\varepsilon$ 闭包 + move），最坏状态数 $O(2^n)$
DFA 最小化初始划分必为「接受态 / 非接受态」两组，再按转移细分
易错：NFA 与 DFA 表达能力相同；正则语言 $\subsetneq$ 上下文无关语言（如 $\{a^nb^n\}$ 是 CFL 非正则）。

1.3 自顶向下：LL(1)

消除左递归： $A \to A\alpha \mid \beta \Rightarrow A \to \beta A',\; A' \to \alpha A' \mid \varepsilon$

提取左公因子： $A \to \alpha\beta \mid \alpha\gamma \Rightarrow A \to \alpha A',\; A' \to \beta \mid \gamma$

LL(1) 条件：$A\to\alpha\mid\beta$ 要求 $\text{First}(\alpha)\cap\text{First}(\beta)=\varnothing$；若 $\varepsilon\in\text{First}(\alpha)$，还需 $\text{First}(\beta)\cap\text{Follow}(A)=\varnothing$。

1.4 语义：SDD / SDT

  • 综合属性：自底向上（孩子 → 父）；继承属性：自父或左兄弟流入。
  • S 属性（仅综合）$\subsetneq$ L 属性（综合 + 受限继承，只依赖父和左兄弟）。
  • S 属性可在 LR 归约时求值；L 属性在 LL/递归下降中一趟左→右求值。
概念辨析
下列关于前端各阶段的说法，正确的是？
A. NFA 比 DFA 能识别更多的语言
B. LR 分析必须先消除左递归
C. S 属性 SDD 是 L 属性 SDD 的真子集
D. 上下文无关文法无法描述所有正则语言
答案：C
A 错：NFA 与 DFA 表达能力相同。
B 错：LR 不需要消除左递归（这是 LR 相对 LL 的优势）。
C 对：S 属性（仅综合）$\subsetneq$ L 属性。
D 错：CFG 严格包含正则语言。

第 2 章 · LR 分析：项集族与分析表（Lect11） 课件 Lect11

2.1 自底向上分析的核心思想

  • 自底向上分析构造最右推导的逆过程：从左到右读入 token，在分析栈顶识别可归约的「模式」并归约。
  • 两类动作：移进 shift（把一个 token 压入分析栈）、归约 reduce（把栈顶若干符号归约为非终结符）。
  • 句柄 handle：当前最右句型中、可被某产生式右部归约的子串，总是出现在栈顶。
LR 文法：能用无冲突的移进-归约预测分析识别的 CFG。L=从左到右扫描；R=构造最右推导。LR(k) 表示部分分析状态记录 $k$ 个「再向前看」符号。

2.2 项（item）= 部分分析状态

用圆点 $\bullet$ 标记「已分析到哪里」，圆点左边是已进栈内容：

项含义
$A \to \bullet\,\alpha$准备开始分析 $\alpha$（栈顶可移进 $\text{First}(\alpha)$）
$A \to \alpha\bullet c\,\gamma$下一步移进终结符 $c$
$A \to \alpha\bullet B\,\gamma$对 $B$ 的每条产生式 $B\to\delta$ 加入 $B\to\bullet\,\delta$（$\varepsilon$ 闭包）
$A \to \alpha\,\bullet$可归约状态（栈顶 $\alpha$ 归约为 $A$）

2.3 构造识别活前缀的 DFA

把所有项作为 NFA 状态：

  • 对 $A\to\alpha\bullet c\gamma$，经 $c$ 转移到 $A\to\alpha c\bullet\gamma$（移进）。
  • 对 $A\to\alpha\bullet X\gamma$（$X$ 非终结符）：① 经 $X$ 转移到 $A\to\alpha X\bullet\gamma$；② 对每条 $X\to\delta$，经 $\varepsilon$ 转移到 $X\to\bullet\delta$。
  • 再用子集构造法（$\varepsilon$ 闭包 + 转移）把 NFA 化为 DFA，得到规范 LR(0) 项集族。

2.4 走通一个完整例子：括号文法

增广文法（无二义版本）：

[0] S' → S EOF
[1] S → ε
[2] S → [ S ] S

构造 LR(0) 项集族（部分状态）：

手算示范 括号文法的 LR(0) 项集与 SLR 分析表

对上面括号文法，构造 LR(0) 项集族 $I_0 \sim I_n$，并据 $\text{Follow}(S)=\{\,]\,,\text{EOF}\}$ 构造 SLR(1) 分析表。

项集族

状态项（闭包后）转移
$I_0$$S'\to\bullet S\,\text{EOF}$；$S\to\bullet$；$S\to\bullet [S]S$$S\!\to\!I_1$，$[\,\to\!I_2$
$I_1$$S'\to S\bullet\text{EOF}$$\text{EOF}\to$ 接受
$I_2$$S\to[\bullet S]S$；$S\to\bullet$；$S\to\bullet[S]S$$S\!\to\!I_3$，$[\,\to\!I_2$
$I_3$$S\to[S\bullet]S$$]\to I_4$
$I_4$$S\to[S]\bullet S$；$S\to\bullet$；$S\to\bullet[S]S$$S\!\to\!I_5$，$[\,\to\!I_2$
$I_5$$S\to[S]S\bullet$—（归约 [2]）

SLR(1) 分析表

含 $S\to\bullet$ 的状态（$I_0,I_2,I_4$）对 $\text{Follow}(S)=\{\,]\,,\text{EOF}\}$ 填归约 [1]；$I_5$ 对 $\text{Follow}(S)$ 填归约 [2]。

状态$[$$]$EOFGOTO S
$I_0$s2r1r11
$I_1$acc
$I_2$s2r1r13
$I_3$s4
$I_4$s2r1r15
$I_5$r2r2

无冲突 ⇒ 该文法是 SLR(1)。

真题改编 · 2018-三
在用 FOLLOW 集消解移进-归约冲突时，下列说法正确的是？
A. 只要某状态含可归约项 $A\to\alpha\bullet$，就一定能用 FOLLOW 消解所有冲突
B. FOLLOW 集过于粗糙，可能仍残留冲突（如 $S\to abd\mid aAc\mid bAd,\;A\to b$ 中栈顶 $ab$ 遇 $d$）
C. SLR(1) 的项集族比 LR(0) 多
D. SLR(1) 用的是 LR(1) 的精确展望符
答案：B
FOLLOW 集是「对所有上下文」求的，太粗糙。课件经典反例 $S\to abd\mid aAc\mid bAd,\;A\to b$：$\text{Follow}(A)=\{c,d\}$，栈顶 $ab$ 遇 $d$ 既想归约 $A\to b$ 又想移进，但实际归约后只有 $S\to aAc$ 适用（只允许 $c$）→ 须用更精确的「再向前看」（LR(1)）。
C 错：SLR(1) 与 LR(0) 项集族完全相同。D 错：SLR 用的是 FOLLOW，不是精确展望符。

第 3 章 · LR(0)/SLR/LALR/LR(1) 辨析（Lect11） 课件 Lect11

3.1 四种 LR 分析对照表（必背）

变种自动机状态归约时的展望符能力
LR(0)$\langle A\to\alpha\bullet\gamma\rangle$不使用展望符，对所有终结符归约最弱
SLR(1)与 LR(0) 相同用 $\text{Follow}(A)$ 确定中
LALR(1)与 LR(0) 同构（合并同心项集）每项带精确展望符，合并后强
LR(1)$\langle A\to\alpha\bullet\gamma,\,c\rangle$每项各带精确展望符 $c$最强

能力关系： $\text{LR}(0) \subsetneq \text{SLR}(1) \subsetneq \text{LALR}(1) \subsetneq \text{LR}(1)$；同时 $\text{LL}(k) \subsetneq \text{LR}(k)$。

状态数： $\text{LALR}(1)$ 状态数 $=$ $\text{LR}(0)$ 状态数（远少于 LR(1)），这是其实用价值的关键。

3.2 LR(1) 闭包的展望符传播规则（必考）

对项 $[A\to\alpha\bullet B\beta,\;a]$ 和产生式 $B\to\gamma$，加入 $[B\to\bullet\gamma,\;b]$，其中 $b\in\text{First}(\beta a)$。

若 $\beta$ 能推出 $\varepsilon$，则 $b$ 包含 $a$。

3.3 冲突类型与 LALR 的陷阱

冲突LR 表中能否出现说明
移进/归约 (S/R)可能同状态既要移进又要归约
归约/归约 (R/R)可能同状态两个归约项展望符重叠
移进/移进 (S/S)不可能移进由 GOTO 唯一决定
合并同心项集生成 LALR(1) 时：可能新增 R/R 冲突（展望符合并后归约项重叠），但不会产生新的 S/R 冲突（移进部分相同）。
课件反例：$S\to aAd\mid bBd\mid aBe\mid bAe,\;A\to c,\;B\to c$，栈顶 $ac$/$bc$ 合并后无法区分归约 $A\to c$ 还是 $B\to c$ → 归约/归约冲突。

3.4 「向前看」vs「再向前看」

  • LL(k)：向前看 $k$ 个符号来决定用哪条产生式推导（展开前就要猜）。
  • LR(k)：移进时向前看 1 个符号；归约时看到完整可归约子串后，再向前看 $k$ 个符号决定用哪条规则归约。
  • 因此 LR 看到的信息更多 → 表达能力更强。
综合判别 判断文法属于 SLR / LALR / LR(1) 哪一级

判断文法 $S \to Aa \mid bAc \mid dc \mid bda$；$A \to d$ 是否为 SLR / LALR / LR(1)。

分析读到 $d$ 后的状态

• 路径 $S\to Aa$：$d$ 由 $A$ 推出，期望后跟 $a$ → $[A\to d\bullet, a]$
• 路径 $S\to bAc$：$d$ 由 $A$ 推出，期望后跟 $c$ → $[A\to d\bullet, c]$
• 路径 $S\to dc$：直接 $[S\to d\bullet c]$（移进 $c$）
• 路径 $S\to bda$：$[S\to bd\bullet a]$

SLR(1)：$\text{Follow}(A)=\{a,c\}$。含 $[A\to d\bullet]$ 的状态对 $a,c$ 都归约，但同状态有 $[S\to d\bullet c]$ 想移进 $c$ → 移进/归约冲突，非 SLR。

LR(1)：$[A\to d\bullet,a]$ 与 $[S\to d\bullet c,\$]$ 在不同状态（展望符不同 → 路径不同 → 状态不同），无冲突。

LALR(1)：合并同心项集后，$[A\to d\bullet,a]$、$[A\to d\bullet,c]$、$[S\to d\bullet c]$ 进入同一状态：对 $c$ 既归约又移进 → 冲突。

结论：仅是 LR(1) 文法。

第 4 章 · SDD / SDT 与移进-归约实现（Lect12） 课件 Lect12

4.1 SDD 与 SDT

  • SDD（语法制导定义）= 属性文法：为产生式关联属性计算规则，不指定计算顺序。
  • SDT（语法制导翻译方案）：把属性计算改写为程序片段，用 { } 插入产生式右部任意位置，明确了求值顺序（深度优先遍历分析树时何时执行动作）。
  • 后缀翻译方案：所有语义动作都在产生式最右侧，适合 S 属性文法在 LR 归约时执行。

4.2 中缀转前缀（副作用 SDT 经典例）

输入 9+5*2，输出 + 9 * 5 2：

Expr → { print('+'); } Expr1 + Term
Term → { print('*'); } Term1 * Factor
Factor → INT { print(INT.lexeme); }

4.3 S 属性的移进-归约实现

分析栈中为每个非终结符记录综合属性；归约 $A\to B_1\cdots B_k$ 时按栈顶 $k$ 个符号属性计算 $A$ 的属性。如括号计数：

[0] S' → S EOF   { S'.cnt = S.cnt; }
[1] S → ε        { S.cnt = 0; }
[2] S → [S1] S2  { S.cnt = 1 + S1.cnt + S2.cnt; }

显式操作分析栈版本：stack[top-3].cnt = 1 + stack[top-2].cnt + stack[top].cnt; top = top-3;

4.4 L 属性的移进-归约实现：标记非终结符 ★难点

核心问题：L 属性含继承属性，信息可自顶向下流动，与自底向上分析方向不一致。
解决条件：当文法本身是 LL 的，自底向上移进时已有足够信息确定展开规则，于是以 LL 文法为基础的 L 属性 SDD 可用移进-归约实现。

方法：插入标记非终结符 $L,M,N$（产生式右部为 $\varepsilon$），在归约位置「下方」的固定偏移处存放继承属性。改写后文法变为 LR 文法。

S' → L S EOF
L → ε   { L.i = 0; }
S → [ M S1 ] N S2     { S.s = S2.s; }
M → ε   { M.i = 栈中归约位置减2处.i + 1; }
N → ε   { N.i = 栈中归约位置减2处.s; }

显式栈操作示例：M→ε: stack[top+1].i = stack[top-1].i + 1; top = top+1;

4.5 LL / LR × S / L 属性 支持矩阵

分析方法S 属性L 属性
LL（递归下降 / 表驱动）✅✅
LR（移进-归约）✅✅ 仅当以 LL 文法为基础（需标记符号）
概念辨析
关于在移进-归约分析中实现 L 属性 SDD，下列说法错误的是？
A. 插入标记非终结符后，文法从 LL 变为 LR，可移进-归约实现
B. 标记符号用于在分析栈固定偏移处放置继承属性
C. 该方法要求底层文法是 LL 的
D. 任意 L 属性 SDD（无论底层文法）都能直接用 LR 移进-归约实现
答案：D（错误项）
只有以 LL 文法为基础的 L 属性 SDD 才能用移进-归约实现，需借助标记非终结符在栈中固定位置安放继承属性。并非任意 L 属性都可以。

第 5 章 · 回填与控制流（Lect13） 课件 Lect13

5.1 回填（backpatching）思想

  • 短路求值时跳转目标在生成跳转指令时尚未确定；回填记录这些指令位置（指令数组下标），暂不填目标，待目标确定后回过头填上 → 一趟完成。
  • 三个辅助函数：makelist(i) 建只含指令 $i$ 的列表；merge(p1,p2) 合并；backpatch(p,i) 把列表 $p$ 中所有跳转目标填为 $i$。

5.2 布尔表达式：truelist / falselist

B → true:    B.truelist = makelist(nextinstr); emit("goto _");
B → E1==E2:  B.truelist = makelist(nextinstr); emit("if E1==E2 goto _");
             B.falselist = makelist(nextinstr); emit("goto _");
B → B1 && B2: backpatch(B1.truelist, nextinstr);
             B.truelist = B2.truelist;
             B.falselist = merge(B1.falselist, B2.falselist);
B → B1 || B2: backpatch(B1.falselist, nextinstr);
             B.truelist = merge(B1.truelist, B2.truelist);
             B.falselist = B2.falselist;
B → !B1:     B.truelist = B1.falselist; B.falselist = B1.truelist;

5.3 控制流语句：nextlist

S → if(B) S1:           backpatch(B.truelist, nextinstr);
                        S.nextlist = merge(B.falselist, S1.nextlist);
S → while(B) S1:        backpatch(S1.nextlist, S1.begin);
                        backpatch(B.truelist, nextinstr);
                        emit("goto S1.begin"); S.nextlist = B.falselist;
手算示范 · 真题母题 布尔表达式回填：x < 100 || (x > 200 && x != y)

从指令编号 100 开始，对 x < 100 || (x > 200 && x != y) 生成三地址码并给出最终 B.truelist / B.falselist。

100: if x < 100 goto _      ; 左 B 的 truelist
101: goto _                 ; 左 B 的 falselist
102: if x > 200 goto _       ; 进入 && 左部
103: goto _
104: if x != y goto _
105: goto _

处理 x>200 && x!=y：backpatch({102}, 104)（左真则测右）。该子式 truelist={104}，falselist=merge({103},{105})={103,105}。

处理 ||：backpatch(左falselist={101}, 102)（左假才测右）。

最终： B.truelist = merge({100}, {104}) = {100, 104}；B.falselist = {103, 105}。

5.4 回填法 vs CFG 直接生成法

回填法CFG / 基本块直接生成
跳转目标综合属性 truelist/falselist（先记后填）继承属性 B.true / B.false（提前生成目标块）
辅助makelist / merge / backpatchnew_bb() / set_bb() / emit()
输出带回填的三地址码序列控制流图（基本块 + 跳转）

第 6 章 · 数组寻址与类型声明（Lect13） 课件 Lect13

6.1 寻址公式（必背）

一维：$\text{addr}(A[i]) = base + i\times w$

二维：$\text{addr}(A[i_1][i_2]) = base + i_1\times w_1 + i_2\times w_2$，其中 $w_2=w$，$w_1=n_2\times w$

$k$ 维按行存放：$\text{addr} = base + (\cdots((i_1 n_2 + i_2)n_3 + i_3)\cdots)n_k + i_k)\times w$

下标非 0 起（Pascal $[low..high]$）：$\text{addr}(a[i]) = base + (i-low)\times w$

6.2 类型宽度计算

数组类型用继承属性 $t$（元素类型）、$w$（元素宽度）；声明 int[2][3]：

  • type = $\text{array}(2,\text{array}(3,\text{int}))$
  • width = $2\times 3\times 4 = 24$（int 宽度 4）

6.3 结构体对齐（真题高频）

对齐规则：每个成员的偏移须是其对齐要求的整数倍，必要时填 padding；结构体总大小须是最大对齐的整数倍。真题常考「给定成员，写访问成员的三地址码（含字节偏移加法）」。
手算示范 · 真题母题 二维数组引用的三地址码

设 int a[10][20]（int 宽度 4，按行存放），写出 x = a[i][j] 的三地址码。

t1 = i * 20      ; 行偏移（元素个数）
t1 = t1 + j      ; 总元素下标
t2 = t1 * 4      ; 字节偏移（w = 4）
x  = a[t2]       ; 取值

地址 $= base + (i\times 20 + j)\times 4$，与 $k$ 维按行公式一致。

第 7 章 · 静态单赋值 SSA（Lect13） 课件 Lect13 · 选答

7.1 SSA 概念

SSA（Static Single Assignment）：所有赋值针对不同名字的变量，对一个名字的使用都能找到唯一定值。LLVM IR、Koopa IR 均采用 SSA。

三地址码 p=a+b; q=p-c; p=q*d; → SSA p1=a+b; q1=p1-c; p2=q1*d;

7.2 合并不同路径定值的两种设计

设计形式代表
φ 函数$x_3 = \phi(x_1, x_2)$LLVM IR
块参数L(z): y = z*a;，跳转写 goto L(x1)Koopa IR

7.3 入门生成法：alloc / load / store

为每个程序变量开辟内存（alloc），用 load 读、store 写，使变量对应唯一内存位置：

S → T ID;:  emit("genvar(ID) = alloc");
E → ID:     E.addr = gentmp(); emit("E.addr = load genvar(ID)");
S → ID=E;:  emit("store E.addr genvar(ID)");

优化：符号表记录变量当前值的地址，尽量推迟写回内存（→ local / global value numbering）。

7.4 高质量 SSA 生成（块参数 / Koopa IR）

  • 两趟法：第一趟每个基本块以所有变量为参数、块内做 local value numbering 转 SSA；第二趟若某参数 $x_i$ 在所有跳转处都等于同一个 $x_k$，则移除该参数并把 $x_i$ 替换为 $x_k$。
  • 一趟法：块内 local value numbering；变量使用不在块内时看前驱——单前驱递归处理前驱，多前驱则添加该变量为块参数并递归传实参。
选答母题 while 循环的块参数 SSA

把 r=1; while(e>0){ r=r*b; e=e-1; } return r; 转为块参数形式的 SSA（Koopa 风格）。

entry:
  goto loop(e0, 1)          ; r 初值 1
loop(e1, r1):
  t = e1 > 0
  if t goto body(e1, r1) else goto done(r1)
body(e2, r2):
  r3 = r2 * b
  e3 = e2 - 1
  goto loop(e3, r3)         ; 回边传递新值
done(r4):
  return r4

每个名字（$e_1,r_1,r_3,\dots$）都只定值一次；循环汇合点用块参数合并来自 entry 与 body 的不同定值（等价于 $\phi$ 函数）。第二趟可消去 loop 中始终不变的参数（如本例 $b$ 未作参数）。

第 8 章 · 非局部数据访问与垃圾回收（Lect06,14） 课件 Lect06,14 · 必答

8.1 静态作用域 vs 动态作用域

静态（词法）作用域动态作用域
非局部名字绑定确定时机过程被定义时过程被调用时
实现访问链 / display运行时为每个名字维护作用域栈
代表多数语言Emacs Lisp
经典输出对比（外层 r，small 内重定义 r=0.125 后调 show）：动态作用域 show 打印 small 的 r → 0.125；静态作用域 show 始终用定义处外层 r → 0.25。

8.2 访问链（access link）

  • 嵌套深度：若 p 定义在深度 $i$ 的过程中，则 p 深度为 $i+1$。沿访问链走一步使深度恰好少一。
  • 建立（深度 $m$ 的 q 调用深度 $n$ 的 p）：若 $m \lt n$（必 $m+1=n$），p 的访问链指向 q 的活动记录；若 $m\ge n$，沿 q 的访问链走 $m-n+1$ 步找到目标活动记录。
  • 访问（深度 $m$ 访问深度 $n$，$n\le m$）：沿访问链走 $m-n$ 步，步数编译期确定。

8.3 显示表（display）

数组 $d$，$d[i]$ 指向最近的深度为 $i$ 的活动记录 → 访问开销为常数。调用深度 $n$ 的 p 时保存原 $d[n]$ 并令其指向 p 的活动记录，返回时恢复。

8.4 过程作为参数 / 结果 → 闭包

  • 过程作参数：传递时同时传其访问链。
  • 过程作结果返回：栈式活动记录管理不再适用（活动记录可能已出栈）→ 用闭包，在堆上存储所需外层局部数据。
  • Lua 的 upvalue：初始指向栈中数据，若逃逸则转移到堆。

8.5 垃圾回收

方法机制优点缺点
引用计数每对象计数，赋值时增减，归零即回收增量、无长停顿、及时空间/时间代价、循环引用泄漏
标记-清扫从根集遍历标记可达，再清扫不可达正确处理循环、几乎无空间代价全面停顿、堆碎片
标记-压缩标记 + 重定位消除碎片消碎片需更新所有指针
拷贝回收From/To 半空间，拷贝可达对象后角色互换无需扫整堆压缩仅用一半空间
世代回收按对象年龄分代，年轻代更频繁回收利用「大多对象短命」实现复杂
根集 root set：无需解引用即可直接访问的数据（静态字段、栈中变量）。可达性：根集可达；可达对象字段指向的对象也可达。一旦不可达就不会再变可达。
真题改编 · 引用计数
关于引用计数式垃圾回收，下列说法正确的是？
A. 能自动回收所有不可达对象，包括循环引用
B. 需要周期性扫描整个堆
C. 删除对象前，需先把其内部指针所指对象的计数各减一
D. 不会产生任何运行时开销
答案：C
A 错：无法回收循环引用（计数永不归零）。B 错：引用计数是增量式，不需扫整堆（那是标记-清扫）。C 对：删除对象前要把它指向的对象计数各 −1（可能级联回收）。D 错：每次指针更新都要改计数，有时间/空间开销。

第 9 章 · 寄存器分配与弦图（Lect07,14） 课件 Lect07,14

9.1 图着色寄存器分配（真题骨架题）

  • 活跃变量分析（后向）：$\text{IN}[B]=\text{use}_B\cup(\text{OUT}[B]-\text{def}_B)$，$\text{OUT}[B]=\bigcup_{S\in succ}\text{IN}[S]$。
  • 冲突图（干扰图）：同一程序点同时活跃的两变量连边。
  • k 着色：反复移除度 $\lt k$ 的结点入栈（simplify），再回填上色；无法移除时溢出 spill。

9.2 SSA → 弦图（选答进阶）

弦图（chordal graph）：每个长度 $\ge 4$ 的环都有弦（连接环中不相邻两点的边）。
关键结论 [Hac07]：SSA IR 产生的冲突图都是弦图；实践中约 95% 冲突图是弦图。
  • 单纯点：邻居构成一个团的点。单纯消除序列：每个 $v_i$ 是子图 $\{v_1,\dots,v_i\}$ 中的单纯点。
  • 定理：图有单纯消除序列 $\iff$ 它是弦图。按单纯消除序列着色得最优方案，复杂度 $O(|V|+|E|)$。
  • 合并 coalescing：在弦图上先着色后合并（合并可能破坏弦图性质，故顺序为「构图→单纯消除序列→着色→合并」）。

9.3 线性扫描寄存器分配（LSRA）

  • 为每个符号寄存器计算活性区间 live interval；区间重叠的不能同寄存器。
  • 维护按区间终点排序的 active 队列；扫到新区间起点时移除过期区间、加入新区间。复杂度 $O(|V|\log|R|)$。
  • 关于代码大小线性，效果接近图着色 → LLVM、JVM JIT 默认采用（JIT 看重编译速度）。
概念辨析 · 选答
关于 SSA 与寄存器分配，正确的是？
A. SSA 形式的冲突图是弦图，可在多项式时间内求得最优着色
B. 一般图的着色问题也能在多项式时间求最优解
C. 线性扫描的效果一定优于图着色
D. 在弦图上做合并后图一定仍是弦图
答案：A
SSA 冲突图是弦图，借单纯消除序列可多项式时间最优着色。B 错：一般图着色 NP 难。C 错：线性扫描更快但效果接近而非一定优于图着色。D 错：弦图上合并可能破坏弦图性质，故须先着色后合并。

第 10 章 · 局部优化 / DAG / 窥孔（Lect08） 课件 Lect08 · 必答

10.1 常用优化方法

方法说明
公共子表达式消除复用已算且分量未变的表达式
复写传播$x=y$ 后把用 $x$ 处换成 $y$，最终删 $x=y$
死代码消除删除计算结果永不被用的语句
常量传播 / 折叠编译期已知常量则代入 / 表达式求值（如 $3\times2\to6$）
代码外提 LICM循环不变式提到循环前只算一次
强度消减用加减替代乘法（归纳变量 $4j$ 每轮 $-4$）
归纳变量消除步调一致的归纳变量合并（如 $i\ge j$ 改 $t_2\ge t_4$）

10.2 基本块 DAG

  • 变量结点表初值；语句 $x=y\,op\,z$ 建标号 $op$ 的结点，孩子为 $y,z$ 当前关联结点，令 $x$ 关联 $N$。
  • 复写 $x=y$ 不建新结点，$x$ 关联到 $y$ 的结点。
  • 建结点前查找相同运算符 + 相同孩子（顺序相同）的已有结点 → 复用（局部公共子表达式消除）。
  • 消死代码：删没有附加活跃变量的根结点；代数恒等式：$x+0=x$、$x\times2=x+x$ 等。
数组别名陷阱：x=a[i]; a[j]=y; z=a[i] 中 a[i] 与 a[j] 可能别名，a[j]=y（运算符 []=）杀死所有依赖 a 的结点，故 z 须重算。指针 *q=y、过程调用同理（保守假设杀死/使用所有可访问数据）。

10.3 窥孔优化（四类）

类别例子
冗余指令消除LD R1,a; ST a,R1 中第二条多余；不可达代码消除
控制流优化goto L1 … L1:goto L2 → goto L2
代数化简LD R2,#0; ADD R3,R1,R2 → LD R3,R1
机器特有指令LD R2,#1; ADD R1,R1,R2 → INC R1
真题改编 · 优化辨析
把 t = 4 * j（循环内 j 每轮减 1）改为循环外 t = 4*j、循环内 t = t - 4，属于？
A. 公共子表达式消除
B. 强度消减（归纳变量）
C. 复写传播
D. 常量折叠
答案：B
$j$ 是归纳变量（每轮 −1），故 $4j$ 每轮 −4，用加减替代乘法即强度消减，但需在循环外对 $t$ 初始化。

第 11 章 · 数据流分析框架（Lect08） 课件 Lect08 · 必答

11.1 框架四要素

  • 域 domain：数据流值集合（变量集 / 定值集 / 表达式集）。
  • 方向：前向（$\text{OUT}[B]=f_B(\text{IN}[B])$，IN 由前驱汇合）/ 后向（$\text{IN}[B]=f_B(\text{OUT}[B])$，OUT 由后继汇合）。
  • 传递函数 $f_B$：基本块入口与出口数据流值的关系，由语句传递函数复合得到。
  • 交汇运算 $\wedge$：$\cup$（may，存在路径满足）/ $\cap$（must，所有路径满足）。

用顶值 $\top$ 初始化，迭代套用方程直到不动点（没有基本块需更新）。

11.2 四大经典数据流问题对照表（必背）

活跃变量可达定值可用表达式
域变量集合定值集合表达式集合
方向后向前向前向
传递函数$(O-\text{def}_B)\cup\text{use}_B$$(I-\text{kill}_B)\cup\text{gen}_B$$(I-\text{ekill}_B)\cup\text{egen}_B$
交汇$\cup$（may）$\cup$（may）$\cap$（must）
边界 / 初值$\text{IN}[\text{EXIT}]=\varnothing$$\text{OUT}[\text{ENTRY}]=\varnothing$$\text{OUT}[\text{ENTRY}]=\varnothing$，其余 $\top=$ 全集
用途寄存器分配 / 死代码常量传播公共子表达式消除
第四个经典问题——忙表达式（very-busy / anticipated expression）：方向后向、交汇 $\cap$（must），是部分冗余消除（PRE）/ 代码提升的理论基础（真题 2021-七）。

11.3 变量符号分析（前向例）

符号格：正 / 零 / 负 / 槑（=所有数，表示「未知」）。交汇 $v_1\wedge v_2=v_1$（若相等），否则 $=$ 槑。基本块传递函数 $f_B=f_{s_n}\circ\cdots\circ f_{s_1}$（前向复合顺序）。

手算示范 判别数据流问题的方向与交汇

对下列分析，分别指出方向（前向/后向）与交汇运算（$\cup$/$\cap$）：①活跃变量 ②可用表达式 ③可达定值 ④忙表达式。

分析方向交汇记忆口诀
活跃变量后向$\cup$ (may)「未来可能被用」→ 任一后继用即活
可用表达式前向$\cap$ (must)「所有路径都算过」→ 取交
可达定值前向$\cup$ (may)「某条路径可达」→ 取并
忙表达式后向$\cap$ (must)「所有后继都会算」→ 后向取交

记忆：活跃/忙后向；可达/可用前向。must（all paths）取交，may（some path）取并。

第 12 章 · 函数式语言的编译（Lect09） 课件 Lect09 · 选答

12.1 环境求值与闭包

  • 环境 $\rho$：维护「自由变量 → 值」的绑定；$[x\mapsto v]\rho$ 扩展，后绑定覆盖先绑定。
  • 求值三元关系 $\rho \vdash E \Rightarrow v$：在环境 $\rho$ 下对 $E$ 求值得 $v$。
  • 静态（词法）作用域：函数体里的自由变量用定义时的环境，不是调用时。
  • 闭包 closure $=(f, x, E_1, \rho)$：记录函数定义时「当时」的环境。这是高阶函数（参数生命周期超过定义它的函数）能正确求值的关键。

let 规则： $\dfrac{\rho\vdash E_1\Rightarrow v_1\quad [x\mapsto v_1]\rho\vdash E_2\Rightarrow v}{\rho\vdash \text{let}(x,E_1,E_2)\Rightarrow v}$

带闭包的 call： 取出闭包记录的 $\rho'$，在 $[x'\mapsto v_1,\,f'\mapsto\text{闭包}]\rho'$ 下求值函数体。

作用域手算陷阱：let f x = let g y = x+y in let x=42 in g(2*x) end end in f 7 end 结果是 91：g 体里的 x 用 g 定义时的 7（不是后来的 42），$g(2\times42)=g(84)=7+84=91$。

12.2 三种正规形式（IR）对照

正规形式约束转换复杂度
KNF（K-Normal Form）运算分量、分支条件不嵌套；let 可随意嵌套简单
ANF（A-Normal Form）运算分量、分支条件、let...in 中间部分都不嵌套中
CPS（Continuation-Passing Style）不嵌套；只有尾递归；每个函数加回调参数复杂
规律：从上到下，嵌套结构越简单，转换算法越复杂。ANF 的 if 陷阱：若把 if 当复杂表达式放入 let，分支后续代码会在两分支各复制一份 → 可能代码指数膨胀；解法是把 if 留在 let 中间部分或引入续延 retif。

12.3 CPS 变换（必会手写）

// 阶乘：递归构造新回调
fac(n,ret){ if(n==0) ret(1);
            else fac(n-1, t1 => ret(n*t1)); }
// 尾递归阶乘：直接传 ret，不引入新回调
tail_fac(n,a,ret){ if(n==0) ret(a); else tail_fac(n-1, n*a, ret); }
// 斐波那契：两处递归 → 嵌套两层回调
fib(n,ret){ if(n<2) ret(1);
            else fib(n-1, t1 => fib(n-2, t2 => ret(t1+t2))); }

CPS ↔ SSA/Koopa：尾递归函数调用就像控制流图上的带参 goto，回调对应一个基本块。

12.4 闭包转换（Closure Conversion）

目标：转换后所有函数都是「最外层」函数 @ℓ，并显式构造闭包。对每个 letfun：

  1. 生成新函数标记 @ℓ；
  2. 分析函数体的自由变量作为闭包参数 $y_1,\dots,y_m$；
  3. 最外层生成 fun @ℓ {y1..ym} x = E1；
  4. 原位置改为 let f = clos @ℓ {y1..ym} in E2。

运行时表示：闭包 = { func: 函数指针, env: 闭包环境 }。优化：若被调函数没有自由变量，就不必创建闭包。

概念辨析 · 选答
关于函数式语言编译，下列说法错误的是？
A. 闭包需要记录函数定义时的环境，以支持静态作用域下的高阶函数
B. KNF 允许 let 任意嵌套，转换最简单
C. CPS 中尾调用相当于带参数的 goto
D. 闭包转换中，即使函数没有自由变量也必须创建闭包环境
答案：D（错误项）
闭包转换的优化之一：若已知具体调用函数且该函数没有自由变量，就不用创建闭包。其余 A/B/C 均正确。

第 13 章 · 类型系统（Lect10） 课件 Lect10 · 选答

13.1 类型与类型判断

  • 类型是对程序行为的简洁、准确的形式化描述。「Well-typed expressions do not go wrong」(Milner)。
  • 类型判断三元关系 $\Gamma \vdash E : T$：在类型上下文 $\Gamma$（变量→类型）下，$E$ 的类型是 $T$。
  • 简单类型：$T ::= \text{int} \mid \text{bool} \mid T_1 \to T_2$。
  • 静态类型缺点：可靠、可判定的类型系统一定会拒绝一些实际安全的程序。

13.2 类型规则（必背形式）

$\dfrac{}{\Gamma\vdash \text{const}(n):\text{int}}\qquad \dfrac{}{\Gamma\vdash \text{var}(x):\Gamma(x)}$

$\dfrac{\Gamma\vdash E_1:\text{bool}\quad \Gamma\vdash E_2:T\quad \Gamma\vdash E_3:T}{\Gamma\vdash \text{if}(E_1,E_2,E_3):T}$（两分支同类型）

$\dfrac{\Gamma\vdash E_1:T_1\quad \Gamma;x:T_1\vdash E_2:T_2}{\Gamma\vdash \text{let}(x,E_1,E_2):T_2}$

$\dfrac{\Gamma\vdash E_1:T_1\to T_2\quad \Gamma\vdash E_2:T_1}{\Gamma\vdash \text{call}(E_1,E_2):T_2}$（函数应用）

13.3 类型可靠性（type soundness）★难点

定理：若 $\varnothing\vdash E:T$，则要么求值得到值 $v$ 且 $v$ 具有类型 $T$，要么求值不停机（也不出错）。
  • 证明方法：对求值推导 $\rho\vdash E\Rightarrow v$ 做结构归纳。
  • 关键技巧——强化命题：直接对原命题归纳会在 let / 函数体处失败，须强化为：「若 $\Gamma\vdash E:T$、$\rho\vdash E\Rightarrow v$ 且 $\rho:\Gamma$（环境与上下文一致），则 $v:T$」。
  • 闭包定型：$\dfrac{\rho:\Gamma\quad \Gamma,f:T_1\to T_2,x:T_1\vdash E:T_2}{\text{closure}(f,x,E,\rho):T_1\to T_2}$。

13.4 多态

类型含义例
参数多态不同类型上行为相同C++ template、Rust 泛型、$\forall X.\,T$
特设多态不同类型上行为不同运算符重载、Rust trait、Haskell typeclass
子类型多态OO 中的子类型继承

多态调用是显式类型实参代入：$\dfrac{\Gamma\vdash E_1:\forall\vec X.T_1\to T_2\quad \Gamma\vdash E_2:T_1[\vec T/\vec X]}{\Gamma\vdash \text{call}(E_1,\langle\vec T\rangle,E_2):T_2[\vec T/\vec X]}$。运行时可做类型擦除。

13.5 乘积 / 加和 / 递归类型

乘积：$\dfrac{\Gamma\vdash E_1:T_1\quad \Gamma\vdash E_2:T_2}{\Gamma\vdash \text{pair}(E_1,E_2):T_1\times T_2}$；单位元 $1$（unit）。$1\times T\simeq T$。

加和：$\dfrac{\Gamma\vdash E_1:T_1+T_2\quad \Gamma\vdash E_2:T_1\to T\quad \Gamma\vdash E_3:T_2\to T}{\Gamma\vdash \text{case}(E_1,E_2,E_3):T}$；单位元 $0$。$0+T\simeq T$。

递归：$\text{nat}\simeq 1+\text{nat}$，$\text{list}(X)\simeq 1+X\times\text{list}(X)$。iso-recursive 用 fold/unfold：$\dfrac{\Gamma\vdash E_1:T[(\mu X.T)/X]}{\Gamma\vdash \text{fold}(E_1):\mu X.T}$。

自应用阶乘为何在简单类型下不可类型化？ makefac 自应用产生约束方程 $T_1 = T_1\to(\text{int}\to\text{int})$，无穷展开，简单类型无法满足 → 体现「类型系统限制表达能力」。用递归类型 $OO\simeq OO\to(\text{int}\to\text{int})$ 可解此方程。

13.6 GADT（泛化代数数据类型）

GADT = 允许 ADT 不同分支有不同的类型参数。经典例：良类型的 eval : 't exp -> 't value（求值无需运行时检查）、良类型的 printf : 'a desc -> 'a（参数个数/类型由格式串决定仍保证良类型）。

概念辨析 · 选答
关于类型系统，下列说法正确的是？
A. 可靠且可判定的类型系统能精确接受所有安全程序
B. 类型可靠性证明可直接对原命题归纳，无需强化
C. self-application 阶乘的约束方程 $T_1=T_1\to(\text{int}\to\text{int})$ 在简单类型下无解
D. 参数多态指多态函数在不同类型上行为不同
答案：C
A 错：可靠可判定一定会拒绝一些实际安全的程序。B 错：须强化命题（引入 $\rho:\Gamma$）才能归纳成功。C 对：该方程无穷展开，简单类型无解，需递归类型。D 错：行为相同才是参数多态，行为不同是特设多态。

第 14 章 · 期末真题精选（普通班）真题改编

以下题目取自普通班 2016/2017/2018/2021 期末真题，作为题型参照。实验班难度更高，请配合下一章「期末模拟练习（更难）」一起练。
真题 · 2018-三（SLR 证明） 补全 LR(0) 自动机并证明文法是 SLR(1)

给定文法，构造 LR(0) 项集自动机，指出冲突状态及类型，并证明该文法是 SLR(1)（即所有冲突均可由 FOLLOW 集消解）。

解题套路

① 增广文法 $S'\to S$；② 从 $I_0=\text{closure}(\{S'\to\bullet S\})$ 起做 GOTO 逐状态展开；③ 找出含可归约项 $A\to\alpha\bullet$ 且同时有移进项或多个归约项的状态（潜在冲突）；④ 对每个冲突状态，检查冲突双方的展望符（移进项的下一终结符 vs $\text{Follow}(A)$）是否不相交；⑤ 若全部不相交 → 是 SLR(1)。

关键是写清楚每个冲突状态的判断依据，而非只给结论。

真题 · 2021-二.1（回填） 用回填技术计算语句的 nextlist

给定一段含 if / while 的程序，按回填技术生成三地址码，求各语句 $S_6\sim S_{11}$ 的 nextlist。

解题套路

① 自底向上为每个布尔/语句维护 truelist、falselist、nextlist；② if(B)S1：backpatch(B.truelist, S1首条)，S.nextlist = merge(B.falselist, S1.nextlist)；③ while(B)S1：循环体末尾回跳测试入口，S.nextlist = B.falselist；④ 逐条记录指令编号，最后合并列表。

注意「多余的 goto」可在后续优化删除，但回填阶段仍按规则生成。

真题 · 2016-二.4（运行时） ML 嵌套函数的活动记录栈

ML 实现 Fibonacci，main→fib0→fib1→fib2 三层嵌套定义，从 fib0(4) 调用直到 fib0(1) 即将返回，画活动记录栈（控制链 + 访问链）。

解题套路

控制链指向调用者的活动记录（动态、与调用顺序有关）；访问链指向词法外围函数的最近活动记录（静态、由嵌套层次决定，与调用顺序无关）。逐层展开调用，按嵌套深度差确定访问链指向。
真题 · 2021-七（数据流） 繁忙表达式与最早放置表达式

定义 very-busy expression（从 $p$ 出发所有路径都会在被杀死前求值 $e$），给出其数据流算法；对具体 CFG 求繁忙集；判定 earliest expression，并给出 earliest[p] 关于 avail/busy/live 的公式。

解题套路

繁忙表达式是后向 + must（取交）分析：出口初始化为空，$\text{IN}=\text{egen}\cup(\text{OUT}-\text{ekill})$，交汇取所有后继的交。
earliest 大致 $=$「繁忙但尚不可用」$\approx \text{busy}[p]\cap\neg\text{avail}[p]$，是部分冗余消除（PRE）的放置点。

这是最接近研究生级 Lazy Code Motion 的真题，非常适合作为实验班加难母题。

第 15 章 · 期末模拟练习（实验班难度）自编加难

本节在普通班真题基础上加难，更贴近实验班。每题标注「加难点」。建议先独立完成再看解答。
模拟 1 · LR 进阶 SLR 失败、LALR 引入 R/R 冲突、仅 LR(1)

文法 $S\to aAd\mid bBd\mid aBe\mid bAe$；$A\to c$；$B\to c$。判断它是 LR(0) / SLR(1) / LALR(1) / LR(1) 中的哪几级，并说明 LALR 合并时发生了什么。
加难点：要求构造出现 R/R 冲突的具体状态，并解释 LR(1) 为何无冲突。

分析

读到 $ac$：可能来自 $S\to aAd$（$[A\to c\bullet,d]$）或 $S\to aBe$（$[B\to c\bullet,e]$）。读到 $bc$：来自 $S\to bBd$（$[B\to c\bullet,d]$）或 $S\to bAe$（$[A\to c\bullet,e]$）。

LR(1)：$ac$ 状态含 $[A\to c\bullet,d]$、$[B\to c\bullet,e]$，展望符不同（$d$ 归约 $A$、$e$ 归约 $B$）→ 无冲突。$bc$ 状态同理。

LALR(1)：$ac$ 与 $bc$ 是同心项集（核心都是 $\{A\to c\bullet, B\to c\bullet\}$），合并后展望符并集：$A\to c\bullet$ 带 $\{d,e\}$、$B\to c\bullet$ 带 $\{d,e\}$ → 对 $d$、$e$ 都既能归约 $A$ 又能归约 $B$ → 归约/归约冲突。

结论：非 SLR、非 LALR，仅 LR(1)。这正是「LALR 合并同心集可能新增 R/R 冲突」的标准反例。

模拟 2 · 数据流（加难） 未初始化变量传播 + 级联死代码消除

定义「僵尸语句」：使用的变量「总是未初始化」的语句。设计数据流分析（域 / 方向 / 传递函数 / 交汇），并讨论级联消除。
加难点：① 区分 may-uninitialized（取并）与 must-uninitialized（取交）两套格并说明保守方向；② 把级联消除形式化为 worklist 不动点迭代并给复杂度。

第一步：未初始化传播（前向）

「必然未初始化」用 must（取交）：域 = 变量集，方向前向，ENTRY 处所有局部变量未初始化。语句 x = expr：若 expr 任一变量 $\in$ 未初始化集 → 该语句是僵尸；否则把 $x$ 移出未初始化集。汇合 $\text{IN}[B]=\bigcap_{P}\text{OUT}[P]$。

may vs must： must-uninitialized（取交，所有路径都未初始化）用于报错/判僵尸，保守地只在「确定未初始化」时动手；may-uninitialized（取并，存在路径未初始化）用于告警。二者保守方向相反。

第二步：级联消除（worklist）

删除一条僵尸语句后，原本依赖其结果的语句可能也变僵尸 → 用 worklist：初始化所有僵尸语句入队；出队删除后，把使用其定值的语句重新检查入队。

复杂度：每条语句最多被重新检查 $O(\text{依赖它的语句数})$ 次，整体 $O(|V|\cdot|\text{vars}|)$。终止性由「未初始化集单调收缩 + 僵尸集单调增长」保证。

模拟 3 · SSA（选答加难） CFG → 块参数 SSA → 非 SSA 三地址码

给定含 if-else 汇合的 CFG，① 转为块参数形式 SSA（Koopa 风格）；② 用两趟法消去冗余块参数；③ 再转回非 SSA 的三地址码（需插入复制指令）。

① 转 SSA

每个基本块对块内重复赋值的变量重命名（local value numbering）；汇合块把来自不同前驱、有不同定值的变量列为块参数，前驱跳转处传实参 goto join(x_then, ...) / goto join(x_else, ...)。

② 两趟优化

第二趟检查每个块参数：若所有跳转到该块的实参都是同一个名字（或同一来源），则移除该参数并用该名字替换所有使用。

③ 转回非 SSA

把块参数 / φ 函数下沉为复制指令：在每个前驱块末尾、跳转前插入 join_param = 该前驱传入的实参，再普通跳转。注意并行复制的交换问题（如 swap）须引入临时变量。

模拟 4 · 类型系统（选答加难） 类型推导 + 可靠性证明的 let 情形

① 对 let f x = (let g y = x + y in g) in (f 2) 3 写出各层类型上下文 $\Gamma$ 并推导整体类型；② 解释类型可靠性证明中，为什么 let 情形必须强化命题（引入 $\rho:\Gamma$）。

① 类型推导

$f : \text{int}\to(\text{int}\to\text{int})$。各层上下文：

$\Gamma_4 = \{f:\text{int}\to(\text{int}\to\text{int})\}$
$\Gamma_1 = \Gamma_4;\,x:\text{int}$
$\Gamma_3 = \Gamma_1;\,g:\text{int}\to\text{int}$
$\Gamma_2 = \Gamma_3;\,y:\text{int}$

$g=\lambda y.\,x+y$ 类型 $\text{int}\to\text{int}$；$f$ 返回 $g$，故 $f:\text{int}\to(\text{int}\to\text{int})$。$(f\,2)$ 得 $\text{int}\to\text{int}$，再应用 $3$ → 整体类型 $\text{int}$。

② 为何强化命题

原命题「$\varnothing\vdash E:T \wedge []\vdash E\Rightarrow v \Rightarrow v:T$」在 let 情形归纳会卡住：$E_2$ 在扩展环境 $[x\mapsto v_1]\rho$ 下求值、在扩展上下文 $\Gamma;x:T_1$ 下定型，无法套用「空环境/空上下文」的归纳假设。

必须强化为「$\Gamma\vdash E:T \wedge \rho\vdash E\Rightarrow v \wedge \rho:\Gamma \Rightarrow v:T$」：由归纳假设 $v_1:T_1$ → $[x\mapsto v_1]\rho : \Gamma;x:T_1$（环境一致性扩展）→ 再用归纳假设得 $v_2:T_2$。变量、letfun、call 情形同样依赖 $\rho:\Gamma$。

模拟 5 · 运行时（加难） 闭包逃逸：高阶函数返回时活动记录的处理

在 2016 ML 嵌套函数题基础上，让内层函数 g 作为返回值逃逸出定义它的 f。讨论：① 为什么栈式活动记录管理失效；② 闭包如何捕获自由变量 x；③ 给出闭包的运行时表示。

① 栈式失效：$f$ 返回后其活动记录出栈，但返回的 $g$ 仍需访问 $f$ 的局部变量 $x$ → 若 $x$ 在已出栈的活动记录里就是悬空引用。

② 捕获自由变量：对 $g$ 做闭包转换，分析出其自由变量 $\{x\}$，把 $x$ 的值复制/移到堆上的闭包环境中（Lua 的 upvalue 逃逸即此）。

③ 运行时表示：$g$ 的闭包 = { func: &g_code, env: { x: 7 } }。调用 $g(a)$ 时通过 closure.func(closure.env, a)，在 env 中取 $x$。活动记录改为堆分配或仅把逃逸变量提升到堆。

第 16 章 · 互动自测题（带打分）自编练习

共 30 道选择/多选题，覆盖 Lect08-15 进阶考点。题目基于课件知识点整理。

📝 期末知识点自测

先选择选项，再点击提交答案；多选题需全对才得分
0 / 0
正确率 0%

第 17 章 · 期末考前速查表 整理速查

17.1 必背公式 / 结论

LR 能力： $\text{LR}(0)\subsetneq\text{SLR}(1)\subsetneq\text{LALR}(1)\subsetneq\text{LR}(1)$；$\text{LL}(k)\subsetneq\text{LR}(k)$；LALR 状态数 = LR(0)。

LR(1) 闭包： $[A\to\alpha\bullet B\beta,a]\Rightarrow[B\to\bullet\gamma,b],\;b\in\text{First}(\beta a)$。

活跃变量： $\text{IN}=\text{use}\cup(\text{OUT}-\text{def})$，后向，$\cup$。

访问链： 建立走 $m-n+1$ 步，访问走 $m-n$ 步。

数组： $\text{addr}=base+(\cdots(i_1 n_2+i_2)\cdots+i_k)\times w$。

17.2 易错陷阱（必看）

SLR 项集族 = LR(0)
区别只在归约用不用 Follow。
LALR 合并只增 R/R 冲突
不会新增 S/R。
LR 无 S/S 冲突
移进由 GOTO 唯一决定。
引用计数不回收循环
需弱引用或标记-清扫。
可用表达式取交（must）
活跃/可达取并（may）。
活跃/忙=后向
可达/可用=前向。
L 属性移进-归约
需 LL 底层 + 标记符号。
闭包记定义时环境
静态作用域，不是调用时。
SSA 冲突图是弦图
可多项式最优着色。
类型可靠性须强化命题
引入 $\rho:\Gamma$ 才能归纳。
ANF 的 if 会复制后续代码
可能指数膨胀。
无自由变量不必建闭包
闭包转换优化。

17.3 答题策略 经验建议

  • 必答题优先抓满分：LR 分析表、SDT 回填、运行时（访问链/GC）、活跃变量+图染色——这些是机械工作，按部就班。
  • 选答题择优：函数式语言与类型系统「作业做过」，性价比高；SSA 生成需多练块参数转换。
  • 数据流题先写清「方向 + 交汇 + 传递函数 + 边界」四要素，再迭代。
  • 类型推导题严格按规则写各层 $\Gamma$，不要望文生义。
🎯 最后一句：必答骨架（LR / SDT 回填 / 运行时 / 优化）默写到肌肉记忆，选答挑两道最熟的（函数式 + 类型，或 SSA），实验班期末稳了。