Verallgemeinerungen von Brzozowskis Methode der Ableitung regulärer Ausdrücke auf Grammatiken?

18

Brzozowskis Methode der Ableitungen ist eine sehr hübsche Technik, um deterministische Automaten aus regulären Ausdrücken auf eine schön algebraische Weise zu erstellen. Ich habe einige nette Verallgemeinerungen dieser Technik ausgearbeitet, um einige größere Grammatikklassen zu behandeln, aber die Algorithmen sind so einfach, dass es durchaus möglich erscheint, dass sie zuvor entdeckt wurden. Aber Googeln Verweise auf Nachkommen dieser Technik scheinen nicht viel aufzuweisen. Weiß jemand von irgendetwas?

Neel Krishnaswami
quelle
2
Ich bin ziemlich gespannt, an welche Grammatikklassen Sie denken. Bezüglich der Nachkommen ist die Technik von Antimirov, die stattdessen nichtdeterministische Automaten erzeugt, sehr schön: Teilableitungen von regulären Ausdrücken und endlichen Automatenkonstruktionen , TCS 155 (2), 1996, ( dx.doi.org/10.1016/0304-3975(95 ) 00182-4 ).
Sylvain
Meinen Sie Verallgemeinerungen für komplexere Sprachen, wie reguläre <kontextfreie <kontextsensitive <...?
s8soj3o289
Ich habe mir Subsysteme von CFGs hauptsächlich in der Nähe von VPLs angesehen.
Neel Krishnaswami
... aber die Menge der Ableitungen ist dann nicht endlich. Und in der Tat, wenn Sie etwas Deterministisches wie mit Brzozowski-Methode wollen, sind Sie wahrscheinlich auf DCFLs beschränkt (daher kann es für VPLs sinnvoll sein).
Sylvain

Antworten:

7

In Total Parser Combinators (ICFP 2010) verwende ich Brzozowski-Derivate, um festzustellen, dass die Zugehörigkeit zu einer Sprache für eine bestimmte Klasse potenziell unendlicher Grammatiken entscheidbar ist.

Nils Anders Danielsson
quelle
12

Dieses Papier könnte Sie interessieren:

Yacc ist tot von Matthew Might und David Darais, 2010

Wir präsentieren zwei neue Ansätze zum Parsen kontextfreier Sprachen. Der erste Ansatz basiert auf einer Erweiterung des Brzozowski-Derivats von regulären Ausdrücken zu kontextfreien Grammatiken. Der zweite Ansatz basiert auf einer Verallgemeinerung der Ableitung auf Parser-Kombinatoren. Die Auszahlung dieser Techniken ist eine kleine (weniger als 250 Codezeilen), einfach zu implementierende Parsing-Bibliothek, die beliebige kontextfreie Grammatiken in Lazy-Parse-Gesamtstrukturen parsen kann. Implementierungen für Scala und Haskell werden bereitgestellt. Vorläufige Experimente mit S-Expressions analysierten Millionen von Token pro Sekunde, was darauf hindeutet, dass diese Technik für den praktischen Einsatz effizient genug ist.

Ebenfalls von potentiellem Interesse:

Mikhail Glushenkov
quelle
Sehr lustiger Papiertitel! :-)
Dai Le
7

In der Mitte der 80er Jahre, als ich an rekursiven Aufstiegsparsern und dem Faktorisieren von Grammatiken arbeitete, begann ich damit, partielle Ableitungen von Grammatiken zu definieren.

Es gibt viele schöne Theorien.

Haben Sie spezielle Fragen?

GHR
quelle
Im Moment bin ich nur auf der Suche nach verwandten Arbeiten. Da ich hauptsächlich an rekursive Descent-Parser gedacht habe, würde ich Anwendungen für das Parsing im LR-Stil finden, wie Sie es besonders interessant finden. Können Sie mich auf einen Ihrer Papiere hinweisen?
Neel Krishnaswami