compiler-construction - 数据流分析和抽象解释有什么区别

Question

数据流分析和抽象解释之间有什么区别，它们是否用于相同的目的？这两者相对于彼此有什么优点和缺点。

Answer 1

简而言之，它们属于不同的类别。这就像比较衣服和裤子。

抽象解释是一个使用抽象域和抽象传递函数形式化定点计算的框架。抽象解释保证了如果满足某些条件，则应该在有限步中找到不动点（详情：http ://www.di.ens.fr/~cousot/COUSOTpapers/POPL77.shtml ）。抽象解释的伟大来自于扩大和缩小。由于它们，抽象解释可以计算无限域上的不动点。

IMO，数据流分析只是抽象解释的一个例子。由于数据流分析使用的大多数具体域都是有限的，因此您甚至不需要扩大和缩小。

Answer 2

我不确定这里的任何答案是否真正解决了原始问题的意图，这似乎是在寻求直观而非技术性的解释。数据流分析涉及在给定位置获取某些信息的价值。“信息”的示例是哪些定义到达给定位置，哪些变量在给定位置存在，哪些表达式在给定位置是常数等。数据流框架通常要求值域形成有限格，即传递函数是单调的（传递函数决定了信息如何从块的入口传播到出口），所有这些都是为了能够计算数据流值的定点。它用于编译器。

抽象解释 (AI) OTOH 旨在构建语言的抽象解释器。目标是确定“这段代码计算什么？让我们尝试从抽象意义上回答这个问题”。例如，如果计算返回某个索引变量 i 的值，AI 可能会计算 i 的范围，这样您就可以回答是否存在边界违规或其他问题。所以抽象值的域略有不同，它可能是范围域、多面体域等。因此，人工智能对数据流设置了不同的约束：具体域和抽象域通常需要通过称为 galois 连接的东西相关联，它将具体值集与抽象值相关联。因为所使用的域不需要是有限的，人工智能不会总是在没有干预的情况下收敛，以扩大/缩小操作的形式。人工智能用于形式验证工具。他们都有共同的愿望，希望函数迭代收敛，但仅此而已。因此，如果您想知道某个位置某物的价值，请使用数据流分析；如果您想知道程序抽象计算的内容，请使用 AI。

数据流和人工智能可以一起使用。例如，反汇编工具 Jakstab 将两者结合起来 - 数据流用于确定间接跳转目标的值（即，新计算的值将被加载的 PC 的值），而 AI 用于抽象地评估一段二进制代码.

Answer 3

它归结为“效率与准确性”。

数据流分析试图合并路径数据，而不是抽象解释。抽象解释遍历所有路径，保持数据值抽象。