Sind separate Parsing- und Lexing-Pässe eine gute Übung für Parser-Kombinatoren?

18

Als ich anfing, Parser-Kombinatoren zu verwenden, war meine erste Reaktion ein Gefühl der Befreiung von einer künstlichen Unterscheidung zwischen Parsing und Lexing. Plötzlich wurde alles nur noch analysiert!

Vor kurzem bin ich jedoch auf dieses Posting auf codereview.stackexchange gestoßen, das jemanden veranschaulicht, der diese Unterscheidung wieder herstellt. Zuerst dachte ich, dass dies sehr albern von ihnen war, aber dann führt die Tatsache, dass Funktionen in Parsec existieren, um dieses Verhalten zu unterstützen, mich selbst in Frage zu stellen.

Welche Vor- und Nachteile hat das Parsen eines bereits lexierten Streams in Parser-Kombinatoren?

Eli Frey
quelle
Könnte jemand das [Parser-Kombinator] -Tag hinzufügen?
Eli Frey

Antworten:

15

Unter Parsing verstehen wir am häufigsten die Analyse von kontextfreien Sprachen. Eine kontextfreie Sprache ist mächtiger als eine reguläre Sprache, daher kann der Parser (meistens) die Arbeit des lexikalischen Analysators sofort erledigen.

Dies ist jedoch a) ziemlich unnatürlich, b) oft ineffizient.

Für a), wenn ich daran denke , wie zum Beispiel ein ifAusdruck aussieht, denke ich , wenn expr DANN ausdr ELSE ausdr und nicht ‚i‘ ‚f‘, vielleicht ein paar Räume, dann ein beliebiges Zeichen ein Ausdruck mit beginnen, usw. Sie das bekommen Idee.

Für b) gibt es leistungsstarke Tools, mit denen lexikalische Entitäten wie Bezeichner, Literale, Klammern aller Art usw. ausgezeichnet erkannt werden können. Sie erledigen ihre Arbeit praktisch im Handumdrehen und bieten Ihnen eine schöne Oberfläche: eine Liste von Token. Keine Sorge mehr, Leerzeichen im Parser zu überspringen. Ihr Parser wird viel abstrakter, wenn es um Token und nicht um Zeichen geht.

Wenn Sie der Meinung sind, dass ein Parser mit Low-Level-Dingen beschäftigt sein sollte, warum dann überhaupt Zeichen verarbeiten? Man könnte es auch auf der Ebene der Bits schreiben! Sie sehen, ein solcher Parser, der auf der Bit-Ebene arbeitet, wäre fast unverständlich. Das Gleiche gilt für Charaktere und Marken.

Nur meine 2 Cent.

Ingo
quelle
3
Nur um der Präzision willen: Ein Parser kann immer die Aufgabe eines lexikalischen Analysators übernehmen.
Giorgio
Auch in Bezug auf die Effizienz: Ich bin nicht sicher, ob ein Parser weniger effizient (langsamer) wäre. Ich würde erwarten, dass die resultierende Grammatik eine Untergrammatik enthält, die eine reguläre Sprache beschreibt, und der Code für diese Untergrammatik wäre so schnell wie ein entsprechender lexikalischer Analysator. IMO ist der eigentliche Punkt (a): wie natürlich und intuitiv es ist, mit einem einfacheren, abstrakteren Parser zu arbeiten.
Giorgio
@Giorgio - Bezüglich deines 1. Kommentars: Du hast recht. Was ich hier im Sinn hatte, sind Fälle, in denen der Lexer pragmatisch etwas Arbeit leistet, die die Grammatik erleichtert, so dass man LALR (1) anstelle von LALR (2) verwenden kann.
Ingo
2
Ich habe nach weiteren Experimenten und Überlegungen meine Akzeptanz Ihrer Antwort aufgehoben. Es scheint, dass ihr zwei aus eurer Welt von Antlr et al. Kommt. In Anbetracht der erstklassigen Eigenschaften von Parser-Kombinatoren definiere ich häufig einfach einen Wrapper-Parser für meine Token-Parser, wobei jedes Token als einzelner Name in der Parser-Ebene verbleibt. Zum Beispiel würde Ihr Wenn-Beispiel so aussehen if = string "if" >> expr >> string "then" >> expr >> string "else" >> expr.
Eli Frey
1
Leistung ist immer noch eine offene Frage, ich werde einige Benchmarks machen.
Eli Frey
8

Jeder, der vorschlägt, dass das Trennen von Lexing und Parsing eine "gute Praxis" ist - da muss ich widersprechen -, bietet in vielen Fällen mehr Leistung, und die Auswirkungen auf die Leistung sind nicht so schlimm, wie sie in der Tabelle dargestellt werden andere Antworten (siehe Packrat ).

Dieser Ansatz ist hervorragend geeignet, wenn mehrere verschiedene Sprachen in einem einzigen Eingabestream gemischt werden müssen. Dies wird nicht nur durch die seltsame metaprogramming orientierten Sprachen wie benötigt Katahdin und gleichermaßen , aber für viel mehr Mainstream - Anwendungen als auch, wie Literarische Programmierung (Misch Latex und, sagen wir, C ++), unter Verwendung von HTML in Kommentaren, Füllung Javascript in HTML, und bald.

SK-Logik
quelle
In meiner Antwort schlug ich vor, dass es sich um eine "gute Praxis in bestimmten Kontexten" und nicht um eine "bessere Praxis in allen Kontexten" handelt.
Giorgio
5

Ein lexikalischer Analysator erkennt eine reguläre Sprache und ein Parser erkennt eine kontextfreie Sprache. Da jede reguläre Sprache auch kontextfrei ist (sie kann durch eine sogenannte rechtslineare Grammatik definiert werden ), kann ein Parser auch eine reguläre Sprache erkennen, und die Unterscheidung zwischen Parser und lexikalischem Analysator scheint eine unnötige Komplexität hinzuzufügen: einen einzelnen Kontext -freie Grammatik (Parser) könnte die Aufgabe eines Parsers und eines lexikalischen Analysators übernehmen.

Andererseits kann es nützlich sein, einige Elemente einer kontextfreien Sprache durch eine reguläre Sprache (und daher einen lexikalischen Analysator) zu erfassen, weil

  1. Diese Elemente werden häufig so häufig angezeigt, dass sie auf standardmäßige Weise behandelt werden können: Erkennen von Zahlen- und Zeichenfolgenliteralen, Schlüsselwörtern, Bezeichnern, Überspringen von Leerzeichen usw.
  2. Das Definieren einer regulären Sprache von Token vereinfacht die resultierende kontextfreie Grammatik, z. B. kann man anhand von Bezeichnern argumentieren, nicht anhand einzelner Zeichen, oder man kann Leerzeichen vollständig ignorieren, wenn sie für diese bestimmte Sprache nicht relevant sind.

Die Trennung von Parsing und lexikalischer Analyse bietet den Vorteil, dass Sie mit einer einfacheren kontextfreien Grammatik arbeiten und einige grundlegende (häufig routinemäßige) Aufgaben im lexikalischen Analysator (divide et impera) zusammenfassen können.

BEARBEITEN

Ich bin mit Parser-Kombinatoren nicht vertraut, daher bin ich mir nicht sicher, wie die obigen Überlegungen in diesem Zusammenhang gelten. Mein Eindruck ist, dass selbst wenn man mit Parser-Kombinatoren nur eine kontextfreie Grammatik hat, die Unterscheidung zwischen zwei Ebenen (lexikalische Analyse / Analyse) dazu beitragen könnte, diese Grammatik modularer zu gestalten. Wie bereits erwähnt, kann die untere Ebene für die lexikalische Analyse grundlegende wiederverwendbare Parser für Bezeichner, Literale usw. enthalten.

Giorgio
quelle
2
Lexemes fällt nicht von Natur aus in reguläre Grammatiken, sondern nach Konvention, da alle Lexer auf regulären Ausdrucksmaschinen basieren. Es schränkt die Ausdruckskraft der Sprachen ein, die Sie gestalten können.
SK-logic
1
Können Sie ein Beispiel für eine Sprache nennen, für die es angebracht wäre, Lexeme zu definieren, die nicht als reguläre Sprache beschrieben werden können?
Giorgio
1
In einigen der von mir erstellten domänenspezifischen Sprachen könnten Bezeichner beispielsweise TeX-Ausdrücke sein, die das hübsche Drucken des Codes vereinfachen, z. B. ein Ausdruck wie \alpha'_1 (K_0, \vec{T})\ alpha'_1, K_0 und \ vec {T}. sind Bezeichner.
SK-logic
1
Bei einer kontextfreien Grammatik können Sie immer ein nicht-terminales N nehmen und die daraus abgeleiteten Wörter als Einheiten behandeln, die für sich genommen eine nützliche Bedeutung haben (z. B. einen Ausdruck, einen Begriff, eine Zahl, eine Aussage). Dies kann unabhängig davon geschehen, wie Sie diese Einheit analysieren (Parser, Parser + Lexer usw.). IMO ist die Wahl eines Parsers + Lexers eher eine technische (wie man das Parsing implementiert) als eine semantische (was bedeuten die von Ihnen analysierten Quellcodeblöcke). Vielleicht übersehe ich etwas, aber die beiden Aspekte sind für mich rechtwinklig.
Giorgio
3
Daher stimme ich Ihnen zu: Wenn Sie einige beliebige Grundbausteine ​​( Lexeme ) definieren und diese mithilfe eines lexikalischen Analysators erkennen möchten, ist dies nicht immer möglich. Ich frage mich nur, ob dies das Ziel eines Lexers ist. Soweit ich weiß, ist das Ziel eines lexikalischen Analysators eher ein technisches: Dem Parser einige Details der Implementierung auf niedriger Ebene zu entziehen.
Giorgio
3

Lexing und Parsing sollten einfach getrennt werden, da sie unterschiedliche Komplexitäten aufweisen. Lexing ist ein DFA (deterministischer endlicher Automat) und ein Parser ist ein PDA (Push-Down-Automat). Dies bedeutet, dass das Parsen von Natur aus mehr Ressourcen verbraucht als das Lexen, und dass nur DFAs bestimmte Optimierungstechniken zur Verfügung stehen. Darüber hinaus ist das Schreiben einer endlichen Zustandsmaschine viel weniger komplex und einfacher zu automatisieren.

Sie sind verschwenderisch, wenn Sie einen Analysealgorithmus zum Lexieren verwenden.

DeadMG
quelle
Wenn Sie einen Parser verwenden, um eine lexikalische Analyse durchzuführen, würde der PDA den Stapel niemals verwenden. Er würde im Grunde genommen als DFA funktionieren: nur Eingaben verbrauchen und zwischen Zuständen wechseln. Ich bin nicht zu 100% sicher, aber ich denke, dass die Optimierungstechniken (Reduzierung der Anzahl von Zuständen), die auf einen DFA angewendet werden können, auch auf einen PDA angewendet werden können. Aber ja: Es ist einfacher, den lexikalischen Analysator als solchen zu schreiben, ohne ein leistungsfähigeres Werkzeug zu verwenden, und dann einen einfacheren Parser darüber zu schreiben.
Giorgio
Außerdem wird das Ganze dadurch flexibler und wartbarer. Angenommen, wir haben einen Parser für die Haskell-Sprache ohne die Layoutregel (dh mit Semikolons und geschweiften Klammern). Wenn wir ein separates Lexer haben, können wir die Layoutregeln jetzt hinzufügen, indem wir einen weiteren Durchgang über die Token durchführen und bei Bedarf geschweifte Klammern und Semikolons hinzufügen. Oder zum einfacheren Beispiel: Angenommen, wir haben mit einer Sprache begonnen, die nur ASCII-Zeichen in Bezeichnern unterstützt, und möchten jetzt Unicode-Buchstaben in Bezeichnern unterstützen.
Ingo
1
@Ingo, und warum müssten Sie es in einem separaten Lexer tun? Ziehen Sie diese Terminals einfach heraus.
SK-logic
1
@ SK-logic: Ich bin mir nicht sicher, ob ich deine Frage verstehe. Warum ein separater Lexer eine gute Wahl sein kann, habe ich in meinem Post versucht zu belegen.
Ingo
Giorgio, nein. Der Stack ist eine entscheidende Komponente eines normalen Parsers im LALR-Stil. Das Lexen mit einem Parser ist eine schreckliche Verschwendung von Speicher (sowohl statischer als auch dynamisch zugewiesener Speicher) und wird viel langsamer. Das Lexer / Parser-Modell ist effizient - benutze es :)
riwalk
1

Einer der Hauptvorteile von Separate Parse / Lex ist die Zwischendarstellung - der Token-Stream. Dies kann auf verschiedene Arten verarbeitet werden, die mit einem kombinierten lex / parse sonst nicht möglich wären.

Das heißt, ich habe festgestellt, dass ein guter, rekursiver Menschenverstand weniger kompliziert und einfacher zu handhaben ist als das Erlernen eines Parsergenerators und ich muss herausfinden, wie man die Schwäche des Grammatikers innerhalb der Regeln des Parsergenerators ausdrückt.

Sylvanaar
quelle
Könnten Sie mehr über Grammatiken erklären, die in einem vorgefertigten Stream leichter ausgedrückt werden als beim Parsen? Ich habe nur Erfahrung mit der Implementierung von Spielzeugsprachen und einigen wenigen Datenformaten. Vielleicht habe ich etwas verpasst. Haben Sie Leistungsmerkmale zwischen Ihren handgerollten RD-Parser / Lex-Combos und BNF-gespeisten (ich nehme an) Generatoren festgestellt?
Eli Frey