25.4 Ein Lexer

Rückschau

Nach der langen Theorie-Geschichte mit den Determinierten endlichen Automaten (äußerst abiturrelevant!) nun wieder etwas Praxis. Wir wollen mit unserem Projekt "Compilerbau" weitermachen.

Bisher hatten wir einen Stackinterpreter programmiert, welche in der Lage war, Stackcode aus einer Textdatei zu lesen und zu interpretieren. Diesen Stackcode haben wir bis jetzt selbst geschrieben, mit einem normalen Texteditor wie zum Beispiel Notepad.exe oder Textwrangler.app.

Ausschau

Wir wollen unser Projekt jetzt so erweitern, dass dieser Stackcode automatisch erzeugt wird. Dazu "bauen" wir uns einen eigenen kleinen Compiler. Wenn beispielsweise der String

"(3 + 4) * 3.14"

eingegeben wird, dann soll der Stackcode

PUSH 3
PUSH 4
ADD
PUSH 3.14
MUL

von unserem Compiler erzeugt werden. Der String kann entweder als Parameter für eine Methode eingegeben werden, oder er wird aus einer Textdatei gelesen, das ist jetzt erst mal egal.

In der Einführung dieser Folge hatten wir gesagt, dass der Übersetzungsvorgang durch einen Compiler sechs Phasen umfasst. Die erste Phase ist die lexikalische Analyse, mit der wir uns jetzt beschäftigen wollen. Determinierte endliche Automaten spielen bei dieser lexikalischen Analyse eine sehr wichtige Rolle.

Lexikalische Analyse

Schauen wir uns noch einmal den Eingabe-String an:

"(3 + 4) * 3.14"

Die Anführungszeichen "" können wir einfach ignorieren, denn der eigentliche String besitzt ja keine Anführungszeichen, dieses dienen ja nur dazu, dem Java-Compiler mitzuteilen, dass jetzt ein String folgt. Die lexikalische Analyse muss sich also nur um die Zeichenkette

(3 + 4) * 3.14

kümmern.

Lexikalische Analyse Schritt für Schritt

Das erste Zeichen dieser Zeichenkette ist eine geöffnete runde Klammer. Hier muss die lexikalische Analyse nur "nachschlagen", ob eine geöffnete runde Klammer zu den erlaubten Zeichen der Sprache gehört. Das ist natürlich der Fall. Bei einem Ausdruck wie

((((3 + 4) * 3.14

würde die lexikalische Analyse keinen Fehler melden, denn alle vier runden Klammern gehören zu den erlaubten Zeichen. Erst die syntaktische Analyse würde einen Fehler erkennen. Aber so weit sind wir noch lange nicht...

Als nächstes Zeichen kommt hier eine Zahl, nämlich die 3. Da in unserem Projekt nicht zwischen ganzen und reellen Zahlen unterschieden wird - alle Zahlen sind grundsätzlich reelle Zahlen - wird die 3 als korrekte reelle (double) Zahl erkannt.

Das nächste Zeichen ist ein Leerzeichen. Ein intelligenter Lexer - so nennt man den Teil des Compilers, der für die lexikalische Analyse zuständig ist - würde natürlich im ersten Analyseschritt alle überflüssigen Leerzeichen entfernen. Aus dem Eingabestring

(3 + 4) * 3.14

würde der String

(3+4)*3.14

erzeugt.

Das nächste Zeichen ist ein Pluszeichen, das natürlich ebenfalls erlaubt ist. Dann kommt wieder eine double-Zahl, dann eine geschlossene runde Klammer gefolgt von einem Multiplikationszeichen. Ganz am Ende noch einmal eine double-Zahl.

Aufgabe des Lexers

Ein einfacher Lexer würde jetzt einfach melden: "In Ordung, der Eingabestring ist korrekt" oder so ähnlich. Aber damit kann ein Compiler nicht viel anfangen. Der Compiler soll ja den Eingabestring in Maschinensprache oder in unserem Fall in Stackcode übersetzen. Dazu muss der Compiler die Zahlenwerte 3, 4 und 3.14 speichern, denn diese müssen ja im Stackcode wieder erscheinen.

Eine Lexer-Klasse

Quelltext eines einfachen Lexers

Hier sehen Sie den Java-Quelltext einer Klasse Lexer, die einen ganz primitiven Lexer zur Verfügung stellt. Die Hauptmethode dieser Klasse ist istInt. Diese Methode überprüft einen Eingabestring s daraufhin, ob es sich um eine lexikalisch korrekte int-Zahl handelt. Dazu wird der determinierte endliche Automat für int-Zahlen modelliert, in dem Quelltext können Sie die drei Zustände 1, 2 und 3 erkennen.

Die beiden privaten Methoden erleichtern istInt die Arbeit, sie testen, ob ein gegebenes Zeichen eine Ziffer (0..9) oder ein Vorzeichen (+, -) ist.

public boolean istDouble(String eingabe)