Lexikalische Analyse

Lexikalische Analyse ist in der Informatik die Zerlegung einer Zeichenkette (z. B. Quelltext) in eine Folge von logisch zusammengehörigen Einheiten, sogenannte Token. Ein Computerprogramm, das eine lexikalische Analyse durchführt, wird Lexer, Tokenizer oder lexikalischer Scanner genannt. Ein Lexer ist meist Teil eines Compilers und wird als erster Schritt in der Analysephase ausgeführt. Das Ergebnis des Lexers wird im nächsten Schritt von einem Parser weiterverarbeitet.

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.

Einzelnachweise

  1. ↑ Stanford Dragon Book Compilerbau - Lexical Analysis (Memento vom 6. März 2016 im Internet Archive) (englisch)