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

我有一个源自ANTLR Parser Generator for Java的AST.我想要做的是以某种方式构建源代码的控制流图,其中每个语句或表达式是唯一的节点.我知道必须有一些这种识别的递归,我想知道你会建议什么是最好的选择,如果ANTLR有一个工具集我可以用于这项工作.干杯,克里斯

编辑 - 我主要关心的是从AST获得控制流图(CFG).这样我就可以获得源代码的树形表示.为了澄清,源代码和实现语言都是Java.

通常,CFG是在较低级别的表示(例如JVM字节码)上计算的.几年前有人就此类事做过论文.在那里可能有一种有用的方式来描述如何获得该表示.

由于源语言和目标语言相同,因此没有代码生成步骤 - 您已经完成了!但是,现在你可以走AST了.在AST的每个节点,你必须问自己:这是一个"跳跃"指令吗？方法调用和if语句是跳转指令的示例.循环结构(例如for和while)也是如此.加法和乘法等指令不跳转.

首先将每个java语句与CFG中的节点以及入口和出口节点相关联.作为第一个近似,走树和:

如果当前语句是方法调用,请确定该方法调用的相应主体的入口节点的位置,并使边缘从当前语句指向该入口节点.如果语句是方法返回,则枚举可以调用它的位置并为其添加边.

对于每个非跳转语句,在它与下一个语句之间建立一个优势.

这会给你一些 CFG.在步骤2中,该过程略显毛茸茸,因为调用的方法可以在库中声明,而不是在AST中的其他地方声明 - 如果是这样,要么不为表示该条目的特殊节点创建边缘或边缘库方法.

这有意义吗？

生成一个真正考虑到所有语言问题的完整控制流图表比看起来更难.你不仅必须确定看起来像"基本块"的东西,而且你必须识别函数调用(有点容易,但识别目标可能更难),其中幕后操作如类初始化器可以发生.并且担心可能发生异常的点以及如果发生异常则控制发生的地方.

如果仔细检查大多数语言,他们也会明确表达式中计算的评估顺序,如果你在表达式中有两个副作用,这就很重要; 控制流应反映顺序(或非顺序,如果未定义).

也许你只想要一个具有基本块和条件的控制流的抽象.这显然有点容易.

在任何一种情况下(简单的CFG或完整的CFG),您需要在每个点上都参与可能的控制流目标(例如,对于大多数情况,例如IF语句,有两个流目标:THEN和ELSE条款).在每个节点处,将该节点链接到适当的控制流目标,可能替换流目标(例如,当您遇到IF时).

为Java(或C)的完整语言语义执行此操作是相当多的工作.您可能只想使用一种计算现成的工具.请参阅http://www.semanticdesigns.com/Products/DMS/FlowAnalysis.html ,了解这些工具的真实情况.