Name des Algorithmus - übereinstimmende Teilbäume in ASTs

Question

Ich habe einen festgelegten S für "kleine" Bäume S[i] , für den ich ihre Positionen innerhalb eines größeren finden muss, die als Muster verwendet werden, um passende Teilbäume in einem größeren Baum T. Ich kenne S, bevor ich mit der Erstellung von T (einem Analysebaum) beginne. Daher denke ich darüber nach, eine Schnittebenenmethode zu verwenden, um die Knoten im Laufe der Zeit abzugleichen (während der Parser die CST generiert).

Die Bäume in S sind nicht die gleichen ASTs wie T - denken Sie an XPath vs. XML - S enthält die Baumdarstellung der XPaths, während T die tatsächliche AST des Quellcodes ist - ich benötige Karten zwischen i und einem Vektor von übereinstimmenden Knoten des T.

Ich bin mir jedoch nicht sicher, welche Namen die Algorithmen verwenden würden.

Grundsätzlich weiß ich, was ich tun möchte. Es fühlt sich an wie ein " dividieren et impera für Bäume" mit einem Stapel, in dem ich bei jeder Schicht des LALR-Parsers, den ich dupliziere, mögliche passende Kandidaten halte die Oberseite des Stapels und entfernen Kandidaten i aus S[i], die sowieso nicht übereinstimmen, und nach einer Reduzierung knalle ich vom Stapel. Zu Beginn sind alle Mitglieder von S mögliche Kandidaten.

Bitte beachten Sie : Hier geht es nur um die AST, die ASG ist eine andere Geschichte ...

Addendum

Hier ist ein Analysebaum-T.

Die Parsing-Funktion kennt eine Liste der sogenannten "Baumpfade" in kanonischer Form, die auch als Bäume dargestellt wird und in S gespeichert ist. Aber sie sehen nicht wie der Parsetree aus, sie haben ihre eigene Sprache, in der sie dargestellt werden können, ähnlich wie bei XPath.

Beispiel eines Baumpfads zum Abrufen aller Funktionen, deren Rückgabewert eine Variable ist:

function[body[return[expr[@type="variable"]]]]]

1. Worauf sollte ich in der vorhandenen Literatur achten?
2. Irgendwelche anderen Ratschläge?
3. Gibt es bereits Sprachen, die solche mit Meta-Annotationen versehenen Bäume abfragen können? Eine Open-Source-C-Bibliothek (nicht C ++) wäre ideal.

Answer 1

1) Ihre S-Bäume als XPath entsprechen einigen T-Bäumen.Warum nicht die T-Bäume im Voraus konstruieren und dann mit dem Muster übereinstimmen?

2) Wenn Sie ein Muster mit einer Struktur abgleichen möchten, können Sie sich vorstellen, das Muster zu einer Art Zustandsmaschine zu kompilieren, die übergeht, wenn bestimmte Teile des Baums abgeglichen werden.Wenn die Zustandsmaschine jemals in einen Akzeptanzzustand wechselt, haben Sie eine Übereinstimmung gefunden.Wenn Sie mehr als ein Muster haben, kann jedes als Zustandsmaschine behandelt werden und Sie können sie "parallel" ausführen (durch Simulation).Um dies effizient zu gestalten, berechnen Sie das Kreuzprodukt aller Zustandsautomaten.Jetzt gibt es nur noch einen und nur einen Übergang pro Eingabe.Diese Idee nenne ich "Musterprodukte" und Sie sehen so etwas wie in einer Vielzahl effizienter Matcher.Ein nah an dem, was Sie tun möchten, ist der Rete-Algorithmus , der verfolgt, welche "Muster"sind live, wenn sich die ihm zugeführten Daten ändern.

Answer 2

Es könnte sich lohnen, einen Blick auf JXPath zu werfen: http://commons.apache.org/jxpath/ Ich bin mir nicht sicher, auf welche Sprache Sie abzielen, aber es könnte den Versuch wert sein.

Wie auch immer, mein erster Impuls, wenn ich versuchen müsste, so etwas zu implementieren, wäre, einen Weg zu finden, beide Bäume zu "serialisieren" und das Problem auf einen einfachen String-Abgleich zu reduzieren.