8

JavaCCで既に生成されたAbstract-Syntax-Treeから制御フローグラフを構築するために、LEParserCfgVisitorクラスを実装する方法を理解しようとしています。すでに存在するツールがあることは知っていますが、コンパイラの最終版に備えてそれをやろうとしています。

グラフをメモリに保持するデータ構造が必要であることはわかっており、後で制御フロー分析を実行できるように、各ノードで 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) について推論するには、まず制御フロー グラフが必要です。

1 つを作成するには、各ツリー ノード (たとえば、特定の各ノード ビジター内) で、ノードが表すグラフの一部を作成します。そのグラフの入口アークと出口アークを親の「訪問者」に渡します。親に情報を渡す必要があるため、純粋に独立したビジターは機能しません。[訪問者によって設定され、親によって検査される各ノードに入口/出口アーク スロットを追加できます。]

一部のノード (「assignmentsstmt」など) は、割り当ての AST を参照するアクション ノードを作成します (フローチャートの「長方形」を考えてください)。心配するサブグラフ アークはありません。一部のノード (たとえば、「if」の場合) は、条件分岐ノード (条件式の AST ノードを参照) (フローチャートの「ダイヤモンド」を考えてください)、フロー結合ノードを作成し、構造化された (if- then-else) サブグラフは、その条件付きブランチ ノードを then 句と else 句のサブグラフ (then エントリ アークと exit アークだけで表される) と結合し、フロー join-node を使用します。次に、この複合サブグラフの入口アークと出口アークを親に渡します。

このスキームは、構造化された制御フローで機能します。構造化されていない制御フロー (たとえば、「GOTO x」) には、面白い調整が必要です。たとえば、最初にグラフの構造化された部分を構築し、生成された制御フローをラベルに関連付けてから、戻って GOTO アクションをパッティングして、関連付けられたものへのアークを作成します。ラベル。

例外について心配することを忘れないでください。それらも GOTO ですが、一般に、構造化された制御フロー グラフの上位に位置します。これらは、多くの場合、最も内側の例外ハンドラ ノードをツリーの下に渡すことによって処理されます。訪問者はツリーを調べて、最新の例外ハンドラを確認する必要があります。

生成されたビジターを使用するより洗練されたスキームは、http://en.wikipedia.org/wiki/Attribute_grammar">属性文法と呼ばれ、対象の値 (この場合、エントリ/出口/例外フロー アーク) をパラメーターと結果としてツリーを上下に移動します. これを行うには属性文法ツールが必要です. ノード構築ロジックを指定する必要があります. 属性文法と本質的に上記の制御フロー グラフを使用します. DMS Software Reengineering Toolkitを使用して部分的に構築し、多くの言語に汎用的な制御フロー分析機能を提供します。

制御フロー グラフを取得したら、制御フロー グラフをウォークスルーすることで、記述したタイプのデータ フロー ソルバーを実装できます。生の使用/生の定義情報を収集するには、CF ノードが指す AST に再度アクセスする必要があります。

言語に構造化された制御フローしかない場合は、AST ノードを使用して制御フロー ノードを表し、データ フローを直接計算できます。

一般的なプロセスの詳細については、こちらを参照してください。

于 2010-12-24T17:37:52.073 に答える