algorithm - 将有序树转换为有向无环图的算法

Question

假设我有一种可以编写的编程语言： x = f(g(1), h(1)) 在这种情况下，有向无环图将显示计算的依赖关系，就像在电子表格中一样（假设非递归表达式）：

 1
| \
g  h
 \ /
  f

这是一个简单的示例，但尝试在 DAG 中“压缩”更复杂的表达式变得有趣。这里的目标是根据依赖关系优化重新计算的次数。

有哪些算法和论文可用于处理这个问题？

Answer 1

更具体一点，它是局部公共子表达式消除。Dragon Book中给出了一个算法，“6.1.2 The Value-Number Method for Constructing DAG's”

Answer 2

编译器作者将此问题称为通用子表达式消除。每本有价值的编译器教科书都涵盖了这个主题。

如果没有控制流，您应该能够做一些类似于hash consing的简单操作。