Lexikalische Analyse

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 zur weiteren Verarbeitung (d. h. syntaktischen Analyse) übergeben.

Die lexikalische Analyse unterteilt die eingegebene Zeichenkette im Wesentlichen in Tokens, indem sie die Zeichen zu Einheiten zusammenfasst und kategorisiert. Dieser Prozess kann jedoch deutlich komplexer ausfallen. Im einfachsten Fall können Lexer Tokens weglassen oder zusätzliche Tokens einfügen. Das Weglassen von Tokens – insbesondere von Leerräumen (Whitespace) und Kommentaren – ist ein sehr häufiges Verfahren, sofern diese vom Compiler nicht benötigt werden. Weniger häufig werden hingegen zusätzliche Tokens eingefügt. Dies geschieht vor allem, um Tokens zu Anweisungen oder Anweisungen zu Blöcken zusammenzufassen und auf diese Weise die Arbeit des Parsers zu vereinfachen.

Die Zeilenfortsetzung ist eine Funktion einiger Programmiersprachen, in denen ein Zeilenumbruch normalerweise als Anweisungsabschluss dient. Meistens führt das Beenden einer Zeile mit einem Backslash, dem unmittelbar ein Zeilenumbruch folgt, dazu, dass die Zeile fortgesetzt wird. Die nachfolgende Zeile wird dabei an die vorangegangene angehängt. Dies erfolgt im Allgemeinen im Lexer: Der Backslash und der Zeilenumbruch werden verworfen, anstatt dass der Zeilenumbruch als Token verarbeitet wird. Zu den Beispielen zählen Bash, andere Shell-Skripte sowie Python.^[2][3]

Viele Programmiersprachen verwenden das Semikolon als Abschlusszeichen von Anweisungen. Meistens ist dies zwingend erforderlich. In einigen Programmiersprachen ist das Semikolon jedoch in vielen Kontexten optional. Dies geschieht hauptsächlich auf der Ebene des Lexers, wo der Lexer ein Semikolon in den Token-Strom ausgibt, obwohl im Eingabezeichenstrom keines vorhanden ist. Dieser Vorgang wird als Semikolon-Einfügung oder automatische Semikolon-Einfügung bezeichnet. In diesen Fällen sind Semikolons zwar Teil der formalen Grammatik der Sprache, müssen jedoch nicht zwangsläufig im Eingabetext zu finden sein, da sie vom Lexer eingefügt werden können. Optionale Semikolons – oder andere Abschlusszeichen und Trennzeichen werden mitunter auch auf der Ebene des Parsers verarbeitet, insbesondere im Falle von nachgestellten Kommas oder Semikolons.

Um Fehler zu vermeiden, empfehlen manche Programmierer die konsequente Verwendung von Semikolons, während andere sogenannte defensive Semikolons – also vorangestellte Semikolons – am Beginn potenziell mehrdeutiger Anweisungen setzen. Die Semikolon-Einfügung in Sprachen, deren Anweisungen durch Semikolons abgeschlossen werden und die Zeilenfortsetzung in Sprachen, deren Anweisungen durch Zeilenumbrüche abgeschlossen werden lassen sich als komplementäre Konzepte betrachten: Die Semikolon-Einfügung fügt ein Token hinzu, obwohl Zeilenumbrüche im Allgemeinen keine Tokens erzeugen. Die Zeilenfortsetzung hingegen verhindert die Erzeugung eines Tokens, obwohl Zeilenumbrüche normalerweise sehr wohl Tokens generieren.^[4]

Folgendes Codebeispiel in der Programmiersprache C++ zeigt die Zerlegung in Token. Der Programmcode wird dabei vom Lexer als eine Zeichenkette behandelt.

#include <iostream>
#include <cmath>
 
const double PI = 3.14159;
 
double circleArea(double r)
{
    return PI * r * r;
}
 
int main()
{
    double radius = 4;
    cout << "Area = " << circleArea(radius) << endl;
    return 0;
}

Der Modifikator const, return und die elementaren Datentypen double und int sind Schlüsselworter. iostream, cmath, PI, circleArea, r, main, radius, cout, endl sind Bezeichner von Variablen, Funktionen und Namesräumen. Die Token =, *, << sind Operatoren. Die explizit geschriebenen Werte 3.14159, 4 und "Area = " sind Literale. <, >, (, ), {, }, ; gehören zur Interpunktion. Die Schlüsselwörter #include sind Präprozessor-Token, die in einer Phase verarbeitet werden, welche vor dem eigentlichen Lexer abläuft. Beim realen Compilieren eines C++ Programms werden diese zunächst expandiert, wobei <iostream> durch Tausende Zeilen Header-Code ersetzt wird, bevor die lexikalische Analyse des eigentlichen Programmcodes beginnt.

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.

• Flex – C++, C (englisch)
• re2c – C (englisch)
• Quex – C++, C (englisch)
• JFlex – Java (englisch)
• AnnoFlex – Java (englisch)
• Lexical – PHP (englisch)