java - 使用 Java 从具有访问者模式的 AST 构建控制流图

Question

我正在尝试弄清楚如何实现我的 LEParserCfgVisitor 类，以便从已经使用 JavaCC 生成的抽象语法树构建控制流图。我知道有些工具已经存在，但我正在努力为我的编译器期末考试做准备。

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

我的主要问题是我还没有弄清楚如何将不同的 block 连接在一起，如何根据它们的性质在每个 block 之间设置正确的边缘:分支、循环等。换句话说，我还没有找到了可以帮助我构建访问者的显式算法。

这是我的空访客。您可以看到它适用于基本语言表达式，例如 if、while 和基本操作 (+,-,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) {
  }
}

谁能帮帮我？

谢谢!

Answer 1

要对数据流进行推理(gen/kill/use/def)，您首先需要一个控制流图。

要构建一个，在每个树节点(例如，在每个特定节点访问者内部)，构建该节点代表的图 block ；将该图的入口点弧和导出弧传递给父“访问者”。纯粹的独立访客是行不通的，因为您需要将信息传递给 parent 。 [您可以向访问者设置并由父级检查的每个节点添加进入/退出弧槽。]

一些节点(例如，对于“assignmentstmt”)将制造一个引用 AST 的 Action 节点以进行分配(想想流程图中的“矩形”)；无需担心任何子图弧。一些节点(例如，对于“if”)将制造一个条件分支节点(引用条件表达式的 AST 节点)，(想想流程图中的“钻石”)，一个流连接节点，并组成一个结构化的(if- then-else) 子图通过将该条件分支节点与 then 和 else 子句的子图(仅由 then 入口和导出弧表示)与流连接节点相结合。然后将进入和退出弧传递给这个复合子图给父级。

此方案适用于结构化控制流。非结构化控制流(例如，“GOTO x”)需要一些有趣的调整，例如，首先构建图形的结构化部分，将生成的控制流与标签相关联，然后返回并调整 GOTO Action 以具有指向相关联的弧标签。

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

使用生成的访问者的更复杂的方案称为 http://en.wikipedia.org/wiki/Attribute_grammar">属性语法，它通过传递感兴趣的值(在在这种情况下，进入/退出/异常流弧)作为参数和结果在树上上下移动。您需要一个属性语法工具来执行此操作；并且您仍然必须指定节点构建逻辑。我们使用属性语法，本质上是上面的使用我们的 DMS Software Reengineering Toolkit 分段构建控制流图，为多种语言提供通用控制流分析工具。

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

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

可以找到有关一般过程的更多详细信息here .