Zusammenhang zwischen schichtreduziertem Parsing und abgegrenzten Fortsetzungen?

13

Hat jemand die Beziehung zwischen Parsing-Techniken zur Schichtreduzierung und abgegrenzten Fortsetzungen formalisiert?

Bei der Erstellung eines Bottom-Up-Parsers (z. B. LR-Parser) nehmen wir eine Grammatik und stellen dann Analysezustände als Mengen von Elementen dar : erweiterte Produktionen der Form , wobei und sind Sequenzen von Terminals und Nichtterminals. Die Markierung , wie weit der Parser in die Zeichenfolge gelangt ist, wobei für das steht, was bisher gesehen wurde, und für eine Vorhersage dessen, was noch analysiert werden kann.EINαβαβαβ

Ein Schaltvorgang in einem Übergang der LR - Parsing - Automaten entspricht einen Präfix des Stapels gegen , und ersetzt sie durch . Eine derart tiefe Manipulation des Stapels ähnelt der Wirkung eines Steueroperators, dies ist jedoch nur eine qualitative Beobachtung.αEIN

Hat jemand den Zusammenhang zwischen Shift-Reduce-Parsing und abgegrenzten Steueroperatoren wie Shift / Reset untersucht?

Neel Krishnaswami
quelle
Interessante Beobachtung.
Dave Clarke
Man hätte erwarten können, dass Michael Sperber irgendwo über diese Beziehung geschrieben hat, da er sich mit CPS LR-Analyse und abgegrenzten Fortsetzungen befasst, aber ich habe nichts gefunden.
Sylvain
Ich erinnere mich, dass Ken Shan mir diese Verbindung bereits im Jahr 2004 erwähnte und vorschlug, dass dies eine großartige Wortspielgelegenheit wäre. Ich weiß nicht, dass er seitdem irgendetwas darüber geschrieben / kodiert hat.
Noam Zeilberger

Antworten:

4

Ich glaube, dass der folgende Aufsatz einige dieser Zusammenhänge untersucht, hauptsächlich indem er Fortsetzungen verwendet, um zurückzuverfolgen, wenn Dinge in Parsern passieren. Aber hier gibt es definitiv noch mehr zu tun.

Modularer Rollback durch Kontrollprotokollierung: Ein Paar doppelter Funktionsperlen

Olin Shivers, Aaron Turon , ICFP 2011.

Sam Tobin-Hochstadt
quelle