アルゴリズムの名前-AST内の一致するサブツリー

Question

「小さな」ツリーのジェネラコディセタグコードのセットがあります。ジェネラコディセタグコードより大きなツリー内の位置を見つける必要があります より大きなツリーで一致するサブツリーを見つけるためのパターンとして使用されますツリー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と同様に、表現する独自の言語があります。

戻り値として変数を持つすべての関数を取得するためのツリーパスの例： ジェネラコディセタグプレ

1. では、既存の文献で何を探す必要がありますか？
2. 他にアドバイスはありますか？
3. このようなメタアノテーション付きツリーをクエリできる言語はすでにありますか？オープンソースのC（C ++ではない）ライブラリが理想的です。

Answer 1

1）XPathとしてのSツリーはいくつかのTツリーに対応します。事前にTツリーを作成して、パターンマッチングしてみませんか？

2）パターンを構造体と照合する場合は、パターンをある種のステートマシンにコンパイルすることを想像できます。これは、照合されるツリーの特定の部分が遷移すると遷移します。ステートマシンが受け入れ状態に入る場合は、一致するものが見つかります。複数のパターンがある場合は、それぞれをステートマシンとして扱い、（シミュレーションによって）「並行して」実行できます。これを効率的にするには、すべてのステートマシンの外積を計算します。現在は1つだけで、入力ごとに1つの遷移のみが発生します。私が「パターン製品」と呼ぶこのアイデアは、さまざまな効率的なマッチャーのようなものです。やりたいことに近いのは、 Reteアルゴリズムです。これは、どの「パターン」を追跡します。供給されるデータが変化してもライブです。

Answer 2

JXPathを調べる価値があるかもしれません： http://commons.apache.org/jxpath/ > 対象としている言語はわかりませんが、試してみる価値はあるかもしれません。

とにかく、このようなことを試みて実装する必要がある場合の最初の衝動は、両方のツリーを「シリアル化」する方法を見つけ、問題を単純な文字列照合の1つに減らすことです。