Quelltext der Seite 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 (Übersetzerbau)|Token]]. Ein [[Computerprogramm]], das eine lexikalische Analyse durchführt, wird '''Lexer''', '''Tokenizer''' oder '''lexikalischer Scanner''' genannt. Ein Lexer ist meist Teil eines [[Compiler]]s und wird als erster Schritt in der [[Compiler#Frontend (auch „Analysephase“)|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 (Übersetzerbau)|Token]], spricht man auch von ''lexikalischer Analyse''. Typischerweise geschieht die Zerlegung nach den Regeln von [[Reguläre Sprache|regulären Grammatik]]en, und der Tokenizer ist durch eine Menge [[endlicher Automat]]en realisiert. Verfahren zur Überführung eines regulären Ausdrucks in einen [[Nichtdeterministischer endlicher Automat|nichtdeterministischen endlichen Automaten]] sind das [[Berry-Sethi-Verfahren]] sowie die Thompson-Konstruktion.<ref>{{Webarchiv |url=http://dragonbook.stanford.edu/lecture-notes/Stanford-CS143/03-Lexical-Analysis.pdf |text=Stanford Dragon Book Compilerbau - Lexical Analysis |wayback=20160306215317 |archiv-bot=}} (englisch)</ref> Durch Anwendung der [[Potenzmengenkonstruktion]] lässt sich ein nichtdeterministischer in einen deterministischen endlichen Automaten überführen.

Ein Tokenizer kann Bestandteil eines [[Parser]]s 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 zur weiteren Verarbeitung (d.&nbsp;h. syntaktischen Analyse) übergeben.

== 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 (Informatik)|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.

{{Siehe auch|Parsergenerator}}

== Weblinks ==
* [https://github.com/westes/flex Flex] – [[C++]], [[C (Programmiersprache)|C]] (englisch)
* [http://re2c.org/ re2c] – [[C (Programmiersprache)|C]] (englisch)
* [http://quex.org/ Quex] – [[C++]], [[C (Programmiersprache)|C]] (englisch)
* [http://www.jflex.de/ JFlex] – [[Java (Programmiersprache)|Java]] (englisch)
* [https://github.com/annoflex/annoflex/ AnnoFlex] – [[Java (Programmiersprache)|Java]] (englisch)
* [https://github.com/ryangjchandler/lexical Lexical] – [[PHP]] (englisch)

== Einzelnachweise ==
<references />

[[Kategorie:Programmierwerkzeug]]
[[Kategorie:Compilerbau]]