编译原理中**中间代码生成**阶段的关键技术，重点围绕**控制流语句（if 和 while）的四元式生成机制**展开

编译原理中中间代码生成阶段的关键技术，重点围绕控制流语句（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

1. 处理外层 if 条件a < b：

   • 生成比较判断四元式：(j<, a, b, 0)，记作 #1；
   • 此时无法确定跳转目标，设置：
     • E.trueList = [1]（若成立则跳至 then 分支）；
     • E.falseList = [2]（否则跳过 then 分支），其中 #2 是下一条指令位置；

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链中以便上层连接。

3. 回填外层 if 的出口：

   • 整个 if 语句结束后，使用backpatch(E.falseList ∪ S.nextList, next_addr)完成所有未决跳转的填充。

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