アルゴリズムの名前-AST内の一致するサブツリー
-
28-10-2019 - |
質問
「小さな」ツリーのジェネラコディセタグコードのセットがあります。ジェネラコディセタグコードより大きなツリー内の位置を見つける必要があります より大きなツリーで一致するサブツリーを見つけるためのパターンとして使用されますツリーS
。 S[i]
(解析ツリー)の構築を開始する前にT
を知っているので、(パーサーがCSTを生成するときに)ノードを一致させるために cuting-plane method を採用することを考えています。
S
のツリーは、T
と同じASTではありません-XPathとXMLについて考えてください-S
はXPathのツリー表現を保持しますが、T
はソースコードの実際のASTです-S
とベクターの間のマップが必要ですT
の一致するノードの数。
ただし、使用するアルゴリズムの名前はわかりません。
基本的に私は自分が何をしたいのかを知っています。それは、複製するLALRパーサーの各シフトで、一致する可能性のある候補を保持するスタックを備えた「木のための分割統治」のように感じます。スタックの一番上にあり、とにかく一致しないi
から候補T
を削除し、削減後、スタックからポップします。最初は、i
のすべてのメンバーが候補になります。
注意:これはASTに関するものであり、ASGは別の話です...
補遺
ここに解析ツリーS[i]
があります。
解析関数は、私が「ツリーパス」と呼んでいるもののリストを、S
に格納された、ツリーとしても表される正規の形式で認識します。ただし、それらは解析ツリーのようには見えません。XPathと同様に、表現する独自の言語があります。
戻り値として変数を持つすべての関数を取得するためのツリーパスの例:
ジェネラコディセタグプレ
- では、既存の文献で何を探す必要がありますか?
- 他にアドバイスはありますか?
- このようなメタアノテーション付きツリーをクエリできる言語はすでにありますか?オープンソースのC(C ++ではない)ライブラリが理想的です。
解決
1)XPathとしてのSツリーはいくつかのTツリーに対応します。事前にTツリーを作成して、パターンマッチングしてみませんか?
2)パターンを構造体と照合する場合は、パターンをある種のステートマシンにコンパイルすることを想像できます。これは、照合されるツリーの特定の部分が遷移すると遷移します。ステートマシンが受け入れ状態に入る場合は、一致するものが見つかります。複数のパターンがある場合は、それぞれをステートマシンとして扱い、(シミュレーションによって)「並行して」実行できます。これを効率的にするには、すべてのステートマシンの外積を計算します。現在は1つだけで、入力ごとに1つの遷移のみが発生します。私が「パターン製品」と呼ぶこのアイデアは、さまざまな効率的なマッチャーのようなものです。やりたいことに近いのは、 Reteアルゴリズムです。これは、どの「パターン」を追跡します。供給されるデータが変化してもライブです。