© APSIS GmbH

9.2.8. Endliche Automaten

Als Beispiel für die für die Verwendung mehrdimensionaler Reihungen lernen wir die endlichen Automaten kennen. Sie sind z.B. geeignet, um die Syntax einer Sprache in einer Matrix zu kodieren. Mit ihrer Hilfe kann ein Compiler sehr schnell prüfen, ob eine gegebene Zeichenfolge z.B. einen gültigen Ada-Bezeichner bildet oder nicht. Ähnlich kann er entscheiden, ob sie aus einem anderen syntaktischen Begriff abgeleitet werden kann oder fehlerhaft ist. Die im Kapitel 1.5.3. auf der Seite 15 beschriebene Syntax der Bezeichner kann z.B. mit Hilfe der folgenden Tabelle überprüft werden:

Abb.: Automatentabelle für Bezeichner

Der endliche Automat fängt seine Arbeit im Zustand Anfang an. Er liest die zu analysierende Folge Zeichen für Zeichen ein. In jedem Schritt geht er in einen anderen Zustand über. In welchen, hängt von seinem vorherigen Zustand und vom eingelesenen Zeichen ab. Soll er z.B. die Zeichenfolge Obj_1 prüfen, läuft er folgende Zustände durch:

Anfang ª Buchstabe O à Gueltig ª Buchstabe b à Gueltig ª Buchstabe j à Gueltig ª Unterstrich à Unterstr ª Ziffer 1 à Gueltig

Zum Schluß befindet er sich im Zustand Gueltig. Dieser ist in der Tabelle mit einem E als Endzustand gekennzeichnet, also ist Obj_1 ein gültiger Bezeichner. Demgegenüber würde die ähnlich verlaufende Analyse der Zeichenfolge Obj_ in den Zustand Unterstr führen, der kein Endzustand ist: In der Tat darf ein Ada-Bezeichner nicht mit einem Unterstrich abgeschlossen werden. Eine Zeichenfolge, die mit einer Ziffer, mit einem Unterstrich oder mit einem anderen Zeichen beginnt, führt in den Zustand Ungueltig, aus dem es kein Entkommen ist. Dieser ist kein Endzustand, also bildet jede solche Zeichenfolge keinen gültigen Bezeichner.

Ähnlich ist Obj__1 kein Ada-Bezeichner, da der zweite Unterstrich in den Zustand Ungueltig führt: In einem Bezeichner dürfen nach der Syntax keine zwei Unterstriche nebeneinander stehen. Jede Zeichenfolge, das ein anderes Zeichen (z.B. + oder ß) enthält, endet ebenfalls im Zustand Ungueltig.

Der obige endliche Automat kann in einer zweidimensionalen konstanten Reihung kodiert werden. Hierfür definieren wir zwei Aufzählungsklassen, die den Spalten- und Zeilenbeschriftungen der Tabelle entsprechen:

class Zeichen extends lehrbuch.Aufz { ...
	// Aufzählungsklasse mit Werten BUCHSTABE, ZIFFER, UNTERSTRICH und ANDERES
}
class Z extends lehrbuch.Aufz { ... // Zustand 
	// Aufzählungsklasse mit Werten ANFANG, GUELTIG, UNTERSTR und UNGUELTIG
}

Ein menügesteuertes Analyseprogramm läßt nun den Anwender jeweils das nächste Zeichen auswählen und benutzt die obigen Reihungen, um die so eingegebene Zeichenfolge zu prüfen:

public class BezeichnerAnalyse extends MenueBez { // BezeichnerAnalyse.java
	// generiert mit einem Menüpunkt für zeichenEingeben
	private final Z[][] automat = { // nach der obigen Tabelle
		{ Z.GUELTIG, Z.UNGUELTIG, Z.UNGUELTIG, Z.UNGUELTIG }, // ANFANG
		{ Z.GUELTIG, Z.GUELTIG, Z.UNTERSTR, Z.UNGUELTIG }, // GUELTIG
		{ Z.GUELTIG, Z.GUELTIG, Z.UNGUELTIG, Z.UNGUELTIG }, // UNTERSTR
		{ Z.UNGUELTIG, Z.UNGUELTIG, Z.UNGUELTIG, Z.UNGUELTIG } // UNGUELTIG
	};
	private final boolean[] endzustand = { false, true, false, false }; // nach der obigen Tabelle
	// nur Zustand Z.GUELTIG ist Endzustand
	private Z zustand = Z.ANFANG;
	protected void zeichenEingeben() { // Rückrufprozedur
		Zeichen eingabeZeichen = Zeichen.BUCHSTABE;
		eingabeZeichen = (Zeichen)eingabeZeichen.auswahl(); // nächstes Zeichen wird ausgewählt
		zustand = automat[zustand.pos()][eingabeZeichen.pos()]; // Zustandsübergang
	}
	public void start() {
	menue(); // Zeichenfolge wird eingegeben und analysiert
	lehrbuch.Bool ergebnis = new lehrbuch.Bool(endzustand[zustand.pos()]);
	ergebnis.ausgeben("Gültiger Bezeichner");
	}
}

Hier wird also in der Menü-Rückrufprozedur die zu analysierende Zeichenfolge mit Hilfe einer Auswahlliste aus den in Frage kommenden Zeichen eingelesen. Nach der Wahl des Menüpunkts "Ende" wird das Ergebnis ausgegeben: Wenn der erreichte Zustand ein Endzustand ist, dann true, ansonsten false.

In diesem Beispiel haben wir die Automatentabelle direkt in Aufzählungsklassen übersetzt, weil sie ihrer Natur genau entsprechen. Weil Java – im Gegensatz zu anderen Sprachen – keine Aufzählungstypen anbietet und die Reihungen mit Ganzzahlen indiziert werden müssen, ist das Programm etwas schwer lesbar. Eine Kodierung der Automatentabelle mit Ganzzahlen schafft Abhilfe. Hierbei kodieren wir – wie üblich – den Zustand Ungueltig mit 0 und Anfang mit 1:

Abb. Kodierte Automatentabelle für Bezeichner

Mit dieser Tabelle braucht das Programm keine Aufzählungsklassen, wir kodieren alles mit int:

public class KodierteAnalyse extends MenueBez { // KodierteAnalyse.java
	// generiert mit einem Menüpunkt für zeichenEingeben
	private final int[][] automat = { // nach der obigen Tabelle
		{ 0, 0, 0, 0 }, // UNGUELTIG = 0
		{ 2, 0, 0, 0 }, // ANFANG = 1
		{ 2, 2, 3, 0 }, // GUELTIG = 2
		{ 2, 2, 0, 0 }, // UNTERSTR = 3
	};
	private final boolean[] endzustand = { false, false, true, false }; // nach der obigen Tabelle
	// nur Zustand 2 ist Endzustand
	private int zustand = 1; // Anfangszustand
	protected void zeichenEingeben() { // Rückrufprozedur
		lehrbuch.Int eingabeZeichen = new lehrbuch.Int();
		try {
			eingabeZeichen = eingabeZeichen.eingeben(); // nächstes Zeichen wird eingegeben
		} catch (lehrbuch.BereichAusn ausnahme) {
		lehrbuch.Komm.meldung("Fehler");
		}
		zustand = automat[zustand][eingabeZeichen.wert()]; // Zustandsübergang
	}
	public void start() {
		menue(); // Zeichenfolge wird eingegeben und analysiert
		lehrbuch.Bool ergebnis = new lehrbuch.Bool(endzustand[zustand]);
		ergebnis.ausgeben("Gültiger Bezeichner");
	}
}

Diese Vorgehensweise, alle Daten mit int zu kodieren, ist zwar sehr verbreitet, die Autoren empfehlen sie trotzdem nicht. Der Compiler würde zum Beispiel die fehlerhafte Zuweisung

zustand = zeichen;

im int-kodierten Programm nicht ablehnen. Wenn unterschiedliche Begriffe der Anwendung (wie Zustände und Eingabezeichen) auf unterschiedliche Klassen abgebildet werden, wird die Typstärke von Java ausgenutzt und die Vermischung von unterschiedlichen Typen frühzeitig (d.h. schon während der Übersetzung) entdeckt. Dies mindert die Kosten und erhöht die Sicherheit der entwickelten Programme.

Übung: Stellen Sie eine ähnliche Tabelle für die vereinfachte Syntax von logischen Ausdrücken zusammen:

Ausdruck := Relation { logischer_Operator Relation }
Relation := Einfacher_Ausdruck [ Relationaler_Operator Einfacher_Ausdruck ]
Einfacher_Ausdruck := [ ! ] Primärausdruck

Die Eingabezeichen für diese Syntax sind !, Primärausdruck, relationaler_Operator und logischer_Operator. Hier können wir – im Gegensatz zur Syntax im Kapitel 7.6.3. – Ausdrücke nicht klammern: Die Rekursion kann nicht von endlichen Automaten bewältigt werden, hierzu wären Kellerautomaten nötig.

Implementieren Sie das Analyseprogramm mit Hilfe der Tabelle. Testen Sie sie mit einem menügesteuerten Programm.

9.2.9. Rekursive Abarbeitung

Anstelle des obigen Dialogprogramms kann ein Stapelprogramm angefertigt werden, das nicht vom Anwender gesteuert wird, sondern die zu analysierende Zeichenfolge fest kodiert enthält oder aus einer Datei einliest. Hierzu verwenden wir jetzt die Technik der rekursiven Abarbeitung:

public class RekursiveAnalyse { // RekursiveAnalyse.java
	// fest kodiert für die Zeichenfolge Obj_1
	... // die Vereinbarungen aus dem Programm (9.9)
	static Zeichen[] zeichenfolge = { Zeichen.BUCHSTABE, Zeichen.BUCHSTABE, Zeichen.BUCHSTABE,
		Zeichen.UNTERSTRICH, Zeichen.ZIFFER }; // Obj_1 fest kodiert
	static int index = 0;
	private static void zeichenfolgeAnalysieren() { // rekursive Prozedur
		try {
			final Zeichen eingabeZeichen = zeichenfolge[index]; // throws IndexOutOfBoundsException
			zustand = automat[zustand.pos()][eingabeZeichen.pos()]; // Zustandsübergang
			index++;
			zeichenfolgeAnalysieren(); // rekursiver Aufruf
		}
		catch(IndexOutOfBoundsException ausnahme) {}// Zeichenfolge ist zu Ende
	}
	public static void main(String[] args) {
		zeichenfolgeAnalysieren();
		lehrbuch.Bool ergebnis = new lehrbuch.Bool(endzustand[zustand.pos()]);
		ergebnis.ausgeben("Gültiger Bezeichner");
	}
}

Hier ruft die Prozedur zeichenfolgeAnalysieren sich selbst auf. Dies ist ein rekursiver Aufruf. Damit die Aufrufe nicht unendlich lang einander folgen (damit keine endlose Rekursion auftritt), muß für eine Unterbrechung gesorgt werden. Dies geschieht durch die Positionierung von index auf das nächste Eingabezeichen: Wenn die Zeichenfolge zu Ende ist, löst der Zugriff auf die Reihung die (ungeprüfte) Ausnahme IndexOutOfBoundsException aus. Hiernach folgen keine rekursiven Aufrufe mehr, die Prozedur zeichenfolgeAnalysieren wird unterbrochen.

Im Kapitel 10.2. auf Seite 222 werden wir als Alternative zu dieser Technik die Wiederholungen kennenlernen.

Übung: Entwickeln Sie ähnliches rekursives Analyseprogramm für Bezeichner, das die zu analysierende Zeichenfolge aus einer Datei (über ein Objekt der Klasse kapitel8.SeqDateiImpl) einliest. Die Rekursion sollen Sie hier mit der Ausnahme SeqDateiImpl.DateiendeAusn abbrechen. Sie brauchen hierzu auch ein Zusatzprogramm (entweder als Dialog- oder als Stapelprogramm), mit dem Sie die Datei beschreiben. Testen Sie Ihr Programm mit zehn unterschiedlichen Zeichenfolgen.

Übung: Es ist natürlich mühsam, zeichenfolge aus den vier Aufzählungswerten BUCHSTABE, UNTERSTRICH, ZIFFER und ANDERES (oder aus Ganzzahlen 0, 1, 2 und 3) zusammenzustellen. Es wäre viel natürlicher, sie als Zeichenkette "Obj_1" angeben zu können. Hierzu kann eine Übersetzungstabelle wie im Kapitel 9.2.5. auf Seite 200 verwendet werden: Zu allen 128 Werten wird in der Klasse kapitel8.Ascii einer der vier Aufzählungswerten zugeordnet.

Einwickeln Sie ein ähnliches Programm wie in der vorigen Übung mit einer Übersetzungstabelle. Lesen Sie die zu analysierende Zeichenfolge mit Hilfe von System.in.read ein und holen Sie die einzelnen Zeichen aus dem erhaltenen String-Objekt mit charAt. Am Ende erhalten Sie die Ausnahme IndexOutOfBoundsException.

10.2.1. Festschleifen

Im Kapitel 9.2.8.  haben wir den endlichen Automaten über ein Wort mit Hilfe der rekursiven Abarbeitung durchlaufen lassen. Es ist natürlicher (und auch lesbarer), den Algorithmus (9.11) als Festschleife zu programmieren:

int zustand = anfangszustand; // der aktuelle Zustand des Automaten
for (int index = 0; index < zeichenfolge.length; index++)
	zustand = automat[zustand][zeichenfolge[index]]; // Zustandsübergang

Die Anzahl der Wiederholungen in der Festschleife ist hier fünf, die Länge des zu analysierenden Bezeichners Obj_1.

Das Gemeinsame in den obigen Beispielen ist, daß die Anzahl der Wiederholungen (drei, 26 oder fünf) schon zur Übersetzungszeit feststeht. Deswegen heißen sie Festschleifen. Sie bilden einen Sonderfall der Zählschleifen.

Wenn in einer Zählschleife ein leerer Bereich angegeben wurde, wird der Rumpf 0-mal ausgeführt:

int anzahl = System.in.read();
for (int i = 1; i <= anzahl; i++)
	System.out.println("Hallo"); // die Anweisung wird nie ausgeführt, wenn 0 eingegeben wurde

Auch in Zählschleifen kann das Schleifenobjekt rückwärts (vom oberen zum unteren Wert) durchlaufen:

for (int i = anzahl; i >= 1; i--) ...

Bemerkung: Java erlaubt in den drei Klauseln beliebige Anweisungen, sogar durch Kommata getrennte Anweisungslisten

for (int i = 0, j = reihung.length; j >= 0; i++, j--) ... // zwei Indizes laufen entgegengesetzt durch

Die erste wird einmal vor dem ersten Schleifenschritt, die beiden anderen werden in jedem Schleifenschritt ausgeführt. Hierdurch kann der Schleifenablauf manipuliert und dadurch das Programm unleserlich gemacht werden. Die Autoren empfehlen die ausschließliche Verwendung der dargestellten Form der Zählschleife.

Übung: Implementieren Sie die Klasse im Programm BezeichnerAnalyse, die einen endlichen Automaten modelliert, mit Hilfe einer Festschleife. Der Automat soll dezimale Ganzzahlliterale analysieren. Rufen Sie sie für fünf verschiedene (drei richtige und zwei falsche) Literale auf.

Der Syntax der dezimalen Ganzzahlliterale kann folgendermaßen formuliert werden:

Dezimales_Ganzzahlliteral := [ Vorzeichen ] Ganzzahl [ Exponent ]
Vorzeichen := + | -
Ganzzahl := Ziffer { [ Unterstrich ] Ziffer }
Exponent := E [ Vorzeichen ] Ziffer [ Ziffer ]

Ein Automat, der ein dezimales Ganzzahlliteral analysiert, kann folgende Tabelle haben:

Andere Zeichen führen in den Zustand Ungueltig, aus dem es kein Entrinnen gibt (d.h. in dem alle Zeichen in den Zustand Ungueltig führen).

© APSIS GmbH