25.2 Lexikalische Analyse und DEAs

Auf der vorherigen Seite haben wir die Arbeitsweisen eines Compilers kennengelernt. Wir wollen nun der Reihe nach die einzelnen Phasen näher unter die Lupe nehmen. Beginnen wir mit der lexikalischen Analyse, der ersten Phase eines Compilers.

Bei der lexikalischen Analyse wird geprüft, ob Bezeichner, Zahlen etc. einer Programmiersprache richtig geschrieben worden sind. Um tiefer in dieses abiturrelevante Thema einzusteigen, beginnen wir mit Java-Bezeichnern.

Beispiel 1: Java-Bezeichner

Ein Java-Bezeichner wie zum Beispiel radius oder klasse7 oder VarList oder objekt_12 wird nach bestimmten Regeln gebildet. Diese Regeln kann man auf verschiedene Weisen ausdrücken, zum Beispiel umgangssprachlich:

Umgangssprachlich:

Ein Java-Bezeichner beginnt immer mit einem Buchstaben. Dann können Buchstaben, Ziffern oder Unterstriche folgen.

Syntaxdiagramm:

Man kann die Regel aber auch durch ein Diagramm definieren:

Syntaxdiagramm für Java-Bezeichner

Hier sehen wir ein sogenanntes Syntaxdiagramm für Java-Bezeichner. Man startet mit einem kleinen oder großen Buchstaben, dann kommen entweder weitere Klein- oder Großbuchstaben, oder Ziffern oder Unterstriche.

Für Voreilige
Determinierter endlicher Automat:

Darstellung eines Java-Bezeichners durch einen determinierten endlichen Automaten mit zwei Zuständen

Diese graphische Darstellung unterscheidet sich von dem Syntaxdiagramm. Ein determinierter endlicher Automat oder kurz DEA besteht aus einer endlichen Anzahl von Zuständen - hier sind es zwei. Die Zustände sind durch Pfeile miteinander verbunden, und an den Pfeilen stehen Zeichen oder ganze Worte.

Die Automat in der Abb. 2 startet im Zustand 1. Wenn dann ein kleiner oder großer Buchstabe erkannt wird, geht der Automat in den Zustand 2 über. Wenn im Zustand 2 ein Buchstabe, eine Ziffer oder ein Unterstrich erkannt wird, bleibt der Automat im Zustand 2. Wird ein anderes Zeichen erkannt, zum Beispiel das Zeichen "&", so geht der Automat in einen Fehlerzustand über, der hier nicht eingezeichnet ist. Auch wenn im Zustand 1 ein anderes Zeichen erkannt wird, gelangt der Automat in einen Fehlerzustand.

Für Voreilige:
Grammatik

Hier sehen Sie eine weitere Art, Java-Bezeichner zu definieren:

P1 Bezeichner --> Buchstabe | Buchstabe Name
P2 Name       --> Buchstabe | Buchstabe Name | Ziffer Name | leer
P3 Buchstabe  --> a | b | ... | z | A | B | ... | Z
P4 Ziffer     --> 0 | 1 | ... | 9

Nach diesen Produktionsregeln kann ein Bezeichner aus einem einzelnen Buchstaben bestehen (erste Alternative der Produktionsregel P1) oder aus einem einzelnen Buchstaben, gefolgt von einem Namen (zweite Alternative von P1).

Dieser Name kann dann wieder ein einzelner Buchstabe sein, alternativ ein Buchstabe gefolgt von einem Namen oder eine Ziffer gefolgt von einem Namen. Auch ein leerer Name ist möglich.

Ein Bezeichner wie xPos3 würde dann folgendermaßen hergeleitet:

Eine Herleitung für den Bezeichner xPos3

Sie müssen an dieser Stelle die Theorie der endlichen Automaten und Grammatiken noch nicht vollständig verstehen, in einem späteren Kapitel wird dieses absolut abiturrelevante Thema noch vertieft.

Beispiel 2: int-Zahlen

Determinierter endlicher Automat für int-Zahlen

Umgangssprachlich könnte man int-Zahlen vielleicht so definieren: Am Anfang kann ein Vorzeichen (+ oder -) kommen, bei positiven Zahlen ist das +-Zeichen aber nicht notwendig. Dann muss eine Ziffer kommen. Danach können weitere Ziffern folgen.

Die Darstellung durch eine Graphik ist vielleicht verständlicher. In der Abbildung 3 sehen wir die graphische Darstellung eines determinierten endlichen Automaten mit drei Zuständen, der int-Zahlen erkennt - oder erzeugt, je nach Sichtweise.

Der DEA für int-Zahlen, näher betrachtet

Wir wollen die Funktionsweise dieses determinierten endlichen Automaten an dem Beispiel +34.56 kennenlernen. Der DEA startet mit Zustand 1 (Startzustand). Als erstes Zeichen wird ein '+' erkannt, was den Automaten in den Zustand 2 versetzt. Das nächste erkannte Zeichen ist '3', damit kommt der DEA in den Zustand 3. Mit der '4', dem nächsten Zeichen, bleibt der DEA im Zustand 3. Jetzt kommt als fünftes Zeichen der Dezimalpunkt. Dieses Zeichen gehört nicht zu den gültigen Zeichen, die aus dem Zustand 3 herausführen. Also landet der Automat in einem Fehlerzustand. Damit ist klar: Die Zeichenfolge +34.56 gehört nicht zu den int-Zahlen.

Mit der Zeichenfolge +34 dagegen würde sich der Automat nach dem Lesen des letzten Zeichens '4' im Zustand 3 befinden. Zustand 3 ist ein Endzustand, und wenn der DEA sich nach dem Lesen des letzten Zeichens in einem Endzustand befindet, ist alles gut. Die Zeichenfolge ist dann eine gültige int-Zahl.

Beispiel 3: double-Zahlen

Determinierter endlicher Automat für double-Zahlen

Hier sehen wir die graphische Darstellung eines DEAs für double-Zahlen. Wir wollen die Arbeitsweise einmal für die Eingabe "+34.56" untersuchen.

Als erstes wird das Zeichen '+' erkannt. Damit gelangt der Automat vom Startzustand 1 in den Zustand 2. Nun kommt das Zeichen '3', und der DEA gelangt in den Zustand 3. Mit dem nächsten Zeichen, der '4', bleibt der DEA im Zustand 3. Jetzt kommt der Dezimalpunkt, wodurch der DEA im Zustand 4 landet. Das Zeichen '5' versetzt den DEA in den Zustand 5, und mit dem letzten Zeichen '6' bleibt der Automat in diesem Endzustand. Alle Zeichen der Eingabe sind abgearbeitet, und der DEA befindet sich in einem Endzustand. Also gehört die Zeichenkette "+34.56" eindeutig zu den double-Zahlen.

Was passiert, wenn dieser DEA eine ganze Zahl vorfindet, zum Beispiel "+34"? Gibt das jetzt eine Fehlermeldung?

Mit '+' gelangt der DEA in Zustand 2, mit '3' in Zustand 3 und mit '4' verbleibt er im Endzustand 3. Da der Zustand 3 ein Endzustand ist, gilt die Zeichenfolge "+34" ebenfalls als gültige double-Zahl.

public boolean istDouble(String eingabe)