假设我有一种可以编写的编程语言: x = f(g(1), h(1)) 在这种情况下，有向无环图将像电子表格一样显示计算的依赖关系(假设非递归表达式):
1
| \
g h
\ /
f
这是一个简单的示例，但尝试在 DAG 中“压缩”更复杂的表达式会变得很有趣。这里的目标是根据依赖关系优化重新计算的次数。
有哪些算法和论文可以用来处理这个问题？
最佳答案
更具体一点，它是 Local Common Subexpression Elimination。 Dragon Book 中给出了一种算法, "6.1.2 构造 DAG 的值数法"
关于将有序树转换为有向无环图的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8117032/