1

JSON 形式で指定された AST から制御フロー グラフ (CFG) を作成したいと考えています。したがって、この AST は各スクリプトに対して TouchDevelop で自動的に作成されます。また、TouchDevelop はオブジェクト指向プログラミングではないため、Visitor パターンを引き続き使用できますか? 有用なポインタをいただければ幸いです。

Update1:私の問題は、どこから始めればよいかわからないことです。インターネットから、Visitor Pattern を使用して AST をウォークスルーし、各ノードにアクセスして情報を収集することになっています。そこから CFG を構築し、データ フロー分析を行うことができます。しかし、次の 2 つの問題があります。

1）私の知る限り、訪問者パターンを使用するにはオブジェクト指向プログラミングモデルが必要です（私は間違っているかもしれません）が、TouchDevelopはそうではありません。

2) 以下の AST は、インターネットで見つけた AST 形式ではありません。JSON形式です。JSON を解析して目的の AST 構造に変換できると思いますが、よくわかりません。

サンプルスクリプトのソースコード

meta version "v2.2,nothing";
meta name "DivideByZero";
//
meta platform "current";

action main() {
  (5 / 0)→post_to_wall;
}

結果の AST (JSON 形式) を以下に示します。

{
    "type":"app",
    "version":"v2.2,nothing",
    "name":"DivideByZero",
    "icon":null,
    "color":null,
    "comment":"",
    "things":[
        {
            "type":"action",
            "name":"main",
            "isEvent":false,
            "outParameters":[
            ],
            "inParameters":[
            ],
            "body":[
                {
                    "type":"exprStmt",
                    "tokens":[
                        {
                            "type":"operator",
                            "data":"("
                        },
                        {
                            "type":"operator",
                            "data":"5"
                        },
                        {
                            "type":"operator",
                            "data":"/"
                        },
                        {
                            "type":"operator",
                            "data":"0"
                        },
                        {
                            "type":"operator",
                            "data":")"
                        },
                        {
                            "type":"propertyRef",
                            "data":"post to wall"
                        }
                    ]
                }
            ],
            "isPrivate":false
        }
    ]

}
4

1 に答える 1

7

TouchDevelop スクリプト言語への参照はまだ見つかりませんでした。あなたがそれで何ができて、何ができないのかわからない。

必ずしも訪問者パターンを使用する必要はありません。ビジター パターンは、抽象構文ツリーがクラス階層のノードのインスタンスによって記述されるときに使用される方法です。AST から CFG への変換は、それよりも一般的です。抽象構文ツリーは抽象データ型であり、treeの特殊なケースです。他の抽象データ型と同様に、さまざまな方法で表現できます。どのように行うかは問題ではありませんが、行う必要があるのは、このツリーを反復処理することだけです。また、反復方法は、使用している言語によって異なります。これはあなたの質問に答えるはずです 2/: JSON 文字列は AST の表現である可能性があります。AST は抽象データ型ですが、JSON 文字列はこの抽象データ型の実装です。

JSON では、値、配列、または (キー、値) 関連付けのセットを使用できます。おそらく、AST ノードは (キー、値) 関連付けのセットになると想定できます。同様に、これらの各ノードtypeには、ノードの種類を識別できる名前のキーがあると思います。

私が正しければ、これは質問に答えます:なぜあなたは訪問者パターンを必要としないのですか? ビジター パターンを使用すると、各ノードのタイプを抽出できます。type（これは「ダブルディスパッチ」と呼ばれるものです）しかし、ここでは、各ノードのタイプがフィールドにエンコードされているため、必要ありません。

通常、AST から CFG への変換は一連の関数を使用して行われます。AST 内のノードのタイプごとに 1 つの関数です。これらの各関数は、パラメーターとして受け取るノードに関連付けられた CFG パーツを書き込む必要があります。子ノードの変換関数を再帰的に呼び出します。(これは、OO-AST の場合にビジター パターンが行うことです)

たとえば、関数がありますConvertNode。この関数は、ノードのフィールドを読み取り、typeノードで対応する変換関数を呼び出します。ルート ノードのタイプはappです。次に、ConvertNode関数は関数にディスパッチしConvertAppます。ConvertAppのようないくつかのフィールドを読み取り、配列nameを反復処理して、これらのノードのそれぞれを呼び出します。次に、適切な関数に呼び出しをディスパッチします。thingsConvertNodeConvertNode

これらの変換関数が呼び出される方法は、正確に AST 構造に従います。ツリーを反復処理するときに CFG がどのように作成されるかは、入力言語に依存します。各変換関数は、構築されたノードまたは CFG のトランジションを返し、呼び出し元が再利用できるようにすることができます。または、呼び出し元がノードまたはトランジションをパラメーターとして渡して、呼び出された関数がそこから構築を続行できるようにすることもできます。CFG を構築する適切な方法を自由に選択して、一般的なルールを破ることができます。構築を単純化する賢い方法があるかもしれません。

于 2013-02-25T12:01:41.450 に答える