简单DAG生成算法的一个性质

“简单”嘛说明肯定有更麻烦、效果可能更好的办法。这里提到的算法就是这样。

龙书第二版363页习题6.1.2有点意思。题目如下：

Compilers - Principles, Techniques, & Tools, Second Edition 写道

Exercise 6.1.2: Construct the DAG and identify the value numbers for the subexpressions of the following expressions, assuming + associates from the left.

a) a + b + (a + b)

b) a + b + a + b

c) a + a + ((a + a + a + (a + a + a + a))

（c)原本在书上就是这么写的……很明显括号没配对是吧 = =

勘误表里没提到这项。莫非是国内的影印版的问题？我无法确认。正确的代码应该是：

a + a + (a + a + a + (a + a + a + a))

这样才对）

如何从表达式的源码生成DAG（Directed Acyclic Graph，有向无环图）呢？龙书在前面给出了一个算法：在解析源码并生成语法树的算法的基础上，如果在创建新的节点前先检查是否已存在相同的节点，若存在则返回已有节点，否则返回新建的节点。

假设DAG的节点是<op,left,right>形式的三元组，其中op是表示运算符的枚举类型的值，left和right是表示子节点的引用。那么在检查是否已存在相同的节点时，只需要分别检查op、left和right是否相同即可。

但是这个简单的算法很明显不保证生成最优（节点数最少）的DAG。以习题6.1.2中的a)和b)为例：

a)

AST：