Endlicher Automat

• als generische Funktion

• ohne Ganzzahlen und Schleifen

Endliche Automaten sind geeignet, um die Syntax einer Sprache in einer Matrix zu kodieren. Mit ihrer Hilfe kann z.B. ein Compiler sehr schnell prüfen, ob eine gegebene Zeichenfolge z.B. einen gültigen Bezeichner bildet oder nicht. Ähnlich kann er entscheiden, ob sie aus einem anderer syntaktischer Begriff abgeleitet werden kann oder fehlerhaft ist. Die Syntax der Bezeichner

Bezeichner ::= Buchstabe { Buchstabe_oder_Ziffer }
Buchstabe_oder_Ziffer ::= Buchstabe | Ziffer
Buchstabe ::= Kleinbuchstabe | Großbuchstabe
Kleinbuchstabe ::= a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q |
    r | s | t | u | v | w | x | y | z
Großbuchstabe ::= A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q |
    R | S | T | U | V | W | X | Y | Z
Ziffer ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

kann z.B. mit Hilfe der folgenden Tabelle überprüft werden:

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 nun in der folgenden zweidimensionalen konstanten Reihung kodiert werden:

type TZeichen is (Buchstabe, Ziffer, Unterstrich, Anderes);
type TZustand is (Anfang, Gueltig, Unterstr, Ungueltig);
Anfangszustand: constant TZustand := Anfang;

Automat: constant array (TZustand, TZeichen) of TZustand := (
	Anfang => (Gueltig, Ungueltig, Ungueltig, Ungueltig),
	Gueltig => (Gueltig, Gueltig, Unterstr, Ungueltig),
	Unterstr => (Gueltig, Gueltig, Ungueltig, Ungueltig),
	Ungueltig => (Ungueltig, Ungueltig, Ungueltig, Ungueltig));

Endzustand: constant array (TZustand) of Boolean := (
	Anfang => False, 
	Gueltig => True, -- nur Zustand Gueltig ist Endzustand
	Unterstr => False,
	Ungueltig => False);

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

with GAufz_EA, GMenue; -- nur mit einem Menüpunkt
procedure Bezeichner_Analyse is
	... -- die obigen Vereinbarungen
	Zustand: TZustand := Anfangszustand; -- der aktuelle Zustand des Automaten
	package MZeichen_EA is new GAufz_EA (TZeichen);
	procedure Zeichen_eingeben is -- Rückrufprozedur
		Eingabe_Zeichen: TZeichen;
	begin
		MZeichen_EA.Auswahlliste (Eingabe_Zeichen); -- nächstes Zeichen wird ausgewählt
		Zustand := Automat (Zustand, Eingabe_Zeichen); -- Zustandsübergang
	end Zeichen_eingeben;
	procedure Menue is new GMenue (Zeichen_eingeben);

begin
	Menue; -- Zeichenfolge wird eingeben und analysiert
	Meldungsfenster (Meldung => Boolean'Image (Endzustand (Zustand)), 
			Titel => "Gueltiger Bezeichner");
end Bezeichner_Analyse;

Hier wird also in der 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.

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

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

Übung: Implementieren Sie das Analyseprogramm mit Hilfe der Tabelle aus der vorherigen Übung.

Rekursive Abarbeitung

Anstelle des obigen Dialogprogramms kann ein Stapelprogramm angefertigt werden, das nicht vom Bediener 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 :

with Meldungsfenster;
procedure Rekursive_Analyse is -- fest kodiert für die Zeichenfolge Obj_1
	... -- die obigen Vereinbarungen
	Zustand: TZustand := Anfangszustand; -- der aktuelle Zustand des Automaten
	type TIndex is (A, B, C, D, E); -- für die Indizierung der 5 Zeichen von Obj_1
	Zeichenfolge: constant array (TIndex) of TZeichen := 
		(Buchstabe, Buchstabe, Buchstabe, Unterstrich, Ziffer); -- Obj_1 fest kodiert
	Index: TIndex := Zeichenfolge'First;

	procedure Zeichenfolge_analysieren is -- rekursive Prozedur
		Eingabe_Zeichen: constant TZeichen := Zeichenfolge (Index);
	begin
		Zustand := Automat (Zustand, Eingabe_Zeichen); -- Zustandsübergang
		Index := TIndex'Succ (Index); -- raises Constraint_Error
		Zeichenfolge_analysieren; -- rekursiver Aufruf
	exception
		when Constraint_Error => null; -- Zeichenfolge ist zu Ende
	end Zeichenfolge_analysieren;

begin
	Zeichenfolge_analysieren;
	Meldungsfenster (Meldung => Boolean'Image (Endzustand (Zustand)), 
			Titel => "Gueltiger Bezeichner");
end Rekursive_Analyse;

Hier ruft die Prozedur Zeichenfolge_analysieren 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 Succ die Ausnahme Constraint_Error aus. Hiernach folgen keine rekursiven Aufrufe mehr, die Prozedur Zeichenfolge_analysieren wird abgeschlossen.

Eine Alternative zu dieser Technik sind die Wiederholungen.

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

Übung: Es ist natürlich mühsam, Zeichenfolge aus den 4 Aufzählungswerten Buchstabe, Unterstrich, Ziffer und Anderes zusammenzustellen. Es wäre viel natürlicher, sie als Zeichenkette "Obj_1" angeben zu können. Hierzu kann eine Übersetzungstabelle verwendet werden: Zu allen 128 Character-Werten aus dem Paket Standard.Ascii wird hier einer der 4 Aufzählungswerten zugeordnet.

Ergänzen Sie also Ihr Programm aus der vorigen Übung mit einer Übersetzungstabelle. So lesen Sie aus der Datei eine Zeichenfolge. Diese Datei können Sie mit einem Texteditor beschreiben.

Automat als Funktionsschablone

Für einen Compiler ist der Algorithmus in Form einer Funktionsschablone geeignet, die mit der Automatentabelle (und der dazugehörigen Datentypen) ausgeprägt werden kann und die zu analysierende Zeichenfolge als Parameter empfängt. Das Ergebnis ist vom Typ Boolean:

generic
	type TZeichen is (<>); -- ein beliebiger diskreter Typ, z.B. Character
	type TZustand is (<>); -- ein beliebiger diskreter Typ (Aufzählungstyp oder Ganzzahltyp)
	type TAutomat is array (TZustand, TZeichen) of TZustand;
	type TEndzustand is array (TZustand) of Boolean;
	type TIndex is (<>); -- ein beliebiger diskreter Typ, oft der Ganzzahltyp Natural
	type TZeichenfolge is array (TIndex) of TZeichen;
	Automat: TAutomat; -- Zustandsübergangstabelle
	Endzustand: TEndzustand; -- Endzustandtabelle
function Syntaxanalyse (Zeichenfolge: TZeichenfolge) return Boolean;
	-- generisches Unterprogramm muß immer zuerst vereinbart und erst dann definiert werden 

function Syntaxanalyse (Zeichenfolge: TZeichenfolge) return Boolean is
	Zustand: TZustand := TZustand'First; -- Anfangszustand
	Index: Zeichenfolge'Range := Zeichenfolge'First;
	procedure Zeichenfolge_analysieren is 
		... -- wie gehabt, oder aber mit Wiederholung
	end Zeichenfolge_analysieren;

begin
	Zeichenfolge_analysieren;
	return Endzustand (Zustand);
end Syntaxanalyse;

Diese Funktionsschablone kann mit der obigen Automatentabelle folgendermaßen ausgeprägt werden:

with Syntaxanalyse, Meldungsfenster;
procedure Analyse_mit_Schablone is -- fest kodiert für die Zeichenfolge Obj_1
	type TZeichen is (Buchstabe, Ziffer, Unterstrich, Anderes); -- Vereinbarungen wie oben
	type TZustand is (Anfang, Gueltig, Unterstr, Ungueltig);
	type TAutomat is array (TZustand, TZeichen) of TZustand;
	type TEndzustand is array (TZustand) of Boolean;
	Automat: TAutomat := ( ... -- wie oben
	Endzustand: constant TEndzustand := ( ... -- wie oben
	type TIndex is (A, B, C, D, E); -- für die Indizierung der 5 Zeichen von Obj_1
	type TZeichenfolge is array (TIndex) of TZeichen;
	Zeichenfolge: constant TZeichenfolge := 
		(Buchstabe, Buchstabe, Buchstabe, Unterstrich, Ziffer); -- Obj_1 fest kodiert

	function Bezeichner_Analyse is new Syntaxanalyse (TZeichen => TZeichen, TZustand => TZustand,
		TAutomat => TAutomat, TEndzustand => TEndzustand, TIndex => TIndex, 
		TZeichenfolge => TZeichenfolge, Automat => Automat, Endzustand => Endzustand); 

begin
		Meldungsfenster (Meldung => Boolean'Image (Bezeichner_Analyse (Zeichenfolge)), -- Aufruf
			Titel => "Gueltiger Bezeichner");
end;

Die Ausprägung wurde also hier auch für die im Programm fest kodierte Zeichenfolge Obj_1 aufgerufen.

Rückmeldungen bitte an den Autor solymosi@tfh-berlin.de

Leitseite des Autors