语义分析实战（三）—— 生成三地址码
章节标题
三地址码的核心作用
三地址码是一种重要的中间表示形式，它的主要作用是：
- 简化代码生成：三地址码的结构简单，便于后续的代码生成
- 支持代码优化：三地址码易于进行各种优化操作
- 平台无关性：三地址码不依赖于具体的目标平台
- 便于调试：三地址码的结构清晰，便于调试和分析
三地址码的基本形式
三地址码的基本形式是：
x = y op z其中：
x、y、z是操作数op是操作符
常见的三地址码指令类型包括：
- 赋值指令：
x = y - 算术指令：
x = y + z,x = y - z,x = y * z,x = y / z - 关系指令：
x = y < z,x = y == z - 跳转指令：
goto L,if x goto L,if x op y goto L - 函数调用指令：
param x,call f, n,x = call f, n - 返回指令：
return,return x
从AST生成三地址码的原理
从AST生成三地址码的过程是一个深度优先遍历的过程，对于每个AST节点，根据其类型生成相应的三地址码指令。
生成过程
- 初始化：创建临时变量计数器，初始化指令列表
- 遍历AST：深度优先遍历AST的每个节点
- 生成指令：根据节点类型生成相应的三地址码指令
- 处理临时变量：为复杂表达式生成临时变量
- 构建指令序列：将生成的指令按顺序添加到指令列表中
表达式的三地址码生成
简单表达式
对于简单的算术表达式，我们可以直接生成对应的三地址码指令。
例如，对于表达式 a + b * c，生成的三地址码如下：
t1 = b * c
t2 = a + t1复杂表达式
对于复杂的表达式，我们需要使用临时变量来存储中间结果。
例如，对于表达式 (a + b) * (c - d)，生成的三地址码如下：
t1 = a + b
t2 = c - d
t3 = t1 * t2语句的三地址码生成
赋值语句
对于赋值语句 x = a + b，生成的三地址码如下：
t1 = a + b
x = t1条件语句
对于if语句：
if (x > y) {
z = x;
} else {
z = y;
}生成的三地址码如下：
if x > y goto L1
goto L2
L1:
z = x
goto L3
L2:
z = y
L3:循环语句
对于while语句：
while (x < 10) {
x = x + 1;
}生成的三地址码如下：
L1:
if x < 10 goto L2
goto L3
L2:
x = x + 1
goto L1
L3:三地址码生成器的实现
1. 三地址码指令类
class ThreeAddressCode:
"""三地址码指令类"""
def __init__(self):
self.instructions = []
self.temp_count = 0
def new_temp(self):
"""生成新的临时变量"""
temp = f"t{self.temp_count}"
self.temp_count += 1
return temp
def emit(self, op, arg1=None, arg2=None, result=None):
"""生成三地址码指令"""
instruction = {
'op': op,
'arg1': arg1,
'arg2': arg2,
'result': result
}
self.instructions.append(instruction)
return instruction
def emit_label(self, label):
"""生成标签指令"""
instruction = {
'op': 'label',
'label': label
}
self.instructions.append(instruction)
return instruction
def get_instructions(self):
"""获取所有指令"""
return self.instructions
def print_instructions(self):
"""打印指令"""
for i, instr in enumerate(self.instructions):
if instr['op'] == 'label':
print(f"{instr['label']}:")
else:
if instr['op'] == 'goto':
print(f" goto {instr['arg1']}")
elif instr['op'] == 'if':
print(f" if {instr['arg1']} {instr['arg2']} {instr['arg3']} goto {instr['result']}")
elif instr['arg2'] is None:
print(f" {instr['result']} = {instr['op']} {instr['arg1']}")
else:
print(f" {instr['result']} = {instr['arg1']} {instr['op']} {instr['arg2']}")2. 从AST生成三地址码
def generate_three_address_code(ast):
"""从AST生成三地址码"""
tac = ThreeAddressCode()
_generate_code(ast, tac)
return tac
def _generate_code(node, tac):
"""递归生成三地址码"""
if node['type'] == 'program':
for stmt in node['statements']:
_generate_code(stmt, tac)
elif node['type'] == 'variable_declaration':
# 处理变量声明
if 'initializer' in node:
init_val = _generate_expression(node['initializer'], tac)
tac.emit('=', init_val, None, node['name'])
elif node['type'] == 'assignment':
# 处理赋值语句
right_val = _generate_expression(node['right'], tac)
tac.emit('=', right_val, None, node['left']['name'])
elif node['type'] == 'if':
# 处理if语句
cond_val = _generate_expression(node['condition'], tac)
label1 = f"L{tac.temp_count}"
label2 = f"L{tac.temp_count + 1}"
label3 = f"L{tac.temp_count + 2}"
tac.temp_count += 3
# 条件判断
tac.emit('if', cond_val, '!=', '0', label1)
tac.emit('goto', label2)
# then分支
tac.emit_label(label1)
_generate_code(node['then_branch'], tac)
tac.emit('goto', label3)
# else分支（如果有）
tac.emit_label(label2)
if 'else_branch' in node:
_generate_code(node['else_branch'], tac)
# 结束标签
tac.emit_label(label3)
elif node['type'] == 'while':
# 处理while语句
label1 = f"L{tac.temp_count}"
label2 = f"L{tac.temp_count + 1}"
label3 = f"L{tac.temp_count + 2}"
tac.temp_count += 3
# 循环开始
tac.emit_label(label1)
cond_val = _generate_expression(node['condition'], tac)
tac.emit('if', cond_val, '==', '0', label3)
# 循环体
tac.emit_label(label2)
_generate_code(node['body'], tac)
tac.emit('goto', label1)
# 循环结束
tac.emit_label(label3)
elif node['type'] == 'return':
# 处理return语句
if 'expression' in node:
return_val = _generate_expression(node['expression'], tac)
tac.emit('return', return_val)
else:
tac.emit('return')
elif node['type'] == 'block':
# 处理块语句
for stmt in node['statements']:
_generate_code(stmt, tac)
def _generate_expression(node, tac):
"""生成表达式的三地址码"""
if node['type'] == 'constant':
# 处理常量
temp = tac.new_temp()
tac.emit('=', str(node['value']), None, temp)
return temp
elif node['type'] == 'variable':
# 处理变量
return node['name']
elif node['type'] == 'binary_op':
# 处理二元操作符
left_val = _generate_expression(node['left'], tac)
right_val = _generate_expression(node['right'], tac)
temp = tac.new_temp()
tac.emit(node['op'], left_val, right_val, temp)
return temp
elif node['type'] == 'unary_op':
# 处理一元操作符
operand_val = _generate_expression(node['operand'], tac)
temp = tac.new_temp()
tac.emit(node['op'], operand_val, None, temp)
return temp
elif node['type'] == 'function_call':
# 处理函数调用
# 生成参数的三地址码
for arg in node['args']:
arg_val = _generate_expression(arg, tac)
tac.emit('param', arg_val)
# 生成函数调用指令
temp = tac.new_temp()
tac.emit('call', node['name'], str(len(node['args'])), temp)
return temp
else:
raise ValueError(f"Unknown expression type: {node['type']}")实用案例分析
案例：生成简单程序的三地址码
假设我们有以下简单的程序：
int main() {
int x = 5;
int y = 3;
int z;
if (x > y) {
z = x + y;
} else {
z = x - y;
}
return z;
}对应的AST结构如下：
{
'type': 'program',
'statements': [
{
'type': 'function_definition',
'name': 'main',
'parameters': [],
'return_type': 'int',
'body': {
'type': 'block',
'statements': [
{
'type': 'variable_declaration',
'name': 'x',
'type': 'int',
'initializer': {
'type': 'constant',
'value': 5
}
},
{
'type': 'variable_declaration',
'name': 'y',
'type': 'int',
'initializer': {
'type': 'constant',
'value': 3
}
},
{
'type': 'variable_declaration',
'name': 'z',
'type': 'int'
},
{
'type': 'if',
'condition': {
'type': 'binary_op',
'op': '>',
'left': {
'type': 'variable',
'name': 'x'
},
'right': {
'type': 'variable',
'name': 'y'
}
},
'then_branch': {
'type': 'block',
'statements': [
{
'type': 'assignment',
'left': {
'type': 'variable',
'name': 'z'
},
'right': {
'type': 'binary_op',
'op': '+',
'left': {
'type': 'variable',
'name': 'x'
},
'right': {
'type': 'variable',
'name': 'y'
}
}
}
]
},
'else_branch': {
'type': 'block',
'statements': [
{
'type': 'assignment',
'left': {
'type': 'variable',
'name': 'z'
},
'right': {
'type': 'binary_op',
'op': '-',
'left': {
'type': 'variable',
'name': 'x'
},
'right': {
'type': 'variable',
'name': 'y'
}
}
}
]
}
},
{
'type': 'return',
'expression': {
'type': 'variable',
'name': 'z'
}
}
]
}
}
]
}生成的三地址码如下：
t0 = 5
x = t0
t1 = 3
y = t1
t2 = x > y
if t2 != 0 goto L3
goto L4
L3:
t3 = x + y
z = t3
goto L5
L4:
t4 = x - y
z = t4
L5:
return z三地址码生成器的测试
下面是一个简单的测试代码，用于测试三地址码生成器的功能：
# 测试三地址码生成器
if __name__ == "__main__":
# 简单的AST示例
ast = {
'type': 'program',
'statements': [
{
'type': 'variable_declaration',
'name': 'x',
'type': 'int',
'initializer': {
'type': 'constant',
'value': 5
}
},
{
'type': 'variable_declaration',
'name': 'y',
'type': 'int',
'initializer': {
'type': 'constant',
'value': 3
}
},
{
'type': 'assignment',
'left': {
'type': 'variable',
'name': 'x'
},
'right': {
'type': 'binary_op',
'op': '+',
'left': {
'type': 'variable',
'name': 'x'
},
'right': {
'type': 'constant',
'value': 1
}
}
},
{
'type': 'if',
'condition': {
'type': 'binary_op',
'op': '>',
'left': {
'type': 'variable',
'name': 'x'
},
'right': {
'type': 'variable',
'name': 'y'
}
},
'then_branch': {
'type': 'block',
'statements': [
{
'type': 'assignment',
'left': {
'type': 'variable',
'name': 'y'
},
'right': {
'type': 'binary_op',
'op': '+',
'left': {
'type': 'variable',
'name': 'y'
},
'right': {
'type': 'constant',
'value': 2
}
}
}
]
}
}
]
}
# 生成三地址码
tac = generate_three_address_code(ast)
# 打印三地址码
print("=== Three-Address Code ===")
tac.print_instructions()
print("========================")三地址码生成器的优化
临时变量优化：减少不必要的临时变量
公共子表达式消除：识别并消除公共子表达式
常量折叠：在生成三地址码时进行常量折叠
死代码消除：消除不会执行的代码
表达式重排序：优化表达式的计算顺序
常见问题及解决方案
临时变量过多：
- 解决方案：实现临时变量复用和优化
表达式复杂度高：
- 解决方案：递归处理表达式，分解复杂表达式
控制流复杂：
- 解决方案：使用标签管理控制流，确保跳转正确
函数调用处理：
- 解决方案：正确处理参数传递和返回值
内存管理：
- 解决方案：合理管理临时变量和标签的生成
总结
三地址码生成是编译器语义分析阶段的重要组成部分，它将抽象语法树转换为一种结构化的中间表示形式，为后续的代码生成和优化奠定基础。
在本集的实战中，我们实现了一个基本的三地址码生成器，包括表达式翻译、语句翻译等核心功能。这个生成器可以处理简单的程序结构，但在实际编译器中，三地址码生成器会更加复杂，需要处理更多的语言特性和优化策略。
通过本集的学习，我们了解了三地址码的基本概念和生成方法，为后续的代码优化和目标代码生成奠定了基础。在后续的实战中，我们将继续完善中间代码生成器，实现更复杂的中间表示和优化功能。