Regex für Baumstrukturen?

Question

Gibt es reguläre Ausdrücke für das Suchen und Ändern von Baumstrukturen? Präzise Mini-Sprachen (wie Perl Regex) sind, was ich suche.

Hier ist ein Beispiel, das klarstellen könnte, was ich suche.

<root> 
    <node name="1"> 
    subtrees .... 
    </node> 
    <node name="2"> 
    <node name="2.1"> 
    data 
    </node> 
    other subtrees... 
    </node> 
</root> 

Eine Operation, die auf dem obigen Baum möglich wäre, ist „move Teilbaum am Knoten 2.1 in der Teilbaum an dem Knoten 1.“ Das Ergebnis der Operation könnte so etwas wie aussehen ..

<root> 
    <node name="1"> 
    subtrees .... 
    <node name="2.1"> 
    data 
    </node> 
    </node> 
    <node name="2"> 
    other subtrees... 
    </node> 
</root> 

Suchen und Ersetzen-Operationen wie alle Knoten mit atleast 2 Kinder finden, alle Knoten finden, deren Daten beginnt mit „a“ und ersetzen Sie es mit „b“, wenn die Unterbäume müssen mindestens 2 andere Geschwister usw. unterstützt werden.

Für Zeichenfolgen, deren einzige Dimension sich über die Länge der Zeichenfolge erstreckt, können viele der obigen Operationen (oder ihre 1D-Entsprechungen) mit regulären Ausdrücken ausgeführt werden. Ich frage mich, ob es Äquivalente für Bäume gibt. (Statt einer einzelnen Regex müssen Sie möglicherweise eine Reihe von Transformationsregeln schreiben, aber das ist in Ordnung).

Ich würde gerne wissen, ob es eine einfache Mini-Sprache (nicht Regex per.se, aber etwas, das so zugänglich ist wie Regex über Bibliotheken, etc ..). um diese Operationen durchzuführen? Vorzugsweise als Python-Bibliothek.

Answer 1

TSurgeon und Tregex aus Stanford ist dazu in der Lage. Sie können die Bibliothek herunterladen von http://nlp.stanford.edu/software/tregex.shtml

Answer 2

Navigieren durch einen binären Suchbaum erfordert Zustand (in welchem ​​Knoten bin ich?) Und Vergleiche (ist dieser Wert kleiner oder größer als das?), Dinge, die nicht durch einen endlichen Automaten erledigt werden können.

Sicher, Sie können nach dem Knoten mit einem bestimmten Wert suchen, aber wie könnten Sie dann beispielsweise einen Knoten entfernen, der kein Blatt ist, wenn Sie dessen Eltern nicht kennen?

Und selbst wenn Sie den Elternteil über die vom Knoten bereitgestellten Informationen kennen, wie bestimmen Sie das Minimum des linken Teilbaums, entfernen Sie ihn und platzieren Sie ihn im Knoten?

Ich denke, Sie fragen zu viel zu FSA.

Answer 3

Ich weiß nicht, eine allgemeine Sprache, die das tun kann, aber es scheint mir, dass Sie nach etwas wie XPath suchen.

Answer 4

Es gibt TXL für Muster-basierte Neuschreibung.

Baum mit Muster Umschreiben ist auch mit Parser Toolkits wie ANTLR getan

Codegenerierung mit Bottom-up-Baum Umschreiben, google BURS oder BURG.

Answer 5

This Artikel gibt einige leckere Hinweise auf rekursive Perl reguläre Ausdrücke, aber ehrlich gesagt ist es selten, eine Baumstruktur auf diese Weise zu sehen.

Typischer würde man einen Parser im State-Machine-Stil schreiben, der Regexes verwenden könnte, um jeden bestimmten Knoten in der Struktur zu analysieren.

Expat ist wahrscheinlich ein gutes Beispiel zu betrachten.

Answer 6

Pattern Matching, von Sprachen wie Scala, F #, Erlang und Haskell bereitgestellt (ich bin mir sicher, dass es mehr gibt) ist entworfen, um Datenstrukturen wie Bäume, vor allem bei Rekursion prägnant zu manipulieren.

here ist eine sehr hohe Ansicht davon, was pattren Matching in Scala tun kann. Die gezeigten Beispiele tun wirklich keine Mustergerechtigkeit.

Wikipedia hat auch ein paar Referenzen zum Mustervergleich. Here und here.

Answer 7

Ich bin etwas überrascht, dass XSLT nicht als Antwort aufgetaucht ist. Zugegeben, ich denke nicht, dass es eine besonders elegante Sprache ist, und die meisten existierenden Lösungen neigen eher zu prozeduralen Ansätzen als zu Pattern-Matching. Sie werden durch die bloße Anwendung von XML auf XML - aber ansonsten - sehr schlecht wiedergegeben es passt zur Rechnung. Pity seine kanonische Darstellung ist so ausführlich, obwohl ...