编译原理中中间代码生成阶段的关键技术，重点围绕控制流语句（if 和 while）的四元式生成机制展开。其核心思想是通过“拉链（chaining）与回填（backpatching）”技术，解决在语法分析过程中跳转目标地址尚未确定的问题。
1. 核心内容详解
代码结构图示
- 图 2-20（if 语句结构）：
if-then：条件表达式 E 的真链指向 then 分支的语句 S1，假链用于后续连接 else 或合并到外层。if-then-else：E 的真链指向 S1，假链指向 S2；S1 和 S2 最终都需跳转到合并点（出口）。
- 图 2-21（while 循环结构）：
- 条件 E 的真链指向循环体 S；
- 循环体执行完后必须无条件跳回判断条件处；
- E 的假链为整个 while 语句的出口；
- 使用
S.chain记录需要回填跳转地址的四元式编号链表。
各节点之间的“链”通过
trueList,falseList,nextList等属性维护，并最终由backpatch填入实际的目标地址。
四元式生成规则
常用操作包括：
GEN("j<", a, b, 0)：生成条件跳转指令，第四个字段暂为空或占位符（NXQ）；MERGE(list1, list2)：合并两个跳转链表；BACKPATCH(list, target)：将链表中所有待填的四元式地址更新为目标target；NXQ：下一个可用的四元式序号，每生成一条四元式自动递增。
示例流程解析：
程序：if a < b then while a < b do a := a + b
处理外层 if 条件
a < b：- 生成比较判断四元式：
(j<, a, b, 0)，记作 #1； - 此时无法确定跳转目标，设置：
E.trueList = [1]（若成立则跳至 then 分支）；E.falseList = [2]（否则跳过 then 分支），其中 #2 是下一条指令位置；
- 生成比较判断四元式：
进入 then 分支处理 while 语句：
- while 的入口标号为当前 NXQ（假设为 #3）；
- 再次判断
a < b→ 生成(j<, a, b, 0)，设为 #4；E1.trueList = [4]E1.falseList = [5]（退出循环）
- 循环体内执行
a := a + b→ 生成赋值四元式 #6； - 添加无条件跳转回入口：
GEN(j, -, -, 3)→ #7； - 将
E1.falseList回填为 #8（循环出口）； - 利用 backpatch 将 #5 处填为 #8；
- 同时，将 #7 加入
S.nextList链中以便上层连接。
回填外层 if 的出口：
- 整个 if 语句结束后，使用
backpatch(E.falseList ∪ S.nextList, next_addr)完成所有未决跳转的填充。
- 整个 if 语句结束后，使用
2. 知识背景补充
这是编译器前端——语义分析与中间代码生成的重要环节。四元式作为三地址码的一种规范形式，具有结构清晰、易于优化和目标代码生成的优点。
- 四元式格式：
(op, arg1, arg2, result)- 如：
(j<, a, b, 10)表示如果 a < b 成立，则跳转到第 10 号四元式； (=, t1, -, a)表示 a = t1；
- 如：
- 拉链回填机制意义：
- 在一遍扫描中无法预知未来语句的位置（如 else 或 while 出口）；
- 先记录待填地址的“链”（即列表），等到目标地址明确后再统一“回填”；
- 实现了无需回溯的一遍编译支持。
# 模拟 BACKPATCH 操作defbackpatch(instruction_list,target):foriininstruction_list:quadruples[i-1].result=str(target)# MERGE 两个链表（不改变原列表）defmerge(list1,list2):returnlist1+list2
