Token für einen Lexer finden

Ich schreibe einen Parser für eine von mir erstellte Auszeichnungssprache (in Python schreiben, aber das ist für diese Frage nicht wirklich relevant - in der Tat, wenn dies wie eine schlechte Idee erscheint, würde ich einen Vorschlag für einen besseren Pfad lieben). .

Ich lese hier über Parser: http://www.ferg.org/parsing/index.html , und ich arbeite daran, den Lexer zu schreiben, der, wenn ich das richtig verstehe, den Inhalt in Token aufteilen soll. Ich habe Probleme zu verstehen, welche Tokentypen ich verwenden sollte oder wie ich sie erstelle. Die Tokentypen in dem Beispiel, mit dem ich verknüpft habe, sind beispielsweise:

• STRING
• IDENTIFIERER
• NUMMER
• WHITESPACE
• KOMMENTAR
• EOF
• Viele Symbole wie {und (zählen als eigener Tokentyp

Das Problem, das ich habe, ist, dass die allgemeineren Tokentypen für mich ein bisschen willkürlich erscheinen. Warum hat STRING beispielsweise einen eigenen Token-Typ im Vergleich zu IDENTIFIER? Eine Zeichenfolge könnte als STRING_START + (IDENTIFIER | WHITESPACE) + STRING_START dargestellt werden.

Dies mag auch mit den Schwierigkeiten meiner Sprache zu tun haben. Beispielsweise werden Variablendeklarationen so geschrieben {var-name var value}und mit bereitgestellt {var-name}. Es scheint '{'und '}'sollte sich um eigene Token handeln, aber sind die Token-Typen VAR_NAME und VAR_VALUE zulässig, oder würden beide unter IDENTIFIER fallen? Außerdem kann der VAR_VALUE tatsächlich Leerzeichen enthalten. Das Leerzeichen nach var-namewird verwendet, um den Beginn des Werts in der Deklaration zu kennzeichnen. Jedes andere Leerzeichen ist Teil des Werts. Wird dieses Leerzeichen zu einem eigenen Token? Whitespace hat in diesem Zusammenhang nur diese Bedeutung. Außerdem {kann es sein , dass keine Variablendeklaration beginnt. Dies hängt vom Kontext ab (es gibt wieder dieses Wort!). {:startet eine Namensdeklaration und{ kann sogar als Teil eines Wertes verwendet werden.

Meine Sprache ähnelt Python, da Blöcke mit Einrückungen erstellt werden. Ich lese darüber , wie Python verwendet die Lexer SPIEGELSTRICH und Dedent Token (die mehr oder weniger als das, was dazu dienen , zu schaffen {und }in vielen anderen Sprachen tun würde). Python behauptet, kontextfrei zu sein, was für mich bedeutet, dass es zumindest dem Lexer egal sein sollte, wo es sich im Stream befindet, während er Token erstellt. Woher weiß Pythons Lexer, dass ein INDENT-Token mit einer bestimmten Länge erstellt wird, ohne die vorherigen Zeichen zu kennen (z. B. dass die vorherige Zeile eine neue Zeile war, erstellen Sie also die Leerzeichen für INDENT)? Ich frage, weil ich das auch wissen muss.

Meine letzte Frage ist die dümmste: Warum ist überhaupt ein Lexer notwendig? Es scheint mir, dass der Parser Zeichen für Zeichen gehen und herausfinden könnte, wo es ist und was es erwartet. Fügt der Lexer den Vorteil der Einfachheit hinzu?

Ihre Frage (wie Ihr letzter Absatz andeutet) bezieht sich nicht wirklich auf den Lexer, sondern auf das korrekte Design der Schnittstelle zwischen dem Lexer und dem Parser. Wie Sie sich vorstellen können, gibt es viele Bücher über das Design von Lexern und Parsern. Ich mag das Parser-Buch von Dick Grune , aber es ist vielleicht kein gutes Einführungsbuch. Ich mag das C-basierte Buch von Appel überhaupt nicht , weil der Code in Ihrem eigenen Compiler nicht sinnvoll erweiterbar ist (wegen der Speicherverwaltungsprobleme, die mit der Entscheidung verbunden sind, C so zu tun, als sei es ML). Meine eigene Einführung war das Buch von PJ Brown , aber es ist keine gute allgemeine Einführung (obwohl es für Dolmetscher besonders gut ist). Aber zurück zu deiner Frage.

Die Antwort ist, so viel wie möglich im Lexer zu tun, ohne vorwärts- oder rückwärtsgerichtete Einschränkungen verwenden zu müssen.

Dies bedeutet, dass Sie (natürlich abhängig von den Details der Sprache) eine Zeichenfolge als "Zeichen gefolgt von einer Folge von nicht-" und dann einem anderen "Zeichen erkennen sollten. Geben Sie dies als einzelne Einheit an den Parser zurück. Es gibt mehrere Gründe dafür, aber die wichtigsten sind

1. Dadurch wird die Menge an Status verringert, die der Parser verwalten muss, und der Speicherverbrauch wird begrenzt.
2. Dies ermöglicht der Lexer-Implementierung, sich auf das Erkennen der grundlegenden Bausteine ​​zu konzentrieren, und gibt den Parser frei, um zu beschreiben, wie die einzelnen syntaktischen Elemente zum Erstellen eines Programms verwendet werden.

Sehr oft können Parser sofort Maßnahmen ergreifen, wenn sie ein Token vom Lexer erhalten. Sobald beispielsweise IDENTIFIER empfangen wird, kann der Parser eine Symboltabellensuche durchführen, um herauszufinden, ob das Symbol bereits bekannt ist. Wenn Ihr Parser auch Zeichenfolgenkonstanten als QUOTE (IDENTIFIER SPACES) * QUOTE analysiert, führen Sie eine Reihe irrelevanter Symboltabellensuchen durch, oder Sie werden die Symboltabellensuchen höher im Syntaxelementbaum des Parsers platzieren, da dies nur möglich ist es an dem Punkt, an dem Sie jetzt sicher sind, dass Sie nicht auf eine Saite schauen.

Um noch einmal zu wiederholen, was ich zu sagen versuche, aber anders ausgedrückt, der Lexer sollte sich mit der Rechtschreibung von Dingen befassen und der Parser mit der Struktur von Dingen.

Sie werden vielleicht bemerken, dass meine Beschreibung, wie eine Zeichenfolge aussieht, einem regulären Ausdruck ähnelt. Das ist kein Zufall. Lexikalische Analysatoren werden häufig in kleinen Sprachen implementiert (im Sinne von Jon Bentleys exzellentem Buch Programming Pearls) ) die reguläre Ausdrücke verwenden. Ich bin es einfach gewohnt, beim Erkennen von Text in regulären Ausdrücken zu denken.

Erkennen Sie Ihre Frage zu Whitespace im Lexer. Wenn Ihre Sprache ein ziemlich freies Format haben soll, geben Sie WHITESPACE-Token nicht an den Parser zurück, da diese nur weggeworfen werden müssen, damit die Produktionsregeln Ihres Parsers im Wesentlichen mit Rauschen überflutet werden - Dinge, die Sie erkennen müssen, nur um sie zu werfen sie weg.

Was das bedeutet, wie Sie mit Leerzeichen umgehen sollen, wenn es syntaktisch bedeutsam ist? Ich bin nicht sicher, ob ich ein Urteil für Sie fällen kann, das wirklich gut funktioniert, ohne mehr über Ihre Sprache zu wissen. Mein vorläufiges Urteil ist, Fälle zu vermeiden, in denen Leerzeichen manchmal wichtig sind und manchmal nicht, und eine Art Trennzeichen (wie Anführungszeichen) zu verwenden. Wenn Sie die Sprache jedoch nicht nach Ihren Wünschen gestalten können, steht Ihnen diese Option möglicherweise nicht zur Verfügung.

Es gibt andere Möglichkeiten, Sprachanalysesysteme zu entwerfen. Natürlich gibt es Compiler-Konstruktionssysteme, mit denen Sie ein kombiniertes Lexer- und Parser-System angeben können (ich glaube, die Java-Version von ANTLR tut dies), aber ich habe noch nie eines verwendet.

Zuletzt eine historische Notiz. Vor Jahrzehnten war es für den Lexer wichtig, vor der Übergabe an den Parser so viel wie möglich zu tun, da die beiden Programme nicht gleichzeitig in den Speicher passen würden. Wenn Sie mehr im Lexer tun, bleibt mehr Speicher verfügbar, um den Parser intelligent zu machen. Ich habe den Whitesmiths C-Compiler einige Jahre lang verwendet, und wenn ich das richtig verstehe, würde er nur mit 64 KB RAM arbeiten (es war ein kleines MS-DOS-Programm), und trotzdem hat er eine Variante von C übersetzt war sehr, sehr nah an ANSI C.

Ich werde auf Ihre letzte Frage eingehen, die nicht wirklich dumm ist. Parser können und bauen komplexe Konstrukte zeichenweise auf. Wenn ich mich recht erinnere, enthält die Grammatik in Harbison und Steele ("C - A reference manual") Produktionen, die einzelne Zeichen als Terminals verwenden und aus den einzelnen Zeichen Bezeichner, Zeichenfolgen, Zahlen usw. als Nicht-Terminals aufbauen.

Vom Standpunkt der formalen Sprachen aus kann alles, was ein Lexer auf der Basis eines regulären Ausdrucks erkennen und als "String-Literal", "Bezeichner", "Nummer", "Schlüsselwort" usw. kategorisieren kann, sogar ein LL (1) -Parser erkennen. Es gibt also kein theoretisches Problem, mit einem Parser-Generator alles zu erkennen.

Aus algorithmischer Sicht kann ein Erkenner für reguläre Ausdrücke weitaus schneller ausgeführt werden als jeder Parser. Aus kognitiver Sicht ist es für einen Programmierer wahrscheinlich einfacher, die Arbeit zwischen einem Lexer mit regulären Ausdrücken und einem Parser-Generator-Parser zu trennen.

Ich würde sagen, dass die Leute aufgrund praktischer Überlegungen die Entscheidung treffen, Lexer und Parser zu trennen.

Es sieht so aus, als würden Sie versuchen, einen Lexer / Parser zu schreiben, ohne die Grammatik wirklich zu verstehen. Wenn Leute einen Lexer und Parser schreiben, schreiben sie sie in der Regel so, dass sie einer bestimmten Grammatik entsprechen. Der Lexer sollte die Token in der Grammatik zurückgeben, während der Parser diese Token verwendet, um Regeln / Nicht-Terminals abzugleichen . Wenn Sie Ihre Eingaben einfach Byte für Byte analysieren könnten, wären ein Lexer und ein Parser möglicherweise zu viel des Guten.

Lexer machen es einfacher.

Grammatikübersicht : Eine Grammatik ist ein Satz von Regeln, nach denen eine Syntax oder Eingabe aussehen soll. Hier ist zum Beispiel eine Spielzeuggrammatik (simple_command ist das Startsymbol):

simple_command:
 WORD DIGIT AND_SYMBOL
simple_command:
     addition_expression

addition_expression:
    NUM '+' NUM

Diese Grammatik bedeutet: -
Ein simple_command besteht entweder aus
A) WORD gefolgt von DIGIT gefolgt von AND_SYMBOL (das sind "Tokens", die ich definiere).
B) Ein "addition_expression" (dies ist eine Regel oder "non-terminal").

Ein Additionsausdruck besteht aus:
NUM, gefolgt von einem '+', gefolgt von einer NUM (NUM ist ein von mir definiertes "Token", '+' ist ein wörtliches Pluszeichen).

Da also simple_command das "Startsymbol" ist (der Ort, an dem ich beginne), überprüfe ich beim Empfang eines Tokens, ob es in simple_command passt. Wenn das erste Token in der Eingabe ein WORT und das nächste Token ein DIGIT und das nächste Token ein AND_SYMBOL ist, habe ich einen simple_command gefunden und kann etwas unternehmen. Ansonsten werde ich versuchen, es mit der anderen Regel von simple_command abzugleichen, die addition_expression ist. Wenn also das erste Token eine NUM gefolgt von einem '+' gefolgt von einer NUM war, habe ich einen simple_command gefunden und eine Aktion ausgeführt. Wenn es keines dieser Dinge ist, dann habe ich einen Syntaxfehler.

Das ist eine sehr, sehr grundlegende Einführung in die Grammatik. Weitere Informationen finden Sie in diesem Wiki-Artikel. Suchen Sie im Internet nach kontextfreien Grammatik-Tutorials.

Anhand einer Lexer / Parser-Anordnung sehen Sie hier ein Beispiel, wie Ihr Parser aussehen könnte:

bool simple_command(){
   if (peek_next_token() == WORD){
       get_next_token();
       if (get_next_token() == DIGIT){
           if (get_next_token() == AND_SYMBOL){
               return true;
           } 
       }
   }
   else if (addition_expression()){
       return true;
   }

   return false;
}

bool addition_expression(){
    if (get_next_token() == NUM){
        if (get_next_token() == '+'){
             if (get_next_token() == NUM){
                  return true;
             }
        }
    }
    return false;
}

Ok, dieser Code ist also irgendwie hässlich und ich würde niemals Triple-Nested-If-Anweisungen empfehlen. Aber der Punkt ist, stellen Sie sich vor, Sie wollen versuchen, dieses Ding Zeichen für Zeichen zu tun, anstatt Ihre netten modularen Funktionen "get_next_token" und "peek_next_token" zu verwenden . Im Ernst, probieren Sie es aus. Das Ergebnis wird dir nicht gefallen. Denken Sie jetzt daran, dass diese Grammatik etwa 30x weniger komplex ist als fast jede nützliche Grammatik. Sehen Sie die Vorteile eines Lexers?

Im Ernst, Lexer und Parser sind nicht die grundlegendsten Themen der Welt. Ich würde empfehlen, zuerst über Grammatiken zu lesen und sie zu verstehen, dann ein bisschen über Lexer / Parser zu lesen und dann einzutauchen.

Meine letzte Frage ist die dümmste: Warum ist überhaupt ein Lexer notwendig? Es scheint mir, dass der Parser Zeichen für Zeichen gehen und herausfinden könnte, wo es ist und was es erwartet.

Das ist nicht dumm, es ist nur die Wahrheit.

Die Praktikabilität hängt jedoch ein wenig von Ihren Tools und Zielen ab. Wenn Sie beispielsweise yacc ohne Lexer verwenden und Unicode-Buchstaben in Bezeichnern zulassen möchten, müssen Sie eine große und hässliche Regel schreiben, die alle gültigen Zeichen explizit auflistet. In einem Lexer könnten Sie möglicherweise eine Bibliotheksroutine fragen, ob ein Charakter Mitglied der Buchstabenkategorie ist.

Das Verwenden oder Nicht-Verwenden eines Lexers ist eine Frage der Abstraktionsebene zwischen Ihrer Sprache und der Zeichenebene. Beachten Sie, dass die Zeichenebene heutzutage eine weitere Abstraktion über der Byte-Ebene ist, die eine Abstraktion über der Bit-Ebene ist.

Zum Schluss können Sie sogar die Bit-Ebene analysieren.

STRING_START + (IDENTIFIER | WHITESPACE) + STRING_START.

Nein, das kann es nicht. Was ist "("? Ihrer Meinung nach ist das keine gültige Zeichenfolge. Und entkommt?

Im Allgemeinen ist es die beste Methode, Leerzeichen zu behandeln, sie zu ignorieren und nicht nur Token abzugrenzen. Viele Menschen bevorzugen sehr unterschiedliche Leerzeichen, und die Durchsetzung von Leerzeichenregeln ist bestenfalls umstritten.