如何使用 antlr 生成 Java CFG(控制流图)? [英] How could I generate Java CFG(Control Flow Graph) using antlr?
问题描述
我正在尝试分析 Java 代码结构.
所以，我使用 ANTLRv3 和 java 语法代码生成了一个 Java 解析器和词法分析器...
但我不知道如何使用生成的解析器和词法分析器生成上下文流图.
我试图通过教程页面学习如何做到这一点，但教程页面已经消失了.
你能给我一个方法吗?或教程页面?
谢谢.
AFAIK，ANTLR 没有提供构建控制流图的具体帮助.
您可以通过遍历 AST 并收集操作(无条件语句)和条件(表达式节点控制条件)的知识，并根据该信息组装图形来自己构建一个.请注意，switch 语句是一种复合条件，需要作为一组决策来处理，或者是一个特殊的 N 路条件.
异常处理可能会改变您认为的无条件操作"；每个方法调用都有可能将控制流重定向到异常处理程序(或函数的出口)，您需要决定是否将这些包含在您的控制流图中.如果您想推理程序的作用(尤其是数据流)，您需要对这些进行建模.
您需要创建控制流节点(只是一种类)，它可以引用 AST 的各个部分(这是动作")和其他两个控制流节点(处理 if-then-else);这些退出中的这个作为真正退出"和虚假退出"或继续到"和陷阱到"退出.其子类将代表纯计算、IF 语句、TRY 块等.
Java 是一种纯粹的结构化"语言这一事实意味着您可以自下而上"构建控制流图；您可以在向上遍历叶子时构建一些控制流图，并在您爬树时组合来自孩子的控制流图.您需要做的是将到目前为止组装的控制流图(最初在叶子处为空)传递到树上，并引用该图中想要将控制权传递给异常处理程序的控制流节点列表.然后当你爬树时，扩展控制流图.
大部分工作发生在一个有条件的地方，比如一个 IF-THEN-ELSE 节点；在这种情况下，具有两组异常的两个控制流子图被传递到该节点.然后创建一个控制流节点来表示条件，将其动作设置为指向条件表达式，将其两个子节点设置为指向传入的两个子图，并将其异常集设置为异常集的并集.
子例程调用获取流节点，其操作是方法调用，退出到以下语句/子表达式，以及另一个最终指向 catch 子句的退出(未填充).将子程序调用节点添加到上来的异常列表中.
同样对待 THROW 语句，尽管它们没有下一步"动作.
当您遇到 TRY 构造时，生成一个条件节点，其操作指向 try 主体，一个出口指向 try 的结尾或 finally 子例程调用.最后，修补异常列表中的所有控制流节点以指向 catch 子句.
您需要将 catch 子句作为一系列 if 语句链接在一起.
您必须将finally"视为从 try 子句和各种 catch 子句调用的子例程调用.
I am trying to analyse Java code sturcture.
So, I generated a Java parser and lexer by using ANTLRv3 and java grammar code...
but I don't know how could I generate Context Flow Graph using the generated parser and lexer.
I tried to learn how to do this through tutorial page, but the tutorial page has already disappeared.
Could you give me a way how to do this? or tutorial page?
Thank you.
AFAIK, ANTLR provides no specific help in building a control flow graph.
You can build one yourself by walking the AST, and collecting knowledge of actions (unconditional statements) and conditions (expression nodes control conditionals), and assembling the graph from that information. Note that switch statements are a kind of compound conditional and need to be handled as a set of decisions, or a special N-way conditional.
Exception handling may change what you think of as "unconditional actions"; every method call has the potential to redirect control flow to the exception handler (or to the exit of the function) and you need to decide if you are going to include these in your control flow graph. If you want to reason about what the program does (especially dataflow) you will need to model these.
You will need to create control flow nodes (just a kind of class) that can refer to pieces of the AST ("this is the action") and to two other control flow nodes (to handle if-then-else); this of these exits as "true exit" and "false exit" or alternatively "continue to" and "trap to" exits. Subclasses of this will represent pure computation, IF statements, TRY blocks, etc.
The fact that Java is a pure "structured" langauge means you can build the control flow graph "bottom up"; you can build bits of the control flow graph as you traverse leaf-upwards, and combine control flow graphs from children as you climb the tree. What you need to do is pass a so-far-assembled control flow graph (initially empty at the leaves) up the tree with a reference to a list of control flow nodes in that graph that want to pass control to an exception handler. Then as you climb the tree, extend the control flow graph.
Most of the work happens at a conditional, such as an IF-THEN-ELSE node; in this case, two control flow subgraphs with two sets of exceptions are passed to that node. You then create a control flow node to represent the conditional, set its action to point to the conditional expression, set its two children to point to the two subgraphs passed in, and set its exception set to the union of the exception set.
Subroutine calls get flow nodes whose action is the method call, with an exit to the following statement/subexpression, and another exit (unfilled) that will eventually point to the catch clause. Add the subroutine call node to the list of exceptions passed up.
Treat THROW statment similarly, although they have have no "next" action.
When you encounter a TRY construct, generate a conditional node with the action pointing to the try body, one exit pointing to the end of try or to a finally subroutine call. Finally, patch all the control flow nodes in the exception list to point to the catch clause.
You'll need to chain the catch clauses together as a sequence of if statements.
You have to treat "finally" as a subroutine call, invoked from the try clause, and the various catch clauses.
这篇关于如何使用 antlr 生成 Java CFG(控制流图)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
