Erstellen von Parse-Bäumen mit Umlagerung

Question

Ich experimentiere mit der Analyse in meiner Freizeit, und ich wollte einen Umlagerungsparser für eine sehr einfache Grammatik umsetzen. Ich habe viele Online-Artikel gelesen, aber ich bin immer noch verwirrt, wie er Parse-Bäume erstellt. Hier ist ein Beispiel für das, was ich tun möchte:

---

Grammatik:

generasacodicetagpre.

Hier ist ein Beispieleingang:

generasacodicetagpre.

dass nach der Tokenisierung:

wird generasacodicetagpre.

---

Ich verstehe das:

.
1. verschieben bedeutet, das erste Input-Token auf den Stapel zu drücken und ihn vom Eingang
2. reduzieren bedeutet, ein oder mehrere Elemente auf dem Stapel mit einem Grammatikelement
zu ersetzen

grundsätzlich sollte dies passieren:

generasacodicetagpre.

Abgesehen von der "Was zu reduzieren?" Zweifel, ich habe keine Ahnung, wie man einen Analyse-Baum richtig baue. Der Baum sollte wahrscheinlich so aussehen:

generasacodicetagpre.

sollte ich einen neuen Knoten zur Reduktion erstellen?

Und wann sollte ich Kindern zum neu erstellten Knoten hinzufügen / Wann sollte ich einen neuen Root-Knoten erstellen?

Answer 1

Die einfache und offensichtliche Sache ist, einen Baumknoten bei jeder Reduktion zu erstellen und die Baumknoten von den Grammatikelementen hinzuzufügen, die auf diesen Baumknoten reduziert wurden.

Dies wird leicht mit einem Knotenstapel verwaltet, der parallel zum "Shift-Token-Stapel läuft, den der rohe Parser verwendet. Für jede Reduktion für eine Länge der Länge N wird der Schicht-Token-Stapel von n verkürzt, und das Nonterminal-Token wird auf den Schieberstapel geschoben. Gleichzeitig kürzen Sie den Knotenstapel, indem Sie die oberen N-Knoten entfernen, einen Knoten für den Nonterminal erstellen, die entfernten N-Knoten als Kinder angehängt und diesen Knoten auf den Knotenstapel drücken.

Diese Richtlinie arbeitet sogar mit Regeln, die null langen rechter Seite aufweisen: Erstellen Sie einen Baumknoten und fügen Sie den leeren Satz von Kindern an (z. B. einen Blattknoten erstellen).

Wenn Sie an einem Terminalknoten als Verringerung (der Zeichen, die das Terminal bildet, an den Terminalknoten denkst, wenn Sie an den Klemmenknoten erfolgen, dann fügen sich der terminalen Knoten direkt ein. Erstellen Sie einen Knoten für das Terminal und drücken Sie ihn an der Stapel.

Wenn Sie dies tun, erhalten Sie einen "konkreten Syntax- / Parse-Baum", der mit der Grammatik isomorph passt. (Wir tun dies für ein kommerzielles Werkzeug, das ich anbiete). Es gibt viele Leute, die keine solchen Betonbäume mögen, da sie Knoten für Schlüsselwörter usw. enthalten, die nicht wirklich viel Wert hinzufügen. Richtig, aber solche Bäume sind äußerst leicht zu konstruieren, und super leicht zu verstehen, weil die Grammatik die Baumstruktur ist. Wenn Sie 2500 Regeln haben (wie wir für einen vollständigen COBOL-Parser tun), ist dies wichtig. Dies ist auch günstig, da der gesamte Mechanismus vollständig in die Parsing-Infrastruktur gebaut werden kann. Der GRAMMAR ENGINEER schreibt einfach Regeln, der Parser läuft, Voila, einen Baum. Es ist auch leicht, die Grammatik zu wechseln: Ändern Sie einfach es, Voila, Sie erhalten immer noch Parsenbäume.

Wenn Sie jedoch keinen Betonbaum wollen, z. B. Sie möchten, dass ein "abstrakter Syntaxbaum", was Sie tun müssen, den GRAMMAR-ENGINEER steuern, welche Reduktionen Knoten erzeugt; Normalerweise fügen Sie jeder Grammatikregel ein gewisses Verfahrensaufsatz (Code) hinzu, der auf einem Reduktionsschritt ausgeführt wird. Wenn dann ein solcher Verfahrensaufhängung einen Knoten erzeugt, bleibt er auf einem Knotenstapel erhalten. Jede prozessurale Befestigung, die einen Knoten erzeugt, muss Knoten, die von den rechten Elementen erzeugt werden, anhängen. Wenn ja, was yacc / bison / ... die meisten der shift-Reduktion-Parser-Motoren tun. Lesen Sie über Yacc oder Bison lesen und untersuchen Sie eine Grammatik. Dieses Programm bietet Ihnen viel Kontrolle, zum Preis der Bestehen, dass Sie diese Kontrolle nehmen. (Für das, was wir tun, wollen wir nicht, dass diese technische Anstrengung beim Aufbau einer Grammatik).

Im Falle der Herstellung von CSTS ist es konzeptionell einfach, "nutzlose" Knoten von Bäumen zu entfernen; Wir tun das in unserem Werkzeug. Das Ergebnis ist viel wie ein AST, ohne den manuellen Anstrengungen, all diese Verfahrensanhänge zu schreiben.

Answer 2

Der Grund für Ihr Problem ist, dass Sie einen Umschalt- / Reduzierkonflikt in Ihrer Grammatik haben:

generasacodicetagpre.

Sie können dies auf zwei Arten beheben:

generasacodicetagpre.

für linke assoziative Bediener oder

generasacodicetagpre.

für richtige assoziative assoziative. Dies sollte auch die Form Ihres Baums bestimmen.

wird in der Regel durchgeführt, wenn eine Klausel abgeschlossen erkannt wird. In dem richtigen assoziativen Fall würden Sie in einem Zustand 1 beginnen, der eine Zahl erwartet, schiebt es auf den Wertstapel und verschiebt den Zustand 2. In Staat 2, wenn das Token kein OP ist, können Sie eine Zahl auf ein expr reduzieren . Andernfalls drücken Sie den Bediener und die Verschiebung in den Zustand 1. Nachdem der Status 1 abgeschlossen ist, können Sie die Anzahl, den Bediener und den Ausdruck an einen anderen Ausdruck reduzieren. Hinweis, Sie benötigen einen Mechanismus, um nach einer Reduktion "zurückzukehren". Der gesamte Parser würde dann in Staat 0 beginnen, sagen, was sofort in den Zustand 1 geht, und akzeptiert nach der Reduktion.

Beachten Sie, dass Werkzeuge wie Yacc oder Bison diese Art von Sachen viel einfacher machen, weil sie alle Machinerie mit niedrigem Pegel und den Stapeln mitbringen.