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

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?

reference-request fl.formal-languages parsing Neel Krishnaswami
quelle

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

arxiv.org/abs/1604.04695

Mehrdad

Antworten:

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

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:

Yacc ist nicht tot , Rezension dieses Papiers von Russ Cox, von re2 Ruhm.
Yacc ist tot: Ein Update , eine Antwort von Matt Might.
Functional Pearl: Analysieren mit Derivaten von Matthew Might, David Darais und Daniel Spiewak - eine aktualisierte Version des Papiers "Yacc is Dead", das auf der ICFP 2011 in Tokio vorgestellt wurde.

Mikhail Glushenkov
quelle

Sehr lustiger Papiertitel! :-)

Dai Le

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