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

核心提示： DAG： 这个DAG的叶节点有2个，内部节点有2个，简单DAG生成算法的一个性质(2)， 对应到三地址代码，是： Three-address code代码t1 = a + bt2 = t1 + t1b) AST： DAG： 这个DAG的叶节点也是两个，等于是做过了自底而上的比较，实现起来很

DAG：

这个DAG的叶节点有2个，内部节点有2个。

对应到三地址代码，是：

Three-address code代码　　　

t1 = a + b
t2 = t1 + t1

b)

AST：

DAG：

这个DAG的叶节点也是两个，但内部节点却有3个，比a)的多一个。

对应到三地址代码，则是：

Three-address code代码　

t1 = a + b
t2 = t1 + a
t3 = t2 + b

问题是什么呢？习题里a)和b)的源码所代表的表达式的运算结果显然应该是一样的，但由于对应的AST的形状不同，导致生成的DAG也有所不同。

如果尝试对AST做等价变形然后再生成DAG，或许是可以选择出较优的版本，不过是否值得为了这个优化而使编译器变得复杂就是另一个问题了。对AST做了等价变形后，要比以某节点N1为根的子树与另一以N2为根的子树是否相同，就得专门写一个TreeComparer了。前面的简单算法是在生成节点的时候就做了比较，等于是做过了自底而上的比较，实现起来很简单。

要写个简单的解析器来生成上面的图十分简单。