- Lexikalische Analyse
-
Ein lexikalischer Scanner (kurz Lexer) ist ein Computerprogramm zur Zerlegung von Eingaben in Folgen von logisch zusammengehörigen Einheiten, so genannte Token (engl. tokens).
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 einer regulären Grammatik, und der Scanner ist als endlicher Automat realisiert. Ein Verfahren zur Überführung eines regulären Ausdrucks in einen endlichen Automaten ist das Berry-Sethi-Verfahren.
Ein Scanner ist ein spezieller Parser und meist vorverarbeitender Teil eines weiteren Parsers. Er erkennt dabei innerhalb der Eingabe Schlüsselwörter, Bezeichner, Operatoren und Konstanten. Erkannte Token werden mit ihrem jeweiligen Typ zurückgeliefert. Der nachfolgende Parser arbeitet dann auf den Token als atomaren Symbolen (auch Terminalsymbole genannt).
Ein Scanner kann einen separaten, so genannten Screener benutzen, um Leerraum und Kommentare zu entfernen. Häufig wird das jedoch von der zugrunde liegenden Grammatik abgedeckt.
Programme zur Erzeugung
Wenn man eine formale Beschreibung der zu erkennenden Lexik angeben kann, lässt sich ein lexikalischer Scanner 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. Siehe auch Parsergenerator.
Weblinks
Wikimedia Foundation.
