使用Java从具有访问者模式的AST构建控制流图 [英] Building a control-flow graph from an AST with a visitor pattern using Java

问题描述

我正在试图弄清楚如何实现我的LEParserCfgVisitor类，以便从已经使用JavaCC生成的Abstract-Syntax-Tree构建控制流图。我知道有一些工具已经存在，但我正在尝试为我的编译器最终做准备。

I'm trying to figure out how to implement my LEParserCfgVisitor class as to build a control-flow graph from an Abstract-Syntax-Tree already generated with JavaCC. I know there are tools that already exist, but I'm trying to do it in preparation for my Compilers final.

我知道我需要一个保持数据结构的数据结构内存中的图形，我希望能够在每个节点中保留IN，OUT，GEN，KILL等属性，以便以后能够进行控制流分析。

I know I need to have a data structure that keeps the graph in memory, and I want to be able to keep attributes like IN, OUT, GEN, KILL in each node as to be able to do a control-flow analysis later on.

我的主要问题是我还没弄明白如何将不同的块连接在一起，因为根据它们的性质在每个块之间有正确的边缘：分支，循环等。换句话说，我没有'找到了一个可以帮助我建立访问者的显式算法。

My main problem is that I haven't figured out how to connect the different blocks together, as to have the right edge between each blocks depending on their nature: branch, loops, etc. In other words, I haven't found an explicit algorithm that could help me build my visitor.

这是我的空访客。你可以看到它适用于基本的语言表达式，比如if，while和基本操作（+， - ，x，^，...）

Here is my empty Visitor. You can see it works on basic langage expressions, like if, while and basic operations (+,-,x,^,...)

public class LEParserCfgVisitor implements LEParserVisitor
{
  public Object visit(SimpleNode node, Object data) { return data; }

  public Object visit(ASTProgram node, Object data) { 
    data = node.childrenAccept(this, data);
    return data; 
  }

  public Object visit(ASTBlock node, Object data) {
  }

  public Object visit(ASTStmt node, Object data) {
  }

  public Object visit(ASTAssignStmt node, Object data) {
  }

  public Object visit(ASTIOStmt node, Object data) { 
  }

  public Object visit(ASTIfStmt node, Object data) {
  }

  public Object visit(ASTWhileStmt node, Object data) {
  }

  public Object visit(ASTExpr node, Object data) { 
  }

  public Object visit(ASTAddExpr node, Object data) {
  }

  public Object visit(ASTFactExpr node, Object data) {
  }

  public Object visit(ASTMultExpr node, Object data) { 
  }

  public Object visit(ASTPowerExpr node, Object data) {  
  }

  public Object visit(ASTUnaryExpr node, Object data) { 
  }

  public Object visit(ASTBasicExpr node, Object data) {
  }

  public Object visit(ASTFctExpr node, Object data) {
  }

  public Object visit(ASTRealValue node, Object data) { 
  }

  public Object visit(ASTIntValue node, Object data) { 
  }

  public Object visit(ASTIdentifier node, Object data) {
  }
}

任何人都可以帮忙吗？

Can anyone give me a hand?

谢谢！

推荐答案

关于数据流的推理（gen / kill / use / def）你首先需要一个控制流图。

To do reasoning about data flows (gen/kill/use/def) you first need a control flow graph.

要构建一个，在每个树节点（例如，在每个特定节点访问者内），构建节点代表的图形片段;将该图的入口点弧和出口弧传递给父访客。纯粹独立的游客将无法工作，因为您需要将信息传递给父母。 [您可以向访问者设置的每个节点添加进入/退出弧形槽，并由父级进行检查。]

To construct one, at each tree node (e.g., inside each specific node visitor), build the piece of the graph that the node represents; pass the entry point arc and the exit arc for that graph to the parent "visitor". Purely independent vistors won't work because you need to pass information to parents. [You could add entry/exit arcs slots to each node that are set by the visitor, and inspected by the parent.]

某些节点（例如，assignmentstmt） ）将制作一个动作节点，参考AST进行分配（在流程图中考虑矩形）;没有任何子图弧需要担心。一些节点（例如，用于if）将制造条件分支节点（引用条件表达式的AST节点），（在流程图中认为菱形），流连接节点，并组成结构化的（如果 - 那么 - 其他）子图通过将该条件分支节点与then和else子句的子图（由当时的入口和出口弧表示）与流连接节点组合在一起。然后，您将入口和出口弧传递给此复合子图到父级。

Some nodes (e.g., for "assignmentstmt") will manufacture an action node referring to the AST for the assignment (think "rectangle" in a flowchart); there aren't any subgraph arcs to worry about. Some nodes (e.g., for "if") will manufacture a conditional branch node (referencing the AST node for the condition expression), (think "diamond" in a flowchart), an flow-join node, and compose a structured (if-then-else) subgraph by combining that conditional branch node with the subgraphs for the then and else clauses (represented just by then entry and exit arcs), with the flow join-node. You then pass the entry and exit arcs to this compound subgraph to the parent.

此方案适用于结构化控制流程。非结构化控制流（例如，GOTO x）需要一些有趣的调整，例如，首先构建图形的结构化部分，将生成的控制流与标签相关联，然后返回并修改GOTO动作以使弧形成为相关联的标签。

This scheme works with structured control flow. Unstructured control flow (e.g, "GOTO x") requires some funny adjustments, e.g, first building the structured part of the graph, associating generated control flow with labels, and then going back and patcing the GOTO actions to have an arc to the associated label.

请记住担心异常;它们也是GOTO，但通常在结构化控制流程图中更高一点。这些通常是通过将最里面的异常处理程序节点向下传递树来处理的;现在，您的访问者需要查看 up 树以查看最新的异常处理程序。

Remember to worry about exceptions; they are GOTOs too, but generally to a point higher in the structured control flow graph. These are often handled by passing the innermost exception handler node down the tree; now your visitors need to look up the tree to see that most recent exception handler.

使用生成的游标的更复杂的方案称为http://en.wikipedia.org/wiki/Attribute_grammar>归属语法，通过上下传递感兴趣的值（在这种情况下，进入/退出/异常流弧），基本上为您管理所有信息流树作为参数和结果。你需要一个属性语法工具来完成这个;你仍然需要指定节点构建逻辑。我们使用属性语法，基本上是上面的控制流程图构造我们的 DMS Software Reengineering Toolkit ，为多种语言提供通用控制流分析功能。

A more sophisticated scheme that uses generated vistors is called an http://en.wikipedia.org/wiki/Attribute_grammar">attribute grammar, which essentially manages all the information flows for you, by passing the values of interest (in this case, entry/exit/exception flow arcs) up and down the tree as parameters and results. You need an attribute grammar tool to do this; and you still have to specify node-building logic. We use attribute grammars and essentially the above control flow graph construction by pieces with our DMS Software Reengineering Toolkit to provide generic control flow analysis facilities for many languages.

获得控制流图后，您可以通过遍历控制流gra来实现所描述类型的数据流求解器pH值。您需要重新访问CF节点指向的AST来收集原始使用/原始def信息。

Once you have the control flow graph, then you can implement a data flow solver of the type you describe by walking over the control flow graph. You'll need to re-visit the ASTs that the CF nodes point-to to collect the raw use/raw def information.

如果您的语言只有 结构化控制流，然后您可以使用ASTs节点来表示控制流节点，并直接计算数据流。

If your langauge has only structured control flow, then you can use the ASTs nodes to represent the control flow nodes, and compute the data flow directly.

有关一般流程的更多详细信息，请访问此处。

More details on the general process can be found here.

这篇关于使用Java从具有访问者模式的AST构建控制流图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！