回填技术

回填技术是编译器语义分析阶段（特别是您列出的第 6 章，处理条件语句和循环语句时）用于生成中间代码的一种高效方法，专门用来处理跳转指令中的地址问题。

📌 核心问题：为什么需要回填？

在生成条件语句（if-else）和循环语句（while）的中间代码（如三地址码）时，会涉及到大量的跳转指令（如 goto L 或 if_false E goto L）。

问题在于： 当编译器遇到一个跳转指令时，它往往并不知道该指令应该跳向的目标标签 在代码中的具体地址（行号或偏移量）。

• 例如： 在翻译 if (E) S1 else S2; 时，当我们生成 if_false E goto L_else 这条指令时，我们还没有开始翻译 ，所以我们不知道 （ 的起始地址）在哪里。

💡 回填技术的核心思想

与其在不知道目标地址时就生成错误的地址或占位符，回填技术采取了以下策略：

1. 生成跳转指令时，先留空目标地址。

2. 记录下哪些跳转指令的目标地址是未知的。

3. 当目标地址最终确定时（即遇到目标标签时），回到（回填）所有记录下的跳转指令，将它们的地址信息填上。

🛠️ 回填技术的实现机制

回填技术依赖于三个主要的链表（List）：

1. 真出口链 (True List, )

• 用途： 存储所有**“当条件为真时”**需要跳转的指令的地址（行号）。

• 示例： if (A or B)，如果 或 为真，我们需要跳转到执行体（）的起始处。

2. 假出口链 (False List, )

• 用途： 存储所有**“当条件为假时”**需要跳转的指令的地址（行号）。

• 示例： if (E) S1 else S2;，如果 为假，我们需要跳转到 的起始处。

3. 下一语句链 (Next List, )

• 用途： 存储所有**“执行完当前语句后”需要跳到当前语句后面**的指令的地址。

• 示例： 执行完 if (E) S1 中的 后，需要无条件跳转到整个 if-else 语句的末尾。

核心操作：backpatch(list, target_address)

这是一个函数，用于执行真正的回填操作：

• 它接收一个指令地址链表 (list) 和一个确定的目标地址 (target_address)。

• 它遍历 list 中的每一个地址 ，然后将第 条指令中的跳转目标地址域填入 。

📝 典型应用：if (E) S1 else S2; 的翻译

以您 6.6 节的 if-then-else 语句为例：

步骤	语义动作 / 生成的代码	链表操作	状态
1. 翻译	t1 = ... (表达式代码)	产生两个链： (真出口) 和 (假出口)	指令需要跳到
2. 遇到 开始	记录当前代码行号	回填 ：`backpatch(E.T, L_{S1})$	为真时的跳转目标确定！
3. 翻译	S1 的中间代码	产生一个 链（无条件跳转）	需要跳到整个语句末尾
4. 结束，无条件跳转	生成 goto ___ 指令，地址留空	将此指令的地址加入 链	现在包含 后的 goto
5. 遇到 开始	记录当前代码行号	回填 ：`backpatch(E.F, L_{S2})$	为假时的跳转目标确定！
6. 翻译	S2 的中间代码	产生一个 链	需要跳到整个语句末尾
7. 语句结束	记录当前代码行号	合并 和 成一个 链。回填 ：`backpatch(D.N, L_{end})$	整个语句结束后的跳转目标确定！

✅ 回填技术的优点

1. 单遍扫描 (One-Pass)： 允许编译器在一次性读取和处理源代码时就生成控制流代码，而不需要进行二次扫描或复杂的符号表查找。

2. 地址无关： 在生成跳转指令时，不必关心目标地址的具体数值，简化了代码生成过程。

3. 适用于 SDT： 它与语法制导翻译 (SDT) 的自顶向下或自底向上方法结合得非常好，特别是当编译器结构化地遍历语法树时。

简而言之，回填技术就是一种“先占位，后填充”的机制，完美解决了在生成跳转指令时“不知道目标地址”的核心问题。