Folge 27 - Lexikalische Analyse

1. Aufgabe der lexikalischen Analyse

Die lexikalische Analyse gehört zur Analysephase eines Übersetzungsvorgangs. Hier wird überprüft, ob z.B. Bezeichner und Zahlenkonstanten korrekt geschrieben sind. Diesen Teil des Compilers kann man mit Hilfe von Determinierten Endlichen Automaten implementieren.

Übung 27.1 (4 Punkte)

Hier sehen Sie den Quelltext einer Klasse Lexer mit einer Methode istInt(), welche den übergebenen String daraufhin überprüft, ob es sich um eine gültige int-Zahl handelt.

Es handelt sich also um die Java-Implementierung eines DEAs für int-Zahlen. Den Quelltext müssen Sie nicht abtippen, sondern klicken Sie einfach hier für die Textdatei.

Nun zu Ihrer Aufgabe:

Ergänzen Sie den Lexer um eine Methode istDouble(), die einen DEA für reelle Zahlen wie z.B. "+3.1459" implementiert (3 Punkte), sowie um eine Methode istBezeichner(), die einen DEA für Java-Bezeichner implementiert (1 Punkt).

Hinweise:

Es wäre übrigens sehr hilfreich, wenn Sie sich langsam mit der umfassenden Klasse String vertraut machten (siehe Sun-Dokumentation). Auf der Sun-Seite finden Sie auch sehr anschauliche Beispiele für die switch-case-Anweisung, die man ja alternativ zu den geschachtelten if-else-Anweisungen einsetzen könnte.

Testen des Lexers:

Sie können Ihre Lexer-Klasse mit diesem Java-Applet überprüfen.

2. Ein Lexer

Wir wollen nun einen richtigen Lexer betrachten, also den Teil eines Compilers, der aus den Eingabezeilen sogenannte Tokenströme erzeugt, die dann dem Parser zur syntaktischen Analyse übergeben werden.

Ein Tokenstrom besteht aus einer linearen Folge (einem Array, einer Arrayliste, einer dynamischen Liste etc.) von einzelnen Token. Ein Token wiederum hat zwei Eigenschaften, einen Typ und einem Attribut, wobei letzteres einen Stringwert oder einen numerischen Wert haben kann.

Unser primitiver Lexer soll folgende sechs Tokentypen kennen:

Tokentyp Stringattribut Zahlenattribut
id Variablenname ---
num --- Zahlenwert
mul * oder / ---
add + oder - ---
assop --- ---
sem --- ---

Der Tokentyp "id" hat ein Stringattribut mit dem Namen des Bezeichners bzw. der Variable. Der Tokentyp "num" hat kein Stringattribut, aber dafür ein Zahlenattribut mit dem Wert der double-Zahl.

Bei den Rechenoperatoren +, -, * und / hat es sich in der Praxis eingebürgert, einen Tokentyp "add" für die Addition und Subtraktion sowie einen Tokentyp "mul" für die Multiplikation und Division einzuführen. Das hängt damit zusammen, dass man zwischen Strichrechnung und Punktrechnung unterscheidet und dass die Punktrechnung eine höhere Priorität hat als die Strichrechnung ("Punktrechnung geht vor Strichrechnung"). Im Stringattribut wird dann gespeichert, um welche Rechenart es sich genau handelt. Beim Tokentyp "add" gibt es dann die beiden Stringattribute "+" und "-", und beim Tokentyp "mul" die beiden Stringattribute "*" und "/".

Die beiden letzten Tokentypen, "assop" und "semi" haben weder ein String- noch ein Zahlenattribut, da es jeweils nur eine "Variante" von den beiden Tokentypen gibt. Alternativ hätte man auch einen neuen Tokentypen "sonstiges" einführen können und im Stringattribut speichern können, ob es sich um einen Zuweisungsoperator, ein Semikolon etc. handelt.

Übung 27.2 (2 Punkte)

Das hört sich ja alles schön und gut an, aber wir wollen jetzt mal etwas praktischer werden. Wie müsste eine Klasse Token aufgebaut sein, um den oben genannten Anforderungen an ein Token gerecht zu werden? Da wir in diesem und den nächsten Kapiteln nicht mehr viel programmieren werden, lohnt es sich eigentlich nicht, dass Sie sich an den Computer setzen. Ein Blatt Papier und ein Bleistift reichen für diese Übung völlig aus. Entwerfen Sie also bitte auf dem Papier, wie eine Klasse Token aussehen müsste (Attribute, Methoden), die so arbeitet, wie oben beschrieben wurde.

3. Probleme bei der Implementierung eines Lexers

Die Klasse Lexer, die Sie in der Übung 27.1 bearbeitet haben, stellt Methoden zur Verfügung, die analysieren, ob ein übergebener String eine double-Zahl, eine int-Zahl oder ein Bezeichner ist. Das ist ja ganz nett, für die praktische Implementation eines Lexers reicht das aber noch lange nicht aus. Bei einem "echten" Lexer geht es nämlich nicht darum, zu beurteilen, ob der String "radius" ein Bezeichner und der String "3.14" eine double-Zahl ist, sondern es soll immer ein kompletter Java-Befehl analysiert werden, z.B. die Zuweisung

umfang = 2*pi * radius;

Hier tauchen ganz neue Probleme auf. Dieser String "umfang = 2*pi * radius" ist weder ein Bezeichner noch eine Zahl, sondern eine Zuweisung. Zur lexikalischen Analyse muss der Lexer diesen String erst in seine einzelnen Bestandteile zerlegen. Ein erster Schritt der Analyse wäre das Entfernen von Leerzeichen, die ja eigentlich nicht benötigt werden, sondern vom Programmierer nur aus Gründen der besseren Übersichtlichkeit hinzugefügt wurden. Nach Entfernung der Leerzeichen sieht der zu analysierende String so aus:

umfang=2*pi*radius;

An dieser Stelle können wir gleich die nächste praktische Übung einschieben, damit Ihnen vor lauter Theorie nicht die Gehirnzellen kollabieren.

Übung 27.3 (2 Punkte)

Schreiben Sie für die Klasse Lexer eine Methode, die sämtliche Leerzeichen aus einem gegebenem String entfernt. In der Sun-Dokumentation zur Klasse String finden Sie sicherlich hilfreiche Methoden.

Zurück zu den Problemen bei der Implementierung eines Lexers.

Schauen wir uns noch einmal den DEA zur Erkennung von Bezeichnern an

und betrachten wir dann noch einmal die Quelltextzeile

umfang=2*pi*radius;

die unser Lexer in einen Tokenstrom zerlegen soll. Der Lexer enthält einen DEA zur Analyse von Bezeichnern sowie eine sehr wichtige Methode getNextToken(), welche das jeweils nächste Token zurückliefert. In unserem konkreten Fall müsste diese Methode beim ersten Aufruf das Token "id" mit dem Stringattribut "umfang" zurückliefern. Ganz am Anfang muss getNextToken aber eine Vor-Analyse machen. Das erste Zeichen des gesamten Strings "umfang=2*pi*radius" ist der Buchstabe "u". Ein solcher Buchstabe kommt weder in einer Zahl noch in einem anderen Token vor, ausschließlich in Bezeichnern, also in id-Token. Nachdem getNextToken() also erkannt hat, dass der String wohl mit einem Bezeichner beginnt, wird der DEA für Bezeichner aufgerufen. Dieser startet im Zustand 1 und wird durch das Zeichen "u" in den Zustand 2 überführt. Jetzt kommen nacheinander die anderen Zeichen des Bezeichners - "m", "f", "a", "n" und "g". Nach dem Abarbeiten von "g" befindet sich der DEA im Zustand 2, also im Endzustand. Der String "umfang=2*pi*radius" ist aber noch lange nicht zuende. Als nächstes Zeichen kommt jetzt ein "=". Dieses Zeichen gehört aber nicht zum Alphabet des DEAs für Bezeichner. Der DEA müsste jetzt also in einen Fehlerzustand geraten.

Mehr möchte ich an dieser Stelle nicht ausführen, weil Sie selbst ja auch noch etwas denken sollen. Also kommen wir zur nächsten Übung dieser Seite, für die Sie wieder keinen Computer benötigen. Solche Übungen empfehlen sich für die häusliche Arbeit! In der Schule sollten Sie dann lieber die praktischen Übungen machen.

Übung 27.4 (4 Punkte)

Sie haben das Problem bei der Implementierung eines Lexers hoffentlich erkannt. Welche Lösung würden Sie für das Problem vorschlagen? Erläutern Sie Ihre Lösung mit Hilfe einer Präsentation, eines übersichtlichen Tafelbildes, einer Zeichnung etc.

Übung 27.4 - Alternative A (4 Punkte)

Demonstrieren Sie mit Hilfe einer Präsentation, wie ein Lexer genau arbeitet und wie eine Java-Quelltextzeile in einzelne Token zerlegt wird. Gehen Sie dabei auch auf die Probleme bei der Implementierung eines Lexers ein. Bewertet wird - wie immer bei Präsentationen - nicht die Präsentation an sich, sondern hauptsächlich Ihr mündlicher Vortrag.

Übung 27.4 - Alternative B (8 Punkte)

Hier finden Sie den Quelltext einer Delphi-Unit, welche einen funktionierenden Lexer zur Verfügung stellt, der so arbeitet, wie auf dieser Seite besprochen.

Schreiben Sie eine entsprechende Java-Klasse Lexer, die das Gleiche leistet.

Persönliche Bemerkung

Ich habe mich selbst an der Aufgabe versucht und habe nach zwei Nachmittagen frustriert aufgeben; Java ist doch wesentlich komplizierter als Pascal bzw. Delph. Aber vielleicht haben Sie ja mehr Erfolg.

weiter mit Folge 29: kontextfreie Grammatiken

Hier beginnen wir mit dem zweiten Teil des Compilierungs-Vorganges, der syntaktischen Analyse. Damit Sie verstehen, wie dieser Teil des Compilers überhaupt arbeitet, ist es zuvor erforderlich, sich mit den Grundlagen der kontextfreien Grammatiken vertraut zu machen.

Diese HTML-Seite wurde erstellt von Ulrich Helmich am 28. Juli 2006.






IMPRESSUM