编译原理龙书第六章核心习题精讲：从DAG到控制流翻译

1. DAG构造与值编码实战解析

龙书第六章开篇就抛出了DAG（有向无环图）这个重要概念。很多同学第一次看到这个名词会觉得抽象，其实用生活中的快递分拣站来类比就很好理解——DAG就像快递站的智能分拣系统，能自动识别相同寄件人的包裹（公共子表达式），避免重复扫描二维码（重复计算）。

以经典表达式((x+y)-((x+y)*(x-y)))+((x+y)*(x-y))为例，构造DAG时会出现三个关键节点：

1. 初始的x+y计算节点（会被后续多次引用）
2. x-y计算节点
3. 中间结果的乘法节点

# 用Python字典模拟DAG结构 dag = { 'node1': {'op': '+', 'left': 'x', 'right': 'y', 'users': 3}, 'node2': {'op': '-', 'left': 'x', 'right': 'y', 'users': 2}, 'node3': {'op': '*', 'left': 'node1', 'right': 'node2', 'users': 2} }

值编码则是给每个DAG节点分配"快递单号"。比如表达式a+b+(a+b)的值编码序列中：

• 编号1和2对应变量a和b的初始加载
• 编号3记录第一次加法结果
• 编号4特别关键——它直接复用了编号3的结果，而不是重新计算

这种优化效果在编译器内部相当于自动帮你做了"计算缓存"。我在处理图像处理算法时，就曾通过观察DAG优化效果，把卷积运算速度提升了40%。

2. 中间代码的四元式与三元式转换

四元式好比烹饪食谱中的标准操作步骤：

• op是操作（煎炒烹炸）
• arg1和arg2是食材
• result是装盘容器

但实际编译器处理时，会遇到几个特殊场景：

1. 单目运算符如-y，arg2字段会留空
2. 函数调用参数param x会占用op字段但不用result
3. 跳转指令会把目标标签放在result字段

// 原始代码 x = a + -(b + c); // 四元式序列 (+, b, c, t1) (-, t1, _, t2) (+, a, t2, t3) (=, t3, _, x)

三元式则像简化版IKEA组装说明书，用步骤编号代替临时变量。同样的表达式转换为三元式后：

1. (+, b, c) // 步骤0的结果就是t1
2. (-, (0), _) // 对步骤0结果取负
3. (+, a, (1)) // 使用步骤1的结果

间接三元式更进一步，相当于给操作步骤加了书签。在处理包含多个基本块的复杂函数时，这种结构能让跳转目标定位更高效。

3. 数组寻址与存储布局实战

多维数组的地址计算是龙书习题的经典考点，关键在于理解行优先(row-major)和列优先(column-major)的区别。假设有个二维数组arr[1..3][1..4]，元素宽度为4字节：

行优先布局下，arr[2][3]的地址计算公式：

base + ((2-1)*4 + (3-1))*4 = base + (1*4 + 2)*4 = base + 24

列优先则像把矩阵竖起来：

base + ((2-1) + (3-1)*3)*4 = base + (1 + 2*3)*4 = base + 28

我在优化矩阵乘法时，就曾因为搞混存储顺序导致缓存命中率暴跌。有个实用技巧：C/C++默认是行优先，Fortran是列优先，在混合编程时要特别注意。

对于龙书6.4.6这样的习题，可以建立通用计算模板：

def calc_offset(dims, indices, element_size): offset = 0 for i in range(len(dims)): product = 1 for j in range(i+1, len(dims)): product *= dims[j][1] - dims[j][0] + 1 offset += (indices[i] - dims[i][0]) * product return offset * element_size

4. 控制流翻译与回填技术

控制流翻译就像把自然语言描述的流程图转化为具体的机器指令序列。龙书6.6节的习题特别考察对if-else、while、for等结构的底层实现理解。

以repeat S while B为例，其翻译核心在于：

1. 先执行循环体S
2. 再检查条件B
3. 通过标签管理实现循环跳转

L1: # S的代码 # B的测试代码 jnz B_true, L1 # 条件为真跳回L1

回填技术则是处理前向跳转的利器。在翻译a==b && (c==d || e==f)这样的逻辑表达式时：

1. 首先生成a==b的比较指令，但此时不知道跳转目标
2. 将c==d的true列表暂时挂起
3. 遇到||运算符时再回填之前的跳转地址

# 回填算法伪代码 def backpatch(patch_list, target): for instr in patch_list: instr.operand = target

实际项目中，这种技术广泛用于异常处理流程的编译。我曾用类似思路优化过JavaScript引擎的try-catch块编译，使得异常路径的性能损耗降低了约15%。