7. 中间代码生成

1. Motivation (为什么需要中间代码？)

在前端（分析）和后端（生成）之间引入中间表示（IR, Intermediate Representation），构建了一个“沙漏型”架构。

主要优势：

便于移植 (Portability)：种语言种机器。
- 无 IR：需要写个编译器。
- 有 IR：前端写个，后端写个，只需的工作量。
便于优化 (Optimization)：
- 中间代码独立于具体硬件，适合进行机器无关优化（如死代码消除、循环不变式外提）。
- 一次优化，所有后端（x86, ARM, RISC-V）受益。

2. Concept (核心概念)

2.1 中间代码的形式

形式	特点	适用场景
语法树 (Syntax Tree)	形象展示语法结构，但可能有冗余。	早期分析阶段。
DAG (有向无环图)	节点去重。识别公共子表达式（Common Subexpression），避免重复计算。	优化阶段。
三地址代码 (3AC)	线性序列，类似汇编。每条指令最多 3 个操作数。	本章重点，易于生成目标代码。

2.2 三地址代码的实现：四元式 (Quadruples)

虽然叫“三地址”，但在数据结构中通常用四元式记录：

结构：(op, arg1, arg2, result)

op：运算符（+, *, minus, if, param, call 等）。
arg1 / arg2：运算对象（变量、常量或临时变量）。若单目运算，arg2 为空。
result：结果存放处（通常是编译器生成的临时变量 t_1, t_2...）。

2.3 布尔表达式的两种翻译流派

数值表示法 (Numerical)：
- 完全计算出 true (1) 或 false (0)。
- 用于：赋值语句 flag = a < b; 或 C 语言风格的计算。
控制流表示法 (Control Flow / Short-Circuit)：
- 核心：不计算具体值，而是通过跳转 (Jump) 到代码的不同位置来代表真假。
- 用于：if, while 等控制语句。支持短路求值（例如 A or B，若 A 为真，直接跳过 B）。

2.4 回填技术 (Backpatching)

问题：生成跳转指令时，目标代码块的标号（Label）通常还未生成。
策略：
1. 生成指令时，目标地址留空（goto _）。
2. 将这些待填的指令地址挂在链表（List）上。
3. 一旦目标位置确定（比如扫描到了 else 或 end），调用 backpatch 将链表中所有指令的目标一次性填上。

3. Method (核心翻译方法)

3.1 赋值语句与数组

核心思想：将高级语言的数组访问转换为低级语言的内存地址偏移。

一维数组 (设起始为 , 元素宽 )：

二维数组 (行优先存储，行长 )：

编译优化技巧：

将公式拆解为“编译时常量”和“运行时变量”：

$变量部分需运行时算常量部分编译时算好$

3.2 布尔表达式与控制流 (回填的核心)

利用属性传递来管理跳转链表。

关键函数：

makelist(i): 创建只包含指令地址 i 的新链表。
merge(p1, p2): 合并两个链表。
backpatch(p, i): 回填，把链表 p 中所有指令的跳转目标设为 i。

翻译方案 (SDT)：

1. if E then S1

E.true backpatch 到 S1 的起始地址 (M.quad)。
E.false 合并入 S.next (跳出语句)。
S1.next 合并入 S.next。

2. while M1 E do M2 S1

M1: 记录循环开始的地址（用于跳回来）。
E.true backpatch 到 S1 的起始 (M2.quad)。
S1.next backpatch 回 M1.quad (循环闭环)。
E.false 成为整个语句的 S.next (跳出循环)。

4. Example (经典例题)

例题 1：算术表达式转四元式

输入：x := (-y) * z + (-y) * z

优化视角：

如果是 DAG 或优化编译器，会识别 (-y)*z 为公共子表达式。但在基础三地址生成中，通常按顺序生成。

序号	op	arg1	arg2	result	说明
(1)	`uminus`	`y`	-	`t1`	处理第一个 -y
(2)	`*`	`t1`	`z`	`t2`	处理 t1 * z
(3)	`uminus`	`y`	-	`t3`	处理第二个 -y
(4)	`*`	`t3`	`z`	`t4`	处理 t3 * z
(5)	`+`	`t2`	`t4`	`t5`	相加
(6)	`:=`	`t5`	-	`x`	赋值

例题 2：布尔表达式的回填 (高频考点)

输入：a < b or c < d and e < f

解析步骤：

a < b (OR 的左侧)
- 若真：整个表达式直接为真加入 Truelist。
- 若假：需要检测右边 goto 下一步判断。
- 生成：
  
  100: if a < b goto _ (真出口，挂入 Truelist)
  
  101: goto _ (假出口，回填为 102)
c < d (AND 的左侧)
- 此时是 OR 的右半部分。
- 若真：需要检测 e < f goto 下一步。
- 若假：AND 失败，且前面 OR 也失败整个表达式为假加入 Falselist。
- 生成：
  
  102: if c < d goto _ (真出口，回填为 104)
  
  103: goto _ (假出口，挂入 Falselist)
e < f (AND 的右侧)
- 若真：整个表达式真加入 Truelist。
- 若假：整个表达式假加入 Falselist。
- 生成：
  
  104: if e < f goto _ (真出口，挂入 Truelist)
  
  105: goto _ (假出口，挂入 Falselist)

最终结果状态：

Truelist: {100, 104} (待回填 True 对应的代码块地址)
Falselist: {103, 105} (待回填 False 对应的代码块地址)

例题 3：数组地址计算优化

输入：x := A[i, j]

条件：整数数组 ()，下标从 1 开始 ()。

公式推导：

展开整理常量：

生成的中间代码：

t1 := i * 20  
t1 := t1 + j     // 计算变址部分  
t2 := base - 84  // C，通常在符号表或编译时已算好  
t3 := t1 * 4     // 乘以字长  
t4 := t2[t3]     // 变址寻址：Mem[base_const + offset]  
x  := t4