8

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

我知道我需要一个将图形保存在内存中的数据结构，并且我希望能够在每个节点中保留 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) {
  }
}

谁能帮我一把？

谢谢！

4

1 回答 1

11

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

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

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

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

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

使用生成的访问者的更复杂的方案称为 http://en.wikipedia.org/wiki/Attribute_grammar">属性语法，它通过传递感兴趣的值（在这种情况下， entry/exit/exception flow arcs) 上下树作为参数和结果。你需要一个属性语法工具来做到这一点；你仍然需要指定节点构建逻辑。我们使用属性语法和上面的控制流图使用我们的DMS 软件再工程工具包逐件构建，为多种语言提供通用控制流分析工具。

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

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

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

于 2010-12-24T17:37:52.073 回答