用Python实战编译原理从零构建三地址码生成器编译原理常被视为计算机科学中最艰深的课程之一那些抽象的文法规则和复杂的语义动作让无数开发者望而生畏。但今天我们将打破这一魔咒——通过Python代码亲手实现一个简化版编译器前端直观感受从源代码到中间代码的完整转换过程。1. 编译器前端架构设计让我们先搭建一个最小化的编译器前端框架。这个框架需要处理三个核心任务词法分析、语法分析和中间代码生成。我们将采用面向对象的设计模式创建几个关键类来封装不同阶段的逻辑。class Lexer: def __init__(self, source_code): self.source source_code self.position 0 self.current_char self.source[self.position] if self.source else None def advance(self): self.position 1 if self.position len(self.source): self.current_char None else: self.current_char self.source[self.position] def skip_whitespace(self): while self.current_char is not None and self.current_char.isspace(): self.advance() def get_next_token(self): # 实现词法分析逻辑 pass词法分析器(Lexer)负责将源代码转换为标记流。我们需要定义各种token类型from enum import Enum class TokenType(Enum): # 基本token类型 INTEGER INTEGER FLOAT FLOAT ID ID ASSIGN SEMI ; LPAREN ( RPAREN ) # 运算符 PLUS MINUS - MUL * DIV / # 比较运算符 LT GT EQ # 关键字 IF IF ELSE ELSE WHILE WHILE EOF EOF语法分析器(Parser)将使用这些token构建抽象语法树(AST)。我们定义一个基础的AST节点类class ASTNode: def __init__(self, tokenNone): self.token token self.children [] def add_child(self, node): self.children.append(node) return self2. 语义分析与属性文法实现语义分析是连接语法和代码生成的关键桥梁。我们将使用属性文法来定义各种语法结构的语义规则。2.1 符号表设计符号表是语义分析的核心数据结构用于记录变量和类型信息class SymbolTable: def __init__(self): self.symbols {} self.scopes [{}] def enter_scope(self): self.scopes.append({}) def exit_scope(self): if len(self.scopes) 1: self.scopes.pop() def add_symbol(self, name, symbol_type, attributesNone): self.scopes[-1][name] { type: symbol_type, attributes: attributes or {} } def lookup(self, name): for scope in reversed(self.scopes): if name in scope: return scope[name] return None2.2 类型系统实现我们需要为不同类型定义宽度和存储需求class TypeSystem: def __init__(self): self.type_widths { int: 4, float: 8, bool: 1, char: 1 } def get_width(self, type_expr): if isinstance(type_expr, str): return self.type_widths.get(type_expr, 0) elif isinstance(type_expr, dict) and type_expr[kind] array: return type_expr[size] * self.get_width(type_expr[element_type]) elif isinstance(type_expr, dict) and type_expr[kind] pointer: return 8 # 假设64位系统 return 02.3 三地址码生成器三地址码是编译器常用的中间表示形式。我们实现一个简单的生成器class ThreeAddressCodeGenerator: def __init__(self): self.code [] self.temp_counter 0 self.label_counter 0 def emit(self, op, arg1None, arg2None, resultNone): instruction { op: op, arg1: arg1, arg2: arg2, result: result } self.code.append(instruction) return instruction def new_temp(self): temp ft{self.temp_counter} self.temp_counter 1 return temp def new_label(self): label fL{self.label_counter} self.label_counter 1 return label def print_code(self): for idx, instr in enumerate(self.code): print(f{idx}: {instr[op]}, end) if instr[arg1] is not None: print(f {instr[arg1]}, end) if instr[arg2] is not None: print(f, {instr[arg2]}, end) if instr[result] is not None: print(f {instr[result]}, end) print()3. 表达式与赋值语句翻译让我们从最简单的赋值语句开始逐步构建完整的翻译系统。3.1 简单赋值翻译对于形如x y z的简单赋值翻译过程如下为右侧表达式生成三地址码将结果赋给左侧变量def translate_assignment(self, node, symbol_table, code_gen): # 假设node结构ASSIGN - ID, EXPR var_name node.children[0].token.value expr_node node.children[1] # 翻译右侧表达式 expr_temp self.translate_expression(expr_node, symbol_table, code_gen) # 查找变量地址 var_entry symbol_table.lookup(var_name) if not var_entry: raise Exception(fUndefined variable: {var_name}) # 生成赋值指令 code_gen.emit(, expr_temp, None, var_name) return var_name3.2 表达式翻译表达式翻译需要处理运算符优先级和类型转换def translate_expression(self, node, symbol_table, code_gen): if len(node.children) 1: # 单个操作数 operand node.children[0] if operand.token.type TokenType.ID: var_entry symbol_table.lookup(operand.token.value) if not var_entry: raise Exception(fUndefined variable: {operand.token.value}) return operand.token.value else: # 常量 temp code_gen.new_temp() code_gen.emit(, operand.token.value, None, temp) return temp # 二元运算 left_temp self.translate_expression(node.children[0], symbol_table, code_gen) right_temp self.translate_expression(node.children[2], symbol_table, code_gen) op node.children[1].token.type.value result_temp code_gen.new_temp() code_gen.emit(op, left_temp, right_temp, result_temp) return result_temp3.3 数组元素访问翻译数组访问需要计算元素地址这是编译原理中的经典问题def translate_array_access(self, node, symbol_table, code_gen): # 假设node结构ARRAY_ACCESS - ID, EXPR_LIST array_name node.children[0].token.value array_entry symbol_table.lookup(array_name) if not array_entry or array_entry[type][kind] ! array: raise Exception(fNot an array: {array_name}) # 计算基地址 base_addr f{array_name}_base # 假设基地址已分配 # 初始化偏移量 offset_temp code_gen.new_temp() code_gen.emit(, 0, None, offset_temp) # 处理每个维度 element_type array_entry[type] expr_list node.children[1] for i, expr_node in enumerate(expr_list.children): # 翻译下标表达式 index_temp self.translate_expression(expr_node, symbol_table, code_gen) # 获取当前维度宽度 if element_type[kind] ! array: raise Exception(Array subscript mismatch) # 计算当前维度的偏移贡献 stride self.type_system.get_width(element_type[element_type]) stride_temp code_gen.new_temp() code_gen.emit(*, index_temp, str(stride), stride_temp) # 累加到总偏移 new_offset code_gen.new_temp() code_gen.emit(, offset_temp, stride_temp, new_offset) offset_temp new_offset element_type element_type[element_type] # 计算最终地址 addr_temp code_gen.new_temp() code_gen.emit(, base_addr, offset_temp, addr_temp) # 加载数组元素 result_temp code_gen.new_temp() code_gen.emit(load, addr_temp, None, result_temp) return result_temp4. 控制流语句翻译控制流语句(if, while等)的翻译是编译器设计的核心挑战需要处理标签和跳转指令。4.1 if语句翻译if语句需要生成条件判断和跳转指令def translate_if(self, node, symbol_table, code_gen): # 假设node结构IF - COND, THEN_PART, [ELSE_PART] cond_node node.children[0] then_node node.children[1] has_else len(node.children) 2 # 生成条件代码 cond_temp self.translate_condition(cond_node, symbol_table, code_gen) # 创建标签 else_label code_gen.new_label() if has_else else None end_label code_gen.new_label() # 条件跳转 if has_else: code_gen.emit(if_false, cond_temp, else_label, None) else: code_gen.emit(if_false, cond_temp, end_label, None) # 生成then部分代码 self.translate_statement(then_node, symbol_table, code_gen) code_gen.emit(goto, end_label, None, None) # 生成else部分代码 if has_else: code_gen.emit(label, else_label, None, None) self.translate_statement(node.children[2], symbol_table, code_gen) # 结束标签 code_gen.emit(label, end_label, None, None)4.2 while循环翻译while循环需要处理循环条件和跳回def translate_while(self, node, symbol_table, code_gen): # 假设node结构WHILE - COND, BODY cond_node node.children[0] body_node node.children[1] # 创建标签 start_label code_gen.new_label() body_label code_gen.new_label() end_label code_gen.new_label() # 循环开始 code_gen.emit(label, start_label, None, None) # 生成条件代码 cond_temp self.translate_condition(cond_node, symbol_table, code_gen) # 条件跳转 code_gen.emit(if_false, cond_temp, end_label, None) # 生成循环体代码 code_gen.emit(label, body_label, None, None) self.translate_statement(body_node, symbol_table, code_gen) # 跳回循环开始 code_gen.emit(goto, start_label, None, None) # 结束标签 code_gen.emit(label, end_label, None, None)4.3 布尔表达式翻译布尔表达式需要特殊处理以支持短路求值def translate_condition(self, node, symbol_table, code_gen): if node.token.type in (TokenType.TRUE, TokenType.FALSE): temp code_gen.new_temp() code_gen.emit(, node.token.value.lower(), None, temp) return temp # 关系表达式 if len(node.children) 3: # E1 relop E2 left self.translate_expression(node.children[0], symbol_table, code_gen) right self.translate_expression(node.children[2], symbol_table, code_gen) op node.children[1].token.type.value result code_gen.new_temp() code_gen.emit(op, left, right, result) return result # 逻辑运算 if node.children[1].token.type TokenType.OR: return self.translate_or(node, symbol_table, code_gen) elif node.children[1].token.type TokenType.AND: return self.translate_and(node, symbol_table, code_gen) raise Exception(Unsupported condition type)5. 完整示例与测试让我们通过一个完整示例演示整个翻译过程# 示例源代码 source { int[3][5] arr; int i 2; int j 3; arr[i][j] 10; if (i j) { arr[i][j] arr[i][j] 1; } else { arr[i][j] arr[i][j] - 1; } while (i 0) { i i - 1; } } # 初始化各组件 lexer Lexer(source) parser Parser(lexer) symbol_table SymbolTable() code_gen ThreeAddressCodeGenerator() type_system TypeSystem() # 注册数组类型 symbol_table.add_symbol(arr, { kind: array, size: 3, element_type: { kind: array, size: 5, element_type: int } }) # 解析和翻译 ast parser.parse() translator Translator(type_system) translator.translate(ast, symbol_table, code_gen) # 输出生成的三地址码 print(Generated Three-Address Code:) code_gen.print_code()运行上述代码将输出类似以下的三地址码0: 2 i 1: 3 j 2: * i, 20 t0 3: * j, 4 t1 4: t0, t1 t2 5: arr_base, t2 t3 6: 10 t4 7: store t3, t4 8: i, j t5 9: if_false t5 L0 10: * i, 20 t6 11: * j, 4 t7 12: t6, t7 t8 13: arr_base, t8 t9 14: load t9 t10 15: t10, 1 t11 16: store t9, t11 17: goto L1 18: label L0 19: * i, 20 t12 20: * j, 4 t13 21: t12, t13 t14 22: arr_base, t14 t15 23: load t15 t16 24: - t16, 1 t17 25: store t15, t17 26: label L1 27: label L2 28: i, 0 t18 29: if_false t18 L3 30: - i, 1 t19 31: t19 i 32: goto L2 33: label L3这个完整的Python实现展示了编译器前端如何将高级语言结构转换为三地址码。通过这个项目你不仅深入理解了编译原理的核心概念还获得了可扩展的代码框架可以继续添加更多语言特性支持。
别再死记硬背SDT了！手把手带你用Python模拟编译器中间代码生成（附完整代码）
发布时间：2026/7/6 19:09:03
用Python实战编译原理从零构建三地址码生成器编译原理常被视为计算机科学中最艰深的课程之一那些抽象的文法规则和复杂的语义动作让无数开发者望而生畏。但今天我们将打破这一魔咒——通过Python代码亲手实现一个简化版编译器前端直观感受从源代码到中间代码的完整转换过程。1. 编译器前端架构设计让我们先搭建一个最小化的编译器前端框架。这个框架需要处理三个核心任务词法分析、语法分析和中间代码生成。我们将采用面向对象的设计模式创建几个关键类来封装不同阶段的逻辑。class Lexer: def __init__(self, source_code): self.source source_code self.position 0 self.current_char self.source[self.position] if self.source else None def advance(self): self.position 1 if self.position len(self.source): self.current_char None else: self.current_char self.source[self.position] def skip_whitespace(self): while self.current_char is not None and self.current_char.isspace(): self.advance() def get_next_token(self): # 实现词法分析逻辑 pass词法分析器(Lexer)负责将源代码转换为标记流。我们需要定义各种token类型from enum import Enum class TokenType(Enum): # 基本token类型 INTEGER INTEGER FLOAT FLOAT ID ID ASSIGN SEMI ; LPAREN ( RPAREN ) # 运算符 PLUS MINUS - MUL * DIV / # 比较运算符 LT GT EQ # 关键字 IF IF ELSE ELSE WHILE WHILE EOF EOF语法分析器(Parser)将使用这些token构建抽象语法树(AST)。我们定义一个基础的AST节点类class ASTNode: def __init__(self, tokenNone): self.token token self.children [] def add_child(self, node): self.children.append(node) return self2. 语义分析与属性文法实现语义分析是连接语法和代码生成的关键桥梁。我们将使用属性文法来定义各种语法结构的语义规则。2.1 符号表设计符号表是语义分析的核心数据结构用于记录变量和类型信息class SymbolTable: def __init__(self): self.symbols {} self.scopes [{}] def enter_scope(self): self.scopes.append({}) def exit_scope(self): if len(self.scopes) 1: self.scopes.pop() def add_symbol(self, name, symbol_type, attributesNone): self.scopes[-1][name] { type: symbol_type, attributes: attributes or {} } def lookup(self, name): for scope in reversed(self.scopes): if name in scope: return scope[name] return None2.2 类型系统实现我们需要为不同类型定义宽度和存储需求class TypeSystem: def __init__(self): self.type_widths { int: 4, float: 8, bool: 1, char: 1 } def get_width(self, type_expr): if isinstance(type_expr, str): return self.type_widths.get(type_expr, 0) elif isinstance(type_expr, dict) and type_expr[kind] array: return type_expr[size] * self.get_width(type_expr[element_type]) elif isinstance(type_expr, dict) and type_expr[kind] pointer: return 8 # 假设64位系统 return 02.3 三地址码生成器三地址码是编译器常用的中间表示形式。我们实现一个简单的生成器class ThreeAddressCodeGenerator: def __init__(self): self.code [] self.temp_counter 0 self.label_counter 0 def emit(self, op, arg1None, arg2None, resultNone): instruction { op: op, arg1: arg1, arg2: arg2, result: result } self.code.append(instruction) return instruction def new_temp(self): temp ft{self.temp_counter} self.temp_counter 1 return temp def new_label(self): label fL{self.label_counter} self.label_counter 1 return label def print_code(self): for idx, instr in enumerate(self.code): print(f{idx}: {instr[op]}, end) if instr[arg1] is not None: print(f {instr[arg1]}, end) if instr[arg2] is not None: print(f, {instr[arg2]}, end) if instr[result] is not None: print(f {instr[result]}, end) print()3. 表达式与赋值语句翻译让我们从最简单的赋值语句开始逐步构建完整的翻译系统。3.1 简单赋值翻译对于形如x y z的简单赋值翻译过程如下为右侧表达式生成三地址码将结果赋给左侧变量def translate_assignment(self, node, symbol_table, code_gen): # 假设node结构ASSIGN - ID, EXPR var_name node.children[0].token.value expr_node node.children[1] # 翻译右侧表达式 expr_temp self.translate_expression(expr_node, symbol_table, code_gen) # 查找变量地址 var_entry symbol_table.lookup(var_name) if not var_entry: raise Exception(fUndefined variable: {var_name}) # 生成赋值指令 code_gen.emit(, expr_temp, None, var_name) return var_name3.2 表达式翻译表达式翻译需要处理运算符优先级和类型转换def translate_expression(self, node, symbol_table, code_gen): if len(node.children) 1: # 单个操作数 operand node.children[0] if operand.token.type TokenType.ID: var_entry symbol_table.lookup(operand.token.value) if not var_entry: raise Exception(fUndefined variable: {operand.token.value}) return operand.token.value else: # 常量 temp code_gen.new_temp() code_gen.emit(, operand.token.value, None, temp) return temp # 二元运算 left_temp self.translate_expression(node.children[0], symbol_table, code_gen) right_temp self.translate_expression(node.children[2], symbol_table, code_gen) op node.children[1].token.type.value result_temp code_gen.new_temp() code_gen.emit(op, left_temp, right_temp, result_temp) return result_temp3.3 数组元素访问翻译数组访问需要计算元素地址这是编译原理中的经典问题def translate_array_access(self, node, symbol_table, code_gen): # 假设node结构ARRAY_ACCESS - ID, EXPR_LIST array_name node.children[0].token.value array_entry symbol_table.lookup(array_name) if not array_entry or array_entry[type][kind] ! array: raise Exception(fNot an array: {array_name}) # 计算基地址 base_addr f{array_name}_base # 假设基地址已分配 # 初始化偏移量 offset_temp code_gen.new_temp() code_gen.emit(, 0, None, offset_temp) # 处理每个维度 element_type array_entry[type] expr_list node.children[1] for i, expr_node in enumerate(expr_list.children): # 翻译下标表达式 index_temp self.translate_expression(expr_node, symbol_table, code_gen) # 获取当前维度宽度 if element_type[kind] ! array: raise Exception(Array subscript mismatch) # 计算当前维度的偏移贡献 stride self.type_system.get_width(element_type[element_type]) stride_temp code_gen.new_temp() code_gen.emit(*, index_temp, str(stride), stride_temp) # 累加到总偏移 new_offset code_gen.new_temp() code_gen.emit(, offset_temp, stride_temp, new_offset) offset_temp new_offset element_type element_type[element_type] # 计算最终地址 addr_temp code_gen.new_temp() code_gen.emit(, base_addr, offset_temp, addr_temp) # 加载数组元素 result_temp code_gen.new_temp() code_gen.emit(load, addr_temp, None, result_temp) return result_temp4. 控制流语句翻译控制流语句(if, while等)的翻译是编译器设计的核心挑战需要处理标签和跳转指令。4.1 if语句翻译if语句需要生成条件判断和跳转指令def translate_if(self, node, symbol_table, code_gen): # 假设node结构IF - COND, THEN_PART, [ELSE_PART] cond_node node.children[0] then_node node.children[1] has_else len(node.children) 2 # 生成条件代码 cond_temp self.translate_condition(cond_node, symbol_table, code_gen) # 创建标签 else_label code_gen.new_label() if has_else else None end_label code_gen.new_label() # 条件跳转 if has_else: code_gen.emit(if_false, cond_temp, else_label, None) else: code_gen.emit(if_false, cond_temp, end_label, None) # 生成then部分代码 self.translate_statement(then_node, symbol_table, code_gen) code_gen.emit(goto, end_label, None, None) # 生成else部分代码 if has_else: code_gen.emit(label, else_label, None, None) self.translate_statement(node.children[2], symbol_table, code_gen) # 结束标签 code_gen.emit(label, end_label, None, None)4.2 while循环翻译while循环需要处理循环条件和跳回def translate_while(self, node, symbol_table, code_gen): # 假设node结构WHILE - COND, BODY cond_node node.children[0] body_node node.children[1] # 创建标签 start_label code_gen.new_label() body_label code_gen.new_label() end_label code_gen.new_label() # 循环开始 code_gen.emit(label, start_label, None, None) # 生成条件代码 cond_temp self.translate_condition(cond_node, symbol_table, code_gen) # 条件跳转 code_gen.emit(if_false, cond_temp, end_label, None) # 生成循环体代码 code_gen.emit(label, body_label, None, None) self.translate_statement(body_node, symbol_table, code_gen) # 跳回循环开始 code_gen.emit(goto, start_label, None, None) # 结束标签 code_gen.emit(label, end_label, None, None)4.3 布尔表达式翻译布尔表达式需要特殊处理以支持短路求值def translate_condition(self, node, symbol_table, code_gen): if node.token.type in (TokenType.TRUE, TokenType.FALSE): temp code_gen.new_temp() code_gen.emit(, node.token.value.lower(), None, temp) return temp # 关系表达式 if len(node.children) 3: # E1 relop E2 left self.translate_expression(node.children[0], symbol_table, code_gen) right self.translate_expression(node.children[2], symbol_table, code_gen) op node.children[1].token.type.value result code_gen.new_temp() code_gen.emit(op, left, right, result) return result # 逻辑运算 if node.children[1].token.type TokenType.OR: return self.translate_or(node, symbol_table, code_gen) elif node.children[1].token.type TokenType.AND: return self.translate_and(node, symbol_table, code_gen) raise Exception(Unsupported condition type)5. 完整示例与测试让我们通过一个完整示例演示整个翻译过程# 示例源代码 source { int[3][5] arr; int i 2; int j 3; arr[i][j] 10; if (i j) { arr[i][j] arr[i][j] 1; } else { arr[i][j] arr[i][j] - 1; } while (i 0) { i i - 1; } } # 初始化各组件 lexer Lexer(source) parser Parser(lexer) symbol_table SymbolTable() code_gen ThreeAddressCodeGenerator() type_system TypeSystem() # 注册数组类型 symbol_table.add_symbol(arr, { kind: array, size: 3, element_type: { kind: array, size: 5, element_type: int } }) # 解析和翻译 ast parser.parse() translator Translator(type_system) translator.translate(ast, symbol_table, code_gen) # 输出生成的三地址码 print(Generated Three-Address Code:) code_gen.print_code()运行上述代码将输出类似以下的三地址码0: 2 i 1: 3 j 2: * i, 20 t0 3: * j, 4 t1 4: t0, t1 t2 5: arr_base, t2 t3 6: 10 t4 7: store t3, t4 8: i, j t5 9: if_false t5 L0 10: * i, 20 t6 11: * j, 4 t7 12: t6, t7 t8 13: arr_base, t8 t9 14: load t9 t10 15: t10, 1 t11 16: store t9, t11 17: goto L1 18: label L0 19: * i, 20 t12 20: * j, 4 t13 21: t12, t13 t14 22: arr_base, t14 t15 23: load t15 t16 24: - t16, 1 t17 25: store t15, t17 26: label L1 27: label L2 28: i, 0 t18 29: if_false t18 L3 30: - i, 1 t19 31: t19 i 32: goto L2 33: label L3这个完整的Python实现展示了编译器前端如何将高级语言结构转换为三地址码。通过这个项目你不仅深入理解了编译原理的核心概念还获得了可扩展的代码框架可以继续添加更多语言特性支持。
