Wir haben die Spezifikation während des Programmierens leicht abändern müssen. Daher hier noch einmal: (Änderungen sind in rot markiert)
 
 

Der Scanner, der die lexikalische Analyse durchführen soll, wird anhand eines deterministischen endlichen Automaten (DEA) realisiert. Die in der Eingabedatei eingabe enthaltenen Zeichen werden zeichenweise eingelesen, analysiert und dienen dabei zur Zustandsänderung des DEA. Wird ein SM-Befehl, ein Identifier oder eine Ganzzahlkonstante erkannt, wird ein entsprechendes Symbol in die Ausgabedatei ausgabe geschrieben, evtl. wird ebenfalls die Symboltabelle Symtab modifiziert; diese Symboltabelle enthält für jeden Identifier neben seiner Darstellung als Zeichenkette ein (einzigartiges) Symbol. [..] Wird ein Identifier erkannt, dem noch kein Symbol in der Symboltabelle zugeordnet ist, wird ein neues (einmaliges) Symbol erzeugt, diesem zugeordnet und in der Symboltabelle gespeichert. Ungültige Identifier werden mit einer Fehlermeldung bemängelt.
 
 

Deklarationen:

Typen:

Symtab - Liste von (Zeichenkette,Symbol)-Tupeln

readforward - Eingabestrom. Liest Dateien aus 8bit-Zeichen (ASCII)

Methoden:

char readforward.nextchar() - liest das nächste Zeichen aus eingabe, gibt es zurück und setzt

den Lesezeiger auf das nächste Element.

charreadforward.lookahead() - liest das nächste Zeichen, setzt den Lesezeiger nicht weiter

void readforward.forgetnext() - „vergißt“ das nächste Zeichen (überspringt es), setzt den

Lesezeiger auf das folgende Element

void readforward.lastagain() - setzt den Eingabedateizeiger um ein Zeichen zurück.

boolean Symtab.isInTab(String sym) - true, wenn sym in der Symboltabelle vorhanden ist

int Symtab.knownSym(String sym) - gibt ein Symbol für sym zurück, falls sym in der Tabelle

vorhanden, ansonsten 0

int Symtab.newSym(String sym) - gibt ein (neues) Symbol für Sym zurück, falls sym nicht in 

der Tabelle ist, ansonsten 0

String Symtab.allSym() - gibt alle Symbole und deren Bezeichner als String aus.

Konstanten:

Die Symbole für die SM-Befehle sind die in dem Buch „Vom Problem zum Programm“ von H. Klaeren auf Seite 131 f. (Def. 4.33) angegebenen Befehlsnummern. Abweichend dazu werden von dem Programm außerdem die Befehle READ mit dem Symbol 17 und WRITE mit 18 erkannt und übersetzt.
 
 

Eingabe:

eingabe - Datei von readforward
 
 

Vorbedingungen:

ausgabe - möglichst beendet durch das Zeichen eof

enthält SM-Code^*)
 
 

Ausgabe:

ausgabe - Datei von Symbolen für SM-Code, falls Vor-, Neben- und Nachbedingung erfüllt sind.
 
 

Nachbedingungen:

Das Programm gibt „EOF erreicht, Programm übersetzt! (x Zeichen!)“ auf die Konsole aus, wenn der Vorgang erfolgreich war, oder eine entsprechende Fehlermeldung, falls nicht.
 
 

^*) Genauere Erläuterung zu den Vorbedingungen: Die Produktion für gültige Identifier ist:

ID:=(a|b|...|z|A|B|...|Z){a|b|...|z|A|B|...|Z|0|1|...|9}

Die von SM-Befehlen benutzten Identifier sind jedoch als Variablennamen oder Sprungmarken ungültig. Wird ein Identifier gelesen, der nicht dieser Produktion entspricht, so wird eine Fehlermeldung ausgegeben und das Programm beendet. (Siehe Ausgabe)

SM-Befehle werden im Buch von Klaeren grundsätzlich in Großbuchstaben angegeben. Dieses Programm übersetzt auch kleingeschriebene SM-Befehle oder Mischungen aus Groß- und Kleinschreibung. Da in dem o.g. Buch keine Angaben über negative Konstantendeklarationen gemacht werden, unterstützt das Programm diese nicht. Statt „const –1“ ist also „const 0 const 1 sub“ zu verwenden.

Begrenzer stehen zwischen den Befehlen und trennen diese voneinander. Gültige Begrenzer sind das Leerzeichen, LF (Line Feet, ASCII 0Ah), CR (Carriage Return, ASCII 0Bh), das Komma und Kommentare der Form (*Kommentar*). Achtung: Das Programm unterscheidet nicht zwischen den einzelnen Begrenzern; es ist daher auch mögich, daß Konstrukte wie call,1 2(* lok. Var. *)3 übersetzt werden wie CALL 1,2,3. Es wird allerdings eine Warnung ausgegeben.
 
 

Das Programm wird im Prinzip ähnlich strukturiert sein wie ich es bereits in Aufgabe 69. des Übungsblattes 3 beschrieben habe. Es ist jedoch nötig, jenen Entwurf um weitere Zustände für die noch fehlenden SM-Befehle zu erweitern.
 
 

N=nächstes Zeichen
ändere Zustand anhand von N

falls Zustand für SM-Befehl, dann Symbol für Befehl ausgeben

falls Zustand für Konstante, dann Konstantensymbol und Konstantenwert ausgeben

falls Zustand für Variable, dann ID-Symbol und Symbol für ID (aus Symboltabelle) ausgeben.

Gegebenenfalls neues Symbol in der Symboltabelle anlegen, wenn der Variablenname noch nicht angelegt wurde.

solange von 1 an wiederholen, bis Zustand eof erreicht

Klasse Symtab:

Implementiert die Symboltabelle
 
 

Klasse Sym:

Enthält die Informationskomponenten der Liste.
 
 

Konstruktor Sym():

Erzeugt ein leeres Element.

Eingabe: keine

Ausgabe: ein neues Element, initialisiert mit Standardwerten.
 
 

Konstruktor Sym(Sym p, Sym n):

Erzeugt ein Element, das in die Liste eingereiht wird.

Eingabe: p - vorangegangenes Element, n - nachfolgendes Element
 
 

Konstruktor Symtab():

Erzeugt eine leere Liste, in der alle Zeiger auf Null stehen.

Eingabe: keine

Ausgabe: leere Liste von Sym
 
 

Methode Add(String bez, int sym) (unsichtbar)

Fügt ein neues Element hinzu.

Eingabe: lex - der hinzuzufügende Bezeichner, sym - das dazugehörige Symbol

Ausgabe: Liste wird um ein Element vergrößert
 
 

Methode Next() (unsichtbar)

Setzt den Zeiger io ein Element weiter. Es findet keine Null-Überprüfung statt.

Eingabe: keine

Ausgabe: weitergesetztes io oder Laufzeitfehler, falls io=null
 
 

Methode Last() (unsichtbar)

Setzt den Zeiger io ein Element zurück. Es findet keine Null-Überprüfung statt.

Eingabe: keine

Ausgabe: zurückgesetztes io oder Laufzeitfehler, falls io=null
 
 

Methode SetIO(int i) (unsichtbar)

Setzt den Zeiger io auf das i-te Element.

Eingabe: i - das gewünschte Element

Ausgabe: weitergesetztes io (io=null falls weniger Elemente als i)
 
 

Methode boolean isInTab(String sym)

Überprüft, ob ein Bezeichner bereits in die Tabelle eingetragen wurde

Eingabe: sym - gesuchte ID

Ausgabe: true, falls in der Liste, sonst false
 
 

Methode int knownSymbol(String sym)

Gibt das Symbol für einen bekannten Bezeichner zurück, oder 0 falls nicht gefunden.

Eingabe: sym - gesuchter ID

Ausgabe: 0 falls unbekannter ID, ansonsten das zugeordnete Symbol
 
 

Methode int newSym(String sym)

Legt ein neues Symbol in der Tabelle an und gibt ein ihm neu zugeordnetes Symbol zurück. (Es findet keine Überprüfung statt, ob das Symbol bereits eingetragen ist. Es wird dann einfach nochmal eingetragen!)

Eingabe: sym - neues Symbol

Ausgabe: neues Symbol, Liste um ein Symbol erweitert
 
 

Methode String allSym()

Gibt alle Symbole und Bezeichner (durch = getrennt) als Unicode-String zurück, jeweils getrennt durch LF+CR.

Klasse readforward (extends RandomAccessFile)

Die Eingabedatei ist von diesem Typ.
 
 

char last

letztes gelesenes Zeichen
 
 

Konstruktor readforward (String name)

Erzeugt eine neue Eingabedatei mit dem Namen name

Eingabe: name - Name der Datei

Ausgabe: neues Dateiobjekt last (enthält das erste Zeichen) oder Laufzeitfehler, falls Datei nicht existriert oder leer
 
 

Methode char nextchar()

Liest das nächste Zeichen und gibt das vorhergehende zurück

Eingabe: keine

Ausgabe: das zuvorgelesene Zeichen, last enthält das nächste, oder ASCII 0 falls EOF
 
 

Methode char lookahead()

Gibt last zurück

Eingabe: keine

Ausgabe: das zuletzt gelesene Zeichen
 
 

Methode forgetnext()

Liest das nächste Zeichen nach last

Eingabe: keine

Ausgabe: last enthält das folgende Zeichen
 
 

Methode lastagain()

Setzt den Lesezeiger um eins zurück und stellt das vorhergehende Zeichen in last bereit. Es wird nicht überprüft, ob die neue Lesezeigerposition gültig ist.

Eingabe: keine

Ausgabe: last enthält das vorhergehende Zeichen oder es wird ein Laufzeitfehler ausgegeben, wenn die neue Leseposition ungültig ist.
 
 

Klasse Analyse

Enthält das Hauptprogramm
 
 

readforward datei

Eingabedatei
 
 

Methode boolean IstBegrenzer (char letztes,int erwartet1,int erwartet2,long Stelle)

Überprüft, ob es sich bei letztes um einen Begrenzer handelt

Eingabe: letztes - zu überprüfendes Zeichen, erwartet1, erwartet2 - erwartete Zeichen, Stelle - Nummer des zuletzt gelesenen Zeichens

Vorbedingung: erwartet1, erwartet2 = 0 (Kommentar) | 32 (Space) | 10 (LF) | 13 (CR) | 44 (Komma). Wird eine andere Zahl angegeben, wird auf jeden Fall eine Warnung ausgegeben, daß ein anderer Begrenzer erwartet wurde.

Ausgabe: true, falls letztes ein Begrenzer ist, sonst false. Wenn ein anderer Begrenzer als einer der erwarteten erkannt wird, wird eine Warnung ausgegeben. Wird ein Kommentar erkannt, wird der Lesezeiger der Eingabedatei bis zum Ende des Kommentars vorgeschoben.
 
 

Methode erlaubterBez (String bez)

Überprüft, ob ein Bezeichner unerlaubte Zeichen enthält.

Eingabe: bez - zu Überprüfender Bezeichner

Ausgabe: false, falls ein unerlaubtes Zeichen im Bezeichner, sonst true
 
 

readforward datei: Eingabedatei
String[] parameter: Die dem Programm beim Start übergebenen Parameter. Die Feldlänge ist abhängig von der Menge der übergebenen Parameter. Benutzt wird sowieso nur parameter[0]; ist dieser nicht existent, so wird ein Benutzungshinweis ausgegeben.

RandomAccessFile ausgabe: Ausgabedatei (Die Spezifikation zu RandomAccessFile findet sich in der Java-Dokumentation §2.20.1, Seite 250ff.¹)

byte Zustand: beschreibt den Zustand des DEA. -1 ist der akzeptierende Zustand

char Zeichen: gelesenes Zeichen

int gelesene Zahl: während der Zustände 66 und 67 enthält diese die gelesene Zahl, ansonsten 0

long Stelle: die Position des Lesezeigers in der Eingabedatei

String gelesenesWort: Enthält immer das zuletzt gelesene „Wort“ (Text zwischen zwei Begrenzern) und wird im Zustand 0 gelöscht

Symtab SymbolTabelle: Die Symboltabelle

Character NurZumGrossschreiben: Character-Objekt, das nur dazu benutzt wird, um Zugriff auf die Funktion .toUpperCase zu erlangen, die benötigt wird, um eine Variable vom Typ char in Großschreibung zu überführen

int S: Nummer des Symbols in der Symboltabelle. (Nur gültig im Zustand 69)
 
 

keine lokalen Variablen
 
 

Sym pre: Vorgänger in der Liste, null falls es keinen gibt
Sym next: Nachfolger in der Liste, null falls es keinen gibt

int Symbol: Symbol (eine Zahl) für einen Bezeichner. Werden einfach fortlaufend nummeriert.

String Lexem: Der Bezeichner, dem die Zahl Symbol zugeordnet ist.

Sym head: Kopf der Liste, null falls Liste leer

Sym root: Wurzel der Liste, null falls Liste leer

Sym io: Lesezeiger der Liste, null falls Liste leer

int gesuchtesSymbol: die Nummer des Bezeichners, der gesucht wird

int neuesSymbol: die Nummer des Bezeichners, der neu in die Tabelle eingefügt wird

Da es sich um eine Erweiterung der Klasse RandomAccessFile handelt, sind hier auch alle Typen und Variablen der Super-Klasse verwendbar. Siehe dazu ¹.

char last: das zuletzt aus der Datei gelesene Zeichen
char l: Zwischenspeicher für das zuletzt gelesene Zeichen

Da es nicht mit vertretbarem Aufwand möglich ist, sämtliche Funktionen des Programms zu beweisen, beschränke ich mich auf Tests. Diese Tests sind so angelegt, daß sämtliche SM-Befehle vorkommen, aber auch nicht erlaubte Bezeichner und andere „Fehler“, um die Fehlerbehandlung zu überprüfen. Dabei habe ich versucht, möglichst jede Besonderheit mit einzubringen.
 
 

test1.sm ist ein tatsächlich funktionierendes SM-Programm: (Siehe Vorlesung)
 
 
 

Programm call 0,anf,1 var x,1 label anf read store 0,x const 2 load 0,x mul const 3 add write jmp 0	„von Hand“ überstezt 16.21.0.22.1.21.1. 20.22.21.1 19.22.1 17 15.21.0.22.2 13.21.2 14.21.0.22.2 3 13.21.3 1 18 6.21.0

Das ausgegebene Programm entspricht vollends den Erwartungen:

16.21.0.22.1.21.1.20.22.2.21.1.19.22.1.17.15.21.0.22.2.13.21.2.14.21.0.22.2.3.13.21.3.1.18.6.21.0
 
 
 
 

test2.sm testet alle SM-Befehle in verschiedener Schreibweise und an verscheidenen Positionen. Es werden ebenfalls alle Begrenzer getestet, sowie Kommentare, die selber Klammern und Sterne beinhalten. Zuletzt enhält es noch einen Bezeichner, der mit einem Bezeichner für einen SM-Befehl beginnt, sowie die Zahlen von 0-20. Das Programm beinhaltet ebenfalls Bezeichner, die sich nur in Groß-/Kleinschreibung unterscheiden:
 
 
 

Programm (* Alles durchtesten! Dies ist kein Programm! *) bezeichner Maeh maeh     bezeichner call CALL CaLl jmp     add,sub mul (* ()**)div ret,jmp je jne JL,JLE jg jge const load store call write,read maeh Maeh     callisteinbezeichner     0,1 2,3 4,5 6,7 8,9 10,11 12,13 14,15 16,17 18,19 20     (* Ende des Tests *)	„von Hand“ überstezt 22.1 22.2 22.3     22.1 16 16 16 6     1.2.3.4.5.6 7 8 9.10.11 12 13 14.15.16 18.17 22.3 22.2     22.4     21.0.21.1.21.2.21.3.21.4.21.5.21.6.21.7.21.8.21.9.21.10.21.11.21.12.21. 13.21.14.21.15.21.16.21.17.21.18.21.19.21.20

Auch hier entspricht die Ausgabe den Erwartungen:

22.1.22.2.22.3.22.1.16.16.16.6.1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.18.17.22.3.22.2.22.4.21.0.21.1.21.2.21.3.21.4.21.5.21.6.21.7.21.8.21.9.21.10.21.11.21.12.21.13.21.14.21.15.21.16.21.17.21.18.21.19.21.20
 
 
 
 
 
 
 
 

test3.sm testet auf ungültige Bezeichner:
 
 

gueltigerBezeichner

ungültigerBezeichner
 
 

Tatsächlich wird eine Kompilierung verweigert.
 
 

test4.sm ist eine leere Datei. Wie geplant wird eine Fehlermeldung ausgegeben, daß die Datei unlesbar sei.