第8章基本块和轨迹

规范化树IR、形成基本块并用轨迹调度整理Tiger控制流；用C编译流水线、状态轨迹和端到端验证门交付规范树、基本块、轨迹顺序、CFG与差分执行

学习目标

能说明“第8章基本块和轨迹”如何规范化树IR、形成基本块并用轨迹调度整理Tiger控制流，并区分作者C/Java/ML轨道、中文C版与本站重写
能先预测“ESEQ、调用和条件跳转怎样被提升或重排而不改变语义？”会改变哪一个C接口、树/图状态、AST/IR、汇编或运行结果，再操作三类交互证据
能只注入“轨迹调度反转条件后忘记同步交换真假目标标签”，定位首个偏离“第8章基本块和轨迹的C模块接口、数据结构、状态变换、输出语义与测试始终一致”的状态，并从同一快照完成恢复

为什么从这个问题开始

“第8章基本块和轨迹”围绕“ESEQ、调用和条件跳转怎样被提升或重排而不改变语义？”建立贯穿任务：在Tiger C实现轨道中复现“第8章基本块和轨迹”的输入、状态、变换与验证。先写下哪个C接口、树/图状态、AST/IR、汇编或运行结果会最先变化，再运行参考、故障和恢复路径；运行后补理由不算预测。只有守住“第8章基本块和轨迹的C模块接口、数据结构、状态变换、输出语义与测试始终一致”并交付规范树、基本块、轨迹顺序、CFG与差分执行，单模块测试、编译成功或性能变化才构成机制证据。

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

“第8章基本块和轨迹”以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版页面核对原版身份。

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

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

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

第8章基本块和轨迹

正式坐标 1/11。 原版目录键 第8章基本块和轨迹。在“第8章基本块和轨迹”的第1个正式坐标中，「第8章基本块和轨迹」通过把Tiger AST降到规范树IR、基本块和可调度控制流推进规范化、基本块与轨迹调度；复核者保存AST—IR映射、临时变量、标签、CFG、规范化与差分执行，出现副作用重复、标签错连或轨迹调度破坏控制语义就撤回结论。

8·1 规范树

正式坐标 2/11。 原版目录键 8.1 规范树。围绕“ESEQ、调用和条件跳转怎样被提升或重排而不改变语义？”，“第8章基本块和轨迹”在坐标2把「8·1 规范树」落实为把Tiger AST降到规范树IR、基本块和可调度控制流；只有AST—IR映射、临时变量、标签、CFG、规范化与差分执行可重放且反例排除副作用重复、标签错连或轨迹调度破坏控制语义，本节点才算掌握。

8·1·1 ESEQ的转换

正式坐标 3/11。 原版目录键 8.1.1 ESEQ的转换。“第8章基本块和轨迹”的目录节点3「8·1·1 ESEQ的转换」不能停在术语或伪码：它要把“ESEQ的转换”放进规范化、基本块与轨迹调度的C接口—状态—变换—验证链，交付第8章基本块和轨迹的输入角色、中间状态、输出、反例与整合证据，并把只复述“ESEQ的转换”名称而没有可观察状态、项目实现和恢复验证设为单一反事实。

8·1·2 一般重写规则

正式坐标 4/11。 原版目录键 8.1.2 一般重写规则。对“第8章基本块和轨迹”而言，「8·1·2 一般重写规则」在第4次检查中改变可观察状态，因为它负责把“一般重写规则”放进规范化、基本块与轨迹调度的C接口—状态—变换—验证链；第8章基本块和轨迹的输入角色、中间状态、输出、反例与整合证据必须与“第8章基本块和轨迹的C模块接口、数据结构、状态变换、输出语义与测试始终一致”对齐，不能接受只复述“一般重写规则”名称而没有可观察状态、项目实现和恢复验证。

8·1·3 将CALL移到顶层

正式坐标 5/11。 原版目录键 8.1.3 将CALL移到顶层。在“第8章基本块和轨迹”的第5个正式坐标中，「8·1·3 将CALL移到顶层」通过把“将CALL移到顶层”放进规范化、基本块与轨迹调度的C接口—状态—变换—验证链推进规范化、基本块与轨迹调度；复核者保存第8章基本块和轨迹的输入角色、中间状态、输出、反例与整合证据，出现只复述“将CALL移到顶层”名称而没有可观察状态、项目实现和恢复验证就撤回结论。

8·1·4 线性语句表

正式坐标 6/11。 原版目录键 8.1.4 线性语句表。围绕“ESEQ、调用和条件跳转怎样被提升或重排而不改变语义？”，“第8章基本块和轨迹”在坐标6把「8·1·4 线性语句表」落实为把“线性语句表”放进规范化、基本块与轨迹调度的C接口—状态—变换—验证链；只有第8章基本块和轨迹的输入角色、中间状态、输出、反例与整合证据可重放且反例排除只复述“线性语句表”名称而没有可观察状态、项目实现和恢复验证，本节点才算掌握。

8·2 处理条件分支

正式坐标 7/11。 原版目录键 8.2 处理条件分支。“第8章基本块和轨迹”的目录节点7「8·2 处理条件分支」不能停在术语或伪码：它要把“处理条件分支”放进规范化、基本块与轨迹调度的C接口—状态—变换—验证链，交付第8章基本块和轨迹的输入角色、中间状态、输出、反例与整合证据，并把只复述“处理条件分支”名称而没有可观察状态、项目实现和恢复验证设为单一反事实。

8·2·1 基本块

正式坐标 8/11。 原版目录键 8.2.1 基本块。对“第8章基本块和轨迹”而言，「8·2·1 基本块」在第8次检查中改变可观察状态，因为它负责把Tiger AST降到规范树IR、基本块和可调度控制流；AST—IR映射、临时变量、标签、CFG、规范化与差分执行必须与“第8章基本块和轨迹的C模块接口、数据结构、状态变换、输出语义与测试始终一致”对齐，不能接受副作用重复、标签错连或轨迹调度破坏控制语义。

8·2·2 轨迹

正式坐标 9/11。 原版目录键 8.2.2 轨迹。在“第8章基本块和轨迹”的第9个正式坐标中，「8·2·2 轨迹」通过把Tiger AST降到规范树IR、基本块和可调度控制流推进规范化、基本块与轨迹调度；复核者保存AST—IR映射、临时变量、标签、CFG、规范化与差分执行，出现副作用重复、标签错连或轨迹调度破坏控制语义就撤回结论。

8·2·3 完善

正式坐标 10/11。 原版目录键 8.2.3 完善。围绕“ESEQ、调用和条件跳转怎样被提升或重排而不改变语义？”，“第8章基本块和轨迹”在坐标10把「8·2·3 完善」落实为把“完善”放进规范化、基本块与轨迹调度的C接口—状态—变换—验证链；只有第8章基本块和轨迹的输入角色、中间状态、输出、反例与整合证据可重放且反例排除只复述“完善”名称而没有可观察状态、项目实现和恢复验证，本节点才算掌握。

8·2·4 最优轨迹

正式坐标 11/11。 原版目录键 8.2.4 最优轨迹。“第8章基本块和轨迹”的目录节点11「8·2·4 最优轨迹」不能停在术语或伪码：它要把Tiger AST降到规范树IR、基本块和可调度控制流，交付AST—IR映射、临时变量、标签、CFG、规范化与差分执行，并把副作用重复、标签错连或轨迹调度破坏控制语义设为单一反事实。

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

分步1 / 3

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

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

输入—表示—翻译流水线

第8章基本块和轨迹

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

正式目录坐标

阶段 1/4

第8章基本块和轨迹 · C模块与输入

输入: 在Tiger C实现轨道中复现“第8章基本块和轨迹”的输入、状态、变换与验证
变换: 冻结规范化、基本块与轨迹调度所需的C接口、源程序、规则、数据结构和版本
输出证据: 第8章基本块和轨迹的模块合同、输入快照与所有权表
不变量检查: 第8章基本块和轨迹的类型、所有权、源位置、名字和接口布局没有错位

第8章基本块和轨迹的可重放协议

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

unit: "tbc-unit-08"
question: "ESEQ、调用和条件跳转怎样被提升或重排而不改变语义？"
scenario: "在Tiger C实现轨道中复现“第8章 基本块和轨迹”的输入、状态、变换与验证"
invariant: "第8章 基本块和轨迹的C模块接口、数据结构、状态变换、输出语义与测试始终一致"
fault: "轨迹调度反转条件后忘记同步交换真假目标标签"
evidence: "规范树、基本块、轨迹顺序、CFG与差分执行"
reset: restore_concept_mode_stage_trace_step_case_gates_and_artifact

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

本页回顾

掌握“第8章基本块和轨迹”不是背术语、表格或伪码，而是围绕“ESEQ、调用和条件跳转怎样被提升或重排而不改变语义？”重建C接口、输入、状态变换、输出、整合和端到端验证，并用“第8章基本块和轨迹的C模块接口、数据结构、状态变换、输出语义与测试始终一致”拒绝“轨迹调度反转条件后忘记同步交换真假目标标签”。最终交付为规范树、基本块、轨迹顺序、CFG与差分执行。

练习与答案

练习

问题 1：C实现合同。 “第8章基本块和轨迹”为什么必须先冻结C接口、源程序、规则、数据结构、目标机和验证口径？

问题 2：目录逐项覆盖。 怎样证明“第8章基本块和轨迹”的正式目录坐标已经进入机制、交互和程序设计项目？

“第8章基本块和轨迹”的目录项「第8章基本块和轨迹」：以“把Tiger AST降到规范树IR、基本块和可调度控制流”解释作用，用“AST—IR映射、临时变量、标签、CFG、规范化与差分执行”提供复核。
“第8章基本块和轨迹”的目录项「8·1 规范树」：以“把Tiger AST降到规范树IR、基本块和可调度控制流”解释作用，用“AST—IR映射、临时变量、标签、CFG、规范化与差分执行”提供复核。
“第8章基本块和轨迹”的目录项「8·1·1 ESEQ的转换」：以“把“ESEQ的转换”放进规范化、基本块与轨迹调度的C接口—状态—变换—验证链”解释作用，用“第8章基本块和轨迹的输入角色、中间状态、输出、反例与整合证据”提供复核。 4. “第8章基本块和轨迹”的目录项「8·1·2 一般重写规则」：以“把“一般重写规则”放进规范化、基本块与轨迹调度的C接口—状态—变换—验证链”解释作用，用“第8章基本块和轨迹的输入角色、中间状态、输出、反例与整合证据”提供复核。 5. “第8章基本块和轨迹”的目录项「8·1·3 将CALL移到顶层」：以“把“将CALL移到顶层”放进规范化、基本块与轨迹调度的C接口—状态—变换—验证链”解释作用，用“第8章基本块和轨迹的输入角色、中间状态、输出、反例与整合证据”提供复核。 6. “第8章基本块和轨迹”的目录项「8·1·4 线性语句表」：以“把“线性语句表”放进规范化、基本块与轨迹调度的C接口—状态—变换—验证链”解释作用，用“第8章基本块和轨迹的输入角色、中间状态、输出、反例与整合证据”提供复核。 7. “第8章基本块和轨迹”的目录项「8·2 处理条件分支」：以“把“处理条件分支”放进规范化、基本块与轨迹调度的C接口—状态—变换—验证链”解释作用，用“第8章基本块和轨迹的输入角色、中间状态、输出、反例与整合证据”提供复核。 8. “第8章基本块和轨迹”的目录项「8·2·1 基本块」：以“把Tiger AST降到规范树IR、基本块和可调度控制流”解释作用，用“AST—IR映射、临时变量、标签、CFG、规范化与差分执行”提供复核。
“第8章基本块和轨迹”的目录项「8·2·2 轨迹」：以“把Tiger AST降到规范树IR、基本块和可调度控制流”解释作用，用“AST—IR映射、临时变量、标签、CFG、规范化与差分执行”提供复核。
“第8章基本块和轨迹”的目录项「8·2·3 完善」：以“把“完善”放进规范化、基本块与轨迹调度的C接口—状态—变换—验证链”解释作用，用“第8章基本块和轨迹的输入角色、中间状态、输出、反例与整合证据”提供复核。 11. “第8章基本块和轨迹”的目录项「8·2·4 最优轨迹」：以“把Tiger AST降到规范树IR、基本块和可调度控制流”解释作用，用“AST—IR映射、临时变量、标签、CFG、规范化与差分执行”提供复核。

问题 3：故障恢复。 怎样证明“轨迹调度反转条件后忘记同步交换真假目标标签”已经被修正？

为“第8章基本块和轨迹”复用同一C接口、输入、规则、数据结构、目标机、预算和顺序，重放参考路径后只注入该故障；记录首个偏离，撤销故障再运行。只有流水线合同、状态轨迹、端到端验证门和规范树、基本块、轨迹顺序、CFG与差分执行重新满足“第8章基本块和轨迹的C模块接口、数据结构、状态变换、输出语义与测试始终一致”，修正才可提交。

名词解释

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

基本块和轨迹: 检索键 tbc-A 对应正式目录坐标「第8章基本块和轨迹」；在“第8章基本块和轨迹”中用于把Tiger AST降到规范树IR、基本块和可调度控制流，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
规范树: 检索键 tbc-B 对应正式目录坐标「8·1 规范树」；在“第8章基本块和轨迹”中用于把Tiger AST降到规范树IR、基本块和可调度控制流，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
ESEQ的转换: 检索键 tbc-C 对应正式目录坐标「8·1·1 ESEQ的转换」；在“第8章基本块和轨迹”中用于把“ESEQ的转换”放进规范化、基本块与轨迹调度的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
一般重写规则: 检索键 tbc-D 对应正式目录坐标「8·1·2 一般重写规则」；在“第8章基本块和轨迹”中用于把“一般重写规则”放进规范化、基本块与轨迹调度的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
将CALL移到顶层: 检索键 tbc-E 对应正式目录坐标「8·1·3 将CALL移到顶层」；在“第8章基本块和轨迹”中用于把“将CALL移到顶层”放进规范化、基本块与轨迹调度的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
线性语句表: 检索键 tbc-F 对应正式目录坐标「8·1·4 线性语句表」；在“第8章基本块和轨迹”中用于把“线性语句表”放进规范化、基本块与轨迹调度的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
处理条件分支: 检索键 tbc-G 对应正式目录坐标「8·2 处理条件分支」；在“第8章基本块和轨迹”中用于把“处理条件分支”放进规范化、基本块与轨迹调度的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
基本块: 检索键 tbc-H 对应正式目录坐标「8·2·1 基本块」；在“第8章基本块和轨迹”中用于把Tiger AST降到规范树IR、基本块和可调度控制流，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
轨迹: 检索键 tbc-I 对应正式目录坐标「8·2·2 轨迹」；在“第8章基本块和轨迹”中用于把Tiger AST降到规范树IR、基本块和可调度控制流，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
完善: 检索键 tbc-J 对应正式目录坐标「8·2·3 完善」；在“第8章基本块和轨迹”中用于把“完善”放进规范化、基本块与轨迹调度的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
最优轨迹: 检索键 tbc-K 对应正式目录坐标「8·2·4 最优轨迹」；在“第8章基本块和轨迹”中用于把Tiger AST降到规范树IR、基本块和可调度控制流，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。

第8章 基本块和轨迹

学习目标

为什么从这个问题开始

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

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

第8章 基本块和轨迹

8·1 规范树

8·1·1 ESEQ的转换

8·1·2 一般重写规则

8·1·3 将CALL移到顶层

8·1·4 线性语句表

8·2 处理条件分支

8·2·1 基本块

8·2·2 轨迹

8·2·3 完善

8·2·4 最优轨迹

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

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

第8章 基本块和轨迹

第8章 基本块和轨迹 · C模块与输入

第8章 基本块和轨迹的可重放协议

本页回顾

练习与答案

练习

名词解释

名词解释

讨论

第8章基本块和轨迹

第8章基本块和轨迹

第8章基本块和轨迹

第8章基本块和轨迹 · C模块与输入

第8章基本块和轨迹的可重放协议