Get Control flow graph from Abstract Syntax Tree
我有一个从ANTLR Parser Generator for Java派生的AST。 我想做的是以某种方式构造源代码的控制流程图，其中每个语句或表达式都是唯一的Node。 我知道此标识必须具有递归性，我想知道您建议的最佳选择是什么，以及ANTLR是否具有可以用于此工作的工具集。 编辑-我主要关心的是从AST获得控制流程图(CFG)。 这样我就可以得到源代码的树形表示。 为了明确起见，源代码和实现语言都是Java。 通常，CFG是在较低级别的表示形式(例如JVM字节码)上计算的。几年前有人对这种事情做了论文。那里可能描述了一种有用的方法来获取该表示形式。
由于您的源语言和目标语言是相同的，因此没有代码生成步骤-您已经完成了！但是，现在您可以开始使用AST了。在AST的每个节点上，您都必须问自己：这是否是"跳跃"指令？方法调用和if语句是跳转指令的示例。循环构造(如 首先，将每个Java语句与CFG中的一个节点以及一个入口和出口节点相关联。作为第一近似，走树并： 这将为您提供某种CFG。在第2步中，该过程有些繁琐，因为所调用的方法可以在库中声明，而不是在AST的其他地方声明-如果是这样，则不要在表示该条目的特殊节点上占优势或占优势库方法。 这有意义吗？
产生一个完全考虑所有语言的完整控制流程图
如果您仔细检查大多数语言，它们也会
也许您只想要控制流的抽象
无论哪种情况(简单CFG或完整CFG)，您都需要使用AST，
对于Java(或C)的完整语言语义而言，做到这一点相当 根据一些评论，听起来OP确实想进行代码生成-将AST转换为基于基本块和跳转点的较低级指令序列。 代码生成是非常特定于语言的，并且在此主题中进行了大量工作。在进行代码生成之前，您需要了解目标语言-无论是汇编语言还是其他某种高级语言。一旦确定了这一点，您只需要遍历AST并生成在AST中实现代码的指令序列。 (我说这很简单，但是可能很难-很难一概而论，因为此处的注意事项是特定于语言的。) 您选择用于代码生成的表示形式将隐式或显式包含控制流图。如果您的目标语言相当低级(接近汇编语言)，则控制流图应该相对容易提取。 (如果需要进一步说明，请发表评论。) 我认为我无法以您可能正在寻找的方式回答您的问题，因为我不知道在ANTLR中以任何方式生成带有或不带有AST的CFG。但是，简而言之，您将使用ANTLR生成的内容来生成单独的Java程序来生成CFG。您将利用ANTLR生成的语法树作为输入，以在自己创建的单独Java程序中生成CFG。从本质上讲，这时您正在构建编译器。您的"编译器"和JVM之间的区别在于，您的输出是程序如何分支其各种执行路径的可视化表示(CFG)，而JVM / Java编译器生成了在真实机器(CPU)上执行的代码。 打个比方，如果有人坐下来写书(例如，用英语)，句子中使用的单个单词是计算机语言的令牌，句子的形成方式类似于上下文无关的语法表示有效的计算机代码，而段落整本小说都以类似的方式讲述一个故事，即语义分析/编译器/ CFG可能会生成/表示逻辑上有效的程序，这些程序实际上在做有用的事情，或多或少没有逻辑错误。换句话说，一旦您克服了有效语法(正确的句子结构)的问题，任何人都可以在页面上写下一堆句子，但是只有某些句子组合才能产生出确实可以起到作用的文本(讲述一个故事)。 您要问的是最后一部分-如何进行语法树转换和解释AST在逻辑上的实际作用。当然，您需要为每种语言构建一个"编译器"。拥有正确的语法并不能告诉您程序的功能-只是从语法角度来看程序是正确的。 Linter和语法突出显示器以及IDE都是基于这样的想法构建的，即试图使难题的最后一部分对人类来说变得更容易，更有效。 过去完成此操作时，我使用了graphviz(尤其是点工具)来生成图形。我通过在编译时实际遍历控制流图来创建点输入文件。 图的布局是一个难题，graphviz做得很好。它可以输出为ps，pdf和各种图像格式，并且布局通常很直观。我强烈推荐它。 您是否尝试过ANTLR Studio？它不会生成孔AST图，但是对于回顾来说，它已经非常有用。 |
