Parsing mit Schichtauflösung - Fragen

10

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,...TA,B,C,...N...X,Y,ZNTα,β,γ,...{NT}Aiωi

Außerdem wird in der gesamten Beschreibung die Äquivalenzbeziehung verwendet.κ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 .AiαβAiαβ,m,nnmβ

Die Grammatik wird um die Regel und die Konstruktion beginnt mit dem Verschiebungselement im Ausgangszustand.S0S$S0S$

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 .AiαβqXqXβ

  2. Wenn es sich bei dem Element um ein fertiges Schichtelement , fügen Sie für jede Regel ein Auflösungselement .AiωBjαAβ,i,0BjαAβ

  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 inAiαβ,m,nXβXNXjωXjωAiαβ,m,nXqXqCiαXβ,m,nqCiαXβ,m,n+1q .

  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 .Aiω,m,nBjαAβ,m,nBjαAβ

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.r0,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?κκ0FOLLOWLM

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 :)

Jakub Lédl
quelle
schlagen vor, diese Frage auf cstheory zu migrieren. Was das Papier betrifft, scheint es ein sehr komplexer Algorithmus zu sein, der "wahrscheinlich" (?) von niemandem implementiert wurde. Die Hauptidee scheint zu sein, willkürlichen Lookahead zu kombinieren, aber auch mit linearer Zeitanalyse ...? Aber wie viele Anwendungen wären mit einem einfacheren, standardmäßigeren, superlinearen Algorithmus in Ordnung? Irgendeine Idee, welche Anwendung würde mit diesem Ansatz besser funktionieren? Hast du einen oder kennst du einen?
VZN
1
Eine sehr schöne theoretische Übung (obwohl ich mir die technischen Details nicht angesehen habe). Angesichts der Tatsache, dass die volle Leistung von LR (k) oft nicht einmal genutzt wird, kann man sich über die praktischen Auswirkungen wundern. Ich sehe zwei Probleme bei dieser Art von Arbeit: (1) Da der Algorithmus komplexer wird, ist es dem menschlichen Verstand immer noch möglich, die Grammatik zu verdrehen und die Konsequenzen zu verstehen, wenn er nicht funktioniert. Es ist eine häufige Tatsache, dass hochentwickelte Techniken sehr lohnend sind, wenn sie funktionieren, aber die Dinge noch schlimmer machen, wenn sie es nicht tun. (2) Wird es in Fällen linear sein, in denen allgemeine CF-Algorithmen nicht linear sind?
Babou

Antworten:

0

Ü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.

vonbrand
quelle