拉链反填技术

问题背景

控制流语句中，跳转目标往往在后续代码中才出现（先引用后定义）。

问题：生成跳转指令时目标标号尚未确定。

拉链反填思想

• 先将跳转指令的目标填为待定（链式结构）
• 待目标确定后反填（backpatching）正确的目标地址

重点 拉链反填是实现一遍扫描翻译控制流语句的关键技术。

链结构

• 链头（chain head）：指向第一条未填充跳转指令
• 链尾（chain tail）：指向最后一条未填充跳转指令
• 每条跳转指令中预留一个字段指向下一条同类跳转指令，形成链表

反填时从链头遍历，依次填入正确的目标地址。

三跳转链

控制流语句翻译涉及三类跳转链：

1. 真链（true chain）：条件为真时的跳转链
2. 假链（false chain）：条件为假时的跳转链
3. 跳转链（jump chain）：无条件跳转链

拉链反填演示

if 语句：if (A > B) X := 1

    ① (>, A, B, T1)
    ② JP T1, ________    ; 真链：待填
    ③ J, ________         ; 假链：待填
    ④ (:=, 1, _, X)
    ⑤ 后续代码

1. 生成前三条指令时，跳转目标未知
2. 遇到 $X:=1$ 后确定真链应跳转到 ④
3. 反填 ② → 目标为 ④
4. 假链应跳转到 ⑤（后续代码），反填 ③ → 目标为 ⑤

if-else 语句：if (A > B) X := 1 else Y := 2

    ① (>, A, B, T1)
    ② JP T1, ________    ; 真链：待填 → 反填为 ④
    ③ J, ________         ; 假链：待填 → 反填为 ⑥
    ④ (:=, 1, _, X)
    ⑤ J, ________         ; 跳转链：跳过else → 反填为 ⑦
    ⑥ (:=, 2, _, Y)
    ⑦ 后续代码

• 真链 ② → 反填 ④
• 假链 ③ → 反填 ⑥
• 跳转链 ⑤（跳过 else 部分）→ 反填 ⑦

while 语句：while (A > B) X := 1

L1:  ① (>, A, B, T1)
     ② JP T1, ________    ; 真链：待填 → 反填为 ④
     ③ J, ________         ; 假链：待填 → 反填为 ⑤（退出）
     ④ (:=, 1, _, X)
     ⑤ J, L1               ; 回到条件判断（已知标号，无需反填）
     ⑥ 后续代码

• 真链 ② → 反填 ④（进入循环体）
• 假链 ③ → 反填 ⑤（退出循环）

重点 拉链反填次序：先生成链，目标确定后从链头遍历反填。