Parsing mit Schichtauflösung - Fragen

Ich bin kürzlich auf ein Papier gestoßen, das die im Titel erwähnte Parsing-Technik beschreibt. Leider ist die in diesem Artikel verwendete Terminologie etwas unverständlich, so dass ich versucht habe, den Konstruktionsalgorithmus intuitiver zu erfassen. Ich glaube, es ist mir gelungen ( diese Präsentation war die Quelle des ah-ha-Moments), aber eine Überprüfung der Richtigkeit durch jemanden, der entweder mit der Technik oder der darin enthaltenen Terminologie vertraut ist, wäre sehr dankbar.

Ich werde meine Einstellung zur Lösung beschreiben (wenn sie korrekt ist, glaube ich, dass sie anderen Menschen helfen könnte, die versuchen, die Technik zu verstehen) und anschließend weitere Fragen stellen. Um sicherzustellen, dass es keine Missverständnisse gibt, verwende ich die folgende Standardnotation: , , , und, wie in der Veröffentlichung, , um die Regel zu bezeichnen Nummer . Ich werde jedoch wahrscheinlich andere Namen für Konzepte verwenden als das Originalpapier.$a, b, c, ... \in T$$A, B, C, ... \in N$$... X, Y, Z \in N \cup T$$\alpha, \beta, \gamma, ... \in \{N \cup T\}^*$$A \xrightarrow{i} \omega$$i$

Außerdem wird in der gesamten Beschreibung die Äquivalenzbeziehung verwendet.$\kappa_0$

Konstruktion

Es gibt zwei Arten von Elementen im Parsing-Automaten: einfache LR (0) -Elemente der Form die ich Shift-Elemente und Elemente der Form nenne die ich Auflösungselemente nenne ; Diese weisen den Parser an, Symbole in den Eingabestream zurückzuschieben und dann das erste Symbol von um die Regelnummer reduzieren .$A \xrightarrow{i} \alpha \bullet \beta$$A \xrightarrow{i} \alpha \bullet \beta, m, n$$n$$m$$\beta$

Die Grammatik wird um die Regel und die Konstruktion beginnt mit dem Verschiebungselement im Ausgangszustand.$S' \xrightarrow{0} S \$$$S' \xrightarrow{0} \bullet S \$$

Um nun den Automaten zu konstruieren, entscheiden Sie sich zwischen diesen Alternativen für jedes Element in einem Zustand :$q$

1. Wenn es sich bei dem Element um ein Verschiebungselement , gibt es im Automaten einen Übergang , wobei das erste Symbol von .$A \xrightarrow{i} \alpha \bullet \beta$$q \xrightarrow{X} q'$$X$$\beta$

2. Wenn es sich bei dem Element um ein fertiges Schichtelement , fügen Sie für jede Regel ein Auflösungselement .$A \xrightarrow{i} \omega \bullet$$B \xrightarrow{j} \alpha A \bullet \beta, i, 0$$B \xrightarrow{j} \alpha A \beta$

3. Wenn es sich bei dem Element um ein Auflösungselement handelt , sei das erste Symbol von . Wenn , fügen Sie für jede Regel ein Verschiebungselement . Wenn andere Elemente als haben wie ihre Vorgriffs - Punkt, einen Übergang hinzufügen an den Automaten. Jedes Auflösungselement in führt zu einem Auflösungselement in$A \xrightarrow{i} \alpha \bullet \beta, m, n$$X$$\beta$$X \in N$$X \xrightarrow{j} \bullet \omega$$X \xrightarrow{j} \omega$$A \xrightarrow{i} \alpha \bullet \beta, m, n$$X$$q \xrightarrow{X} q'$$C \xrightarrow{i} \alpha \bullet X \beta, m, n$$q$$C \xrightarrow{i} \alpha X \bullet \beta, m, n + 1$$q'$ .

4. Wenn es sich bei dem Element um ein Auflösungselement , werden keine Lookahead-Informationen bereitgestellt und können verworfen werden. Fügen Sie jedoch zuerst ein Auflösungselement für jede Regel .$A \xrightarrow{i} \omega \bullet, m, n$$B \xrightarrow{j} \alpha A \bullet \beta, m, n$$B \xrightarrow{j} \alpha A \beta$

Dies ist natürlich nur eine Skizze; Tatsächlich muss zuerst eine Schließung des Staates berechnet werden, und erst dann können wir uns mit Übergängen / Verschiebungen und Auflösungen befassen.

Die Umwandlung des Automaten in eine Parsing-Tabelle mit Schichtauflösung ist danach trivial. Nur als geringfügige Abweichung interpretieren die Autoren des Papiers eine Auflösung als die Akzeptanzaktion. Angesichts des resultierenden Automaten fand ich es einfacher, eine Verschiebung von einfach als Akzeptanzaktion zu behandeln.$r_{0,0}$$\$$

Fragen

Der erste ist natürlich, ob der oben beschriebene Prozess korrekt ist.

Der zweite betrifft die Äquivalenzbeziehungen. Ich kann nur vermuten, dass die Äquivalenzbeziehung dafür verantwortlich ist, zu entscheiden, welche Auflösungselemente eingegeben werden, wenn ein fertiges Schichtelement gesehen wurde. scheint zu einem Lookahead zu führen, der den -Sätzen von LSLR-Parsern auffallend ähnlich ist . Das Papier beschreibt eine "feinere Äquivalenzbeziehung" auf Seite 11; Gibt es eine Möglichkeit, diese Beziehung intuitiv zu interpretieren? Sind andere Beziehungen bekannt?$\kappa$$\kappa_0$$FOLLOW_{LM}$

Und im letzten geht es um Konfliktlösung. Das Papier beschreibt gut, was eine Unzulänglichkeit in einem Automaten mit Schichtauflösung darstellt; Gibt es eine Möglichkeit, diese Unzulänglichkeiten zu beheben, ähnlich wie bei der Lösung von Konflikten in einem herkömmlichen LR-Parser? Könnte so etwas wie eine Konfliktlösung im yacc- Stil über Vorrang und Assoziativität in einem ShRe-Parser-Generator implementiert werden?

Vielen Dank, wenn Sie dies alles lesen und alle Antworten sehr geschätzt werden :)

Überprüfen Sie, ob dies in der Enzyklopädie D. Grune, CJH Jacobs, "Parsing Techniques: a Practical Guide" (Spinger, 2008) diskutiert wird. Wenn nicht, ist es vielleicht einer diskutierten Technik ähnlich genug.