Tokenizer
Ein Tokenizer (auch lexikalischer Scanner, kurz Lexer) ist ein Computerprogramm zur Zerlegung von Plain text (zum Beispiel Quellcode) in Folgen von logisch zusammengehörigen Einheiten, so genannte Token (englisch tokens). Als solcher ist er oft Teil eines Compilers.
Grundlagen
Bei der Zerlegung einer Eingabe in eine Folge von logisch zusammengehörigen Einheiten, in die so genannten Token, spricht man auch von lexikalischer Analyse. Typischerweise geschieht die Zerlegung nach den Regeln von regulären Grammatiken, und der Tokenizer ist durch eine Menge endlicher Automaten realisiert. Verfahren zur Überführung eines regulären Ausdrucks in einen nichtdeterministischen endlichen Automaten sind das Berry-Sethi-Verfahren sowie die Thompson-Konstruktion.[1] Durch Anwendung der Potenzmengenkonstruktion lässt sich ein nichtdeterministischer in einen deterministischen endlichen Automaten überführen.
Ein Tokenizer kann Bestandteil eines Parsers sein und hat dort vorverarbeitende Funktion. Er erkennt innerhalb der Eingabe Schlüsselwörter, Bezeichner, Operatoren und Konstanten. Diese bestehen aus mehreren Zeichen, bilden aber jeweils logische Einheiten, sogenannte Token. Diese werden an den Parser zu weiteren Verarbeitung (d. h. syntaktischen Analyse) weitergereicht.
Programme zur Erzeugung
Wenn man eine formale Beschreibung der zu erkennenden Lexik angeben kann, lässt sich ein Tokenizer automatisch generieren. Das in Unix-Betriebssystemen enthaltene Programm Lex sowie das als freie Software entwickelte Flex erfüllen genau diese Funktion. Aus der formalen Beschreibung generieren diese Programme eine Funktion, die aus einem eingegebenen Text das jeweils nächste Token ermittelt und zurückgibt. Diese Funktion findet dann meist in einem Parser Verwendung.
Weblinks
Einzelnachweise
- Stanford Dragon Book Compilerbau (Memento des Originals vom 6. März 2016 im Internet Archive) Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis. (englisch)
