使用 Java 通过访问者模式从 AST 构建控制流图

Question

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

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

我的主要问题是，我还没有弄清楚如何将不同的块连接在一起，因为每个块之间的右边缘取决于它们的性质：分支、循环等。换句话说，我还没有找到明确的方法可以帮助我构建访客的算法。

这是我的空访客。你可以看到它适用于基本的语言表达式，例如 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）进行推理，您首先需要一个控制流图。

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

某些节点（例如，对于“assignmentstmt”）将创建一个引用 AST 进行分配的操作节点（认为流程图中的“矩形”）；没有任何子图弧需要担心。一些节点（例如，“if”）将创建一个条件分支节点（引用条件表达式的 AST 节点）（想想流程图中的“菱形”）、一个流连接节点，并组成一个结构化的（if- then-else）子图，通过将条件分支节点与 then 和 else 子句的子图（仅由 then 入口和出口弧表示）与流连接节点组合起来。然后，将此复合子图的入口和出口弧传递给父级。

该方案适用于结构化控制流。非结构化控制流（例如，“GOTO x”）需要一些有趣的调整，例如，首先构建图形的结构化部分，将生成的控制流与标签相关联，然后返回并修补 GOTO 操作以具有到关联的弧线。标签。

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

使用生成的访问者的更复杂的方案称为 http://en.wikipedia.org/wiki/Attribute_grammar"> 属性语法，它本质上通过传递感兴趣的值（在本例中）来为您管理所有信息流，进入/退出/异常流弧）作为参数和结果在树中上下移动，您需要一个属性语法工具来执行此操作，并且您仍然需要指定节点构建逻辑，并且本质上是上述控制流。使用我们的DMS 软件重新工程工具包分段构建图形，以提供通用控制流分析工具对于许多语言。

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

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

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