Sind Lexer und Parser theoretisch wirklich so unterschiedlich?
Es scheint in Mode zu sein, reguläre Ausdrücke zu hassen: Coding Horror , ein weiterer Blog-Beitrag .
Beliebte lexingbasierte Tools: pyictions , geshi oder prettify verwenden jedoch alle reguläre Ausdrücke. Sie scheinen alles zu lexen ...
Wann ist Lexing genug, wann brauchen Sie EBNF?
Hat jemand die von diesen Lexern produzierten Token mit Bison- oder Antlr-Parser-Generatoren verwendet?
Antworten:
Was Parser und Lexer gemeinsam haben:
Sie lesen Symbole eines Alphabets aus ihrer Eingabe.
Sie analysieren diese Symbole und versuchen, sie mit der Grammatik der Sprache abzugleichen, die sie verstanden haben.
Sie fügen den Sprachstücken, die sie finden, Semantik (Bedeutung) hinzu.
*
,==
,<=
,^
werden als "Operator" Token durch die C / C ++ Lexer klassifiziert werden.[number][operator][number]
,[id][operator][id]
,[id][operator][number][operator][number]
werden als „Ausdruck“ Nicht - Terminal durch den Parser C ++ / C klassifiziert werden.Sie können den erkannten Elementen eine zusätzliche Bedeutung (Daten) hinzufügen.
Sie alle produzieren auf ihrer Ausgabe einen richtigen Satz der Sprache, die sie erkennen.
[TXT][TAG][TAG][TXT][TAG][TXT]...
.Wie Sie sehen können, haben Parser und Tokenizer viel gemeinsam. Ein Parser kann ein Tokenizer für einen anderen Parser sein, der seine Eingabetoken als Symbole aus seinem eigenen Alphabet liest (Token sind einfach Symbole eines Alphabets), genauso wie Sätze aus einer Sprache alphabetische Symbole einer anderen höheren Ebene sein können Sprache. Wenn
*
und-
beispielsweise die Symbole des Alphabets sindM
(als "Morsecodesymbole"), können Sie einen Parser erstellen, der Zeichenfolgen dieser Punkte und Linien als im Morsecode codierte Buchstaben erkennt. Die Sätze in der Sprache "Morsecode" könnten Token für einen anderen Parser sein, für den diese Tokensind atomare Symbole seiner Sprache (zB "English Words" -Sprache). Und diese "englischen Wörter" könnten Token (Symbole des Alphabets) für einen übergeordneten Parser sein, der die Sprache "englische Sätze" versteht. Und all diese Sprachen unterscheiden sich nur in der Komplexität der Grammatik . Nichts mehr.Was ist also mit diesen "Chomsky-Grammatikstufen"? Nun, Noam Chomsky hat Grammatiken je nach Komplexität in vier Stufen eingeteilt:
Stufe 3: Regelmäßige Grammatiken
Sie reguläre Ausdrücke verwenden, das heißt, sie nur von den Symbolen des Alphabets bestehen kann (a
,b
), deren Verkettungen (ab
,aba
,bbb
etd.) Oder Alternativen (zBa|b
).Sie können als Finite-State-Automaten (FSA) wie NFA (Nondeterministic Finite Automaton) oder besser DFA (Deterministic Finite Automaton) implementiert werden.
Normale Grammatiken können nicht mit verschachtelter Syntax umgehen , z. B. richtig verschachtelte / übereinstimmende Klammern
(()()(()()))
, verschachtelte HTML / BBcode-Tags, verschachtelte Blöcke usw. Dies liegt daran, dass Zustandsautomaten unendlich viele Zustände haben müssen, um unendlich viele Verschachtelungsebenen verarbeiten zu können.Stufe 2: Kontextfreie Grammatiken
Sie können verschachtelte, rekursive, selbstähnliche Zweige in ihren Syntaxbäumen haben, sodass sie gut mit verschachtelten Strukturen umgehen können.Sie können als Zustandsautomat mit Stapel implementiert werden. Dieser Stapel wird verwendet, um die Verschachtelungsebene der Syntax darzustellen. In der Praxis werden sie normalerweise als Top-Down-Parser mit rekursivem Abstieg implementiert, der den Prozeduraufrufstapel der Maschine verwendet, um die Verschachtelungsebene zu verfolgen, und rekursiv aufgerufene Prozeduren / Funktionen für jedes nicht-terminale Symbol in ihrer Syntax verwendet.
Sie können jedoch nicht mit einer kontextsensitiven Syntax umgehen . Wenn Sie beispielsweise einen Ausdruck haben
x+3
und dies in einem Kontext derx
Name einer Variablen und in einem anderen Kontext der Name einer Funktion usw. sein kann.Stufe 1: Kontextsensitive Grammatiken
Stufe 0: Uneingeschränkte Grammatik
Wird auch als rekursiv aufzählbare Grammatik bezeichnet.
quelle
STMT_END
in Ihrer Syntax (für den Parser) ein Terminalsymbol verwenden , um das Ende von Anweisungen zu kennzeichnen. Jetzt können Sie ein Token mit demselben Namen verknüpfen lassen, das vom Lexer generiert wird. Sie können jedoch das tatsächliche Lexem ändern, für das es steht. Z.B. Sie können festlegen ,STMT_END
wie;
C / C ++ haben - wie Quellcode. Oder Sie können es so definierenend
, dass es dem Pascal-Stil ähnelt. Oder Sie können es so definieren, dass'\n'
die Anweisung nur mit dem Zeilenende endet, wie in Python. Die Syntax der Anweisung (und des Parsers) bleibt jedoch unverändert :-) Nur der Lexer muss geändert werden.Ja, sie unterscheiden sich theoretisch und in der Umsetzung sehr.
Lexer werden verwendet, um "Wörter" zu erkennen, aus denen Sprachelemente bestehen, da die Struktur solcher Wörter im Allgemeinen einfach ist. Reguläre Ausdrücke beherrschen diese einfachere Struktur sehr gut, und es gibt sehr leistungsstarke Matching-Engines für reguläre Ausdrücke, die zum Implementieren von Lexern verwendet werden.
Parser werden verwendet, um die "Struktur" von Sprachphrasen zu erkennen. Eine solche Struktur geht im Allgemeinen weit über das hinaus, was "reguläre Ausdrücke" erkennen können. Daher benötigt man "kontextsensitive" Parser, um eine solche Struktur zu extrahieren. Kontextsensitive Parser sind schwer zu erstellen, daher besteht der technische Kompromiss darin, "kontextfreie" Grammatiken zu verwenden und den Parsern ("Symboltabellen" usw.) Hacks hinzuzufügen, um den kontextsensitiven Teil zu verarbeiten.
Weder die Lexing- noch die Parsing-Technologie werden wahrscheinlich bald verschwinden.
Sie können vereinheitlicht werden, indem entschieden wird, die "Parsing" -Technologie zum Erkennen von "Wörtern" zu verwenden, wie dies derzeit von sogenannten scannerlosen GLR-Parsern untersucht wird. Dies hat Laufzeitkosten zur Folge, da Sie allgemeinere Maschinen für häufig auftretende Probleme einsetzen, für die dies nicht erforderlich ist, und in der Regel die Kosten dafür übernehmen. Wenn Sie viele freie Zyklen haben, spielt dieser Overhead möglicherweise keine Rolle. Wenn Sie viel Text verarbeiten, spielt der Overhead eine Rolle, und klassische Parser für reguläre Ausdrücke werden weiterhin verwendet.
quelle
EBNF trägt wirklich nicht viel zur Leistungsfähigkeit von Grammatiken bei. Es ist nur eine Annehmlichkeit / Abkürzung Notation / "syntaktischer Zucker" über die Standard-Grammatikregeln von Chomsky's Normal Form (CNF). Zum Beispiel die EBNF-Alternative:
Sie können in CNF erreichen, indem Sie einfach jede alternative Produktion separat auflisten:
Das optionale Element von EBNF:
Sie können in CNF eine nullbare Produktion erzielen, dh eine , die durch eine leere Zeichenfolge ersetzt werden kann (hier nur durch leere Produktion gekennzeichnet; andere verwenden Epsilon oder Lambda oder einen gekreuzten Kreis):
Eine Produktion in einer Form wie der letzten
B
oben wird als "Löschen" bezeichnet, da sie alles löschen kann, wofür sie in anderen Produktionen steht (Produkt eine leere Zeichenfolge anstelle von etwas anderem).Null-oder-mehr-Wiederholung von EBNF:
Sie können Obtan verwenden, indem Sie eine rekursive Produktion verwenden, dh eine, die sich irgendwo darin einbettet. Dies kann auf zwei Arten erfolgen. Die erste ist die linke Rekursion (die normalerweise vermieden werden sollte, da Parser für rekursiven Abstieg von oben nach unten sie nicht analysieren können):
In dem Wissen, dass nur eine leere Zeichenfolge (letztendlich) gefolgt von null oder mehr
A
s generiert wird , kann dieselbe Zeichenfolge ( aber nicht dieselbe Sprache! ) Mit der rechten Rekursion ausgedrückt werden :Und wenn es
+
um eine oder mehrere Wiederholungen von EBNF geht:Dies kann durch Ausklammern eines
A
und Verwendung*
wie zuvor erfolgen:was Sie in CNF als solches ausdrücken können (ich verwende hier die richtige Rekursion; versuchen Sie, die andere selbst als Übung herauszufinden):
Wenn Sie das wissen, können Sie jetzt wahrscheinlich eine Grammatik für einen regulären Ausdruck (dh eine reguläre Grammatik ) als eine Grammatik erkennen, die in einer einzelnen EBNF-Produktion ausgedrückt werden kann, die nur aus Terminalsymbolen besteht. Im Allgemeinen können Sie reguläre Grammatiken erkennen, wenn Sie ähnliche Produktionen sehen:
Das heißt, Sie verwenden nur leere Zeichenfolgen, Terminalsymbole, einfache Nicht-Terminals für Ersetzungen und Statusänderungen und verwenden nur die Rekursion, um eine Wiederholung zu erzielen (Iteration, die nur lineare Rekursion ist - die nicht baumartig verzweigt). Nichts weiter fortgeschrittenes, dann sind Sie sicher, dass es sich um eine reguläre Syntax handelt, und Sie können dafür nur Lexer verwenden.
Wenn Ihre Syntax jedoch die Rekursion auf nicht triviale Weise verwendet, um baumartige, selbstähnliche, verschachtelte Strukturen wie die folgende zu erzeugen:
dann können Sie leicht erkennen, dass dies nicht mit regulären Ausdrücken möglich ist, da Sie es in keiner Weise in eine einzige EBNF-Produktion auflösen können; Sie werden am Ende auf
S
unbestimmte Zeit ersetzen , was immer ein weiteresa
s undb
s auf beiden Seiten hinzufügt . Lexer (genauer gesagt: Finite-State-Automaten, die von Lexern verwendet werden) können nicht bis zu einer beliebigen Zahl zählen (sie sind endlich, erinnerst du dich?), Daher wissen sie nicht, wie vielea
s vorhanden waren, um sie gleichmäßig mit so vielenb
s abzugleichen. Grammatiken wie diese werden (zumindest) als kontextfreie Grammatiken bezeichnet und erfordern einen Parser.Kontextfreie Grammatiken sind bekanntermaßen zum Parsen bekannt, daher werden sie häufig zur Beschreibung der Syntax von Programmiersprachen verwendet. Aber es gibt noch mehr. Manchmal ist eine allgemeinere Grammatik erforderlich - wenn Sie unabhängig voneinander mehr Dinge gleichzeitig zählen müssen. Wenn Sie beispielsweise eine Sprache beschreiben möchten, in der runde Klammern und eckige Klammern verwendet werden können, diese jedoch korrekt miteinander gepaart werden müssen (Klammern mit Klammern, rund mit rund). Diese Art der Grammatik wird als kontextsensitiv bezeichnet . Sie erkennen es daran, dass links (vor dem Pfeil) mehr als ein Symbol angezeigt wird. Beispielsweise:
Sie können sich diese zusätzlichen Symbole auf der linken Seite als "Kontext" für die Anwendung der Regel vorstellen. Es könnte einige Voraussetzungen sein, Nachbedingungen usw. Zum Beispiel wird die obige Regel ersetzen
R
inS
, aber nur , wenn es zwischendurchA
undB
diejenigen zu verlassenA
undB
sie unverändert. Diese Art von Syntax ist wirklich schwer zu analysieren, da sie eine vollständige Turing-Maschine benötigt. Es ist eine ganz andere Geschichte, also werde ich hier enden.quelle
Um die gestellte Frage zu beantworten (ohne übermäßig zu wiederholen, was in anderen Antworten erscheint)
Lexer und Parser sind nicht sehr unterschiedlich, wie aus der akzeptierten Antwort hervorgeht. Beide basieren auf einfachen Sprachformalismen: reguläre Sprachen für Lexer und fast immer kontextfreie (CF) Sprachen für Parser. Sie sind beide mit ziemlich einfachen Rechenmodellen verbunden, dem Finite-State-Automaten und dem Push-Down-Stack-Automaten. Reguläre Sprachen sind ein Sonderfall kontextfreier Sprachen, so dass Lexer mit der etwas komplexeren CF-Technologie hergestellt werden können. Aber es ist aus mindestens zwei Gründen keine gute Idee .
Ein grundlegender Punkt bei der Programmierung ist, dass eine Systemkomponente mit der am besten geeigneten Technologie ausgestattet werden sollte, damit sie leicht zu produzieren, zu verstehen und zu warten ist. Die Technologie sollte nicht übertrieben sein (unter Verwendung von Techniken, die viel komplexer und kostspieliger sind als erforderlich), und sie sollte auch nicht an der Grenze ihrer Leistungsfähigkeit stehen, sodass technische Verzerrungen erforderlich sind, um das gewünschte Ziel zu erreichen.
Deshalb "scheint es in Mode zu sein, reguläre Ausdrücke zu hassen". Obwohl sie viel können, benötigen sie manchmal eine sehr unlesbare Codierung, um dies zu erreichen, ganz zu schweigen von der Tatsache, dass verschiedene Erweiterungen und Einschränkungen bei der Implementierung ihre theoretische Einfachheit etwas verringern. Lexer tun dies normalerweise nicht und sind normalerweise eine einfache, effiziente und geeignete Technologie zum Parsen von Token. Die Verwendung von CF-Parsern für Token wäre übertrieben, obwohl dies möglich ist.
Ein weiterer Grund, den CF-Formalismus nicht für Lexer zu verwenden, besteht darin, dass es möglicherweise verlockend ist, die volle CF-Leistung zu nutzen. Dies könnte jedoch zu strukturellen Problemen beim Lesen von Programmen führen.
Grundsätzlich ist der größte Teil der Struktur des Programmtextes, aus dem die Bedeutung extrahiert wird, eine Baumstruktur. Es drückt aus, wie der Analysesatz (Programm) aus Syntaxregeln generiert wird. Die Semantik wird durch Kompositionstechniken (Homomorphismus für mathematisch orientierte) aus der Art und Weise abgeleitet, wie Syntaxregeln zum Erstellen des Analysebaums erstellt werden. Daher ist die Baumstruktur wesentlich. Die Tatsache, dass Token mit einem regulären lexer auf Set-Basis identifiziert werden, ändert nichts an der Situation, da CF, das mit Regular zusammengesetzt ist, immer noch CF ergibt (ich spreche sehr locker von regulären Wandlern, die einen Zeichenstrom in einen Tokenstrom verwandeln).
Mit CF zusammengesetzte CF (über CF-Wandler ... Entschuldigung für die Mathematik) geben jedoch nicht unbedingt CF und machen die Dinge möglicherweise allgemeiner, aber in der Praxis weniger nachvollziehbar. Daher ist CF nicht das geeignete Werkzeug für Lexer, obwohl es verwendet werden kann.
Einer der Hauptunterschiede zwischen regulären und CF-Sprachen besteht darin, dass reguläre Sprachen (und Wandler) mit fast jedem Formalismus auf verschiedene Weise sehr gut zusammensetzen, während CF-Sprachen (und Wandler) dies nicht tun, nicht einmal mit sich selbst (mit wenigen Ausnahmen).
(Beachten Sie, dass normale Wandler möglicherweise andere Verwendungszwecke haben, z. B. die Formalisierung einiger Techniken zur Behandlung von Syntaxfehlern.)
BNF ist nur eine spezielle Syntax für die Darstellung von CF-Grammatiken.
EBNF ist ein syntaktischer Zucker für BNF , der die Möglichkeiten der regulären Notation nutzt, um eine genauere Version der BNF-Grammatiken zu erhalten. Es kann immer in ein äquivalentes reines BNF umgewandelt werden.
Die reguläre Notation wird in EBNF jedoch häufig nur verwendet, um diese Teile der Syntax hervorzuheben, die der Struktur lexikalischer Elemente entsprechen und mit dem Lexer erkannt werden sollten, während der Rest eher in reinem BNF dargestellt wird. Aber es ist keine absolute Regel.
Zusammenfassend lässt sich sagen, dass die einfachere Struktur von Token mit der einfacheren Technologie regulärer Sprachen besser analysiert werden kann, während die baumorientierte Struktur der Sprache (der Programmsyntax) von CF-Grammatiken besser behandelt wird.
Ich würde vorschlagen, auch die Antwort von AHR zu lesen .
Dies lässt jedoch eine Frage offen: Warum Bäume?
Bäume sind eine gute Grundlage für die Angabe der Syntax, weil
Sie geben dem Text eine einfache Struktur
Es ist sehr praktisch, die Semantik auf der Grundlage dieser Struktur mit dem Text zu verknüpfen, und zwar mit einer mathematisch gut verstandenen Technologie (Komposition über Homomorphismen), wie oben angegeben. Es ist ein grundlegendes algebraisches Werkzeug, um die Semantik mathematischer Formalismen zu definieren.
Daher ist es eine gute Zwischendarstellung, wie der Erfolg von Abstract Syntax Trees (AST) zeigt. Beachten Sie, dass sich AST häufig vom Analysebaum unterscheidet, da die von vielen Fachleuten (z. B. LL oder LR) verwendete Analysetechnologie nur für eine Teilmenge von CF-Grammatiken gilt, wodurch grammatikalische Verzerrungen erzwungen werden, die später in AST korrigiert werden. Dies kann mit einer allgemeineren Parsing-Technologie (basierend auf dynamischer Programmierung) vermieden werden, die jede CF-Grammatik akzeptiert.
Aussagen über die Tatsache, dass Programmiersprachen eher kontextsensitiv (CF) als CF sind, sind willkürlich und umstritten.
Das Problem ist, dass die Trennung von Syntax und Semantik willkürlich ist. Das Überprüfen von Deklarationen oder Typübereinstimmungen kann entweder als Teil der Syntax oder als Teil der Semantik angesehen werden. Gleiches gilt für die Übereinstimmung von Geschlecht und Anzahl in natürlichen Sprachen. Es gibt jedoch natürliche Sprachen, in denen die Pluralübereinstimmung von der tatsächlichen semantischen Bedeutung von Wörtern abhängt, so dass sie nicht gut zur Syntax passt.
Viele Definitionen von Programmiersprachen in der Denotationssemantik setzen Deklarationen und Typprüfungen in die Semantik. Die Aussage von Ira Baxter, dass CF-Parser gehackt werden, um eine von der Syntax geforderte Kontextsensitivität zu erhalten, ist bestenfalls eine willkürliche Sicht auf die Situation. Es kann in einigen Compilern als Hack organisiert sein, muss es aber nicht sein.
Es ist auch nicht nur so, dass CS-Parser (in dem Sinne, wie sie in anderen Antworten hier verwendet werden) schwer zu erstellen und weniger effizient sind. Sie sind auch nicht ausreichend, um die Kinf der Kontextsensitivität, die erforderlich sein könnte, klar auszudrücken. Und sie erzeugen natürlich keine syntaktische Struktur (wie z. B. Analysebäume), die geeignet ist, die Semantik des Programms abzuleiten, dh den kompilierten Code zu generieren.
quelle
Es gibt eine Reihe von Gründen, warum der Analyseteil eines Compilers normalerweise in lexikalische Analyse- und Analysephasen (Syntaxanalyse) unterteilt ist.
resource___ Compiler (2. Auflage) geschrieben von Alfred V. Abo Universität Columbia Monica S. Lam Stanford Universität Ravi Sethi Avaya Jeffrey D. Ullman Stanford Universität
quelle