Suchen Sie nach einer klaren Definition dessen, was ein "Tokenizer", "Parser" und "Lexer" sind und wie sie miteinander in Beziehung stehen und verwendet werden?

151

Ich suche nach einer klaren Definition dessen, was ein "Tokenizer", "Parser" und "Lexer" sind und wie sie miteinander zusammenhängen (z. B. verwendet ein Parser einen Tokenizer oder umgekehrt)? Ich muss ein Programm erstellen, das c / h-Quelldateien durchläuft, um Datendeklarationen und Definitionen zu extrahieren.

Ich habe nach Beispielen gesucht und kann einige Informationen finden, aber ich habe wirklich Mühe, die zugrunde liegenden Konzepte wie Grammatikregeln, Analysebäume und abstrakten Syntaxbaum zu verstehen und wie sie miteinander zusammenhängen. Letztendlich müssen diese Konzepte in einem tatsächlichen Programm gespeichert werden, aber 1) wie sehen sie aus, 2) gibt es gemeinsame Implementierungen.

Ich habe mir Wikipedia zu diesen Themen und Programmen wie Lex und Yacc angesehen, aber da ich noch nie eine Compiler-Klasse (EE-Major) durchlaufen habe, fällt es mir schwer, vollständig zu verstehen, was los ist.

parsing lexer tokenize Lordhog
quelle

Antworten:

165

Ein Tokenizer unterteilt einen Textstrom in Token, normalerweise durch Suchen nach Leerzeichen (Tabulatoren, Leerzeichen, neue Zeilen).

Ein Lexer ist im Grunde ein Tokenizer, aber er fügt normalerweise einen zusätzlichen Kontext zu den Token hinzu - dieses Token ist eine Zahl, dieses Token ist ein Zeichenfolgenliteral, dieses andere Token ist ein Gleichheitsoperator.

Ein Parser nimmt den Token-Stream aus dem Lexer und wandelt ihn in einen abstrakten Syntaxbaum um, der das (normalerweise) durch den Originaltext dargestellte Programm darstellt.

Zuletzt habe ich nachgesehen, dass das beste Buch zu diesem Thema "Compiler: Prinzipien, Techniken und Werkzeuge" war, das normalerweise nur als "Das Drachenbuch" bekannt ist.

Roger Lipscombe
quelle
8
Zweifellos ist "The Dragon Book" ein gutes Buch, aber es erfordert, dass der Leser eine gute Grundlage in CS hat. Ein Buch mit mehr praktischer Anziehungskraft wäre "Writing Compilers and Interpreters" von Ronald Mak, "Modern Compiler Implementation", Andrew Appel; "Compilerkonstruktion", Niklaus Wirth; "Kompilieren mit C # und Java" und "Compiler und Compiler-Generatoren: eine Einführung mit C ++" von Pat Terry; und natürlich "The Definitive ANTLR Reference" von Terrence Parr.
Andre Artus
5
Nur um sicher zu gehen, klopfe ich nicht an Ihre Empfehlung. "The Dragon Book" war mein erstes Buch über Compiler-Technologie, aber es war schwierig im Vergleich zu beispielsweise Wirths Buch, das Sie in wenigen Stunden lesen können. Damals hatte ich nur wenige Möglichkeiten, da es das einzige Buch war, das ich in die Hände bekommen konnte (es war 1991, vor Amazon und dem WWW). Ich hatte das und eine Sammlung von Textdateien, die von Jack W. Crenshaw produziert wurden und "LET'S BUILD A COMPILER" hießen (danke Jack!). Dies ist immer noch das Buch, um die Prinzipien besser zu verstehen, aber die meisten Programmierer brauchen nur eine pragmatische Einführung.
Andre Artus
10
Ich würde nicht zustimmen, dass ein Parser / per Definition / einen abstrakten Syntaxbaum erzeugt. Parser können alle möglichen unterschiedlichen Ausgaben erzeugen. Beispielsweise ist es üblich, dass ein Parser eine Folge von Aufrufen an eine Builder-Oberfläche erzeugt - siehe das Builder-Muster im Buch "Viererbande". Der entscheidende Punkt ist, dass der Parser eine Folge von Token analysiert, um festzustellen, ob die Folge einer (normalerweise kontextfreien) Grammatik entspricht oder nicht, und möglicherweise eine Ausgabe basierend auf der grammatikalischen Struktur der Folge erzeugt.
Theodore Norvell
2
"Lassen Sie uns einen Compiler erstellen" ist hier: compilers.iecc.com/crenshaw . Ich fand den Link von hier: prog21.dadgum.com/30.html
Roger Lipscombe
1
@Pithkos: Wenn dies die einzigen Einschränkungen sind, haben Sie nur gesagt, dass die Funktion eine Eingabe in einer unbenannten (mathematischen) Domäne übernimmt und in einer anderen unbenannten Domäne erzeugt und ausgibt, z. B. F (X) -> Y. Das bedeutet so ziemlich alles Sie können dies nur als "Funktion" bezeichnen. Wenn Sie darauf bestehen, dass die Domäne von X <StreamOfCharacter, Grammar> und die Domäne von Y Tree mit der Eigenschaft ist, dass sie die Form der Grammatik widerspiegelt, würde ich F (X, G) -> T als a bezeichnen Parser. Oft curry wir F in Bezug auf G, weil sich G nicht oft ändert, also ist F [G] (X) -> T das, was Sie üblicherweise als Parser sehen.
Ira Baxter
18

Beispiel:

int x = 1;

Ein Lexer oder Tokeniser teilt dies in Token 'int', 'x', '=', '1', ';' auf.

Ein Parser nimmt diese Token und verwendet sie, um auf irgendeine Weise zu verstehen:

  • Wir haben eine Erklärung
  • Es ist eine Definition einer ganzen Zahl
  • Die Ganzzahl heißt 'x'.
  • 'x' sollte mit dem Wert 1 initialisiert werden
Gra
quelle
9
Ein Lexer wird feststellen, dass "int", "=" und ";" sind Token ohne weitere Bedeutung, dass "x" ein Bezeichnername oder etwas ist, Wert "x" und "1" eine ganze Zahl oder Zahl, Wert "1". Ein Tokenizer wird das nicht unbedingt tun.
David Thornley
5

Ich würde sagen, dass ein Lexer und ein Tokenizer im Grunde dasselbe sind und dass sie den Text in seine Bestandteile (die 'Token') zerschlagen. Der Parser interpretiert dann die Token mithilfe einer Grammatik.

Ich würde mich jedoch nicht zu sehr auf die genaue terminologische Verwendung einlassen - die Leute verwenden oft "Parsing", um eine Aktion zum Interpretieren eines Textklumpens zu beschreiben.

Will Dean
quelle
1
Bei PEG-Parsern ist die Unterscheidung zwischen Tokenizer und Parser noch weniger klar.
Andre Artus
0

( Hinzufügen zu den gegebenen Antworten )

  • Tokenizer entfernt auch alle Kommentare und gibt nur Token an den Lexer zurück.
  • Lexer werden auch Bereiche definieren für die Token (Variablen / Funktionen)
  • Der Parser erstellt dann die Code- / Programmstruktur
mcha
quelle
1
Hallo @downvoter, kannst du näher erläutern, warum du tatsächlich downvotiert hast?
Koray Tugay
1
Ich bin nicht der Downvoter, aber ich denke, der Downvote war möglicherweise, weil Ihre Antwort nicht richtig erscheint. Ein Tokenizer entfernt möglicherweise Rauschen (normalerweise Leerzeichen, aber möglicherweise auch Kommentare), speist den Lexer jedoch häufig nicht. Ein DFA-basierter Lexer markiert und identifiziert Token (z. B. eine Zahl, eine Zeichenfolge, eine Kennung, aber auch ein Leerzeichen oder einen Kommentar), kann diese jedoch nicht erfassen, da hierfür der später erstellte Syntaxbaum erforderlich wäre der Parser.
Lucero
1) Ich verstehe Ihre offensichtliche Unterscheidung zwischen "Lexer" und "Tokenizer" nicht. Ich habe Parser für mehr als 50 Sprachen erstellt und hatte noch nie zwei separate Mechanismen, die den Quelltext in Atome aufteilen. Für mich sind dies also nur Synonyme. 2) Wenn Sie kompilieren, ist das Entfernen von Kommentaren und Leerzeichen im Lexer sinnvoll. Wenn Sie Transformationstools von Quelle zu Quelle erstellen, können Sie keine Kommentare verlieren, da diese im transformierten Text erneut angezeigt werden müssen. Das Entfernen von Kommentaren ist also IMMER falsch. Wir können darüber streiten, wie man es schafft, Leerzeichen zu erhalten. ...
Ira Baxter
1
... [Die von mir erstellten Tools (siehe meine Biografie) erfassen beide mit ausreichender Genauigkeit, um sie im transformierten Code zu reproduzieren. Wir gehen noch weiter und erfassen das Format der Atome, einschließlich seltsamer Dinge wie die Anführungszeichen für Zeichenketten und die Anzahl der Radix- / führenden Nullen für Zahlen, um zu verhindern, dass der Benutzer das transformierte Ergebnis ablehnt. Also , was Sie verpasst haben nicht nur tun lexers nicht unbedingt strippen Informationen, aber in der Tat können sie müssen capture Informationen über und jenseits der Roh - Token]. ....
Ira Baxter
... 3) Lexer definieren "Bereiche" nur in hoffnungslos umständlichen Parsern, die Schwierigkeiten haben, mit syntaktischen Mehrdeutigkeiten umzugehen. C- und C ++ - Parser sind das kanonische Beispiel. siehe meine Diskussion unter stackoverflow.com/a/1004737/120163 ). Man muss es nicht so (hässlich) machen. Ich finde Ihre Antwort einfach falsch.
Ira Baxter