Was ist die leistungsstärkste Art von Parser?

Als Nebenprojekt schreibe ich eine Sprache mit Python. Ich habe mit einem Flex / Bison-Klon namens Ply angefangen, stoße aber an die Grenzen dessen, was ich mit dieser Art von Grammatik ausdrücken kann, und ich bin nicht daran interessiert, meine Sprache zu zerhacken, weil die Impedanz nicht mit der übereinstimmt das Werkzeug. Daher bin ich nicht abgeneigt, meine eigenen zu schreiben.

Also, was ist die mächtigste Art von Parser? Zitate zu Beiträgen (sowie zu weiteren einführenden Artikeln) sind willkommen.

(Ich weiß, dass 'mächtig' nicht genau definiert ist, aber lassen Sie uns ein wenig locker damit umgehen und sehen, wohin die Antworten gehen.)

Eine Grammatik wird normalerweise als kontextfreie Grammatik definiert - eine genaue Definition finden Sie auf der Wikipedia-Seite, aber sie funktioniert genauso wie bei PLY, das auf Bison basiert , das wiederum auf yacc basiert .

Hier steht , dass PLY einen LALR-Parser verwendet . Hierbei handelt es sich im Wesentlichen um einen LR-Parser, bei dem die Nachschlagetabellen komprimiert werden, was möglicherweise zu Analysekonflikten führt und die Aussagekraft einer LR-Grammatik (dh einer kontextfreien Grammatik, die ein LR-Parser analysieren kann) einschränkt. Wenn Sie sich über die Grenzen dieses besonderen Zweiges von Parsern und die der anderen Parser wissen wollen, ein Überblick über alle Arten von Parsing - Techniken (LL, LR und andere) gegeben hier .

Um Ihre Frage zu beantworten: Es gibt Parsing-Algorithmen, mit denen jede kontextfreie Sprache analysiert werden kann, auch wenn die Sprache mehrdeutig ist (dh es gibt mehr als eine Möglichkeit, die Eingabe zu interpretieren):

Der erste derartige Algorithmus war der CYK-Algorithmus , der leider eine Laufzeit von , wobei n die Länge der Eingabezeichenfolge und | ist G | ist die Größe der Grammatik und daher für das Parsen von Sprachen unpraktisch.$O(n^3 |G|)$$n$$|G|$

Der zweite Algorithmus ist der Earley-Algorithmus . Dieser Algorithmus kann auch jede kontextfreie Grammatik analysieren. Obwohl der Algorithmus Zeit benötigt, um eine mehrdeutige Sprache zu analysieren, benötigt er nur O ( n 2 ) Zeit, um eine eindeutige Sprache zu analysieren. Außerdem funktioniert es für die meisten LR-Grammatiken anscheinend in linearer Zeit und besonders gut für linksrekursive Grammatiken.$O(n^3)$$O(n^2)$

Hier finden Sie eine Abhandlung über die praktische Implementierung (Anpassung) des Earley-Algorithmus. Sie schließen daraus: "Angesichts der Allgemeingültigkeit des Earley-Parsings im Vergleich zu LALR (1) und der Tatsache, dass selbst PEPs ((deren Implementierung des Earley-Algorithmus)) die schlechteste Zeit für a nicht wahrnehmbar wären Benutzer, das ist ein hervorragendes Ergebnis ".

Der letzte Parsertyp ist der GLR-Parser . Dies ist eine verallgemeinerte Version des LR-Parsings, mit der jede kontextfreie Sprache analysiert werden kann.

Eine ausgereifte Implementierung von GLR ist ASF + SDF . Bison kann auch einen GLR-Parser generieren, obwohl seine Implementierung sich geringfügig vom 'Standard'-GLR-Algorithmus unterscheidet. Der Elkhound-Algorithmus ist ein GLR / LALR-Hybridalgorithmus. Wenn möglich, wird LALR und bei Bedarf GLR verwendet, um sowohl schnell als auch in der Lage zu sein, jede Grammatik zu analysieren.

Über die kontextfreien Grammatiken hinaus gibt es kontextsensitive Grammatiken , die jedoch im Allgemeinen schwer zu analysieren sind und nicht so viel Aussagekraft hinzufügen: Sie können mehr daraus machen, aber für die meisten Anwendungen sind die zusätzlichen Verwendungen nicht relevant, es sei denn, Sie analysieren eine natürliche Sprache.

Als letzter Schritt gibt es uneingeschränkte Grammatiken . Zu diesem Zeitpunkt ist die Grammatik Turing-vollständig, sodass man nicht festlegen kann, wie lange es dauern wird, eine bestimmte Sprache zu analysieren, was für die meisten Parsing-Anwendungen unerwünscht ist. Die Extraleistung wird fast nie benötigt. Wenn Sie die gesamte Leistung nutzen möchten, steht Ihnen die Sprachmaschine zur Verfügung.

Schließlich ist die Implementierung eines eigenen Parser-Generators keine triviale Angelegenheit, insbesondere, um eine schnelle Implementierung zu erreichen. Ich persönlich habe gerade meine eigene Version von flex (dem Lexer-Generator) fertiggestellt, und obwohl dies eine Übung für relativ einfache algorithmische Probleme zu sein schien, wurde es ziemlich kompliziert, die richtigen zu finden, insbesondere, als ich versuchte, Unicode zu unterstützen. Ziehen Sie in Betracht, eine bereits vorhandene Implementierung zu verwenden, anstatt Ihre eigene zu schreiben.

Eine Veröffentlichung auf der ICFP 2010 in diesem Jahr, Total Parser Combinators , beschreibt eine nachweislich terminierende Parser-Kombinator-Bibliothek und stellt außerdem fest, dass in dieser Bibliothek "Parser-Kombinatoren so aussagekräftig wie möglich sind", da die Terminierung des Parsers garantiert ist. Leider kann ich mich nicht an die Erklärung erinnern, die der Autor für das gegeben hat, was "so ausdrucksvoll wie möglich" bedeutet, aber es scheint auf jeden Fall relevant für Ihre Frage nach "Macht" zu sein.

Wenn Sie nicht nur kontextfreie Grammatiken zum Parsen von Programmiersprachen verwenden möchten, sondern auch die Polynomzeit verwenden möchten, können Sie Ausdrucksgrammatiken oder Boolesche Grammatiken analysieren. Letztere sind auch in LL- und LR-Varianten verfügbar (siehe hier ). In der formalen Sprachtheorie werden auch die leistungsfähigen, aber in linearer Zeit erkennbaren Church-Rosser-Sprachen untersucht, mir sind jedoch keine implementierten Parser-Generatoren für diese bekannt.

In der Verarbeitung natürlicher Sprache sind die Geschmäcker unterschiedlich, beispielsweise spielt der Umgang mit Mehrdeutigkeiten (auch: inhärente Mehrdeutigkeiten) und der freien Wortreihenfolge eine sehr wichtige Rolle. Hier können Ihnen die Stichwörter " leicht kontextsensitive Sprachen" und " Automaten neu starten" beim Lesen helfen.

Parser-Generator-Tools:

ANTLR ist sehr gut. Alternativ können Sie sich JavaCC anschauen