15

我有一个从 ANTLR Parser Generator for Java 派生的 AST。我想做的是以某种方式构建源代码的控制流图，其中每个语句或表达式都是一个唯一的节点。我知道这个识别肯定有一些递归性，我想知道你会建议什么作为最佳选择，如果 ANTLR 有一个我可以用于这项工作的工具集。干杯，克里斯

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

4

6 回答 6

11

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

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

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

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

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

这有意义吗？

于 2008-09-18T15:30:36.680 回答
5

生成一个真正考虑到所有语言问题的完整控制流图比看起来更难。您不仅必须识别看似“基本块”的内容，还必须识别函数调用（有点容易，但识别目标可能更难），其中类初始化程序等幕后操作可以发生。并担心可能发生异常的点以及发生异常时控制的去向。

如果您仔细检查大多数语言，他们也会清楚表达式中计算的计算顺序，如果您在表达式中有两个副作用，这很重要；控制流应反映顺序（或非顺序，如果未定义）。

也许您只想要具有基本块和条件的控制流的抽象。这显然要容易一些。

在任何一种情况下（简单 CFG 或完整 CFG），您都需要遍历 AST，在每个点都引用可能的控制流目标（例如，对于大多数情况，例如 IF 语句，有两个流目标：THEN 和ELSE 子句）。在每个节点，将该节点链接到适当的控制流目标，可能会替换流目标（例如，当您遇到 IF 时）。

为 Java（或 C）的完整语言语义做到这一点需要做很多工作。您可能只想使用现成的计算此工具的工具。请参阅http://www.semanticdesigns.com/Products/DMS/FlowAnalysis.html 了解从我们的工具中出来的真正样子。

于 2009-06-17T08:46:18.827 回答
1

根据一些评论，听起来 OP 确实想要进行代码生成——将 AST 转换为基于基本块和跳转点的较低级别的指令序列。

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

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

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

于 2008-09-18T14:11:06.060 回答
-1

你试过ANTLR Studio吗？它不会生成空洞 AST 图，但对于复习来说，它已经很有帮助了。

于 2008-09-18T13:35:29.327 回答
-1

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

图形布局是一个难题，graphviz 做得很好。它可以输出为 ps、pdf 和各种图像格式，并且布局通常非常直观。我强烈推荐它。

于 2008-09-18T13:51:54.623 回答
-2

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

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

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

Linter、语法高亮器和 IDE 都是围绕着试图让这最后一块拼图成为人类更容易和更有效的任务的想法而构建的。

于 2018-08-31T03:15:16.063 回答