10

大学のプロジェクト用にコンパイラを書いています。抽象構文ツリーを制御フロー グラフ (CFG) に変換したいと考えています。

私は、CFGのノード ( V) は AST のノードであるべきだと考えています。私はエッジセット ( G=(V,E)) を構築する方法をアルゴリズム的に知っていますが、プロセスをもう少し形式的に書くのに苦労しています

この scala スタイルのパターン マッチング (疑似) を作成しました。

def edges(n:Node)(nestedin_next: Node) : List[(Node,Node)] = 
    n match {
       case (c_1 :: c_2::tl) => (c1,c2) :: edges(c2::tl)(nestedin_next)++
                                   edges(c_1)(c_2)//recurse
       case c_1 :: Nil => (c_1,nestedin_next)::Nil
       case  i@ IF(_,c1,c2) => (i,c1)::(i,c2)::edges(c1)(nestedin_next)++
                                edges(c2)(nestedin_next)
       case _ => Nil
     }

次のような AST 構造に一致する必要があります。

( IF(1,
       ASSIGN(x,1), // ia1
       ASSIGN(x,2) // ia2
     ) ::  // i1
  ASSIGN(y,2) ::  // a1
  ASSIGN(z,ADD(x,y)) :: //a2 
  IF(z, 
       RET(z), //i2r1
         assign(z,0):: // i2a1
         ret(z) // i2r2
  ) :://i2
   Nil
)

次のようなエッジセットを提供します。

{ i1 -> ia1,
   i1 -> ia2,
   ia1 -> a1,
   ia2 -> a1,
   a1 -> a2,
   a2 -> i2,
   i2 -> i2r1
   i2-> i2a1
   i2a1 -> i2r2
   i2r2 -> _|_
   i2r1 -> _|_ 
}

CFG(ドット) ドットソース

これをスカラ「疑似コード」よりも少し形式的に行う方法についてのヒントはありますか?

私は次のような帰納的なことを考えています:

e[[ IF(_,b1,b2) ]] = (if -> b1) + (if -> b2) \cup e[[ b1 ]] \cup e[[ b2 ]]
e[[ b1, b2 ]] = e[[b1]] \cup e[[b2]]

（ただし、上記はツリーのみを提供し、グラフは提供しません。たとえば、then-branch のエッジから次のステートメントへのエッジはありません）

編集：

私はkiama とscala のデータフローについて調べてきましたが、彼らが使用する「成功」と「フォロー」のアプローチが気に入っています。それにもかかわらず、私はそれをより正式な説明に煮詰めるのに苦労しています。これは主に、正式に指定しようとすると見苦しくなる詳細の一部を隠す気の利いchildAttrたのせいです。s.next

EDIT2：

私は Dragon Book と「Modern Compiler Implementation in ML」、およびLearning to write a compilerの他の資料のいくつかを読み、一部/ほとんどがデータ フローと制御フローについて言及していますが、作成方法についてはあまり触れていません。正式な方法でCFG。

EDIT3：

Kiamaの著者、准教授である Tony Sloane 博士から、検索するための追加の参考文献をいくつか受け取りました。

私が見ることができる限り、それらの本によると「それを行う方法」は、ASTよりもプログラムの「ステートメントごと」に基づいており、基本ブロックに基づいています。それにもかかわらず、素晴らしいインプット！

4

2 に答える 2

5

Google の Closure Compilerは、JavaScript の AST を制御フロー グラフに変換する制御フロー分析を実装しています。この実装のアイデアは、次の論文から着想を得ています: Declarative Intraprocedural Flow Analysis of Java Source Code。

于 2010-09-04T18:37:30.503 に答える
3

もう少しフォーマルに見えるものを単純に作成することを意図している場合は、これらのマッチング操作を標準表記法を使用して推論ルールとして表現できます。再帰的にではなく、単一の縮小ステップで表現する必要があります。これは、適用できなくなるまでこれらのルールを適用し続けるだけで十分だからです。

とはいえ、この定義は基本的に、scala コードとまったく同じことを言っています。本当に「正式な」ことをしたい場合は、証明する必要があるプロパティは次のとおりです。

  • CFG 変換アルゴリズムは常に終了します
  • 特定の AST 入力に対して CFG が最小かどうか
  • 特定の AST 入力に対して、アルゴリズムによって導出可能な一意の CFG があるかどうか (つまり、どの CFG が生成されるかは非決定論的ではありません)。

基本的なブロック アプローチ (ステートメントごとのアプローチではなく) も、必ずしも悪い考えではないと思います。基本ブロックに一致する場合、この一致の存在に基づいてセット メンバーシップについてアサーションを作成するルールを作成できることは、完全に合理的であるように思われます。あなたがスケッチし始めた帰納的な定義はうまく機能するようです。

他に興味深いのは、(形式的に)構造化された運用セマンティクスと CFG の構築を関連付けることです。この分野ではすでに作業が行われている可能性がありますが、Google で大まかな検索を行っただけで、両者の間に明確に述べられた関係は見つかりませんでしたが、直感的には存在するはずです。

于 2010-09-04T15:45:29.867 に答える