Lernpfad Know-How-Computer/KHA-Parser als Endlicher Automat - Versionsgeschichte

Ukalina am 14. April 2026 um 15:19 Uhr

2026-04-14T15:19:34Z

← Nächstältere Version		Version vom 14. April 2026, 15:19 Uhr
Zeile 341:		Zeile 341:
	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:		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:

			{{Lösung versteckt
			\|1 =
	<syntaxhighlight lang="java">		<syntaxhighlight lang="java">
	/** KHA_Parser als Endlicher Automat		/** KHA_Parser als Endlicher Automat
Zeile 404:		Zeile 406:
	} // class KHA_Parser		} // class KHA_Parser
	</syntaxhighlight>		</syntaxhighlight>
			\|2 = Java-Programm anzeigen
			\|3= Java-Progamm verbergen
			}}

	====Zwei Anmerkungen zum Schluss====		====Zwei Anmerkungen zum Schluss====

Ukalina am 14. April 2026 um 15:14 Uhr

2026-04-14T15:14:13Z

← Nächstältere Version		Version vom 14. April 2026, 15:14 Uhr
Zeile 15:		Zeile 15:
	# '''Zielcode-Generierung''' (Codegenerator)		# '''Zielcode-Generierung''' (Codegenerator)
	: Die einzelnen Phasen sind allerdings bei einem Compiler deutlich komplexer und ihre Implementierung ist erheblich aufwändiger als bei einem Assembler.		: 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~~.		* 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'''" und seine Darstellung als "'''Zustandsübergangsgraph'''" vorgestellt, die beide in der Theoretischen Informatik eine wichtige Rolle spielen.
	}} <!-- Box Lernpfad -->		}} <!-- Box Lernpfad -->

Ukalina am 14. April 2026 um 14:41 Uhr

2026-04-14T14:41:04Z

← Nächstältere Version		Version vom 14. April 2026, 14:41 Uhr
Zeile 1:		Zeile 1:
	__NOTOC__		__NOTOC__
	{{Fortsetzung\|		{{Fortsetzung
	vorher=zurück\|		\|vorher=zurück\|vorherlink=Lernpfad_Know-How-Computer/Know-How-Assembler_-_Grammatik_einer_formalen_Sprache
	vorherlink=Lernpfad_Know-How-Computer/Know-How-Assembler_-_Grammatik_einer_formalen_Sprache\|		\|weiter=weiter\|weiterlink=Lernpfad_Know-How-Computer/Anhang
	weiter=weiter\|		\|übersicht=Kapitelübersicht\|übersichtlink=Lernpfad_Know-How-Computer#Kapitelübersicht
	weiterlink=Lernpfad_Know-How-Computer/Anhang\|		}}
	übersicht=~~Startseite~~\|
	übersichtlink=Lernpfad_Know-How-Computer}}

	{{Box		{{Box
	\|1=Ein Parser als Endlicher Automat am Beispiel Know-How-Assembler		\|Titel = Ein Parser als Endlicher Automat am Beispiel Know-How-Assembler
	\|2=Im Kapitel [[Lernpfad_Know-How-Computer/Know-How-Assembler_-_Grammatik_einer_formalen_Sprache\|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:		\|Klasse = Lernpfad
	# Lexikalische Analyse (Lexer oder auch Scanner)		\|Inhalt =
	# Syntaktische Analyse (Parser)		* Im Kapitel [[Lernpfad_Know-How-Computer/Know-How-Assembler_-_Grammatik_einer_formalen_Sprache\|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:
	# Zielcode-Generierung (Codegenerator)		# '''Lexikalische Analyse''' (Lexer oder auch Scanner)
	Die einzelnen Phasen sind allerdings bei einem Compiler deutlich komplexer und ihre Implementierung ist erheblich aufwändiger als bei einem Assembler.		# '''Syntaktische Analyse''' (Parser)
			# '''Zielcode-Generierung''' (Codegenerator)
	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.		: Die einzelnen Phasen sind allerdings bei einem Compiler deutlich komplexer und ihre Implementierung ist erheblich aufwändiger als bei einem Assembler.
	~~\|3=Lernpfad~~}}		* 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.
			}} <!-- Box Lernpfad -->

	====Lexikalische Analyse====		====Lexikalische Analyse====
Zeile 411:		Zeile 410:


	{{Fortsetzung\|		{{Fortsetzung
	vorher=zurück\|		\|vorher=zurück\|vorherlink=Lernpfad_Know-How-Computer/Know-How-Assembler_-_Grammatik_einer_formalen_Sprache
	vorherlink=Lernpfad_Know-How-Computer/Know-How-Assembler_-_Grammatik_einer_formalen_Sprache\|		\|weiter=weiter\|weiterlink=Lernpfad_Know-How-Computer/Anhang
	weiter=weiter\|		\|übersicht=Kapitelübersicht\|übersichtlink=Lernpfad_Know-How-Computer#Kapitelübersicht
	weiterlink=Lernpfad_Know-How-Computer/Anhang\|		}}
	übersicht=~~Startseite~~\|
	übersichtlink=Lernpfad_Know-How-Computer}}

	[[Kategorie:Know-How-Computer]]		[[Kategorie:Know-How-Computer]]
	[[Kategorie:Informatik]]		[[Kategorie:Informatik]]
	[[Kategorie:Sekundarstufe 2]]		[[Kategorie:Sekundarstufe 2]]
			[[Kategorie:Barrierefrei]]

Ukalina am 30. Juli 2025 um 19:18 Uhr

2025-07-30T19:18:45Z

← Nächstältere Version		Version vom 30. Juli 2025, 19:18 Uhr
Zeile 90:		Zeile 90:

	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?		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 [[Lernpfad_Know-How-Computer/Know-How-Assembler_-~~Grammatik_einer_formalen_Sprache~~\|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.		Nach den Syntax-Regeln aus dem Kapitel [[Lernpfad_Know-How-Computer/Know-How-Assembler_-_Grammatik_einer_formalen_Sprache\|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=====		=====Übergangsregeln in Form von Wenn-dann-sonst-Aussagen=====
Zeile 342:		Zeile 342:
	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:		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:

	<~~source~~ lang="java">		<syntaxhighlight lang="java">
	/** KHA_Parser als Endlicher Automat		/** KHA_Parser als Endlicher Automat
	* @author Ulrich Kalina		* @author Ulrich Kalina
Zeile 404:		Zeile 404:

	} // class KHA_Parser		} // class KHA_Parser
	</~~source~~>		</syntaxhighlight>

	====Zwei Anmerkungen zum Schluss====		====Zwei Anmerkungen zum Schluss====
Zeile 419:		Zeile 419:
	übersichtlink=Lernpfad_Know-How-Computer}}		übersichtlink=Lernpfad_Know-How-Computer}}

	[[Kategorie:~~Lernpfad~~]]		[[Kategorie:Know-How-Computer]]
	[[Kategorie:Informatik]]		[[Kategorie:Informatik]]
	~~[[Kategorie:Programmieren]]~~
	~~[[Kategorie:Know-How-Computer]]~~
	[[Kategorie:Sekundarstufe 2]]		[[Kategorie:Sekundarstufe 2]]

Ukalina am 30. Juli 2025 um 14:07 Uhr

2025-07-30T14:07:03Z

← Nächstältere Version		Version vom 30. Juli 2025, 14:07 Uhr
Zeile 422:		Zeile 422:
	[[Kategorie:Informatik]]		[[Kategorie:Informatik]]
	[[Kategorie:Programmieren]]		[[Kategorie:Programmieren]]
			[[Kategorie:Know-How-Computer]]
	[[Kategorie:Sekundarstufe 2]]		[[Kategorie:Sekundarstufe 2]]

Ukalina am 30. Juli 2025 um 13:43 Uhr

2025-07-30T13:43:30Z

← Nächstältere Version		Version vom 30. Juli 2025, 13:43 Uhr
Zeile 10:		Zeile 10:
	{{Box		{{Box
	\|1=Ein Parser als Endlicher Automat am Beispiel Know-How-Assembler		\|1=Ein Parser als Endlicher Automat am Beispiel Know-How-Assembler
	\|2=Im Kapitel [[Lernpfad_Know-How-Computer/Know-How-Assembler_-~~Grammatik_einer_formalen_Sprache~~\|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:		\|2=Im Kapitel [[Lernpfad_Know-How-Computer/Know-How-Assembler_-_Grammatik_einer_formalen_Sprache\|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)		# Lexikalische Analyse (Lexer oder auch Scanner)
	# Syntaktische Analyse (Parser)		# Syntaktische Analyse (Parser)

Ukalina: Die Seite wurde neu angelegt: „NOTOC {{Fortsetzung| vorher=zurück| vorherlink=Lernpfad_Know-How-Computer/Know-How-Assembler_-_Grammatik_einer_formalen_Sprache| weiter=weiter| weiterlink=Lernpfad_Know-How-Computer/Anhang| übersicht=Startseite| übersichtlink=Lernpfad_Know-How-Computer}} {{Box |1=Ein Parser als Endlicher Automat am Beispiel Know-How-Assembler |2=Im Kapitel Lernpfad_Know-How-Computer/Know-How-Assembler_-Grammatik_einer_formalen_Sprache|Know-How-Assembler - Gramm…“

2025-07-21T08:31:56Z

Die Seite wurde neu angelegt: „__NOTOC__ {{Fortsetzung| vorher=zurück| vorherlink=Lernpfad_Know-How-Computer/Know-How-Assembler_-_Grammatik_einer_formalen_Sprache| weiter=weiter| weiterlink=Lernpfad_Know-How-Computer/Anhang| übersicht=Startseite| übersichtlink=Lernpfad_Know-How-Computer}} {{Box |1=Ein Parser als Endlicher Automat am Beispiel Know-How-Assembler |2=Im Kapitel Lernpfad_Know-How-Computer/Know-How-Assembler_-Grammatik_einer_formalen_Sprache|Know-How-Assembler - Gramm…“

Neue Seite

__NOTOC__
{{Fortsetzung|
vorher=zurück|
vorherlink=Lernpfad_Know-How-Computer/Know-How-Assembler_-_Grammatik_einer_formalen_Sprache|
weiter=weiter|
weiterlink=Lernpfad_Know-How-Computer/Anhang|
übersicht=Startseite|
übersichtlink=Lernpfad_Know-How-Computer}}

{{Box
|1=Ein Parser als Endlicher Automat am Beispiel Know-How-Assembler
|2=Im Kapitel [[Lernpfad_Know-How-Computer/Know-How-Assembler_-Grammatik_einer_formalen_Sprache|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.
|3=Lernpfad}}

====Lexikalische Analyse====
Die Aufgabe eines Lexers wird am Beispiel des KHA-Programms "Von x auf 0" aus dem Kapitel [[Lernpfad_Know-How-Computer/KHC-Maschinensprache_-_erste_Schritte_Teil_2|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: 
<code>start: isz x; jmp xminus1; stp; xminus1: dec x; jmp start; x: 3;</code>

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 <code>inc</code>, <code>dec</code> oder <code>stp</code> werden als "reservierte Bezeichner" zu eigenen lexikalischen Einheiten zusammengefasst, wobei der KHA-Lexer hier noch einmal unterscheidet zwischen den vier Adressbefehlen <code>inc</code>, <code>dec</code>, <code>jmp</code> und <code>isz</code>, die erst durch einen nachfolgenden Bezeichner als Befehl komplett werden, und dem Stoppbefehl <code>stp</code>, bei dem dies nicht so ist.

Auch die Symbole <code>:</code> und <code>;</code> 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:
{| cellpadding="5" cellspacing="0"border="1"
|+ '''Tokentypen des KHA-Lexers'''
!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"

<code>start</code> <code>:</code> <code>isz</code> <code>x</code> <code>;</code> <code>jmp</code> <code>xminus1</code> <code>;</code> <code>stp</code> <code>;</code> <code>xminus1</code> <code>:</code> <code>dec</code> <code>x</code> <code>;</code> <code>jmp</code> <code>start</code> <code>;</code> <code>x</code> <code>:</code> <code>3</code> <code>;</code>

wird vom Lexer in die folgende '''Tokenkette''' zerlegt, wobei für die Tokentypen die Abkürzungen aus obiger Tabelle verwendet werden:

<code>(B|start)</code> <code>(:|:)</code> <code>(A|isz)</code> <code>(B|x)</code> <code>(;|;)</code> <code>(A|jmp)</code> <code>(B|xminus1)</code> <code>(;|;)</code> <code>(S|stp)</code> <code>(;|;)</code> <code>(B|xminus1)</code> <code>(:|:)</code> <code>(A|dec)</code> <code>(B|x)</code> <code>(;|;)</code> <code>(A|jmp)</code> <code>(B|start)</code> <code>(;|;)</code> <code>(B|x)</code> <code>(:|:)</code> <code>(Z|3)</code> <code>(;|;)</code>

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

<code>:</code> <code>anfang</code> <code>inc</code> <code>dec</code> <code>;</code> <code>stp</code> <code>4</code>

akzeptieren und in folgende Token-Kette überführen:

<code>(:|:)</code> <code>(B|anfang)</code> <code>(A|inc)</code> <code>(A|dec)</code> <code>(;|;)</code> <code>(S|stp)</code> <code>(Z|4)</code>

====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''':

<code>B</code> <code>:</code> <code>A</code> <code>B</code> <code>;</code> <code>A</code> <code>B</code> <code>;</code> <code>S</code> <code>;</code> <code>B</code> <code>:</code> <code>A</code> <code>B</code> <code>;</code> <code>A</code> <code>B</code> <code>;</code> <code>B</code> <code>:</code> <code>Z</code> <code>;</code>

====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 [[Lernpfad_Know-How-Computer/Know-How-Assembler_-Grammatik_einer_formalen_Sprache|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======
<pre>
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
</pre>
======Übergangsregel für den Zustand f======
<pre>
wenn zustand ist f
dann wenn Symbol ist beliebig
dann setze zustand = f
wenn_ende
</pre>

=====Ü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:
{| cellpadding="5" cellspacing="0"border="1"
|+ '''Übergangstabelle für die Zustände n und f'''
!     Symbol Zustand
!A
!B
!S
!Z
!:
!;
|-
|align="center" |'''n'''
|a
|b
|s
|f
|f
|f
|-
|align="center" |'''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======
<pre>
wenn zustand ist s
dann wenn Symbol ist ';'
dann setze zustand = n
sonst setze zustand = f
wenn_ende
</pre>

Wir können damit die obige Übergangstabelle folgendermaßen um eine s-Zeile ergänzen:

{| cellpadding="5" cellspacing="0"border="1"
|+ '''Übergangstabelle für die Zustände n, f und s'''
!     Symbol Zustand
!A
!B
!S
!Z
!:
!;
|-
|align="center" |'''n'''
|a
|b
|s
|f
|f
|f
|-
|align="center" |'''f'''
|f
|f
|f
|f
|f
|f
|-
|align="center" |'''s'''
|f
|f
|f
|f
|f
|n
|}

Selbst, wenn ein Programm lediglich aus der einzigen Anweisung <code>stp ;</code> 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'''.

{{Box
|1=Aufgabe
|2=Formuliere eine Übergangsregel für den Zustand a in Form einer Wenn-dann-sonst-Aussage. Warum ist es hier nicht notwendig, noch einen zusätzlichen Zustand zu definieren? Wie lautet die entsprechende a-Zeile in der Übergangstabelle?
|3=Üben}}

{{ Lösung versteckt
|1=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======
<pre>
wenn zustand ist a
dann wenn Symbol ist 'B'
dann setze zustand = s
sonst setze zustand = f
wenn_ende
</pre>

{{(!}} cellpadding="5" cellspacing="0"border="1"
{{!+}} '''Zeile für Zustand a in der Überganstabelle'''
!     Symbol Zustand
!A
!B
!S
!Z
!:
!;
{{!-}}
{{!}}align="center" {{!}}'''a'''
{{!}}f
{{!}}s
{{!}}f
{{!}}f
{{!}}f
{{!}}f
{{!)}}

|2=Lösung anzeigen
|3=Lösung verbergen}}

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======
<pre>
wenn zustand ist b
dann wenn Symbol ist ':'
dann setze zustand = d
sonst setze zustand = f
wenn_ende
</pre>

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======
<pre>
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
</pre>

Die vollständige Übergangstabelle für unseren EA sieht demnach so aus:

{| cellpadding="5" cellspacing="0"border="1"
|+ '''Übergangstabelle für EA "KHA-Parser"'''
!     Symbol Zustand
!A
!B
!S
!Z
!:
!;
|-
|align="center" |'''n'''
|a
|b
|s
|f
|f
|f
|-
|align="center" |'''a'''
|f
|s
|f
|f
|f
|f
|-
|align="center" |'''b'''
|f
|f
|f
|f
|d
|f
|-
|align="center" |'''d'''
|a
|f
|s
|s
|f
|f
|-
|align="center" |'''s'''
|f
|f
|f
|f
|f
|n
|-
|align="center" |'''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=====
[[Datei:KHA-Parser als EA Graph Arial24.png|alternativtext=Graph zum KHA-Parser, dargestellt als Endlicher Automat mit Zustandsübergängen|left|400px|KHA-Parser als EA - Ü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.
{{Box|1=   Hinweis
|2=Diese Grafik gibt es im [[Lernpfad_Know-How-Computer/Anhang|Anhang]] auch als taktile Schwellpapier-Kopiervorlage mit Braillebeschriftung.
|3=}}
{{clear}}
====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:

<source lang="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
</source>

====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.

{{Fortsetzung|
vorher=zurück|
vorherlink=Lernpfad_Know-How-Computer/Know-How-Assembler_-_Grammatik_einer_formalen_Sprache|
weiter=weiter|
weiterlink=Lernpfad_Know-How-Computer/Anhang|
übersicht=Startseite|
übersichtlink=Lernpfad_Know-How-Computer}}

[[Kategorie:Lernpfad]]
[[Kategorie:Informatik]]
[[Kategorie:Programmieren]]
[[Kategorie:Sekundarstufe 2]]