Lexer gegen Parser

308

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?

Naveen
quelle
2
Ja. Ich versuche, Autohotkey zu analysieren. Ich konnte sehr schnell einen Syntax-Textmarker mit Pygementen erstellen. Aber antlr dauert viel länger ... Ich habe nicht viel Fremdbestäubung zwischen den beiden Werkzeugen gesehen.
Naveen
67
Es ist nur in Mode, reguläre Ausdrücke zu hassen, wenn sie missbraucht werden. Viele Menschen versuchen, reguläre Ausdrücke zu verwenden, wenn eine kontextfreie Analyse erforderlich ist. Sie scheitern immer. Und sie beschuldigen die Technologie des regulären Ausdrucks. Das ist so, als würde man sich beschweren, dass Ihr Hammer eine miese Säge ist. Stimmt, aber Sie werden nicht viel Sympathie bekommen.
Ira Baxter
2
Zum Glück fange ich mit antlr an, etwas schneller zu werden. Viel Lexing ist kontextfrei und manchmal sogar kontextabhängig.
Naveen
1
Ein grundlegender Aspekt des Problems von Lexer gegen Parser ist, dass Lexer auf endlichen Automaten (FSA) oder genauer auf endlichen Wandlern (FST) basieren. Die meisten Parsing-Formalismen (nicht nur kontextfrei) werden im Schnittpunkt mit FSA oder der Anwendung von FST geschlossen. Daher erhöht die Verwendung des einfacheren auf regulären Ausdrücken basierenden Formalismus für Lexer nicht die Komplexität der syntaktischen Strukturen der komplexeren Parser-Formalismen. Dies ist ein absolut wichtiges Problem der Modularität bei der Definition der Struktur und Semantik von Sprachen, das von den hoch bewerteten Antworten gerne ignoriert wird.
Babou
Es sollte angemerkt werden , dass lexers und Parser nicht haben andere sein, zB LLLPG und frühere Versionen von ANTLR verwenden die gleiche LL (k) Parsing - System sowohl für Lexer und Parser. Der Hauptunterschied besteht darin, dass reguläre Ausdrücke normalerweise für Lexer ausreichen, nicht jedoch für Parser.
Qwertie

Antworten:

475

Was Parser und Lexer gemeinsam haben:

  1. Sie lesen Symbole eines Alphabets aus ihrer Eingabe.

    • Hinweis: Das Alphabet muss nicht unbedingt aus Buchstaben bestehen. Aber es muss sich um Symbole handeln, die für die von Parser / Lexer verstandene Sprache atomar sind .
    • Symbole für den Lexer: ASCII-Zeichen.
    • Symbole für den Parser: die bestimmten Token, die Endsymbole ihrer Grammatik sind.
  2. Sie analysieren diese Symbole und versuchen, sie mit der Grammatik der Sprache abzugleichen, die sie verstanden haben.

    • Hier liegt normalerweise der wahre Unterschied. Siehe unten für mehr.
    • Von Lexern verstandene Grammatik: reguläre Grammatik (Chomskys Stufe 3).
    • Von Parsern verstandene Grammatik: kontextfreie Grammatik (Chomskys Stufe 2).
  3. Sie fügen den Sprachstücken, die sie finden, Semantik (Bedeutung) hinzu.

    • Lexer fügen Bedeutung hinzu, indem sie Lexeme (Zeichenfolgen aus der Eingabe) als bestimmte Token klassifizieren . Eg All diese Lexeme: *, ==, <=, ^werden als "Operator" Token durch die C / C ++ Lexer klassifiziert werden.
    • Parsers attach Bedeutung von Zeichenketten aus dem Eingang (Sätze) , wie die besonderen Klassifizierung nonterminals und den Aufbau der Parsing - Baum . ZB all diese Zeichenkette: [number][operator][number], [id][operator][id], [id][operator][number][operator][number]werden als „Ausdruck“ Nicht - Terminal durch den Parser C ++ / C klassifiziert werden.
  4. Sie können den erkannten Elementen eine zusätzliche Bedeutung (Daten) hinzufügen.

    • Wenn ein Lexer eine Zeichenfolge erkennt, die eine richtige Zahl darstellt, kann er sie in ihren Binärwert konvertieren und mit dem Token "number" speichern.
    • Wenn ein Parser einen Ausdruck erkennt, kann er seinen Wert berechnen und mit dem Knoten "Ausdruck" des Syntaxbaums speichern.
  5. Sie alle produzieren auf ihrer Ausgabe einen richtigen Satz der Sprache, die sie erkennen.

    • Lexer produzieren Token , die Sätze der regulären Sprache sind, die sie erkennen. Jedes Token kann eine innere Syntax haben (obwohl Level 3, nicht Level 2), aber das spielt keine Rolle für die Ausgabedaten und für die, die sie lesen.
    • Parser erzeugen Syntaxbäume , die Darstellungen von Sätzen der kontextfreien Sprache sind, die sie erkennen. Normalerweise ist es nur ein großer Baum für die gesamte Dokument- / Quelldatei, da die gesamte Dokument- / Quelldatei ein geeigneter Satz für sie ist. Es gibt jedoch keine Gründe, warum der Parser bei seiner Ausgabe keine Reihe von Syntaxbäumen erzeugen konnte. Zum Beispiel könnte es ein Parser sein, der SGML-Tags erkennt, die im Klartext stecken. So wird es tokenize das SGML - Dokument in eine Reihe von Token: [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 sind M(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, bbbetd.) Oder Alternativen (zB a|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+3und dies in einem Kontext der xName 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.

SasQ
quelle
70
Oh ja? Was sind diese "Wörter oder Token"? Es sind nur Sätze in der regulären Sprache, die aus Buchstaben des Alphabets bestehen. Und was sind diese "Konstrukte" oder "Bäume" im Parser? Sie sind auch Sätze , aber in einer anderen, höheren Sprache, für die die jeweiligen Token alphabetische Symbole sind. Der Unterschied ist nicht das, was Sie gesagt haben, sondern die KOMPLEXITÄT DER VERWENDETEN SPRACHE . Konfrontieren Sie Ihre -1 mit einem Handbuch zur Parsing-Theorie.
SasQ
3
@SasQ Wäre es fair zu sagen, dass sowohl Lexer als auch Parser Grammatik und eine Reihe von Token als Eingabe verwenden?
Parag
4
Ganz so. Beide nehmen eine Reihe von Symbolen aus dem Alphabet, das sie erkennen. Für Lexer besteht dieses Alphabet nur aus einfachen Zeichen. Für Parser besteht das Alphabet aus Terminalsymbolen, unabhängig davon, wie sie definiert sind. Sie können auch Zeichen sein, wenn Sie keinen Lexer verwenden und Ein-Zeichen-Bezeichner und einstellige Zahlen usw. verwenden (sehr nützlich in den ersten Entwicklungsstadien). Aber sie sind normalerweise Token (lexikalische Klassen), weil Token eine gute Abstraktion sind: Sie können die tatsächlichen Lexeme (Zeichenfolgen) ändern, für die sie stehen, und der Parser sieht die Änderung nicht.
SasQ
6
Beispielsweise können Sie STMT_ENDin 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_ENDwie ;C / C ++ haben - wie Quellcode. Oder Sie können es so definieren end, 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.
SasQ
24
Stunden auf Wikipedia und Google haben nicht geholfen, aber Sie haben Chomskys Grammatik in 3 Minuten erklärt. Danke dir.
Enrey
107

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.

Ira Baxter
quelle
40
Schöne Erklärung, Ira. Hinzufügen zu Ihrer Analogie: Während es bei Lexern darum geht, die richtigen Wörter zu finden, geht es bei Parsern darum, die richtigen Sätze zu finden. "See Spot Run" und "Spot Run See" gelten für einen Lexer. Ein Parser benötigt, um festzustellen, ob die Phrasenstruktur falsch ist (in der englischen Grammatik).
Alan
Ich denke, ein Parser ist für einen Lexer wie ein Tree Walker für einen Parser. Ich bin nicht davon überzeugt, dass die Theorie so anders ist: antlr.org/wiki/display/~admin/ANTLR+v4+lexers, aber ich fange an, die Unterschiede in der Konvention zwischen ihnen zu verstehen ...
Naveen
4
Die Theorie ist sehr unterschiedlich. Die meisten Parser-Technologien versuchen, bis zu einem gewissen Grad mit kontextfreien Sprachen umzugehen (einige machen nur einen Teil, z. B. LALR, andere machen alles, z. B. GLR). Die meisten Lexer-Technologien versuchen nur, reguläre Ausdrücke zu verwenden.
Ira Baxter
3
Die Theorie ist anders, weil sie von vielen verschiedenen Leuten vorgeschlagen wurde und unterschiedliche Terminologie und Algorithmen verwendet. Aber wenn Sie sie genau betrachten, können Sie die Ähnlichkeiten erkennen. Zum Beispiel ist das Problem der linken Rekursion dem Problem des Nichtdeterminismus in NFAs sehr ähnlich, und das Entfernen der linken Rekursion ähnelt dem Entfernen des Nichtdeterminismus und der Umwandlung von NFA in DFA. Token sind Sätze für den Tokenizer (Ausgabe), aber alphabetische Symbole für den Parser (Eingabe). Ich leugne die Unterschiede (Chomsky-Level) nicht, aber Ähnlichkeiten helfen beim Design sehr.
SasQ
1
Mein Amtskollege befasste sich mit Kategorietheorie. Er zeigte, wie der Begriff der kategorialen Theorie von Garben alle Arten des Mustervergleichs abdeckte, und konnte LR-Parsing aus einer abstrakten kategorialen Spezifikation ableiten. Wenn Sie also abstrakt genug sind, können Sie solche Gemeinsamkeiten finden. Der Punkt der Kategorietheorie ist, dass man oft "ganz nach oben" abstrahieren kann; Ich bin sicher, Sie könnten einen Parser für Kategorietheorie erstellen, der die Unterschiede beseitigt. Aber jede praktische Verwendung muss auf die spezifische Problemdomäne beschränkt werden, und dann zeigen sich die Unterschiede als real.
Ira Baxter
32

Wann ist Lexing genug, wann brauchen Sie EBNF?

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:

S --> A | B

Sie können in CNF erreichen, indem Sie einfach jede alternative Produktion separat auflisten:

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

Das optionale Element von EBNF:

S --> X?

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):

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 der letzten Boben 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:

S --> A*

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):

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.

In dem Wissen, dass nur eine leere Zeichenfolge (letztendlich) gefolgt von null oder mehr As generiert wird , kann dieselbe Zeichenfolge ( aber nicht dieselbe Sprache! ) Mit der rechten Rekursion ausgedrückt werden :

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 +um eine oder mehrere Wiederholungen von EBNF geht:

S --> A+

Dies kann durch Ausklammern eines Aund Verwendung *wie zuvor erfolgen:

S --> A A*

was Sie in CNF als solches ausdrücken können (ich verwende hier die richtige Rekursion; versuchen Sie, die andere selbst als Übung herauszufinden):

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`.

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:

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, 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:

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 möglich ist, da Sie es in keiner Weise in eine einzige EBNF-Produktion auflösen können; Sie werden am Ende auf Sunbestimmte Zeit ersetzen , was immer ein weiteres as und bs 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 viele as vorhanden waren, um sie gleichmäßig mit so vielen bs 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:

A R B --> A S B

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 Rin S, aber nur , wenn es zwischendurch Aund Bdiejenigen zu verlassen Aund Bsie 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.

SasQ
quelle
1
Sie geben an, dass EBNF "nur eine Bequemlichkeits- / Abkürzungsnotation /" syntaktischer Zucker "gegenüber den Standard-Grammatikregeln der Chomsky-Normalform (CNF) ist". Aber CNF hat kaum etwas mit dem Thema zu tun. EBNF kann leicht in Standard-BNF umgewandelt werden. Zeitraum. Es ist syntaktischer Zucker für Standard-BNF.
Babou
11

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.

babou
quelle
Ja, Analysebäume und ASTs sind unterschiedlich, aber so gut wie nicht wirklich nützlich. Siehe meine Diskussion darüber: stackoverflow.com/a/1916687/120163
Ira Baxter
@IraBaxter Ich stimme Ihnen nicht zu, aber ich habe jetzt nicht wirklich Zeit, eine saubere Antwort auf Ihren Beitrag zu verfassen. Grundsätzlich nehmen Sie einen pragmatischen Standpunkt ein (und verteidigen auch Ihr eigenes System, denke ich). Dies ist sogar noch einfacher, da Sie allgemeine CF-Parser verwenden (GLR ist jedoch möglicherweise nicht die effizienteste), anstatt deterministische wie in einigen Systemen. Ich betrachte AST als Referenzdarstellung, die sich für eine formal definierte Behandlung, nachweislich korrekte Transformationen, mathematische Beweise, die Nichtanalyse mehrerer konkreter Darstellungen usw.
eignet
Die "pragmatische" Sichtweise ist der Grund, warum ich behaupte, dass sie sich in nützlicher Weise nicht sehr unterscheiden. Und ich glaube einfach nicht, dass die Verwendung eines (Ad-hoc-AST) "nachweislich korrekte Transformationen" liefert; Ihr Ad-hoc-AST hat keine offensichtliche Beziehung zur tatsächlichen Grammatik der verarbeiteten Sprache (und hier ist mein System insofern vertretbar, als unser "AST" nachweislich ein isomorphes Äquivalent zum BNF ist). Ad-hoc-ASTs bieten Ihnen keine zusätzliche Möglichkeit, "mehrere konkrete Darstellungen" zu analysieren. Ihr Einwand gegen GLR (nicht am effizientesten) erscheint ziemlich sinnlos. Sie sind auch nicht nicht deterministisch.
Ira Baxter
Tatsächlich verstehe ich keinen Teil Ihrer Einwände gegen meinen Kommentar. Sie müssen diese "saubere Antwort" schreiben.
Ira Baxter
@IraBaxter Kommentare sind zu eingeschränkt für eine richtige Antwort (Vorschlag?). "Ad hoc" ist kein geeignetes Qualifikationsmerkmal für AST, das ich befürworte. Dies sollte (manchmal) die Referenzsyntax sein. Dies ist historisch wahr, wenn man sowohl die Geschichte des AST-Konzepts in der Informatik als auch die Geschichte formaler Systeme als Begriffe (Bäume) in einer sortierten Algebra zusammen mit der Interpretation betrachtet. AST ist das Referenzformular, kein abgeleitetes. Siehe auch moderne Proofsysteme und automatische Programmerstellung. Möglicherweise sind Sie voreingenommen, weil Sie nach einer konkreten Syntax arbeiten müssen, die von anderen entwickelt wurde.
Babou
7

Es gibt eine Reihe von Gründen, warum der Analyseteil eines Compilers normalerweise in lexikalische Analyse- und Analysephasen (Syntaxanalyse) unterteilt ist.

  1. Die Einfachheit des Designs ist der wichtigste Gesichtspunkt. Die Trennung von lexikalischer und syntaktischer Analyse ermöglicht es uns oft, mindestens eine dieser Aufgaben zu vereinfachen. Zum Beispiel wäre ein Parser, der sich mit Kommentaren und Leerzeichen als syntaktische Einheiten befassen musste. Deutlich komplexer als einer, der Kommentare und Leerzeichen annehmen kann, wurden vom lexikalischen Analysator bereits entfernt. Wenn wir eine neue Sprache entwerfen, kann die Trennung von lexikalischen und syntaktischen Belangen zu einem saubereren Gesamtsprachendesign führen.
  2. Die Effizienz des Compilers wird verbessert. Ein separater lexikalischer Analysator ermöglicht es uns, spezielle Techniken anzuwenden, die nur der lexikalischen Aufgabe dienen, nicht der Aufgabe des Parsens. Darüber hinaus können spezielle Puffertechniken zum Lesen von Eingabezeichen den Compiler erheblich beschleunigen.
  3. Die Portabilität des Compilers wurde verbessert. Eingabegerätspezifische Besonderheiten können auf den lexikalischen Analysator beschränkt werden.

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

AHR
quelle