第13章垃圾收集

比较标记清扫、引用计数、复制、分代、增量收集及其编译器接口；用C编译流水线、状态轨迹和端到端验证门交付根集、对象图、描述字、屏障、回收轨迹与暂停统计

学习目标

能说明“第13章垃圾收集”如何比较标记清扫、引用计数、复制、分代、增量收集及其编译器接口，并区分作者C/Java/ML轨道、中文C版与本站重写
能先预测“编译器生成的栈图、根与写屏障怎样让收集器正确识别对象？”会改变哪一个C接口、树/图状态、AST/IR、汇编或运行结果，再操作三类交互证据
能只注入“分代收集漏执行老生代到新生代写屏障”，定位首个偏离“第13章垃圾收集的C模块接口、数据结构、状态变换、输出语义与测试始终一致”的状态，并从同一快照完成恢复

为什么从这个问题开始

“第13章垃圾收集”围绕“编译器生成的栈图、根与写屏障怎样让收集器正确识别对象？”建立贯穿任务：在Tiger C实现轨道中复现“第13章垃圾收集”的输入、状态、变换与验证。先写下哪个C接口、树/图状态、AST/IR、汇编或运行结果会最先变化，再运行参考、故障和恢复路径；运行后补理由不算预测。只有守住“第13章垃圾收集的C模块接口、数据结构、状态变换、输出语义与测试始终一致”并交付根集、对象图、描述字、屏障、回收轨迹与暂停统计，单模块测试、编译成功或性能变化才构成机制证据。

原版书目、296个正式坐标与C轨道边界

“第13章垃圾收集”以Andrew W. Appel作者官方目录核对 Modern Compiler Implementation 的C、Java、ML三种实现轨道、2部分、21章和Tiger语言附录；以作者C版页面核对Andrew·W·Appel与Maia Ginsburg、Cambridge University Press、C实现轨道、平装ISBN 0-521-60765-5、软件/练习模块与勘误入口，再以Cambridge C版页面核对原版身份。

“第13章垃圾收集”以中文版修订版完整目录核对赵克佳、黄春、沈志宇译《现代编译原理：C语言描述（修订版）》，人民邮电出版社，2018年，385页，ISBN 9787115476883。“第13章垃圾收集”的正式分母为2个部分标题、21个章标题、1个附录标题、251个编号节/小节、附录4节和17个正式“程序设计”项目，合计296个核心层级；每章重复的推荐阅读与习题不另计。

作者页面可访问不等于允许复制书稿，“第13章垃圾收集”不复制、翻译或改写原文、图表、伪码与习题；所有中文讲解、C接口示意、状态轨迹、反例、交互、练习和答案均为独立教学重写。本页独立核对 1只用于核对本页C实现或现代IR边界，不能混入Java/ML轨道或反向证明原书采用本站表述。

原版目录层级与C项目机制

第二部分高级主题

正式坐标 1/14。 原版目录键 第二部分高级主题。在“第13章垃圾收集”的第1个正式坐标中，「第二部分高级主题」通过把“高级主题”放进垃圾收集、对象图与编译器接口的C接口—状态—变换—验证链推进垃圾收集、对象图与编译器接口；复核者保存第13章垃圾收集的输入角色、中间状态、输出、反例与整合证据，出现只复述“高级主题”名称而没有可观察状态、项目实现和恢复验证就撤回结论。

第13章垃圾收集

正式坐标 2/14。 原版目录键 第13章垃圾收集。围绕“编译器生成的栈图、根与写屏障怎样让收集器正确识别对象？”，“第13章垃圾收集”在坐标2把「第13章垃圾收集」落实为整合编译阶段或追踪根、对象图、屏障和回收状态；只有端到端阶段快照、根集、对象图、屏障、回收与运行结果可重放且反例排除接口命名碰撞、根/描述字或写屏障缺失，本节点才算掌握。

13·1 标记-清扫式收集

正式坐标 3/14。 原版目录键 13.1 标记-清扫式收集。“第13章垃圾收集”的目录节点3「13·1 标记-清扫式收集」不能停在术语或伪码：它要整合编译阶段或追踪根、对象图、屏障和回收状态，交付端到端阶段快照、根集、对象图、屏障、回收与运行结果，并把接口命名碰撞、根/描述字或写屏障缺失设为单一反事实。

13·2 引用计数

正式坐标 4/14。 原版目录键 13.2 引用计数。对“第13章垃圾收集”而言，「13·2 引用计数」在第4次检查中改变可观察状态，因为它负责把“引用计数”放进垃圾收集、对象图与编译器接口的C接口—状态—变换—验证链；第13章垃圾收集的输入角色、中间状态、输出、反例与整合证据必须与“第13章垃圾收集的C模块接口、数据结构、状态变换、输出语义与测试始终一致”对齐，不能接受只复述“引用计数”名称而没有可观察状态、项目实现和恢复验证。

13·3 复制式收集

正式坐标 5/14。 原版目录键 13.3 复制式收集。在“第13章垃圾收集”的第5个正式坐标中，「13·3 复制式收集」通过整合编译阶段或追踪根、对象图、屏障和回收状态推进垃圾收集、对象图与编译器接口；复核者保存端到端阶段快照、根集、对象图、屏障、回收与运行结果，出现接口命名碰撞、根/描述字或写屏障缺失就撤回结论。

13·4 分代收集

正式坐标 6/14。 原版目录键 13.4 分代收集。围绕“编译器生成的栈图、根与写屏障怎样让收集器正确识别对象？”，“第13章垃圾收集”在坐标6把「13·4 分代收集」落实为整合编译阶段或追踪根、对象图、屏障和回收状态；只有端到端阶段快照、根集、对象图、屏障、回收与运行结果可重放且反例排除接口命名碰撞、根/描述字或写屏障缺失，本节点才算掌握。

13·5 增量式收集

正式坐标 7/14。 原版目录键 13.5 增量式收集。“第13章垃圾收集”的目录节点7「13·5 增量式收集」不能停在术语或伪码：它要整合编译阶段或追踪根、对象图、屏障和回收状态，交付端到端阶段快照、根集、对象图、屏障、回收与运行结果，并把接口命名碰撞、根/描述字或写屏障缺失设为单一反事实。

13·6 Baker算法

正式坐标 8/14。 原版目录键 13.6 Baker算法。对“第13章垃圾收集”而言，「13·6 Baker算法」在第8次检查中改变可观察状态，因为它负责把“Baker算法”放进垃圾收集、对象图与编译器接口的C接口—状态—变换—验证链；第13章垃圾收集的输入角色、中间状态、输出、反例与整合证据必须与“第13章垃圾收集的C模块接口、数据结构、状态变换、输出语义与测试始终一致”对齐，不能接受只复述“Baker算法”名称而没有可观察状态、项目实现和恢复验证。

13·7 编译器接口

正式坐标 9/14。 原版目录键 13.7 编译器接口。在“第13章垃圾收集”的第9个正式坐标中，「13·7 编译器接口」通过落实C模块接口、数据结构、所有权、阶段输入/输出和可运行项目推进垃圾收集、对象图与编译器接口；复核者保存头文件/实现对照、模块依赖、状态快照、构建日志与黄金输出，出现混用Java/ML轨道接口或单模块状态无法在C中整合就撤回结论。

13·7·1 快速分配

正式坐标 10/14。 原版目录键 13.7.1 快速分配。围绕“编译器生成的栈图、根与写屏障怎样让收集器正确识别对象？”，“第13章垃圾收集”在坐标10把「13·7·1 快速分配」落实为把“快速分配”放进垃圾收集、对象图与编译器接口的C接口—状态—变换—验证链；只有第13章垃圾收集的输入角色、中间状态、输出、反例与整合证据可重放且反例排除只复述“快速分配”名称而没有可观察状态、项目实现和恢复验证，本节点才算掌握。

13·7·2 数据布局的描述

正式坐标 11/14。 原版目录键 13.7.2 数据布局的描述。“第13章垃圾收集”的目录节点11「13·7·2 数据布局的描述」不能停在术语或伪码：它要把“数据布局的描述”放进垃圾收集、对象图与编译器接口的C接口—状态—变换—验证链，交付第13章垃圾收集的输入角色、中间状态、输出、反例与整合证据，并把只复述“数据布局的描述”名称而没有可观察状态、项目实现和恢复验证设为单一反事实。

13·7·3 导出指针

正式坐标 12/14。 原版目录键 13.7.3 导出指针。对“第13章垃圾收集”而言，「13·7·3 导出指针」在第12次检查中改变可观察状态，因为它负责把“导出指针”放进垃圾收集、对象图与编译器接口的C接口—状态—变换—验证链；第13章垃圾收集的输入角色、中间状态、输出、反例与整合证据必须与“第13章垃圾收集的C模块接口、数据结构、状态变换、输出语义与测试始终一致”对齐，不能接受只复述“导出指针”名称而没有可观察状态、项目实现和恢复验证。

程序设计：描述字

正式坐标 13/14。 原版目录键 程序设计：描述字。在“第13章垃圾收集”的第13个正式坐标中，「程序设计：描述字」通过整合编译阶段或追踪根、对象图、屏障和回收状态推进垃圾收集、对象图与编译器接口；复核者保存端到端阶段快照、根集、对象图、屏障、回收与运行结果，出现接口命名碰撞、根/描述字或写屏障缺失就撤回结论。

程序设计：垃圾收集

正式坐标 14/14。 原版目录键 程序设计：垃圾收集。围绕“编译器生成的栈图、根与写屏障怎样让收集器正确识别对象？”，“第13章垃圾收集”在坐标14把「程序设计：垃圾收集」落实为整合编译阶段或追踪根、对象图、屏障和回收状态；只有端到端阶段快照、根集、对象图、屏障、回收与运行结果可重放且反例排除接口命名碰撞、根/描述字或写屏障缺失，本节点才算掌握。

先预测，再操作三个C轨道实验

分步1 / 3

1. C模块、输入与翻译流水线

为“第13章垃圾收集”选择正式目录坐标，在参考流水线与单一故障间切换，逐阶段核对接口、状态、输出和不变量。

输入—表示—翻译流水线

第13章垃圾收集

选择正式目录坐标，再比较参考编译合同与单一故障的首个状态分岔。

正式目录坐标

阶段 1/4

第13章垃圾收集 · C模块与输入

输入: 在Tiger C实现轨道中复现“第13章垃圾收集”的输入、状态、变换与验证
变换: 冻结垃圾收集、对象图与编译器接口所需的C接口、源程序、规则、数据结构和版本
输出证据: 第13章垃圾收集的模块合同、输入快照与所有权表
不变量检查: 第13章垃圾收集的类型、所有权、源位置、名字和接口布局没有错位

第13章垃圾收集的可重放协议

阶段	允许动作	必留证据	拒绝条件
第13章垃圾收集 · C模块与输入	冻结垃圾收集、对象图与编译器接口所需的C接口、源程序、规则、数据结构和版本	第13章垃圾收集的模块合同、输入快照与所有权表	未满足“第13章垃圾收集的类型、所有权、源位置、名字和接口布局没有错位”
第13章垃圾收集 · 算法与状态	执行比较标记清扫、引用计数、复制、分代、增量收集及其编译器接口的最小算法并保存每一步状态	第13章垃圾收集的参考轨迹、故障轨迹与首个状态分岔	未满足“第13章垃圾收集每一步可由同一C接口、输入、规则和执行顺序复算”
第13章垃圾收集 · 输出与整合	比较变换前后AST/IR/汇编/运行时状态和跨模块传递	第13章垃圾收集的前后差、接口谱系与恢复路径	未满足“第13章垃圾收集没有把单模块通过或单一样例正确当作端到端正确性”
第13章垃圾收集 · 独立验证	重放预测、单故障、恢复和不适用边界	第13章垃圾收集的接受、回退或拒绝理由	未满足“第13章垃圾收集满足“第13章垃圾收集的C模块接口、数据结构、状态变换、输出语义与测试始终一致””

unit: "tbc-unit-13"
question: "编译器生成的栈图、根与写屏障怎样让收集器正确识别对象？"
scenario: "在Tiger C实现轨道中复现“第13章 垃圾收集”的输入、状态、变换与验证"
invariant: "第13章 垃圾收集的C模块接口、数据结构、状态变换、输出语义与测试始终一致"
fault: "分代收集漏执行老生代到新生代写屏障"
evidence: "根集、对象图、描述字、屏障、回收轨迹与暂停统计"
reset: restore_concept_mode_stage_trace_step_case_gates_and_artifact

“第13章垃圾收集”要求从同一C接口、源程序、规则、数据结构、目标机、预算和执行顺序重放参考、故障与恢复路径。重置后若目录选择、模式、阶段、轨迹步骤、案例、证据门或交付包没有回到基线，本次比较已经混入状态泄漏。

本页回顾

掌握“第13章垃圾收集”不是背术语、表格或伪码，而是围绕“编译器生成的栈图、根与写屏障怎样让收集器正确识别对象？”重建C接口、输入、状态变换、输出、整合和端到端验证，并用“第13章垃圾收集的C模块接口、数据结构、状态变换、输出语义与测试始终一致”拒绝“分代收集漏执行老生代到新生代写屏障”。最终交付为根集、对象图、描述字、屏障、回收轨迹与暂停统计。

练习与答案

练习

问题 1：C实现合同。 “第13章垃圾收集”为什么必须先冻结C接口、源程序、规则、数据结构、目标机和验证口径？

问题 2：目录逐项覆盖。 怎样证明“第13章垃圾收集”的正式目录坐标已经进入机制、交互和程序设计项目？

“第13章垃圾收集”的目录项「第二部分高级主题」：以“把“高级主题”放进垃圾收集、对象图与编译器接口的C接口—状态—变换—验证链”解释作用，用“第13章垃圾收集的输入角色、中间状态、输出、反例与整合证据”提供复核。 2. “第13章垃圾收集”的目录项「第13章垃圾收集」：以“整合编译阶段或追踪根、对象图、屏障和回收状态”解释作用，用“端到端阶段快照、根集、对象图、屏障、回收与运行结果”提供复核。
“第13章垃圾收集”的目录项「13·1 标记-清扫式收集」：以“整合编译阶段或追踪根、对象图、屏障和回收状态”解释作用，用“端到端阶段快照、根集、对象图、屏障、回收与运行结果”提供复核。
“第13章垃圾收集”的目录项「13·2 引用计数」：以“把“引用计数”放进垃圾收集、对象图与编译器接口的C接口—状态—变换—验证链”解释作用，用“第13章垃圾收集的输入角色、中间状态、输出、反例与整合证据”提供复核。 5. “第13章垃圾收集”的目录项「13·3 复制式收集」：以“整合编译阶段或追踪根、对象图、屏障和回收状态”解释作用，用“端到端阶段快照、根集、对象图、屏障、回收与运行结果”提供复核。
“第13章垃圾收集”的目录项「13·4 分代收集」：以“整合编译阶段或追踪根、对象图、屏障和回收状态”解释作用，用“端到端阶段快照、根集、对象图、屏障、回收与运行结果”提供复核。
“第13章垃圾收集”的目录项「13·5 增量式收集」：以“整合编译阶段或追踪根、对象图、屏障和回收状态”解释作用，用“端到端阶段快照、根集、对象图、屏障、回收与运行结果”提供复核。
“第13章垃圾收集”的目录项「13·6 Baker算法」：以“把“Baker算法”放进垃圾收集、对象图与编译器接口的C接口—状态—变换—验证链”解释作用，用“第13章垃圾收集的输入角色、中间状态、输出、反例与整合证据”提供复核。 9. “第13章垃圾收集”的目录项「13·7 编译器接口」：以“落实C模块接口、数据结构、所有权、阶段输入/输出和可运行项目”解释作用，用“头文件/实现对照、模块依赖、状态快照、构建日志与黄金输出”提供复核。
“第13章垃圾收集”的目录项「13·7·1 快速分配」：以“把“快速分配”放进垃圾收集、对象图与编译器接口的C接口—状态—变换—验证链”解释作用，用“第13章垃圾收集的输入角色、中间状态、输出、反例与整合证据”提供复核。 11. “第13章垃圾收集”的目录项「13·7·2 数据布局的描述」：以“把“数据布局的描述”放进垃圾收集、对象图与编译器接口的C接口—状态—变换—验证链”解释作用，用“第13章垃圾收集的输入角色、中间状态、输出、反例与整合证据”提供复核。 12. “第13章垃圾收集”的目录项「13·7·3 导出指针」：以“把“导出指针”放进垃圾收集、对象图与编译器接口的C接口—状态—变换—验证链”解释作用，用“第13章垃圾收集的输入角色、中间状态、输出、反例与整合证据”提供复核。 13. “第13章垃圾收集”的目录项「程序设计：描述字」：以“整合编译阶段或追踪根、对象图、屏障和回收状态”解释作用，用“端到端阶段快照、根集、对象图、屏障、回收与运行结果”提供复核。
“第13章垃圾收集”的目录项「程序设计：垃圾收集」：以“整合编译阶段或追踪根、对象图、屏障和回收状态”解释作用，用“端到端阶段快照、根集、对象图、屏障、回收与运行结果”提供复核。

问题 3：故障恢复。 怎样证明“分代收集漏执行老生代到新生代写屏障”已经被修正？

为“第13章垃圾收集”复用同一C接口、输入、规则、数据结构、目标机、预算和顺序，重放参考路径后只注入该故障；记录首个偏离，撤销故障再运行。只有流水线合同、状态轨迹、端到端验证门和根集、对象图、描述字、屏障、回收轨迹与暂停统计重新满足“第13章垃圾收集的C模块接口、数据结构、状态变换、输出语义与测试始终一致”，修正才可提交。

名词解释

本章出现的专业名词，用大白话再讲一遍。

高级主题: 检索键 tbc-A 对应正式目录坐标「第二部分高级主题」；在“第13章垃圾收集”中用于把“高级主题”放进垃圾收集、对象图与编译器接口的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
垃圾收集: 检索键 tbc-B 对应正式目录坐标「第13章垃圾收集」；在“第13章垃圾收集”中用于整合编译阶段或追踪根、对象图、屏障和回收状态，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
标记-清扫式收集: 检索键 tbc-C 对应正式目录坐标「13·1 标记-清扫式收集」；在“第13章垃圾收集”中用于整合编译阶段或追踪根、对象图、屏障和回收状态，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
引用计数: 检索键 tbc-D 对应正式目录坐标「13·2 引用计数」；在“第13章垃圾收集”中用于把“引用计数”放进垃圾收集、对象图与编译器接口的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
复制式收集: 检索键 tbc-E 对应正式目录坐标「13·3 复制式收集」；在“第13章垃圾收集”中用于整合编译阶段或追踪根、对象图、屏障和回收状态，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
分代收集: 检索键 tbc-F 对应正式目录坐标「13·4 分代收集」；在“第13章垃圾收集”中用于整合编译阶段或追踪根、对象图、屏障和回收状态，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
增量式收集: 检索键 tbc-G 对应正式目录坐标「13·5 增量式收集」；在“第13章垃圾收集”中用于整合编译阶段或追踪根、对象图、屏障和回收状态，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
Baker算法: 检索键 tbc-H 对应正式目录坐标「13·6 Baker算法」；在“第13章垃圾收集”中用于把“Baker算法”放进垃圾收集、对象图与编译器接口的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
编译器接口: 检索键 tbc-I 对应正式目录坐标「13·7 编译器接口」；在“第13章垃圾收集”中用于落实C模块接口、数据结构、所有权、阶段输入/输出和可运行项目，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
快速分配: 检索键 tbc-J 对应正式目录坐标「13·7·1 快速分配」；在“第13章垃圾收集”中用于把“快速分配”放进垃圾收集、对象图与编译器接口的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
数据布局的描述: 检索键 tbc-K 对应正式目录坐标「13·7·2 数据布局的描述」；在“第13章垃圾收集”中用于把“数据布局的描述”放进垃圾收集、对象图与编译器接口的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
导出指针: 检索键 tbc-L 对应正式目录坐标「13·7·3 导出指针」；在“第13章垃圾收集”中用于把“导出指针”放进垃圾收集、对象图与编译器接口的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
描述字: 检索键 tbc-M 对应正式目录坐标「程序设计：描述字」；在“第13章垃圾收集”中用于整合编译阶段或追踪根、对象图、屏障和回收状态，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
垃圾收集: 检索键 tbc-N 对应正式目录坐标「程序设计：垃圾收集」；在“第13章垃圾收集”中用于整合编译阶段或追踪根、对象图、屏障和回收状态，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。

第13章 垃圾收集

学习目标

为什么从这个问题开始

原版书目、296个正式坐标与C轨道边界

原版目录层级与C项目机制

第二部分 高级主题

第13章 垃圾收集

13·1 标记-清扫式收集

13·2 引用计数

13·3 复制式收集

13·4 分代收集

13·5 增量式收集

13·6 Baker算法

13·7 编译器接口

13·7·1 快速分配

13·7·2 数据布局的描述

13·7·3 导出指针

程序设计：描述字

程序设计：垃圾收集

先预测，再操作三个C轨道实验

1. C模块、输入与翻译流水线

第13章 垃圾收集

第13章 垃圾收集 · C模块与输入

第13章 垃圾收集的可重放协议

本页回顾

练习与答案

练习

名词解释

名词解释

讨论

第13章垃圾收集

第二部分高级主题

第13章垃圾收集

第13章垃圾收集

第13章垃圾收集 · C模块与输入

第13章垃圾收集的可重放协议