Wann sollte ein Parser-Kombinator verwendet werden? Wann benutzt man einen Parser Generator?

59

Ich habe mich in letzter Zeit intensiv mit der Welt der Parser befasst und wollte meine eigene Programmiersprache erstellen.

Ich fand jedoch heraus, dass es zwei unterschiedliche Ansätze zum Schreiben von Parsern gibt: Parser-Generatoren und Parser-Kombinatoren.

Interessanterweise konnte ich keine Ressource finden, die erklärt, in welchen Fällen welcher Ansatz besser ist. Vielmehr kannten viele Ressourcen (und Personen), die ich zu dem Thema befragte, den anderen Ansatz nicht, sondern erklärten nur ihren Ansatz als den Ansatz und nannten den anderen überhaupt nicht:

Einfache Übersicht:

Parser-Generator

Ein Parser-Generator nimmt eine Datei, die in einer DSL geschrieben ist, die ein Dialekt der Extended Backus-Naur-Form ist , und wandelt sie in Quellcode um, der dann (beim Kompilieren) zu einem Parser für die in dieser DSL beschriebene Eingabesprache werden kann.

Dies bedeutet, dass der Kompilierungsprozess in zwei separaten Schritten durchgeführt wird. Interessanterweise sind Parser-Generatoren selbst auch Compiler (und viele von ihnen hosten sich tatsächlich selbst ).

Parser-Kombinator

Ein Parser-Kombinator beschreibt einfache Funktionen, sogenannte Parser , die alle eine Eingabe als Parameter verwenden und versuchen, die ersten Zeichen dieser Eingabe zu entfernen, wenn sie übereinstimmen. Sie geben ein Tupel zurück (result, rest_of_input), das resultmöglicherweise leer ist (z. B. niloder Nothing), wenn der Parser nichts von dieser Eingabe analysieren konnte. Ein Beispiel wäre ein digitParser. Andere Parser können natürlich Parser als erste Argumente verwenden (das letzte Argument bleibt weiterhin die Eingabezeichenfolge), um sie zu kombinieren : z. B. many1versucht sie, so oft wie möglich mit einem anderen Parser übereinzustimmen (aber mindestens einmal, oder es schlägt selbst fehl).

Sie können jetzt natürlich kombinieren (komponieren) digitund beispielsweise many1einen neuen Parser erstellen integer.

Es kann auch ein übergeordneter choiceParser geschrieben werden, der eine Liste von Parsern aufnimmt und diese nacheinander ausprobiert.

Auf diese Weise können sehr komplexe Lexer / Parser erstellt werden. In Sprachen, die das Überladen von Operatoren unterstützen, ähnelt dies auch sehr stark EBNF, obwohl es immer noch direkt in der Zielsprache geschrieben ist (und Sie alle Funktionen der gewünschten Zielsprache verwenden können).

Einfache Unterschiede

Sprache:

  • Parser-Generatoren sind in einer Kombination aus dem EBNF-ischen DSL und dem Code geschrieben, den diese Anweisungen generieren sollen, wenn sie übereinstimmen.
  • Parser-Kombinatoren werden direkt in der Zielsprache geschrieben.

Lexing / Parsing:

  • Parser-Generatoren unterscheiden sich sehr stark zwischen dem 'Lexer' (der eine Zeichenfolge in Token aufteilt, die markiert werden können, um den Wert anzuzeigen, mit dem wir es zu tun haben) und dem 'Parser' (der die Ausgabeliste der Token aus dem Lexer entnimmt) und versucht, sie zu kombinieren, um einen abstrakten Syntaxbaum zu bilden).
  • Parser-Kombinatoren haben / brauchen diese Unterscheidung nicht; In der Regel erledigen einfache Parser die Arbeit des "Lexers", und die Parser auf höherer Ebene rufen diese einfacheren auf, um zu entscheiden, welche Art von AST-Knoten erstellt werden soll.

Frage

Aber selbst angesichts dieser Unterschiede (und diese Liste der Unterschiede ist wahrscheinlich noch lange nicht vollständig!) Kann ich keine fundierte Entscheidung treffen, wann ich welche verwenden soll. Ich verstehe nicht, welche Auswirkungen / Konsequenzen diese Unterschiede haben.

Welche Problemeigenschaften deuten darauf hin, dass ein Problem mit einem Parser-Generator besser gelöst werden könnte? Welche Problemeigenschaften deuten darauf hin, dass ein Problem mit einem Parser-Kombinator besser gelöst werden kann?

Qqwy
quelle
4
Es gibt mindestens zwei weitere Möglichkeiten, Parser zu implementieren, die Sie nicht erwähnt haben: Parser-Interpreter (ähnlich wie Parser-Generatoren, außer dass die Parsersprache nicht in C oder Java kompiliert wird, sondern direkt ausgeführt wird) und einfach das Schreiben der Parser von Hand. Das Schreiben des Parsers von Hand ist die bevorzugte Implementierungsform für viele moderne produktionsreife, industrietaugliche Sprachimplementierungen (z. B. GCC, Clang javac, Scala). Es gibt Ihnen die größte Kontrolle über den internen Parser-Status, was Ihnen hilft, gute Fehlermeldungen zu generieren (was in den letzten Jahren…
Jörg W Mittag
3
… Hat für Sprachimplementierer einen sehr hohen Stellenwert). Außerdem sind viele vorhandene Parser-Generatoren / Interpreter / Kombinatoren nicht wirklich darauf ausgelegt, die vielfältigen Anforderungen zu erfüllen, die moderne Sprachimplementierungen erfüllen müssen. Beispielsweise verwenden viele moderne Sprachimplementierungen denselben Code für die Stapelkompilierung, die IDE-Hintergrundkompilierung, die Syntaxhervorhebung, das automatisierte Refactoring, die intelligente Codevervollständigung, die automatische Dokumentationserstellung, das automatische Diagramm usw. Scala verwendet den Compiler sogar für die Laufzeitreflexion und sein Makrosystem . Viele bestehende Parser ...
Jörg W Mittag
1
… Frameworks sind nicht flexibel genug, um damit umzugehen. Beachten Sie auch, dass es Parser-Frameworks gibt, die nicht auf EBNF basieren. ZB packrat Parser für das Parsing von Ausdrucksgrammatiken .
Jörg W Mittag
2
Ich denke, es hängt stark von der Sprache ab, die Sie zu kompilieren versuchen. Um welchen Typ handelt es sich (LR, ...)?
Qwerty_so
1
Ihre obige Annahme basiert auf BNF, das normalerweise einfach mit einer Lexer / LR-Parser-Kombination kompiliert wird. Sprachen basieren jedoch nicht unbedingt auf LR-Grammatiken. Also, welches ist deins, das du kompilieren willst?
qwerty_so

Antworten:

59

Ich habe in den letzten Tagen viel recherchiert, um besser zu verstehen, warum diese getrennten Technologien existieren und wo ihre Stärken und Schwächen liegen.

Einige der bereits vorhandenen Antworten wiesen auf einige ihrer Unterschiede hin, gaben jedoch nicht das vollständige Bild wieder und schienen einigermaßen unvoreingenommen zu sein, weshalb diese Antwort verfasst wurde.

Diese Darstellung ist lang, aber wichtig. ertrage es mit mir (oder wenn du ungeduldig bist, scrolle bis zum Ende, um ein Flussdiagramm zu sehen).


Um die Unterschiede zwischen Parser-Kombinatoren und Parser-Generatoren zu verstehen, muss man zuerst den Unterschied zwischen den verschiedenen Arten von Parsing verstehen, die existieren.

Parsing

Parsing ist der Prozess der Analyse einer Zeichenfolge nach einer formalen Grammatik. (In der Informatik wird Parsing verwendet, um einem Computer zu ermöglichen, in einer Sprache geschriebenen Text zu verstehen, wobei normalerweise ein Analysebaum erstellt wird , der den geschriebenen Text darstellt und die Bedeutung der verschiedenen geschriebenen Teile in jedem Knoten des Baums speichert. Dieser Analysebaum kann dann für verschiedene Zwecke verwendet werden, z. B. zum Übersetzen in eine andere Sprache (in vielen Compilern verwendet), zum direkten Interpretieren der schriftlichen Anweisungen (SQL, HTML), sodass Tools wie Linters ihre Arbeit erledigen können usw. Manchmal ist ein Analysebaum nicht explizitgeneriert, sondern die Aktion, die an jedem Knotentyp im Baum ausgeführt werden soll, wird direkt ausgeführt. Dies erhöht die Effizienz, aber unter Wasser existiert immer noch ein impliziter Analysebaum.

Das Parsen ist ein Problem, das rechnerisch schwierig ist. Zu diesem Thema wurde über 50 Jahre lang geforscht, aber es gibt noch viel zu lernen.

Grob gesagt gibt es vier allgemeine Algorithmen, mit denen ein Computer Eingaben analysieren kann:

  • LL-Analyse. (Kontextfreies Parsing von oben nach unten.)
  • LR-Analyse. (Kontextfreies Parsing von unten nach oben.)
  • PEG + Packrat-Analyse.
  • Earley Parsing.

Beachten Sie, dass diese Arten des Parsens sehr allgemeine theoretische Beschreibungen sind. Es gibt mehrere Möglichkeiten, jeden dieser Algorithmen auf physischen Maschinen mit unterschiedlichen Kompromissen zu implementieren.

LL und LR können nur kontextfreie Grammatiken betrachten (das heißt, der Kontext um die geschriebenen Token ist nicht wichtig, um zu verstehen, wie sie verwendet werden).

PEG- / Packrat-Parsing und Earley-Parsing werden viel seltener verwendet: Earley-Parsing kann viel mehr Grammatiken verarbeiten (einschließlich solcher, die nicht unbedingt kontextfrei sind), ist jedoch weniger effizient (wie der Drache behauptet) Buch (Abschnitt 4.1.1); Ich bin nicht sicher, ob diese Behauptungen noch korrekt sind). Syntaxanalyse der Ausdrucksgrammatik + Packrat-Syntaxanalyse ist eine Methode, die relativ effizient ist und auch mehr Grammatiken als LL und LR verarbeiten kann, aber Mehrdeutigkeiten verbirgt, wie im Folgenden kurz erläutert wird.

LL (von links nach rechts, Ableitung ganz links)

Dies ist möglicherweise die natürlichste Art, über das Parsen nachzudenken. Die Idee ist, sich das nächste Token in der Eingabezeichenfolge anzusehen und dann zu entscheiden, welcher von möglicherweise mehreren möglichen rekursiven Aufrufen zum Generieren einer Baumstruktur verwendet werden soll.

Dieser Baum wird von oben nach unten erstellt, dh, wir beginnen am Stamm des Baums und lesen die Grammatikregeln auf die gleiche Weise wie in der Eingabezeichenfolge. Es kann auch als Konstruktion eines 'Postfix'-Äquivalents für den' Infix'-Token-Stream angesehen werden, der gelesen wird.

Parser, die Parsing im LL-Stil ausführen, können so geschrieben werden, dass sie der angegebenen ursprünglichen Grammatik sehr ähnlich sind. Dies macht es relativ einfach, sie zu verstehen, zu debuggen und zu verbessern. Klassische Parser-Kombinatoren sind nichts anderes als "Lego-Teile", die zu einem Parser im LL-Stil zusammengesetzt werden können.

LR (von links nach rechts, Ableitung ganz rechts)

LR-Parsing läuft umgekehrt von unten nach oben: Bei jedem Schritt werden die obersten Elemente auf dem Stapel mit der Grammatikliste verglichen, um festzustellen, ob sie auf eine übergeordnete Regel in der Grammatik reduziert werden können . Wenn nicht, wird das nächste Token aus dem Eingabestream verschoben und auf den Stapel gelegt.

Ein Programm ist korrekt, wenn wir am Ende einen einzelnen Knoten auf dem Stapel haben, der die Ausgangsregel aus unserer Grammatik darstellt.

Schau voraus

In beiden Systemen ist es manchmal erforderlich, mehr Token aus der Eingabe herauszusuchen, bevor entschieden werden kann, welche Auswahl getroffen werden soll. Dies ist die (0), (1), (k)oder (*)-Syntax Sie sehen , nachdem die Namen dieser beiden allgemeinen Algorithmen, wie LR(1) oder LL(k). ksteht in der Regel für "so viel wie Ihre Grammatik benötigt", während in der *Regel für "dieser Parser führt Backtracking durch" steht, das leistungsfähiger / einfach zu implementieren ist, aber einen viel höheren Speicher- und Zeitverbrauch aufweist als ein Parser, der einfach weiter analysieren kann linear.

Beachten Sie, dass Parser im LR-Stil bereits viele Token auf dem Stapel haben, wenn sie sich entscheiden, nach vorne zu schauen, sodass sie bereits weitere Informationen zum Versenden haben. Dies bedeutet, dass sie für dieselbe Grammatik häufig weniger Vorausschau benötigen als einen Parser im LL-Stil.

LL vs. LR: Mehrdeutigkeit

Wenn man die beiden obigen Beschreibungen liest, mag man sich fragen, warum es eine Analyse im LR-Stil gibt, da eine Analyse im LL-Stil viel natürlicher erscheint.

Das Parsen im LL-Stil hat jedoch ein Problem: Linke Rekursion .

Es ist sehr natürlich, eine Grammatik wie folgt zu schreiben:

expr ::= expr '+' expr | term term ::= integer | float

Ein Parser im LL-Stil bleibt jedoch beim Parsen dieser Grammatik in einer Endlosschleife stecken: Wenn Sie die am weitesten links stehende Möglichkeit der exprRegel ausprobieren, wird diese Regel erneut wiederholt, ohne dass Eingaben erforderlich sind.

Es gibt Möglichkeiten, dieses Problem zu beheben. Am einfachsten ist es, Ihre Grammatik so umzuschreiben, dass diese Art der Rekursion nicht mehr auftritt:

expr ::= term expr_rest expr_rest ::= '+' expr | ϵ term ::= integer | float (Hier steht ϵ für die 'leere Zeichenkette')

Diese Grammatik ist jetzt richtig rekursiv. Beachten Sie, dass es sofort viel schwieriger zu lesen ist.

In der Praxis kann eine Linksrekursion indirekt mit vielen anderen dazwischen liegenden Schritten auftreten. Dies macht es schwierig, nach etwas Ausschau zu halten. Aber der Versuch, es zu lösen, erschwert das Lesen Ihrer Grammatik.

In Abschnitt 2.5 des Drachenbuchs heißt es:

Wir scheinen einen Konflikt zu haben: Einerseits brauchen wir eine Grammatik, die das Übersetzen erleichtert, andererseits brauchen wir eine deutlich andere Grammatik, die das Parsen erleichtert. Die Lösung besteht darin, mit der Grammatik für eine einfache Übersetzung zu beginnen und sie sorgfältig zu transformieren, um das Parsen zu erleichtern. Durch Eliminieren der linken Rekursion können wir eine Grammatik erhalten, die zur Verwendung in einem prädiktiven rekursiven Abstammungsübersetzer geeignet ist.

Parser im LR-Stil haben nicht das Problem dieser Linksrekursion, da sie den Baum von unten nach oben erstellen. Die mentale Übersetzung einer Grammatik wie oben in einen Parser im LR-Stil (der häufig als endlicher Automat implementiert wird )
ist jedoch sehr schwierig (und fehleranfällig), da es häufig Hunderte oder Tausende von Zuständen gibt Zustandsübergänge zu berücksichtigen. Aus diesem Grund werden Parser im LR-Stil normalerweise von einem Parser-Generator generiert , der auch als "Compiler-Compiler" bezeichnet wird.

So lösen Sie Mehrdeutigkeiten

Wir haben oben zwei Methoden zur Lösung von Linksrekursions-Ambiguitäten gesehen: 1) Neuschreiben der Syntax 2) Verwenden eines LR-Parsers.

Es gibt aber auch andere Arten von Unklarheiten, die schwerer zu lösen sind: Was ist, wenn zwei verschiedene Regeln gleichzeitig gleichermaßen anwendbar sind?

Einige gebräuchliche Beispiele sind:

Sowohl Parser im LL-Stil als auch im LR-Stil haben Probleme damit. Probleme mit dem Parsen arithmetischer Ausdrücke können durch Einführen von Operatorpriorität gelöst werden. In ähnlicher Weise können andere Probleme wie das Dangling Else gelöst werden, indem man ein Vorrangverhalten auswählt und daran festhält. (In C / C ++ zum Beispiel gehört der Dangling else immer zum nächsten 'if').

Eine andere "Lösung" für dieses Problem ist die Verwendung der Parser Expression Grammar (PEG): Diese ähnelt der oben verwendeten BNF-Grammatik, aber wählen Sie im Zweideutigkeitsfall immer die erste aus. Natürlich wird das Problem dadurch nicht wirklich "gelöst", sondern es wird ausgeblendet, dass tatsächlich eine Mehrdeutigkeit vorliegt: Die Endbenutzer wissen möglicherweise nicht, welche Auswahl der Parser vornimmt, und dies kann zu unerwarteten Ergebnissen führen.

Weitere Informationen, die viel ausführlicher sind als dieser Beitrag, einschließlich der Frage, warum es im Allgemeinen unmöglich ist zu wissen, ob Ihre Grammatik keine Mehrdeutigkeiten aufweist, und die Auswirkungen davon sind der wunderbare Blog-Artikel LL und LR im Kontext: Warum analysieren? Werkzeuge sind schwer . Ich kann es nur empfehlen. Es hat mir sehr geholfen, all die Dinge zu verstehen, über die ich gerade spreche.

50 Jahre Forschung

Aber das Leben geht weiter. Es stellte sich heraus, dass "normale" Parser im LR-Stil, die als Automaten mit endlichen Zuständen implementiert wurden, oft Tausende von Zuständen und Übergängen benötigten, was ein Problem bei der Programmgröße darstellte. Daher wurden Varianten wie Simple LR (SLR) und LALR (Look-Ahead LR) geschrieben, die andere Techniken kombinieren, um den Automaten zu verkleinern und den Speicherbedarf der Parserprogramme zu verringern.

Eine andere Möglichkeit, die oben aufgeführten Unklarheiten zu lösen, besteht darin, verallgemeinerte Techniken zu verwenden , bei denen im Falle einer Unklarheit beide Möglichkeiten beibehalten und analysiert werden: Entweder kann es nicht gelingen, die Zeile zu analysieren (in diesem Fall ist die andere Möglichkeit die 'korrekt' eins) und beide zurückgeben (und auf diese Weise zeigen, dass eine Mehrdeutigkeit vorliegt), falls beide korrekt sind.

Interessanterweise hat sich nach der Beschreibung des Generalized LR- Algorithmus herausgestellt, dass ein ähnlicher Ansatz zum Implementieren von Generalized LL-Parsern verwendet werden kann , der ähnlich schnell ist ($ O (n ^ 3) $ Zeitkomplexität für mehrdeutige Grammatiken, $ O (n) $ für völlig eindeutige Grammatiken, wenn auch mit mehr Buchhaltung als ein einfacher (LA) LR-Parser (was einen höheren Konstantenfaktor bedeutet), aber wiederum ermöglichen, dass ein Parser in einem rekursiven Abstiegsstil (von oben nach unten) geschrieben wird, der viel natürlicher ist zu schreiben und zu debuggen.

Parser-Kombinatoren, Parser-Generatoren

Mit dieser langen Darstellung kommen wir nun zum Kern der Frage:

Was ist der Unterschied zwischen Parser-Kombinatoren und Parser-Generatoren und wann sollte einer über dem anderen verwendet werden?

Es sind wirklich verschiedene Arten von Tieren:

Parser-Kombinatoren wurden erstellt, weil Parser von oben nach unten geschrieben wurden und festgestellt wurde, dass viele von ihnen eine Menge gemeinsam haben .

Parser-Generatoren wurden erstellt, weil die Leute nach Parsern suchten, die nicht die Probleme hatten, die Parser im LL-Stil hatten (dh Parser im LR-Stil), was sich als sehr schwierig von Hand erwies. Übliche sind Yacc / Bison, die (LA) LR implementieren.

Interessanterweise ist die Landschaft heutzutage etwas durcheinander:

  • Es ist möglich, Parser-Kombinatoren zu schreiben , die mit dem GLL- Algorithmus arbeiten , wodurch die Mehrdeutigkeitsprobleme der klassischen LL-Parser behoben werden, während sie genauso lesbar / verständlich sind wie alle Arten von Top-Down-Parsing.

  • Parser-Generatoren können auch für Parser im LL-Stil geschrieben werden. ANTLR macht genau das und verwendet andere Heuristiken (Adaptive LL (*)), um die Mehrdeutigkeiten, die klassische Parser im LL-Stil hatten, aufzulösen.

Im Allgemeinen ist es schwierig, einen LR-Parser-Generator zu erstellen und die Ausgabe eines (LA) LR-ähnlichen Parser-Generators zu debuggen, der auf Ihrer Grammatik ausgeführt wird, da Ihre ursprüngliche Grammatik in das "Inside-Out" -LR-Formular übersetzt wird. Auf der anderen Seite, Tools wie Yacc / Bison haben viele Jahre Optimierungen hatten, und eine Menge für die Verwendung in der freien Natur zu sehen ist , was bedeutet , dass jetzt viele Menschen es als betrachten die Art und Weise Parsing zu tun und sind skeptisch gegenüber neuen Ansätzen.

Welche Sie verwenden sollten, hängt davon ab, wie schwer Ihre Grammatik ist und wie schnell der Parser sein muss. Abhängig von der Grammatik kann eine dieser Techniken (/ Implementierungen der verschiedenen Techniken) schneller sein, einen geringeren Speicherbedarf aufweisen, einen geringeren Speicherbedarf aufweisen oder erweiterbarer oder leichter zu debuggen sein als die anderen. Ihr Kilometerstand kann variieren .

Randnotiz: Zum Thema Lexikalische Analyse.

Die lexikalische Analyse kann sowohl für Parser-Kombinatoren als auch für Parser-Generatoren verwendet werden. Die Idee ist, einen 'dummen' Parser zu haben, der sehr einfach zu implementieren ist (und daher schnell ist), der einen ersten Durchgang über Ihren Quellcode durchführt, beispielsweise das Wiederholen von Leerzeichen, Kommentaren usw. und möglicherweise das 'Tokenisieren' in einem sehr Grob gesagt die verschiedenen Elemente, die Ihre Sprache ausmachen.

Der Hauptvorteil ist, dass dieser erste Schritt den eigentlichen Parser sehr viel einfacher macht (und aus diesem Grund möglicherweise schneller). Der Hauptnachteil ist, dass Sie einen separaten Übersetzungsschritt haben und z. B. das Melden von Fehlern mit Zeilen- und Spaltennummern aufgrund der Entfernung von Leerzeichen schwieriger wird.

Ein Lexer ist letztendlich "nur" ein weiterer Parser und kann mit einer der oben genannten Techniken implementiert werden. Wegen seiner Einfachheit werden oft andere Techniken als für den Hauptparser verwendet, und zum Beispiel gibt es zusätzliche "Lexer-Generatoren".


Tl; Dr:

Hier ist ein Flussdiagramm, das für die meisten Fälle gilt: Bildbeschreibung hier eingeben

Qqwy
quelle
@Sjoerd Es ist in der Tat eine Menge Text, da es sich als sehr schwieriges Problem herausstellte. Wenn Sie wissen, wie ich den letzten Absatz klarer gestalten kann, bin ich gespannt: "Welche Sie verwenden sollten, hängt davon ab, wie schwer Ihre Grammatik ist und wie schnell der Parser sein muss. Abhängig von der Grammatik, Eine dieser Techniken (/ Implementierungen der verschiedenen Techniken) ist möglicherweise schneller, hat einen geringeren Speicherbedarf, einen geringeren Speicherbedarf oder ist erweiterbarer oder leichter zu debuggen als die anderen. Ihr Kilometerstand kann variieren. "
Qqwy
1
Die anderen Antworten sind viel kürzer und klarer und können viel besser beantworten.
Sjoerd
1
@Sjoerd der Grund, warum ich diese Antwort schrieb, war, dass die anderen Antworten das Problem zu stark vereinfachten, eine teilweise Antwort als vollständige Antwort darstellten und / oder in die Falle des anekdotischen Irrtums fielen . Die obige Antwort ist die Verkörperung der Diskussion, die Jörg W. Mittag, Thomas Killian und ich in den Kommentaren der Frage hatten, nachdem wir verstanden hatten, worüber sie sprachen und sie präsentierten, ohne Vorkenntnisse vorauszusetzen.
Qqwy
Auf jeden Fall habe ich der Frage ein tl; dr-Flussdiagramm hinzugefügt. Befriedigt dich das, @Sjoerd?
Qqwy
2
Parser-Kombinatoren können das Problem in der Tat nicht lösen, wenn Sie sie nicht verwenden. Es gibt mehr Kombinatoren als nur |das ist der springende Punkt. Das richtige Umschreiben exprist das noch prägnantere expr = term 'sepBy' "+"(wobei hier einfache Anführungszeichen Backticks ersetzen, um ein Funktions-Infix zu aktivieren, da bei Mini-Markdown kein Entweichen von Zeichen erforderlich ist). Im allgemeineren Fall gibt es auch den chainByKombinator. Mir ist klar, dass es schwierig ist, eine einfache Parsing-Aufgabe als Beispiel zu finden, die für PCs nicht gut geeignet ist, aber das ist wirklich ein starkes Argument für sie.
Steven Armstrong
8

Für Eingaben, die garantiert frei von Syntaxfehlern sind oder bei denen die syntaktische Korrektheit insgesamt in Ordnung ist, ist die Arbeit mit Parser-Kombinatoren viel einfacher, insbesondere in funktionalen Programmiersprachen. Dies sind Situationen wie das Programmieren von Rätseln, das Lesen von Datendateien usw.

Die Funktion, mit der Sie die Komplexität von Parser-Generatoren erhöhen möchten, sind Fehlermeldungen. Sie möchten Fehlermeldungen, die den Benutzer auf eine Zeile und eine Spalte verweisen und hoffentlich auch für einen Menschen verständlich sind. Es braucht viel Code, um das richtig zu machen, und die besseren Parser-Generatoren wie antlr können Ihnen dabei helfen.

Mit der automatischen Generierung können Sie jedoch nur so weit kommen, dass die meisten kommerziellen und langlebigen Open Source-Compiler ihre Parser manuell schreiben. Ich nehme an, wenn Sie sich dabei wohl gefühlt hätten, hätten Sie diese Frage nicht gestellt, und ich würde empfehlen, mit dem Parser-Generator zu arbeiten.

Karl Bielefeldt
quelle
2
Vielen Dank für Ihre Antwort! Warum ist es mit einem Parser-Generator einfacher, lesbare Fehlermeldungen zu erstellen als mit einem Parser-Kombinator? (Unabhängig davon, um welche Implementierung es sich speziell handelt) Ich weiß zum Beispiel, dass sowohl Parsec als auch Spirit Funktionen zum Drucken von Fehlermeldungen einschließlich Zeilen- und Spalteninformationen enthalten, sodass dies auf jeden Fall auch in Parser-Kombinatoren möglich erscheint.
Qqwy
Es ist nicht so, dass Sie mit Parser-Kombinatoren keine Fehlermeldungen ausgeben können, sondern dass ihre Vorteile weniger offensichtlich sind, wenn Sie Fehlermeldungen in die Mischung werfen. Machen Sie mit beiden Methoden eine relativ komplexe Grammatik und Sie werden sehen, was ich meine.
Karl Bielefeldt
Mit einem Parser-Kombinator können Sie per Definition nur die Fehlermeldung "Ab diesem Zeitpunkt wurde keine legale Eingabe gefunden" erhalten. Das sagt dir nicht wirklich, was los war. Theoretisch könnten die einzelnen Parser, die zu diesem Zeitpunkt aufgerufen wurden, Ihnen sagen, was erwartet wurde, und sie haben es NICHT gefunden, aber alles, was Sie tun könnten, ist, alles auszudrucken, was zu einer looooooangen Fehlermeldung führt.
John R. Strohm
1
Parser-Generatoren sind auch nicht gerade für ihre guten Fehlermeldungen bekannt, um ehrlich zu sein.
Miles Rout
Nicht standardmäßig, nein, aber sie haben bequemere Hooks zum Hinzufügen guter Fehlermeldungen.
Karl Bielefeldt
4

Sam Harwell, einer der Betreuer des ANTLR-Parsergenerators, schrieb kürzlich :

Ich habe festgestellt, dass [Kombinatoren] meine Anforderungen nicht erfüllen:

  1. ANTLR bietet mir Tools zum Verwalten von Dingen wie Mehrdeutigkeiten. Während der Entwicklung gibt es Tools, die mir mehrdeutige Analyseergebnisse anzeigen, damit ich diese Mehrdeutigkeiten in der Grammatik beseitigen kann. Zur Laufzeit kann ich die Mehrdeutigkeit ausnutzen, die sich aus unvollständigen Eingaben in der IDE ergibt, um genauere Ergebnisse bei Funktionen wie der Codevervollständigung zu erzielen.
  2. In der Praxis habe ich festgestellt, dass Parser-Kombinatoren nicht geeignet sind, meine Leistungsziele zu erreichen. Ein Teil davon geht zurück
  3. Wenn Analyseergebnisse für Funktionen wie Gliederung, Code-Vervollständigung und intelligenter Einzug verwendet werden, können sich geringfügige Änderungen an der Grammatik leicht auf die Genauigkeit dieser Ergebnisse auswirken. ANTLR bietet Tools, mit denen diese Fehlanpassungen in Kompilierungsfehler umgewandelt werden können, selbst in Fällen, in denen die Typen andernfalls kompiliert würden. Ich kann mit Sicherheit ein neues Sprachfeature erstellen, das sich auf die Grammatik auswirkt, da ich weiß, dass der gesamte zusätzliche Code, der die IDE bildet, von Anfang an eine umfassende Erfahrung für das neue Feature bietet. Mein Fork von ANTLR 4 (auf dem das C # -Ziel basiert) ist das einzige mir bekannte Tool, das versucht, diese Funktion bereitzustellen.

Parser-Kombinatoren sind im Grunde genommen ein cooles Spielzeug zum Spielen, aber sie sind einfach nicht dafür geeignet, ernsthafte Arbeit zu leisten.

Mason Wheeler
quelle
3

Wie Karl erwähnt, weisen Parsergeneratoren in der Regel eine bessere Fehlerberichterstattung auf. In Ergänzung:

  • Sie sind in der Regel schneller, da sich der generierte Code auf die Syntax spezialisieren und Sprungtabellen für den Lookahead generieren lässt.
  • Sie verfügen in der Regel über bessere Tools, um mehrdeutige Syntax zu identifizieren, Linksrekursionen zu entfernen, Fehlerzweige auszufüllen usw.
  • Sie neigen dazu, rekursive Definitionen besser zu handhaben.
  • Sie sind in der Regel robuster, da die Generatoren schon länger im Einsatz sind und mehr von der Kesselplatte für Sie tun, was die Wahrscheinlichkeit verringert, dass Sie es vermasseln.

Auf der anderen Seite haben Kombinatoren ihre eigenen Vorteile:

  • Sie sind im Code enthalten. Wenn sich Ihre Syntax zur Laufzeit ändert, können Sie die Dinge leichter mutieren.
  • Sie sind in der Regel einfacher zu binden und tatsächlich zu konsumieren (die Ausgabe von Parser-Generatoren ist in der Regel sehr allgemein und umständlich in der Verwendung).
  • Sie sind im Code enthalten, daher ist das Debuggen in der Regel etwas einfacher, wenn Ihre Grammatik nicht den Erwartungen entspricht.
  • Sie haben tendenziell eine flachere Lernkurve, da sie wie jeder andere Code funktionieren. Parser-Generatoren neigen dazu, ihre eigenen Macken zu haben, um zu lernen, wie man Dinge zum Laufen bringt.
Telastyn
quelle
Parser-Generatoren neigen dazu, im Vergleich zu handgeschriebenen LL-Parsern mit rekursiver Herkunft, die in der realen Welt verwendet werden, fürchterliche Fehler zu melden. Parser-Generatoren bieten selten Statustabellen-Übergangshooks an, die für eine gute Diagnose erforderlich sind. Aus diesem Grund verwendet fast jeder echte Compiler keine Parser-Kombinatoren oder Parser-Generatoren. LL rekursiv-anständige Parser sind trivial zu konstruieren, obwohl sie nicht als "saubere" PCs / PGs, sondern nützlicher sind.
Dhchdhd