前言
在前两篇文章中，我们讲了：
- 语法分析：把代码变成语法树
- 语义分析：检查代码是否有意义
现在，编译器已经理解了代码的结构和含义。接下来要做什么？
把代码翻译成更接近机器的形式。
这就像翻译一本书：
- 原文：高级编程语言（Python、Java）
- 译文：机器语言（0和1）
- 中间代码：介于两者之间的"草稿"
今天，我们深入讲解中间代码生成。
一、为什么需要中间代码？
1.1 直接翻译的问题
假设你要把一本中文书翻译成10种语言：
flowchart LR
A[中文] --> B[英语]
A --> C[法语]
A --> D[德语]
A --> E[日语]
A --> F[...]
style A fill:#e1f5ff
需要 10 个翻译官。
但如果先翻译成世界语（国际辅助语言）：
flowchart LR
A[中文] --> B[世界语<br/>中间语言]
B --> C[英语]
B --> D[法语]
B --> E[德语]
B --> F[日语]
B --> G[...]
style A fill:#e1f5ff
style B fill:#fff4e1
只需要 1 + 10 = 11 个翻译步骤，而不是 10 个直接翻译。
1.2 编译器中的中间代码
编译器面临同样的问题：
源语言：Python, Java, C++, JavaScript, ...
目标机器：x86, ARM, RISC-V, MIPS, ...
如果直接翻译：需要 M × N 种编译器。
使用中间代码：
flowchart LR
A[Python] --> D[中间代码 IR]
B[Java] --> D
C[C++] --> D
D --> E[x86]
D --> F[ARM]
D --> G[RISC-V]
style D fill:#fff4e1
只需要 M + N 种转换。
1.3 中间代码的好处
| 好处 | 说明 |
|---|---|
| 可移植性 | 一次编写，到处运行 |
| 优化机会 | 在中间层做优化，适用所有平台 |
| 简化编译器 | 前端只管生成IR，后端只管翻译IR |
| 模块化 | 前端和后端独立开发 |
二、中间代码的形式
中间代码有多种形式，我们讲解最常见的几种。
2.1 三地址码（Three-Address Code）
什么是三地址码？
三地址码：每条指令最多包含三个地址（两个操作数 + 一个结果）。
就像简单的计算器指令：
t1 = a + b # 两个操作数 (a, b) + 一个结果 (t1)
t2 = t1 * c # 两个操作数 (t1, c) + 一个结果 (t2)
x = t2 # 一个操作数 (t2) + 一个结果 (x)
为什么叫"三地址"？
每条指令涉及最多三个地址（变量或临时变量）：
x = y op z
↑ ↑ ↑
1 2 3
三地址码的指令类型
| 指令类型 | 形式 | 例子 |
|---|---|---|
| 赋值 | x = y | x = a |
| 二元运算 | x = y op z | x = a + b |
| 一元运算 | x = op y | x = -a |
| 无条件跳转 | goto L | goto L1 |
| 条件跳转 | if x goto L | if x > 0 goto L1 |
| 参数传递 | param x | param a |
| 函数调用 | call f, n | call foo, 2 |
| 返回 | return x | return t1 |
| 数组访问 | x = y[i] | x = arr[i] |
| 指针操作 | x = *y | x = *p |
示例：从源代码到三地址码
源代码：
a = 1 + 2 * 3
三地址码：
t1 = 2 * 3
t2 = 1 + t1
a = t2
图解：
graph TD
A["源代码: a = 1 + 2 * 3"] --> B[语法树]
B --> C["三地址码"]
C --> D["t1 = 2 * 3"]
C --> E["t2 = 1 + t1"]
C --> F["a = t2"]
style A fill:#e1f5ff
style C fill:#fff4e1
style D fill:#e8f5e9
style E fill:#e8f5e9
style F fill:#e8f5e9
2.2 静态单赋值（SSA）
什么是SSA？
SSA（Static Single Assignment）：每个变量只被赋值一次。
普通代码：
x = 1
x = 2
y = x
SSA形式：
x1 = 1
x2 = 2
y1 = x2
每次赋值都产生一个新版本。
为什么需要SSA？
简化优化：
普通形式：
x = 1
x = 2 # x 的值变了
y = x # y = ?
SSA形式：
x1 = 1
x2 = 2 # x2 是新版本
y1 = x2 # y1 肯定等于 2
在SSA中，定义-使用链非常清晰。
φ函数：处理分支
当控制流汇合时，需要φ函数选择值：
源代码：
if condition:
x = 1
else:
x = 2
y = x # x 的值来自哪个分支？
SSA形式：
if condition:
x1 = 1
else:
x2 = 2
x3 = φ(x1, x2) # 选择：如果来自then块，选x1；否则选x2
y1 = x3
图解：
flowchart TD
A[condition?] -->|true| B[x1 = 1]
A -->|false| C[x2 = 2]
B --> D["x3 = φ(x1, x2)"]
C --> D
D --> E[y1 = x3]
style A fill:#e1f5ff
style D fill:#fff4e1
2.3 其他中间表示
| 形式 | 特点 | 使用场景 |
|---|---|---|
| 三地址码 | 简单、易理解 | 教学入门 |
| SSA | 单赋值、易优化 | 现代编译器（LLVM、GCC） |
| 栈式虚拟机 | 基于栈操作 | JVM、.NET |
| CFG | 控制流图 | 优化分析 |
| 数据流图 | 数据依赖关系 | 并行优化 |
三、如何生成中间代码？
3.1 语法树遍历
从语法树生成三地址码：
graph TD
A[语法树] --> B[遍历树节点]
B --> C[为每个运算生成临时变量]
C --> D[生成三地址指令]
D --> E[中间代码]
style A fill:#e1f5ff
style E fill:#d4edda
3.2 实现示例
让我们实现一个三地址码生成器：
from dataclasses import dataclass
from typing import List, Union
@dataclass
class Instruction:
"""三地址码指令"""
op: str # 操作符
result: str # 结果
arg1: str = None # 操作数1
arg2: str = None # 操作数2
def __str__(self):
if self.op == 'assign':
return f"{self.result} = {self.arg1}"
elif self.op in ['+', '-', '*', '/']:
return f"{self.result} = {self.arg1} {self.op} {self.arg2}"
elif self.op == 'uminus':
return f"{self.result} = -{self.arg1}"
elif self.op == 'param':
return f"param {self.result}"
elif self.op == 'call':
return f"{self.result} = call {self.arg1}, {self.arg2}"
elif self.op == 'return':
return f"return {self.result}"
else:
return f"{self.op} {self.result} {self.arg1} {self.arg2}"
class ThreeAddressCodeGenerator:
"""三地址码生成器"""
def __init__(self):
self.instructions: List[Instruction] = []
self.temp_count = 0
self.label_count = 0
def new_temp(self) -> str:
"""生成新的临时变量"""
self.temp_count += 1
return f"t{self.temp_count}"
def new_label(self) -> str:
"""生成新的标签"""
self.label_count += 1
return f"L{self.label_count}"
def emit(self, op: str, result: str, arg1: str = None, arg2: str = None):
"""生成一条指令"""
instr = Instruction(op, result, arg1, arg2)
self.instructions.append(instr)
def generate(self, node) -> str:
"""从AST节点生成三地址码，返回结果的地址"""
if isinstance(node, dict):
node_type = node.get('type')
# 数字常量
if node_type == 'number':
temp = self.new_temp()
self.emit('assign', temp, str(node['value']))
return temp
# 变量
elif node_type == 'variable':
return node['name']
# 二元运算
elif node_type == 'binary':
left_addr = self.generate(node['left'])
right_addr = self.generate(node['right'])
result_addr = self.new_temp()
self.emit(node['operator'], result_addr, left_addr, right_addr)
return result_addr
# 一元运算
elif node_type == 'unary':
operand_addr = self.generate(node['operand'])
result_addr = self.new_temp()
self.emit('uminus', result_addr, operand_addr)
return result_addr
# 赋值
elif node_type == 'assignment':
value_addr = self.generate(node['value'])
self.emit('assign', node['variable'], value_addr)
return node['variable']
# if 语句
elif node_type == 'if':
return self.generate_if(node)
# while 语句
elif node_type == 'while':
return self.generate_while(node)
# 代码块
elif node_type == 'block':
for stmt in node['statements']:
self.generate(stmt)
return None
return str(node)
def generate_if(self, node) -> None:
"""生成 if 语句的三地址码"""
else_label = self.new_label()
end_label = self.new_label()
# 计算条件
cond_addr = self.generate(node['condition'])
# 条件跳转
self.emit('ifFalse', cond_addr, else_label)
# then 块
self.generate(node['then_branch'])
self.emit('goto', end_label)
# else 块
self.emit('label', else_label)
if 'else_branch' in node:
self.generate(node['else_branch'])
# 结束标签
self.emit('label', end_label)
def generate_while(self, node) -> None:
"""生成 while 语句的三地址码"""
start_label = self.new_label()
end_label = self.new_label()
# 开始标签
self.emit('label', start_label)
# 计算条件
cond_addr = self.generate(node['condition'])
# 条件跳转
self.emit('ifFalse', cond_addr, end_label)
# 循环体
self.generate(node['body'])
# 跳回开始
self.emit('goto', start_label)
# 结束标签
self.emit('label', end_label)
def print_code(self):
"""打印生成的三地址码"""
print("=== 三地址码 ===")
for instr in self.instructions:
print(f" {instr}")
# 测试：生成 a = 1 + 2 * 3 的三地址码
print("示例1：简单表达式\n")
ast1 = {
'type': 'assignment',
'variable': 'a',
'value': {
'type': 'binary',
'operator': '+',
'left': {'type': 'number', 'value': 1},
'right': {
'type': 'binary',
'operator': '*',
'left': {'type': 'number', 'value': 2},
'right': {'type': 'number', 'value': 3}
}
}
}
gen1 = ThreeAddressCodeGenerator()
gen1.generate(ast1)
gen1.print_code()
# 测试：生成 if 语句
print("\n示例2：if 语句\n")
ast2 = {
'type': 'if',
'condition': {'type': 'variable', 'name': 'x'},
'then_branch': {
'type': 'assignment',
'variable': 'y',
'value': {'type': 'number', 'value': 1}
},
'else_branch': {
'type': 'assignment',
'variable': 'y',
'value': {'type': 'number', 'value': 2}
}
}
gen2 = ThreeAddressCodeGenerator()
gen2.generate(ast2)
gen2.print_code()
# 测试：生成 while 语句
print("\n示例3：while 语句\n")
ast3 = {
'type': 'while',
'condition': {
'type': 'binary',
'operator': '<',
'left': {'type': 'variable', 'name': 'i'},
'right': {'type': 'number', 'value': 10}
},
'body': {
'type': 'block',
'statements': [
{
'type': 'assignment',
'variable': 'i',
'value': {
'type': 'binary',
'operator': '+',
'left': {'type': 'variable', 'name': 'i'},
'right': {'type': 'number', 'value': 1}
}
}
]
}
}
gen3 = ThreeAddressCodeGenerator()
gen3.generate(ast3)
gen3.print_code()
3.3 输出示例
示例1：简单表达式
=== 三地址码 ===
t1 = 2 * 3
t2 = 1 + t1
a = t2
示例2：if 语句
=== 三地址码 ===
ifFalse x L1
y = 1
goto L2
label L1
y = 2
label L2
示例3：while 语句
=== 三地址码 ===
label L1
t1 = i < 10
ifFalse t1 L2
t2 = i + 1
i = t2
goto L1
label L2
四、中间代码优化
中间代码生成后，可以做各种优化。
4.1 常量折叠
优化前：
t1 = 2 * 3
t2 = 1 + t1
优化后：
t1 = 6
t2 = 7
实现：
class ConstantFolder:
"""常量折叠优化"""
def __init__(self, instructions):
self.instructions = instructions
def optimize(self):
"""执行常量折叠"""
optimized = []
constants = {} # 记录已知的常量值
for instr in self.instructions:
if instr.op == 'assign' and instr.arg1.isdigit():
# 记录常量
constants[instr.result] = int(instr.arg1)
optimized.append(instr)
elif instr.op in ['+', '-', '*', '/']:
left_val = constants.get(instr.arg1)
right_val = constants.get(instr.arg2)
if left_val is not None and right_val is not None:
# 可以计算
if instr.op == '+':
result = left_val + right_val
elif instr.op == '-':
result = left_val - right_val
elif instr.op == '*':
result = left_val * right_val
elif instr.op == '/':
result = left_val // right_val
# 替换为常量赋值
new_instr = Instruction('assign', instr.result, str(result))
constants[instr.result] = result
optimized.append(new_instr)
print(f"✅ 常量折叠: {instr.arg1} {instr.op} {instr.arg2} → {result}")
else:
optimized.append(instr)
else:
optimized.append(instr)
return optimized
4.2 死代码消除
优化前：
t1 = 2 * 3 # t1 从未被使用
t2 = 1 + 5
a = t2
优化后：
t2 = 6
a = t2
4.3 公共子表达式消除
优化前：
t1 = a + b
t2 = a + b # 重复计算
t3 = t1 * t2
优化后：
t1 = a + b
t2 = t1 # 复用
t3 = t1 * t2
五、实战：完整的中间代码生成器
让我们实现一个完整的系统：
from typing import List, Dict, Set
@dataclass
class BasicBlock:
"""基本块：连续执行的指令序列"""
label: str
instructions: List[Instruction]
predecessors: Set[str]
successors: Set[str]
class IntermediateCodeSystem:
"""完整的中间代码系统"""
def __init__(self):
self.generator = ThreeAddressCodeGenerator()
self.blocks: Dict[str, BasicBlock] = {}
def generate_from_ast(self, ast):
"""从AST生成中间代码"""
print("📊 第一步：生成三地址码")
self.generator.generate(ast)
self.generator.print_code()
print("\n🔧 第二步：常量折叠优化")
self.optimize_constants()
print("\n🗑️ 第三步：死代码消除")
self.eliminate_dead_code()
print("\n📦 第四步：构建基本块")
self.build_basic_blocks()
def optimize_constants(self):
"""常量折叠"""
folder = ConstantFolder(self.generator.instructions)
self.generator.instructions = folder.optimize()
self.generator.print_code()
def eliminate_dead_code(self):
"""死代码消除"""
# 找出所有被使用的变量
used_vars = set()
# 第一遍：收集所有被使用的变量
for instr in self.generator.instructions:
if instr.arg1:
used_vars.add(instr.arg1)
if instr.arg2:
used_vars.add(instr.arg2)
# 第二遍：移除未被使用的赋值
optimized = []
for instr in self.generator.instructions:
if instr.op == 'assign':
# 检查结果是否被使用
if instr.result in used_vars or not instr.result.startswith('t'):
optimized.append(instr)
else:
print(f"❌ 移除死代码: {instr}")
else:
optimized.append(instr)
self.generator.instructions = optimized
self.generator.print_code()
def build_basic_blocks(self):
"""构建基本块"""
# 简化版：按标签分割基本块
current_block = []
current_label = "entry"
for instr in self.generator.instructions:
if instr.op == 'label':
# 新基本块开始
if current_block:
self.blocks[current_label] = BasicBlock(
label=current_label,
instructions=current_block,
predecessors=set(),
successors=set()
)
current_label = instr.result
current_block = []
else:
current_block.append(instr)
# 最后一个块
if current_block:
self.blocks[current_label] = BasicBlock(
label=current_label,
instructions=current_block,
predecessors=set(),
successors=set()
)
# 打印基本块
for label, block in self.blocks.items():
print(f"\n基本块 [{label}]:")
for instr in block.instructions:
print(f" {instr}")
def visualize_cfg(self):
"""可视化控制流图"""
print("\n📊 控制流图（CFG）:")
print("```mermaid")
print("graph TD")
for label, block in self.blocks.items():
instr_str = '<br/>'.join([str(i) for i in block.instructions[:3]])
if len(block.instructions) > 3:
instr_str += '<br/>...'
print(f" {label}[\"{label}<br/>{instr_str}\"]")
print("```")
# 完整示例
print("=" * 60)
print("完整示例：编译表达式计算程序")
print("=" * 60)
program = {
'type': 'block',
'statements': [
# a = 10
{
'type': 'assignment',
'variable': 'a',
'value': {'type': 'number', 'value': 10}
},
# b = 20
{
'type': 'assignment',
'variable': 'b',
'value': {'type': 'number', 'value': 20}
},
# c = a + b * 2
{
'type': 'assignment',
'variable': 'c',
'value': {
'type': 'binary',
'operator': '+',
'left': {'type': 'variable', 'name': 'a'},
'right': {
'type': 'binary',
'operator': '*',
'left': {'type': 'variable', 'name': 'b'},
'right': {'type': 'number', 'value': 2}
}
}
}
]
}
system = IntermediateCodeSystem()
system.generate_from_ast(program)
六、中间代码与目标代码
6.1 从中间代码到机器码
中间代码最终要翻译成机器码：
flowchart LR
A[中间代码 IR] --> B[指令选择]
B --> C[寄存器分配]
C --> D[指令调度]
D --> E[目标代码]
style A fill:#fff4e1
style E fill:#d4edda
6.2 示例：三地址码到x86汇编
三地址码：
t1 = a + b
t2 = t1 * c
x = t2
x86汇编：
mov eax, [a] ; 加载 a
add eax, [b] ; eax = a + b
imul eax, [c] ; eax = (a + b) * c
mov [x], eax ; 存储到 x
6.3 寄存器分配
问题：寄存器有限，如何高效使用？
三地址码： 寄存器分配后：
t1 = a + b R1 = a + b
t2 = t1 * c R1 = R1 * c (复用 R1)
t3 = t2 - d R2 = d (需要新寄存器)
R1 = R1 - R2
七、实际编译器中的中间代码
7.1 LLVM IR
LLVM 使用自己的中间表示：
; 源代码: int add(int a, int b) { return a + b; }
define i32 @add(i32 %a, i32 %b) {
entry:
%sum = add i32 %a, %b
ret i32 %sum
}
7.2 Java 字节码
Java 编译成字节码：
; 源代码: int add(int a, int b) { return a + b; }
iload_0 ; 加载第一个参数
iload_1 ; 加载第二个参数
iadd ; 相加
ireturn ; 返回
7.3 GCC GIMPLE
GCC 使用 GIMPLE：
; 源代码: a = b + c * d;
t1 = c * d;
a = b + t1;
八、总结
8.1 核心概念
- 中间代码：介于源代码和机器码之间的表示
- 三地址码：每条指令最多三个地址
- SSA：每个变量只赋值一次
- 优化：常量折叠、死代码消除等
8.2 编译流程
flowchart TD
A[源代码] --> B[词法分析]
B --> C[语法分析]
C --> D[语义分析]
D --> E[中间代码生成]
E --> F[中间代码优化]
F --> G[目标代码生成]
G --> H[机器码]
style E fill:#fff4e1
style F fill:#fff4e1
8.3 为什么重要？
- ✅ 可移植性：支持多平台
- ✅ 优化机会：在中间层做优化
- ✅ 模块化：前端后端分离
- ✅ 简化编译器：复杂度降低
扩展阅读
- 《编译原理》（龙书）- 第6、8、9章
- 《Engineering a Compiler》- Intermediate Representations
- LLVM Language Reference Manual
- SSA Book
中间代码是编译器的"通用语言"，让代码能在不同平台上运行。