从DAG到三地址码：手把手图解龙书第六章核心习题（附完整代码）

从DAG到三地址码图解龙书编译原理核心习题实战指南编译原理作为计算机科学的基石课程常常让学习者感到抽象难懂。Alfred V. Aho等编著的《编译原理》俗称龙书第六章关于中间代码生成的讲解尤其是DAG构造与三地址码转换部分往往成为理解过程中的关键难点。本文将以可视化方式拆解这一核心章节通过分步图解完整代码示例带您亲手实现从表达式到DAG再到三地址码的完整转换过程。1. 理解DAG表达式优化的可视化基石有向无环图(DAG)是编译器优化阶段的重要数据结构它能有效识别表达式中的公共子表达式。让我们通过具体案例理解其构造原理。1.1 DAG构造基础步骤以表达式((xy)-((xy)*(x-y)))((xy)*(x-y))为例词法分析首先识别出所有原子操作数和运算符操作数x, y运算符, -, *构建初始节点id(x) id(y) \ / (1)逐步扩展构建x-y子表达式-(2) / \ id(x) id(y)合并公共子表达式(xy)*(3) / \ (1) -(2)完整DAG结构(5) / \ -(4) *(3) | / \ (1) id(x) id(y) / \ id(x) id(y)1.2 值编码实战值编码(value numbering)是DAG的紧凑表示方法对上述DAG进行编码# 值编码表结构 value_numbering [ {op: id, left: x, right: None}, # 节点0 {op: id, left: y, right: None}, # 节点1 {op: , left: 0, right: 1}, # 节点2 {op: -, left: 0, right: 1}, # 节点3 {op: *, left: 2, right: 3}, # 节点4 {op: -, left: 2, right: 4}, # 节点5 {op: , left: 5, right: 4} # 节点6 ]提示值编码表中操作数指向其节点编号运算符记录操作类型和操作数引用关系。2. 三地址码生成从抽象到可执行三地址码是编译器常用的中间表示形式具有接近机器码的特点。我们通过实例演示转换过程。2.1 基本转换规则表达式类型三地址码模式示例二元运算t1 arg1 op arg2t1 x y一元运算t1 op arg1t1 -y数组访问t1 arr[index]t1 a[i]赋值target sourcex t32.2 完整转换案例将DAG节点转换为三地址码序列def generate_three_address(dag): code [] temp_counter 0 def walk(node): nonlocal temp_counter if isinstance(node, int): # 已处理过的节点 return ft{node} left_ref walk(node[left]) right_ref walk(node[right]) if node[right] else None if node[op] id: return node[left] # 直接返回变量名 temp_var ft{temp_counter} temp_counter 1 if node[op] in [, -, *, /]: code.append(f{temp_var} {left_ref} {node[op]} {right_ref}) elif node[op] uminus: code.append(f{temp_var} -{left_ref}) return temp_var result walk(dag[-1]) # 从根节点开始 return code执行上述函数将生成t0 x y t1 x - y t2 t0 * t1 t3 t0 - t2 t4 t3 t23. 进阶应用控制结构与数组处理3.1 条件语句的三地址码转换以if (ab cd) x1为例// 三地址码实现 100: if a ! b goto 104 102: if c ! d goto 104 103: x 1 104:对应的语法制导翻译规则def gen_if_condition(condition, true_label, false_label): code [] if condition[op] : mid_label new_label() code gen_if_condition(condition[left], mid_label, false_label) code.append(f{mid_label}:) code gen_if_condition(condition[right], true_label, false_label) elif condition[op] ||: # 类似处理逻辑相反 pass else: code.append(fif {condition[left]} {condition[op]} {condition[right]} goto {true_label}) code.append(fgoto {false_label}) return code3.2 数组访问的地址计算多维数组访问需要计算元素偏移量。以按行存储的2D数组A[i][j]为例参数说明base_addr数组起始地址row_size每行元素数elem_size单个元素字节数i, j下标索引计算公式offset (i * row_size j) * elem_size address base_addr offset对应的三地址码t1 i * 20 # 假设row_size20 t2 t1 j t3 t2 * 4 # 假设elem_size4 t4 A[t3] # 最终访问4. 完整工具链实现4.1 Python实现DAG构造器class DAGNode: def __init__(self, op, leftNone, rightNone): self.op op self.left left self.right right self.id id(self) class DAGBuilder: def __init__(self): self.node_map {} def build(self, expr): if isinstance(expr, int) or isinstance(expr, str): return self.get_node(id, expr) op expr[0] left self.build(expr[1]) right self.build(expr[2]) if len(expr) 2 else None return self.get_node(op, left, right) def get_node(self, op, left, rightNone): key (op, left.id if hasattr(left, id) else left, right.id if hasattr(right, id) else right) if key not in self.node_map: self.node_map[key] DAGNode(op, left, right) return self.node_map[key]4.2 可视化输出工具使用Graphviz生成DAG图示from graphviz import Digraph def visualize_dag(root): dot Digraph() visited set() def walk(node): if node.id in visited: return visited.add(node.id) if node.op id: dot.node(str(node.id), labelnode.left) else: dot.node(str(node.id), labelnode.op) walk(node.left) dot.edge(str(node.id), str(node.left.id)) if node.right: walk(node.right) dot.edge(str(node.id), str(node.right.id)) walk(root) return dot注意实际工程中需要考虑更多边界情况如类型检查、错误处理等。