lexers vs Parsern

Question

Sind lexers und Parser wirklich, dass andere in der Theorie?

Es scheint in Mode reguläre Ausdrücke zu hassen: Coding Horror , einem anderen Blog Post .

Allerdings beliebte lexing basierte Tools: pygments , geshi oder verschönern , alle reguläre Ausdrücke verwenden. Sie scheinen lex etwas ...

Wenn Lexing genug, wenn Sie brauchen EBNF?

Hat jemand die Token durch diese lexers mit Bison oder ANTLR Parser-Generatoren?

produziert verwendet

Answer 1

Was Parser und Lexer gemeinsam haben:

1. Sie lesen Symbole von einigen Alphabet von ihrem Eingang.

   • Hinweis: Das Alphabet muss nicht unbedingt von Buchstaben sein. Aber es hat von Symbolen sein, die Atom für die Sprache sind verstanden durch Parser / Lexer.
   • Symbole für die Lexer. ASCII-Zeichen
   • Symbole für den Parser. Die jeweiligen Token, die Terminal-Symbole ihrer Grammatik sind

2. Sie analysieren diese Symbole und versuchen, sie zu passen mit dem Grammatik der Sprache verstanden sie.
   

   • Hier, wo der wirkliche Unterschied liegt in der Regel. Siehe unten für mehr.
   • Grammatik verstanden durch lexers: regelmäßige Grammatik (Chomsky Level 3)
   .
   • Grammatik verstanden von Parsern: kontextfreie Grammatik (Chomsky Stufe 2)
   .

3. Sie legen Semantik (Bedeutung) zu den Sprach Stücke finden sie.

   • lexers attach Sinn durch die Klassifizierung Lexeme (Strings von Symbolen aus dem Eingang) als insbesondere Token . Z.B. Alle diese Lexeme. *, ==, <= wird ^ als "Operator" eingestuft werden Jeton über die C / C ++ Lexer
   • Parsers attach Bedeutung von Zeichenketten aus dem Eingang (Sätze) als besondere Klassifizierung nonterminals und den Aufbau der Parse-Baum . Z.B. all diese Zeichenkette. [number][operator][number], [id][operator][id] werden [id][operator][number][operator][number] als "Ausdruck" Nicht-Terminal durch die C / C ++ Parser klassifiziert werden

4. Sie können einige zusätzliche Bedeutung anhängen (Daten) zu den anerkannten Elemente.

   • Wenn ein Lexer eine Zeichensequenz erkennt eine richtige Zahl darstellt, kann sie es in ihren Binärwert und speichern mit der „Nummer“ Token umwandeln.
   • Ähnlich wird, wenn ein Parser einen Ausdruck erkennen, er kann seinen Wert und Laden mit dem „Ausdruck“ Knoten des Syntaxbaums berechnen.

5. Sie alle Produkte an ihrem Ausgang eine richtige Sätze der Sprache erkennen sie.

   • lexers produzieren Token , welche Sätze des reguläre Sprache sie erkennen. Jedes Token kann eine innere Syntax hat (obwohl Level 3, nicht Stufe 2), aber das spielt keine Rolle für die Ausgangsdaten und für die, die sie liest.
   • Parsers produzieren Syntaxbäume , die Darstellungen von Sätze des kontextfreie Sprache sie erkennen. Normalerweise ist es nur ein großer Baum für die gesamte Dokument / Quelldatei, weil die gesamte Dokument / Quelldatei ein richtigen ist Satz für sie. Aber es gibt keine Gründe, warum Parser nicht eine Reihe von Syntaxbäumen an seinem Ausgang erzeugen konnten. Z.B. es könnte ein Parser sein, die in Klartext klebten SGML-Tags erkennt. So dass es dann tokenize das SGML-Dokument in eine Reihe von Token. [TXT][TAG][TAG][TXT][TAG][TXT]...

Wie Sie sehen können, Parser und Tokenizer haben viel gemeinsam. Ein Parser kann ein tokenizer für andere Parser sein, der seine Eingabe-Token als Symbole aus dem eigenen Alphabet liest (Token sind einfach Symbole einiger Alphabet) in der gleichen Weise wie Sätze aus einer Sprache sein kann alphabetische Symbole aus einem anderen, höheren Ebene Sprache. Zum Beispiel, wenn * und - die Symbole des Alphabets M (als „Morse Code-Symbole“) sind, dann können Sie einen Parser bauen, die in der Morse-Code kodierten Strings dieser Punkte und Linien als Buchstaben erkennt. Die Sätze in der Sprache „Morse-Code“ könnte Token für einen anderen Parser, für die diese Token sind Atomsymbole seiner Sprache (zum Beispiel „Englisch Words“ Sprache). Und diese „Englische Wörter“ könnte Token (Symbole des Alphabets) werden für einige höherer Ebene Parser, der „englischen Sätze“ Sprache versteht. Und allediese Sprachen unterscheiden sich nur in der Komplexität der Grammatik . Sonst nichts.

Also, was ist alles über diese „Grammatik Ebene Chomskys“? Nun, Noam Chomsky klassifizierte Grammatiken in vier Stufen je nach ihrer Komplexität:

• Stufe 3: Reguläre 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 (zB a|b).
  Sie können als umgesetzt werden endliche Automaten (FSA), wie NFA (Nichtdeterministische Finite Automaton) oder besser DFA (deterministische endliche Automaten).
  Reguläre Grammatiken mit nicht verarbeiten können verschachtelte Syntax , zB korrekt verschachtelt / angepasst Klammern (()()(()())), verschachtelte HTML / BBcode Tags, verschachtelte Blöcke usw. Es ist, weil Automaten zu behandeln es viele Staaten unendlich haben müssen sollten unendlich viele Verschachtelungsebenen zu behandeln.

• Stufe 2: Kontextfreie Grammatiken

  Sie haben können, rekursiv, selbstähnliche Zweige in ihre Syntaxbäume verschachtelt, so dass sie gut mit verschachtelten Strukturen umgehen kann.
  können Sie als Automat mit Stack implementiert werden. Dieser Stapel wird verwendet, um die Verschachtelungstiefe der Syntax darzustellen. In der Praxis sind sie in der Regel als Top-down, rekursiv absteigenden Parser implementiert, den Prozeduraufruf-Stack der verwendet Maschine die Verschachtelungsebene zu verfolgen, und die Verwendung rekursiv Prozeduren / Funktionen für jedes Nicht-Terminal-Symbol in ihrer Syntax aufgerufen.
  aber sie können nicht mit einer kontextsensitiven Syntax behandeln. Z.B. Wenn Sie einen Ausdruck x+3 und in einem Kontext haben diese x ein Name einer Variablen sein könnte, und in anderem Kontext könnte es ein Name eine Funktion usw. sein.

• Stufe 1: Kontextsensitive Grammatiken

• Level 0:. Unrestricted Grammatiken
  auch rekursiv aufzählbar Grammatiken

genannt

Answer 2

Ja, sind sie in der Theorie sehr unterschiedlich ist, und bei der Umsetzung.

lexers werden verwendet, „Worte“ zu erkennen, die Sprachelemente bilden, weil die Struktur solcher Wörter im Allgemeinen einfach ist. Reguläre Ausdrücke sind extrem gut in diese einfachere Struktur der Handhabung, und es gibt sehr leistungsfähigen regulären Ausdrücken passende Motoren verwendet lexers zu implementieren.

Parser wird verwendet, „Struktur“ eine Sprache Phrasen zu erkennen. Eine solche Struktur ist in der Regel weit über das „reguläre Ausdrücke“ erkennen kann, so braucht man „Kontextsensitiv“ Parser solche Struktur zu extrahieren. Kontextsensitive Parser schwer zu bauen sind, so dass der Engineering-Kompromiss „kontextfrei“ Grammatiken verwenden und fügen Sie Hacks zu den Parser ( „Symboltabellen“, etc.) die kontextsensitive Teil zu behandeln.

Weder Lexing noch Technik Parsen wahrscheinlich bald weg gehen.

Sie können mit der Entscheidung vereinigt werden verwenden „Parsen“ Technologie „Worte“ zu erkennen, wie sie derzeit von sogenannten abtastlosen GLR-Parser erforscht. Das hat eine Laufzeit Kosten, da Sie allgemeinere Maschinen anwenden, was oft ein Problem, dass es nicht braucht, und in der Regel zahlen Sie für den in Overhead. Wo Sie viele kostenlose Zyklen haben, dass Overhead kann keine Rolle spielen. Wenn Sie eine Menge Text zu verarbeiten, dann wird der Kopf Materie und klassische regulärer Ausdruck Parser wird auch weiterhin verwendet werden.

Answer 3

  

Wenn Lexing genug, wenn Sie brauchen EBNF?

EBNF fügt wirklich nicht viel zu der Macht von Grammatiken. Es ist nur eine Bequemlichkeit / Shortcut Notation / "syntaktischer Zucker" über die Standard Chomskys Normalform (CNF) Grammatikregeln. Zum Beispiel ist die EBNF Alternative:

S --> A | B

Sie können in CNF erreichen, indem nur jede alternative Produktion Auflistung separat:

S --> A      // `S` can be `A`,
S --> B      // or it can be `B`.

Das optionale Element von EBNF:

S --> X?

Sie können mit einer in CNF erreichen Nullable Produktion, welche die eine ist, die durch eine ersetzt werden kann leere Zeichenfolge (durch nur leere Produktion hier bezeichnet, andere Verwendung epsilon oder Lambda oder durchgestrichenen Kreis):

S --> B       // `S` can be `B`,
B --> X       // and `B` can be just `X`,
B -->         // or it can be empty.

Eine Produktion in einer Form, wie die letzte B oben genannt wird, „Löschen“, weil es löschen können, was sie steht in anderen Produktionen (Produkt eine leere Zeichenfolge statt etwas anderes).

Null-oder-mehr repetiton von EBNF:

S --> A*

Sie können obtan mithilfe von rekursive Produktion, das heißt, eine, die sich in ihrem irgendwo einbettet. Es kann auf zwei Arten erfolgen. Erstens ist ein Linksrekursion (die in der Regel vermieden werden sollte, weil Top-Down Rekursiver Abstieg nicht analysieren kann):

S --> S A    // `S` is just itself ended with `A` (which can be done many times),
S -->        // or it can begin with empty-string, which stops the recursion.

Zu wissen, dass es erzeugt nur einen leeren String (letztlich), gefolgt von null oder mehr As, die gleichen Zeichenfolge ( aber nicht die gleiche Sprache! ) kann ausgedrückt werden mit rechtser Rekursion :

S --> A S    // `S` can be `A` followed by itself (which can be done many times),
S -->        // or it can be just empty-string end, which stops the recursion.

Und wenn es darum geht, + für eine oder mehr-Wiederholung von EBNF:

S --> A+

es kann durch Ausklammern eines A und mit * wie vor durchgeführt werden:

S --> A A*

, die Sie in CNF als solche ausdrücken kann (ich verwende richtige Rekursion hier, versuchen herauszufinden, die andere sich als Übung):

S --> A S   // `S` can be one `A` followed by `S` (which stands for more `A`s),
S --> A     // or it could be just one single `A`.

Das Wissen, dass, können Sie jetzt wahrscheinlich eine Grammatik für einen regulären Ausdruck erkennen (das heißt, regelmäßige Grammatik ) als eine, die in einer einzigen EBNF Produktion ausgedrückt werden kann nur von Terminalsymbolen aus. Allgemeiner gesagt, können Sie reguläre Grammatiken erkennen, wenn Sie Produktionen ähnlich wie diese sehen:

A -->        // Empty (nullable) production (AKA erasure).
B --> x      // Single terminal symbol.
C --> y D    // Simple state change from `C` to `D` when seeing input `y`.
E --> F z    // Simple state change from `E` to `F` when seeing input `z`.
G --> G u    // Left recursion.
H --> v H    // Right recursion.

Das heißt, mit nur leeren Strings, Terminal-Symbolen, einfaches Nicht-Terminals für Ersetzungen und Zustandsänderungen, und unter Verwendung von Rekursion nur Wiederholungen zu erreichen (Iteration, die gerade ist lineare Rekursion - derjenige, nicht verzweigen baumartige). Nichts weiter fortgeschritten über diese, dann sind Sie sicher, dass es eine regelmäßige Syntax und Sie können mit nur Lexer für das gehen.

Aber wenn Ihre Syntax verwendet Rekursion in einer nicht-triviale Weise zu produzieren baumartige, selbstähnlich, verschachtelte Strukturen, wie die folgende:

S --> a S b    // `S` can be itself "parenthesized" by `a` and `b` on both sides.
S -->          // or it could be (ultimately) empty, which ends recursion.

dann können Sie leicht erkennen, dass dies nicht mit regulären Ausdrücken durchgeführt werden, weil Sie es nicht in einem einzigen EBNF Produktion in irgendeiner Weise lösen können; Sie werden auf unbestimmte Zeit mit Substitution für S am Ende, die immer weitere as und bs auf beiden Seiten hinzufügen. Lexer (genauer gesagt: Finite State Automata von lexers verwendet wird) nicht auf beliebige Zahl zählen (sie endlich sind, erinnern Sie sich?), So dass sie nicht wissen, wie viele as es gab sie mit so vielen bs gleichmäßig anzupassen. Grammatiken wie diese werden als kontextfreie Grammatiken (zumindest), und sie erfordern einen Parser.

Kontextfreie Grammatiken sind bekannt zu parsen, so dass sie allgemein zur Beschreibung Programmiersprachen Syntax verwendet werden. Aber es gibt mehr. Manchmal ist eine allgemeinere Grammatik erforderlich - wenn Sie mehr Dinge zur gleichen Zeit zu zählen, unabhängig. Zum Beispiel, wenn Sie eine Sprache beschreiben wollen, wo man verschachtelt runde Klammern und eckige Klammern verwenden kann, aber sie haben zu korr gepaartekt miteinander (Zahnspangen mit Klammern, rund mit rund). Diese Art von Grammatik heißt kontextsensitive . Sie können es durch erkennen, dass es auf der linken Seite mehr als ein Symbol hat (vor dem Pfeil). Zum Beispiel:

A R B --> A S B

Sie können denken, diese zusätzlichen Symbole auf der linken Seite als „Kontext“ für die Regel angewendet wird. Es könnte einige Voraussetzungen sein, Nachbedingungen usw. Zum Beispiel wird die obige Regel R in S ersetzen, aber nur, wenn es zwischendurch A und B, jene A und B selbst unverändert bleibt. Diese Art von Syntax ist wirklich schwer zu analysieren, weil es eine ausgewachsene Turing-Maschine benötigt. Es ist eine ganz andere Geschichte, also werde ich hier beenden.

Answer 4

Um die Frage zu beantworten, wie gefragt (ohne übermäßig zu wiederholen, was in erscheint andere Antworten)

Lexer und Parser sind nicht sehr verschieden, wie die vorgeschlagene akzeptierte Antwort. Beide basieren auf einer einfachen Sprache Formalismen: regular Sprachen für lexers und fast immer kontextfrei (CF) Sprachen für Parser. Beide sind mit relativ einfachen Rechen zugeordnet Modelle, der endliche Automat und die Push-down-Stapel Automaten. Reguläre Sprachen sind ein Sonderfall von kontextfreien Sprachen, so dass lexers konnte mit dem etwas komplexeren CF hergestellt werden Technologie. Aber es ist keine gute Idee, für mindestens zwei Gründe.

Ein wesentlicher Punkt in der Programmierung ist, dass eine Systemkomponente soll sein buit mit der am besten geeigneten Technologie, so dass es leicht zu ist produzieren, zu verstehen und zu pflegen. Die Technologie sollte nicht Overkill (Techniken viel komplexer und kostspieliger als nötig verwendet wird), noch sollten sie an der Grenze seiner Macht, was somit technischen Verrenkungen um das gewünschte Ziel zu erreichen.

Aus diesem Grunde: „Es scheint in Mode reguläre Ausdrücke zu hassen“. Obwohl sie viel tun können, benötigen sie manchmal sehr unleserlich Codierung, es zu erreichen, nicht die Tatsache, dass verschiedene Erweiterungen zu erwähnen und Einschränkungen bei der Implementierung reduzieren etwas ihre theoretischen Einfachheit. Lexer in der Regel nicht tun, und sind in der Regel eine einfache, effiziente und geeignete Technologie, um Parse-Token. Unter Verwendung von CF-Parser für Token sein Overkill würde, wenn es möglich ist.

Ein weiterer Grund CF Formalismus nicht für lexers zu verwenden ist, dass es könnte dann die volle CF Macht zu nutzen, verlockend sein. Aber das könnte raise sructural Probleme in Bezug auf das Lesen von Programmen.

Im Grunde ist die meisten der Struktur des Programmtextes, aus der extrahiert bedeutet, ist eine Baumstruktur. Es drückt aus, wie das Parsing Satz (Programm) von Syntaxregeln erzeugt. Semantics ist durch Kompositionstechniken (Homomorphismus für das abgeleitete mathematisch orientierten) aus dem Weg Syntaxregeln zusammengesetzt sind, um Aufbau des Parsing-Baum. Daraus ergibt sich die Baumstruktur ist von wesentlicher Bedeutung. Die Tatsache, dass Token mit einem regulären Set basierend Lexer identifiziert die Situation nicht ändern, weil CF mit regelmäßigen noch zusammengesetzt CF gibt (ich spreche sehr lose über regelmäßige Wandler, dass Mach einen Strom von Zeichen in einen Strom von Token).

Allerdings CF zusammengesetzt mit CF (über CF-Wandler ... sorry für die math), geben nicht notwendigerweise CF und Macht macht die Dinge mehr allgemein, aber weniger lenkbar in der Praxis. So CF ist nicht der geeignete Werkzeug für lexers, obwohl es verwendet werden kann.

Eine der wichtigsten Unterschiede zwischen normalen und CF ist, dass regelmäßige Sprachen (und Wandler) komponieren sehr gut mit fast jedem Formalismus auf verschiedene Weise, während CF Sprachen (und Wandler) zu tun nicht einmal mit sich selbst (mit wenigen Ausnahmen) nicht.

(Beachten Sie, dass regelmäßige Wandler können andere Anwendungen, wie Formalisierung eines Fehlers Syntax Handhabungstechniken.)

BNF ist nur eine spezielle Syntax für CF Grammatiken präsentiert.

EBNF ist ein syntaktischer Zucker für BNF , mit den Einrichtungen der regelmäßigen Notation knappere Version von BNF-Grammatiken zu geben. Es kann immer sein ein äquivalentes reines BNF umgewandelt in.

Allerdings ist die regelmäßige Notation oft in EBNF verwendet nur diese zu betonen Teile der Syntax, die entsprechen die Struktur der lexikalischen Elemente und sollen mit dem Lexer erkannt werden, während der Rest mit werden eher in geraden BNF dargestellt. Aber es ist keine absolute Regel.

Um es zusammenzufassen, die einfachere Struktur des Token wird besser analysiert mit die einfachere Technologie der regulären Sprachen, während der Baum orientiert Struktur der Sprache (der Programmsyntax) besser durch CF gehandhabt Grammatiken.

würde ich vorschlagen, auch Blick auf Antwort der AHR.

Aber diese Blätter eine Frage offen: Warum Bäume

Bäume sind eine gute Basis für die Angabe Syntax weil

• geben sie eine einfache Struktur auf den Text

• gibt es sehr bequem für die Semantik mit dem Text Assoziieren auf der Grundlage dieser Struktur mit einem mathematisch gut verstanden Technologie (Kompositionalität über homomorphisms), wie Oben angegeben. Es ist ein grundlegendes algebraische Werkzeug definieren die Semantik mathematischer Formalismen.

Daher ist es eine gute Zwischendarstellung, wie sie durch die gezeigte Erfolg Abstract Syntax Trees (AST). Beachten Sie, dass AST sind oft unterscheidet sich von Parse-Baum, weil die Parsing-Technologie von vielen genutzt Fachleute (wie LL oder LR) gilt nur für eine Teilmenge von CF Grammatiken, so grammatische Distorsionen zwingen, die später in AST korrigiert. Dies kann mit allgemeineren Parsing vermieden werden Technologie (basierend auf dynamische Programmierung), die jede CF Grammatik akzeptiert.

Erklärung über die Tatsache, dass Programmiersprachen kontextsensitive (CS) statt CF ist willkürlich und strittig.

Das Problem ist, dass die Trennung von Syntax und Semantik willkürlich. Überprüfen Erklärungen oder Typ Vereinbarung kann als gesehen werden entweder ein Teil der Syntax oder ein Teil der Semantik. Das gleiche würde für Geschlecht und Zahl Vereinbarung in natürlichen Sprachen. Aber es gibt natürlich Sprachen, in denen mehrere Abkommen über die tatsächlichen semantischen abhängt so von Worten bedeutet, dass es nicht gut mit Syntax paßt.

Viele Definitionen von Programmiersprachen in denotational Semantik Ort Erklärungen und geben Sie in der Semantik überprüft. So besagt, wie getan von Ira Baxter dass CF-Parser, einen Kontext zu erhalten gehackt werden durch Syntax erforderliche Empfindlichkeit ist bestenfalls eine beliebige Ansicht der Situation. Es kann in einigen Compilern als Hack organisiert werden, aber es nicht sein.

Auch ist es nicht nur, dass CS-Parser (in dem Sinne, in anderen Antworten verwendete hier) ist schwer zu bauen, und weniger effizient. Sie sind auch unzureichend perspicuously die zum Ausdruck bringen kinf von Kontextsensitivität, die erforderlich sein könnte. Und das tun sie nicht erzeugt von Natur aus einer syntaktischen Struktur (wie Parsebäume), dass ist praktisch, um die Semantik des Programms zu leiten, das heißt zu erzeugen, der kompilierte Code.

Answer 5

Es gibt eine Reihe von Gründen, warum die Analyse Teil eines Compilers ist normalerweise lexikalische Analyse getrennt und in dem Parsen (Syntaxanalyse) Phasen.

1. Einfachheit des Designs ist die wichtigste Überlegung. Die Trennung von lexikalischen und syntaktischen Analyse ermöglicht es uns oft zumindest eine dieser Aufgaben zu vereinfachen. Zum Beispiel kann ein Parser, der mit Kommentaren und Leerraum als syntaktische Einheiten zu tun hatte wären. Wesentlich komplexer als eine, die bereits durch die lexikalische Analyse entfernt wurden Kommentare und weißen Raum einnehmen kann. Wenn wir eine neue Sprache, Trennung lexikalische und syntaktische Bedenken entwerfen zu einem saubereren Gesamtsprachdesign führen kann.
2. Compiler Effizienz verbessert wird. Eine separate lexikalische Analyse ermöglicht es uns, spezielle Techniken anzuwenden, die nur die lexikalische Aufgabe dienen, nicht die Aufgabe der Analyse. Darüber hinaus spezialisierte Techniken zum Lesen von Eingabezeichen Pufferung kann deutlich den Compiler beschleunigen.
3. Compiler Portabilität verbessert. Input-gerätespezifische Besonderheiten können auf die lexikalische Analyse beschränkt werden.

Ressource ___ Compiler (2nd Edition) geschrieben von- Alfred V. Abo Universität von Columbia Monica S. Lam Universität in Stanford Ravi Sethi Avaya Jeffrey D. Ullman Stanford University