Lernpfad Know-How-Computer/KHA-Parser als Endlicher Automat
Im Kapitel Know-How-Assembler - Grammatik einer formalen Sprache wurde darauf hingewiesen, dass die Überprüfung eines Assemblercodes auf seine formale Korrektheit auch von einem Computerprogramm übernommen werden kann. Bei höheren Programmiersprachen wie z.B. C++, Delphi, Java oder Python heißen solche Übersetzungsprogramme Compiler. Von ihrem Grundaufbau her sind Assembler und Compiler vergleichbar. Im Compilerbau teilt man den Übersetzungsprozess üblicherweise in drei Phasen ein:
- Lexikalische Analyse (Lexer oder auch Scanner)
- Syntaktische Analyse (Parser)
- Zielcode-Generierung (Codegenerator)
Die einzelnen Phasen sind allerdings bei einem Compiler deutlich komplexer und ihre Implementierung ist erheblich aufwändiger als bei einem Assembler.
In diesem Kapitel geht es darum, wie man den Parser eines Know-How-Assemblers in einer Programmiersprache wie z.B. Java implementieren kann. Dabei wird zugleich auch das Konzept eines "Endlichen Automaten" vorgestellt, das in der theoretischen Informatik eine wichtige Rolle spielt.Lexikalische Analyse
Die Aufgabe eines Lexers wird am Beispiel des KHA-Programms "Von x auf 0" aus dem Kapitel Programmieren in der KHC-Maschinensprache - erste Schritte Teil 2 verdeutlicht. Hier zunächst noch einmal der Programmcode in Assemblersprache, wobei die Anweisungen jetzt nicht mehr durch Zeilenumbrüche, sondern durch Semikolons voneinander getrennt werden:
start: isz x; jmp xminus1; stp; xminus1: dec x; jmp start; x: 3;
Der KHA-Lexer durchläuft nun den Programmtext Zeichen für Zeichen und versucht, daraus eine so genannte Token-Kette zu erstellen. Dabei fasst er zusammengehörende Zeichen zu lexikalischen Einheiten zusammen - z.B. eine Buchstabenfolge zu einem Bezeichner oder eine Ziffernfolge zu einer Zahl - und bildet daraus die so genannten Tokens.
Auch Befehlsworte wie inc, dec oder stp werden als "reservierte Bezeichner" zu eigenen lexikalischen Einheiten zusammengefasst, wobei der KHA-Lexer hier noch einmal unterscheidet zwischen den vier Adressbefehlen inc, dec, jmp und isz, die erst durch einen nachfolgenden Bezeichner als Befehl komplett werden, und dem Stoppbefehl stp, bei dem dies nicht so ist.
Auch die Symbole : und ; bilden jeweils eigene lexikalische Einheiten.
Ein Token ist ein Elementepaar, das aus einem Tokenwert und seinem Tokentyp besteht, Schreibweise: (Tokentyp | Tokenwert). Die Tokenwerte sind die als lexikalische Einheiten identifzierten Teilstücke des Quellcodes. Die Tokentypen des KHA-Lexers sind in der folgenden Tabelle aufgeführt:
| Tokentyp | Abk. | Beispiele für Tokenwerte |
|---|---|---|
| Bezeichner | B | start , x , xminus1 |
| Adressbefehl | A | inc , dec , jmp, isz |
| Stoppbefehl | S | stp |
| Zahl | Z | 0 , 5 , 27 |
| Doppelpunkt | : | : |
| Semikolon | ; | ; |
Das KHA-Programm "Von x auf 0"
start : isz x ; jmp xminus1 ; stp ; xminus1 : dec x ; jmp start ; x : 3 ;
wird vom Lexer in die folgende Tokenkette zerlegt, wobei für die Tokentypen die Abkürzungen aus obiger Tabelle verwendet werden:
(B|start) (:|:) (A|isz) (B|x) (;|;) (A|jmp) (B|xminus1) (;|;) (S|stp) (;|;) (B|xminus1) (:|:) (A|dec) (B|x) (;|;) (A|jmp) (B|start) (;|;) (B|x) (:|:) (Z|3) (;|;)
Wenn die lexikalische Analyse des Lexers nicht erfolgreich ist, weil er im Quellcode z.B. auf ein unerlaubtes Zeichen wie '+' oder '#' stößt, dann liefert er eine Fehlermeldung. Andernfalls übergibt er die gewonnene Token-Kette zur weiteren Verarbeitung (syntaktische Analyse) an den Parser.
Der Lexer kann zwar unerlaubte Zeichen erkennen, überflüssige Leerzeichen, Zeilenumbrüche und Kommentare entfernen und lexikalische Einheiten identifizieren, um daraus eine Token-Kette zu bilden, er überprüft jedoch im Gegensatz zum Parser noch nicht, ob die Tokens innerhalb dieser Kette in einer syntaktisch korrekten Abfolge im Sinne der KHA-Grammatik stehen. Der Lexer würde also z.B. auch die (syntaktisch falsche) Befehlsfolge
: anfang inc dec ; stp 4
akzeptieren und in folgende Token-Kette überführen:
(:|:) (B|anfang) (A|inc) (A|dec) (;|;) (S|stp) (Z|4)
Syntaktische Analyse (Parser)
Der Parser überprüft die vom Lexer erstellte Token-Kette auf syntaktische Korrektheit. Bei höheren Programmiersprachen, die auch verschachtelte Strukturen (z.B. for-Schleife in while-Schleife) und Klammerausdrücke erlauben, ist dies deutlich aufwändiger als bei einer Assemblersprache, in der es solche Strukturen nicht gibt. Im Folgenden wird gezeigt, wie ein Parser für den Know-How-Assembler mit Hilfe des relativ einfachen Konzepts eines "Endlichen Automaten" realisiert werden kann.
Ausgangspunkt für die Arbeit dieses Endlichen Automaten ist die Token-Kette, die der Lexer zuvor erzeugt hat. Da der Parser lediglich die korrekte Reihenfolge der Token prüft, benötigt er dafür auch nur die Tokentypen aus der Kette. Die Tokenwerte werden erst später in der dritten Phase bei der Code-Generierung wieder benötigt.
Wenn man aus der Token-Kette zum KHA-Programm "Von x auf 0” nur die (abgekürzten) Tokentypen zu einer Zeichenkette zusammenfasst, dann erhält man folgende Tokentyp-Kette:
B : A B ; A B ; S ; B : A B ; A B ; B : Z ;
Endlicher Automat
Wie kann nun die Prüfung auf korrekte Abfolge der Tokentyp-Symbole mit Hilfe eines Endlichen Automaten (EA) in einem Computerprogramm (z.B. in Java) implementiert werden? Das soll im Folgenden Schritt für Schritt erläutert werden.
Einen Endlichen Automaten können wir uns als eine Maschine vorstellen, die eine Zeichenkette - in unserem Fall die Tokentyp-Kette - schrittweise Symbol für Symbol verarbeitet. Der Automat befindet sich dabei jederzeit in genau einem von mehreren fest definierten Zuständen. Am Anfang, noch bevor ein Symbol verarbeitet wurde, befindet er sich im so genannten Startzustand, den wir hier einmal "neutral" bzw. abgekürzt n nennen.
Welche Symbole sind in diesem Startzustand syntaktisch zulässig - oder mit anderen Worten: Mit welchen Symbolen kann ein KHA-Programm beginnen - und mit welchen nicht? Nach den Syntax-Regeln aus dem Kapitel Know-How-Assembler - Grammatik einer formalen Sprache geht hervor, dass ein KHA-Programm entweder mit einem Adressbefehl (Tokentyp 'A'), einem Bezeichner für ein Label (Tokentyp 'B') oder mit einem Stoppbefehl (Tokentyp 'S') beginnen kann. Jedes dieser Symbole überführt den EA vom Zustand n in einen neuen Folgezustand - nennen wir diese einmal a, b und s. Alle anderen Symbole wie Doppelpunkt, Semikolon oder Zahl sind am Anfang nicht erlaubt. Falls sie trotzdem gleich zu Beginn als erstes Symbol auftauchen, wird dadurch den EA in den Fehler-Zustand f überführt, aus dem er auch im Folgenden nicht mehr herauskommt - egal welche Eingabe-Symbole noch folgen. Denn wenn erst einmal ein Fehler in der Symbolabfolge aufgetreten ist, kann dieser nicht durch weitere korrekte Abfolgen "ungeschehen" gemacht werden.
Übergangsregeln in Form von Wenn-dann-sonst-Aussagen
Die so genannten Übergangsregeln, die für einen Zustand festlegen, welchen Folgezustand der EA einnimmt - je nachdem, welches Eingabe-Symbol als nächstes folgt - können kurz in Form von Wenn-Dann-Sonst-Aussagen ausgedrückt werden:
Übergangsregel für den Zustand n
wenn zustand ist n
dann wenn Symbol ist 'A'
dann setze zustand = a
sonst wenn Symbol ist 'B'
dann setze zustand = b
sonst wenn Symbol ist 'S'
dann setze zustand = s
sonst setze zustand = f
wenn_ende
Übergangsregel für den Zustand f
wenn zustand ist f
dann wenn Symbol ist beliebig
dann setze zustand = f
wenn_ende
Übergangstabelle
Eine kompakte und übersichtliche Art, die Übergangsregeln darzustellen, ist die so genannte Übergangstabelle. Im folgenden Beispiel werden die ersten beiden Regeln für die Zustände n und f so dargestellt:
| Symbol Zustand |
A | B | S | Z | : | ; |
|---|---|---|---|---|---|---|
| n | a | b | s | f | f | f |
| f | f | f | f | f | f | f |
Für jede Kombination aus einem Zustand in der ersten Spalte und einem Eingabe-Symbol in der obersten Zeile steht der jeweilige Folgezustand in derjenigen Tabellenzelle, in der sich die entsprechende Zustandszeile und die Symbolspalte kreuzen.
Natürlich muss es jetzt auch für die neuen Zustände a, b und s entsprechende Übergangsregeln bzw. Zeilen in der Übergangstabelle geben, durch die für jedes Eingabe-Symbol ein Folgezustand festgelegt wird. Wie sehen diese Regeln aus?
Besonders einfach ist das für den Zustand s zu beantworten. Nach einem Stopp-Befehl muss zwingend ein Semikolon folgen. Alle anderen Symbole führen zum Fehlerzustand f. In welchen Folgezustand gelangt der EA aber von s aus, wenn ein Semikolon folgt? Offenbar ist dann ja eine KHA-Anweisung als vollständig und abgeschlossen erkannt worden und der Überprüfungsprozess befindet sich daher wieder in seiner ursprünglichen Ausgangssituation. Mit anderen Worten: Der EA gelangt also wieder zurück in den Startzustand n.
Übergangsregel für den Zustand s
wenn zustand ist s
dann wenn Symbol ist ';'
dann setze zustand = n
sonst setze zustand = f
wenn_ende
Wir können damit die obige Übergangstabelle folgendermaßen um eine s-Zeile ergänzen:
| Symbol Zustand |
A | B | S | Z | : | ; |
|---|---|---|---|---|---|---|
| n | a | b | s | f | f | f |
| f | f | f | f | f | f | f |
| s | f | f | f | f | f | n |
Selbst, wenn ein Programm lediglich aus der einzigen Anweisung stp ; besteht (was inhaltlich zwar ziemlich sinnfrei, syntaktisch aber nicht unzulässig ist), dann wäre die Rückkehr in den Zustand n ein Beleg dafür, dass dieses Programm zumindest syntaktisch korrekt ist. Der Zustand n ist daher bei unserem EA nicht nur der Start- sondern zugleich auch der so genannte Zielzustand.
Wenn auf einen Adressbefehl ein Bezeichner folgt, dann muss auf diesen nur noch ein abschließendes Semikolon folgen, damit eine vollständige KHA-Anweisung entsteht. Alle anderen Eingabe-Symbole führen zu einem Fehler. Das ist dann aber genau die gleiche Situation, wie wir sie bereits vom s-Zustand kennen. Wir müssen in diesem Fall also gar keinen neuen Zustand einführen, sondern können auch hier s als Folgezustand verwenden:
Übergangsregel für den Zustand a
wenn zustand ist a
dann wenn Symbol ist 'B'
dann setze zustand = s
sonst setze zustand = f
wenn_ende
| Symbol Zustand |
A | B | S | Z | : | ; |
|---|---|---|---|---|---|---|
| a | f | s | f | f | f | f |
Bleibt noch zu klären, was passiert, wenn wir im zustand b gelandet sind. In diesem Fall muss als nächstes Symbol zwingend ein Doppelpunkt folgen. Hierfür führen wir den weiteren Zustand d (Doppelpunkt) ein und legen fest:
Übergangsregel für den Zustand b
wenn zustand ist b
dann wenn Symbol ist ':'
dann setze zustand = d
sonst setze zustand = f
wenn_ende
Welche Übergangsregeln müssen für den Zustand d gelten? Nach einem Doppelpunkt darf laut Syntaxregeln entweder das Symbol 'A' für einen Adressbefehl oder 'Z' für eine Zahl oder 'S' für einen Stopp-Befehl folgen. Im letzten Fall 'S' kann wieder der Zustand s als Folgezustand verwendet werden, denn daran anschließend wird nur noch ein abschließendes Semikolon akzeptiert. Das Gleiche gilt für das Symbol 'Z'. Bleibt schließlich noch der Fall, dass auf den Doppelpunkt ein Adressbefehl 'A' folgt. Für diesen Fall kann der schon vorhandene Zustand a als Folgezustand festgelegt werden. Insgesamt erhält man folgende
Übergangsregel für den Zustand d
wenn zustand ist d
dann wenn Symbol ist 'A'
dann setze Zustand = a
sonst wenn Symbol ist 'S'
dann setze Zustand = s
sonst wenn Symbol = 'Z'
dann setze Zustand = s
sonst setze zustand = f
wenn_ende
Die vollständige Übergangstabelle für unseren EA sieht demnach so aus:
| Symbol Zustand |
A | B | S | Z | : | ; |
|---|---|---|---|---|---|---|
| n | a | b | s | f | f | f |
| a | f | s | f | f | f | f |
| b | f | f | f | f | d | f |
| d | a | f | s | s | f | f |
| s | f | f | f | f | f | n |
| f | f | f | f | f | f | f |
Aus der Tabelle sieht man u.a., dass der EA auf unterschiedlichen Wegen in den Zustand s gelangen kann. Aber egal, auf welchem Weg er dorthin kommt: Sobald sich der EA im s-Zustand befindet, fehlt nur noch ein abschließendes Semikolon, damit eine vollständige KHA-Anweisung entsteht und der EA wieder in den Zustand n zurückkehrt. Dies sieht man auch recht gut an der folgenden Darstellung des EA als Übergangsgraph.
Übergangsgraph
- Zustände werden im Graphen durch Kreise dargestellt, die den jeweiligen Zustandsbezeichner umschließen.
- Der Doppelkreis (hier um Zustand n) zeigt an, dass es sich um einen Zielzustand handelt.
- Der von Außen kommende Pfeil (in diesem Fall ebenfalls zum Zustand n) kennzeichnet den Startzustand.
- Die Zustandsübergänge werden durch Pfeile dargestellt.
- Die Beschriftung eines Pfeils gibt an, welches Eingabesymbol den entsprechenden Übergang bewirkt.
In diesem Übergangsgraph für den KHA-Parser als EA wurde aus Gründen der Übersichtlichkeit der Fehler-Zustand f weggelassen.
Eine einfache Implementierung des KHA-Parsers in Java
Mithilfe der Übergangsregeln in Form von Wenn-dann-sonst-Aussagen kann der KHA-Parser recht einfach in einer höheren Programmiersprache mit geschachtelten if-else-Anweisungen implementiert werden. Hier z.B. ein bewusst einfach gehaltenes Konsolen-Programm in Java:
/** KHA_Parser als Endlicher Automat
* @author Ulrich Kalina
* @version 27.06.2025
* Beispiel KHA-Programm "Von x auf 0"
* start: isz x; jmp xminus1; stp; xminus1: dec x; jmp start; x :3;
* mit Tokentyp-Kette: B:AB; AB; S; B:AB; AB; B:Z;
*/
public class KHA_Parser {
public static void main(String[] args) {
String typkette ="B:AB;AB;S;B:AB;AB;B:Z;" ; // "Von x auf 0" wird akzeptiert
// String typkette ="B:AB;ABS;B:AB;AB;" ; // wird nicht akzeptiert
// String typkette ="S;S;" ; // wird akzeptiert
// String typkette ="SS;" ; // wird nicht akzeptiert
// String typkette ="A;" ; // wird nicht akzeptiert
// String typkette ="AB;" ; // wird akzeptiert
System.out.println("Tokentyp-Kette = " +typkette+ "\nStartzustand = n");
char zustand = 'n'; // Startzustand
for (int i=0; i<typkette.length(); i++) {
char eingabezeichen =typkette.charAt(i); // Zeichen an Position i
System.out.print("Kombination (" + zustand + "|" + eingabezeichen + ")");
if (zustand == 'n') {
if (eingabezeichen == 'A') zustand='a';
else if (eingabezeichen == 'B') zustand='b';
else if (eingabezeichen == 'S') zustand='s';
else zustand = 'f';
} // if (zustand == 'n')
else if (zustand == 'a') {
if (eingabezeichen == 'B') zustand='s';
else zustand = 'f';
} // if (zustand == 'a')
else if (zustand == 'b') {
if (eingabezeichen == ':') zustand='d';
else zustand = 'f';
} // if (zustand == 'b')
else if (zustand == 's') {
if (eingabezeichen == ';') zustand='n';
else zustand = 'f';
} // if (zustand == 's')
else if (zustand == 'd') {
if (eingabezeichen == 'A') zustand='a';
else if (eingabezeichen == 'S') zustand='s';
else if (eingabezeichen == 'Z') zustand='s';
else zustand = 'f';
} // if (zustand == 'd')
System.out.println(" ergibt neuen zustand "+ zustand);
} // for
if(zustand=='n') System.out.println("akzeptiert!"); // Zielzustand
else System.out.println("nicht akzeptiert!");
} // main()
} // class KHA_Parser
Zwei Anmerkungen zum Schluss
- Der in diesem Kapitel vorgestellte Endliche Automat stimmt in einem Punkt nicht ganz mit der KHA-Syntax überein: Er akzeptiert nämlich auch eine leere Symbolkette als gültiges KHA-Programm. Das liegt daran, dass sein Startzustand n zugleich auch sein Zielzustand ist. Die KHA-Syntaxregeln schreiben aber vor, dass ein KHA-Programm mindestens eine (nicht leere) Anweisung enthalten muss. Dieser "Schönheitsfehler" lässt sich beheben, indem man getrennt vom Zustand n noch einen zusätzlichen Zielzustand z einführt. Darauf wurde an dieser Stelle zugunsten der Übersichtlichkeit bewusst verzichtet, zumal man den Ausnahmefall "leere Eingabe-Kette" programmtechnisch sehr einfach auch anders abfangen kann.
- Auch die Compiler höhere Programmiersprachen verwenden für die syntaktische Analyse einen Parser. Dieser lässt sich aber im Gegensatz zum Know-How-Assembler nicht mehr durch das Konzept eines Endlichen Automaten realisieren. Das liegt daran, dass ein Endlicher Automat immer nur den gerade aktuellen Zustand "kennt" und speichert. Bei Programmiersprachen, die verschachtelte Strukturen erlauben, muss sich der Parser aber zusätzlich die Schachtelungstiefe merken, auf der sich ein Ausdruck befindet: Zu jeder Klammer, die geöffnet wird, muss irgendwann auch wieder eine schließende Klammer folgen. Um einen Parser zu implementieren, der dies überwachen kann, benötigt man leistungsfähigere Konzepte wie z.B. einen Stack als höhere Datenstruktur.
