15

ANTLR Parser Generator for Java から派生した AST があります。私がやりたいことは、ソース コードの制御フロー グラフを何らかの形で構築することです。ここで、各ステートメントまたは式は一意のノードです。この識別には再帰性があるに違いないことを理解しています。最良のオプションとして何を提案するか、ANTLR にこのジョブに使用できるツールセットがあるかどうか疑問に思っていました。乾杯、クリス


編集 - 私の主な関心事は、AST から制御フロー グラフ (CFG) を取得することです。このようにして、ソースのツリー表現を取得できます。明確にするために、ソース コードと実装言語の両方が Java です。

4

6 に答える 6

11

通常、CFG は下位レベルの表現 (JVM バイトコードなど) で計算されます。数年前、誰かがそのようなことについて論文を書きました。その表現に到達する方法については、そこに説明されている役立つ方法があるかもしれません。

ソース言語とターゲット言語が同じなので、コード生成の手順はありません。これで完了です。ただし、AST を実行できるようになりました。AST の各ノードで、これは「ジャンプ」命令かどうかを自問する必要があります。メソッド呼び出しと if ステートメントは、ジャンプ命令の例です。ループ構造 ( や などfor)も同様whileです。加算や乗算などの命令は非ジャンプです。

最初に、CFG 内の各 Java ステートメントに、入口ノードと出口ノードとともにノードを関連付けます。最初の概算として、ツリーをたどって次のことを行います。

  1. 現在のステートメントがメソッド呼び出しの場合、そのメソッド呼び出しの対応する本体のエントリ ノードがどこにあるかを把握し、現在のステートメントからそのエントリ ノードを指すエッジを作成します。ステートメントがメソッドの戻り値である場合は、それを呼び出した可能性のある場所を列挙し、それらにエッジを追加します。
  2. ジャンプしないステートメントごとに、それと次のステートメントの間にエッジを作成します。

これにより、ある種の CFG が得られます。呼び出されたメソッドはライブラリで宣言され、AST の他の場所では宣言されていない可能性があるため、手順はステップ 2 で少し複雑です。ライブラリメソッド。

これは理にかなっていますか?

于 2008-09-18T15:30:36.680 に答える
1

いくつかのコメントに基づいて、OP が実際にコード生成を行いたいように思えます。基本ブロックとジャンプ ポイントに基づいて、AST を下位レベルの命令シーケンスに変換します。

コード生成は非常に言語固有であり、このトピックには多くの作業が費やされています。コード生成を行う前に、ターゲット言語を知る必要があります。それがアセンブラーであるか、単に他の高級言語であるかに関係なく。これを特定したら、あとは AST を調べて、AST にコードを実装する一連の命令を生成するだけです。(これは単純だと言いますが、難しい場合があります。ここでの考慮事項はかなり言語固有であるため、一般化するのは困難です。)

コード生成用に選択する表現には、暗黙的または明示的に制御フロー グラフが含まれます。ターゲット言語がかなり低レベル (アセンブラーに近い) の場合、制御フロー グラフは比較的簡単に抽出できるはずです。

(もっと明確にしたい場合はコメントしてください。)

于 2008-09-18T14:11:06.060 に答える
-1

過去にこれを行ったとき、グラフを生成するために、特に dot ツールを使用してgraphvizを使用しました。コンパイル時に制御フロー グラフを実際にトラバースして、ドット入力ファイルを作成しました。

グラフのレイアウトは難しい問題ですが、graphviz は優れた仕事をします。ps、pdf、およびさまざまな画像形式に出力でき、レイアウトは通常、非常に直感的に見ることができます。強くお勧めします。

于 2008-09-18T13:51:54.623 に答える
-1

ANTLR Studioを試したことがありますか? これはホールの AST グラフを生成しませんが、レビューのために、すでに非常に役に立ちます。

于 2008-09-18T13:35:29.327 に答える