Ein Lexer (auch Tokenizer oder Scanner) ist der Baustein eines Compilers, der den Quelltext als Zeichenstrom einliest und in eine Folge von Token zerlegt. Er führt damit die lexikalische Analyse aus — die erste Phase der Übersetzung, noch vor der eigentlichen Syntaxanalyse.
Was ein Token ist
Ein Token ist die kleinste bedeutungstragende Einheit einer Programmiersprache: Schlüsselwörter (if, while, return), Bezeichner (Variablen- und Funktionsnamen), Zahlen (42, 3.14), Operatoren (+, -, ==) und Symbole ((, ), {, }). Jedes Token trägt seinen Typ, das gelesene Lexem (den Originaltext) und meist die Zeilen- und Spaltenposition für gute Fehlermeldungen.
Wie ein Lexer arbeitet
- Muster als reguläre Ausdrücke: Jeder Token-Typ wird durch ein Muster beschrieben, z. B. [a-zA-Z_][a-zA-Z0-9_]* für Bezeichner.
- Endlicher Automat: Die Muster werden zu einem deterministischen endlichen Automaten (DFA) kombiniert. Die klassische Konstruktion stammt von Ken Thompson: regulärer Ausdruck zuerst in einen NFA, per Subset-Konstruktion in einen DFA, anschließend minimiert.
- Longest Match: Gelesen wird immer der längste passende Präfix des Eingabestroms. Passt z. B. "if" sowohl als Schlüsselwort als auch als Bezeichner-Anfang, gewinnt bei gleicher Länge die Prioritätsregel — Schlüsselwörter werden vor Bezeichnern gematcht.
- Überspringen: Leerzeichen, Tabulatoren, Zeilenumbrüche und Kommentare erzeugen meist kein Token, sondern werden direkt übersprungen.
Werkzeuge und Praxis
Klassische Lexer-Generatoren sind lex und flex (C), daneben re2c und Ragel. Viele moderne Sprachen verwenden dagegen handgeschriebene Lexer, weil sie schneller sind und bessere Fehlermeldungen erlauben — Go, Rust und Java gehören dazu. Eine bekannte Besonderheit ist der Lexer-Hack in C: Ob ein Bezeichner ein Typname ist (z. B. nach typedef), entscheidet erst der Parser, sodass Lexer und Parser dort enger zusammenarbeiten müssen. Verwandt: Regex: Reguläre Ausdrücke.
Lexer und Parser im Zusammenspiel
Der Lexer liefert dem Parser einen Strom fertiger Token — der Parser sieht nie einzelne Zeichen. Dadurch wird die Syntax der Sprache auf der Ebene von Token beschrieben, und der Syntaxbaum entsteht aus der Tokenfolge. Das ist auch der Grund, warum die semantische Analyse und alle späteren Compiler-Phasen mit strukturierten Token- und Baum-Daten arbeiten statt mit rohem Text.
Verwandte Grundlagen: Lexikalische Analyse, Token, Parser, Compiler, Interpreter, Programmiersprache.