从抽象语法树获取控制流程图

Question

我有一个源自 Java ANTLR Parser Generator 的 AST。我想要做的是以某种方式构建源代码的控制流图，其中每个语句或表达式都是一个唯一的节点。我知道这个识别一定有一些递归性，我想知道你会建议什么作为最好的选择，以及 ANTLR 是否有一个我可以用来完成这项工作的工具集。欢呼，克里斯

---

编辑 - 我主要关心的是从 AST 获取控制流图（CFG）。这样我就可以获得源的树表示。澄清一下，源代码和实现语言都是Java。

Answer 1

通常 CFG 是在较低级别的表示上计算的（例如JVM 字节码）。有人做到了 一篇论文 几年前就谈过这样的事情。其中可能描述了一种有用的方法来获取该表示。

由于您的源语言和目标语言相同，因此没有代码生成步骤 - 您已经完成了！然而，现在你可以走 AST 了。在 AST 的每个节点，你必须问自己：这是否是一个“跳跃”指令？方法调用和 if 语句是跳转指令的示例。循环结构也是如此（例如 for 和 while）。加法和乘法等指令是非跳转的。

首先将 CFG 中的每个 java 语句与一个节点相关联，以及一个入口和出口节点。作为第一个近似，遍历树并：

1. 如果当前语句是方法调用，则找出该方法调用的相应主体的入口节点在哪里，并创建一条从当前语句指向该入口节点的边。如果该语句是方法返回，则枚举可能调用它的位置并为其添加边缘。
2. 对于每个非跳跃语句，在它和下一个语句之间建立一条边。

这会给你 某种 CFG 的。该过程在步骤 2 中有点麻烦，因为调用的方法可能在库中声明，而不是在 AST 的其他地方声明——如果是这样，要么不创建边，要么创建到表示该条目的特殊节点的边库方法。

这有道理吗？

Answer 2

产生一个真正考虑所有语言问题的完整控制流程图比看起来要困难。您不仅必须识别似乎是“基本块”的内容，而且还必须识别函数调用（很容易，而且可以识别 目标 可能会更难），诸如类初始化器之类的幕后操作可能会发生。并担心如果确实发生异常，可能会发生例外以及控制的点。

如果您仔细检查大多数语言，他们还将清楚地对表达式计算评估的订购，这很重要，如果您在表达式中有两种副作用。控制流应该反映顺序（或未定义的非订单）。

也许您只希望具有基本块和条件的控制流的抽象。显然有点容易。

在任何情况下（简单的CFG或完整CFG），您都需要在每个点上行走AST，每个点都有参考可能的控制流动目标（例如，在大多数情况下，例如IF语句，有两个流动目标：THEN 和 ELSE 子句）。在每个节点上，将节点链接到适当的控制流动目标，可能会替换流动目标（例如，遇到if时）。

为此，对于Java（或C）的完整语言语义是很多工作。您可能只需使用计算此货架的工具即可。看 http://www.semanticdesigns.com/Products/DMS/FlowAnalysis.html通过我们的工具，了解它的真实面貌。

Answer 3

根据一些评论，听起来OP真的想做 代码生成 -- 将 AST 转换为基于基本块和跳转点的较低级指令序列。

代码生成是非常特定于语言的，并且已经在这个主题上投入了大量的工作。在进行代码生成之前，您需要了解您的 目标语言 ——无论是汇编语言还是其他高级语言。一旦确定了这一点，您只需遍历 AST 并生成一系列指令来实现 AST 中的代码。（我说这很简单，但可能很难——很难概括，因为这里的考虑因素是特定于语言的。）

您选择用于代码生成的表示形式将隐式或显式包含控制流图。如果您的目标语言相当低级（接近汇编语言），那么控制流图应该相对容易提取。

（如果您需要更多说明，请发表评论。）

Answer 4

你有没有尝试过 安特鲁工作室？它不会生成空洞 AST 图，但对于回顾来说，它已经非常有帮助了。

Answer 5

当我过去这样做时，我用过 图形可视化, ，特别是点工具，用于生成图表。我通过在编译时实际遍历控制流图来创建点输入文件。

图形布局是 难题, ，而 graphviz 做得非常出色。它可以输出为 ps、pdf 和各种图像格式，并且布局通常看起来非常直观。我强烈推荐它。

Answer 6

我认为我无法以您可能正在寻找的方式回答您的问题，因为我不知道 ANTLR 中有什么方法可以生成带有或不带有 AST 的 CFG。但是，简而言之，您将使用 ANTLR 生成的内容来生成一个单独的 Java 程序来生成 CFG。您可以利用 ANTLR 生成的语法树作为输入，在您自己创建的单独 Java 程序中生成 CFG。此时，您实质上正在构建一个编译器。“编译器”和 JVM 之间的区别在于，您的输出是程序如何分支其各种执行路径的可视化表示 (CFG)，而 JVM/Java 编译器生成在真实机器 (CPU) 上执行的代码。

打个比方，如果有人坐下来写一本书（例如英语），句子中使用的各个单词就是计算机语言的令牌，句子的形成方式与上下文无关语法表达有效计算机代码的方式类似，而段落整部小说以类似的方式讲述一个故事，语义分析/编译器/CFG 可能会产生/表示逻辑上有效的程序，这些程序实际上做了一些有用的事情，并且或多或少没有逻辑错误。换句话说，一旦克服了有效语法（正确的句子结构）的问题，任何人都可以在一页上写一堆句子，但只有某些句子组合才能产生实际做某事（讲故事）的文本。

您要问的是最后一部分 - 如何获取语法树并转换或解释 AST 实际在逻辑上所做的事情。当然，您需要为您想要执行此操作的每种语言构建一个“编译器”。拥有正确的语法并不能告诉你 什么 程序确实如此——只是从语法的角度来看程序是正确的。

Linters、语法荧光笔和 IDE 都是围绕着这样的想法构建的：试图让最后一块拼图对人类来说变得更容易、更高效。