Zur Themenübersicht

2. Grundlagen und Grammatik des Keller Automaten

1. Grundlagen

Ein Kellerautomat besitzt im Gegensatz zu den bisher bekannten Automaten einen Keller, auf dem eine Folge von Terminal- und Nichtterminalsymbolen liegt. Ein Kellerautomat kann Sprachen zu kontextfreien Grammatiken erkennen. Was genau bei einer Eingabe passiert, hängt neben der Eingabe und dem aktuellen Zustand zusätzlich noch vom obersten Kellersymbol ab:

Handelt es sich um ein Nichtterminalsymbol wird eine den Ersetzungsregeln der Grammatik (für diese NTS) entsprechende Folge von Terminal- und Nichtterminalsymbolen auf den Keller gelegt. Falls es mehrere mögliche Ersetzungen für ein Nichtterminalsymbol gibt, muss die Grammatik so formuliert sein, dass anhand der nächsten k Eingabzeichen entschieden werden kann, welche Ersetzungsregel anzuwenden ist. (Eine solche Grammatik heißt vorrausschauend vom Grad k). Wenn es keine passende Regel für das aktuelle Eingabezeichen (unter Beachtung der nächsten k Eingabezeichen) gibt, dann gehört der zu prüfende Ausdruck nicht zur Sprache.

Handelt es sich um ein Terminalsymbol, wird das aktuelle Eingabezeichen mit ihm verglichen. Wenn sie übereinstimmen, kann das nächsten Eingabezeichen verarbeitet werden. Falls sie sich unterscheiden, gehört der zu prüfende Ausdruck nicht zur Sprache.

2. Grammatik

Um unsere Sprache nun mithilfe eines Kellerautomaten Parsen zu können benötigen wir zunächst eine vorrauschauende Grammatik, mit der unsere Sprache erzeugt werden kann.

Eine vom Grad 1 ist die folgende:

Nichtterminalsambole:
{S; nNOT; nSONST; BEFEHL; ANFRAGE}

Terminalsymbole:
{ε; wenn; dann; sonst; solangewie; tue; not; {; }; vor; drehe_links; drehe_rechts; nimm; gib; vornefrei; itemda; blicktnach_links; blicktnach_rechts; blicktnach_oben; blicktnach_unten; itemsimrucksack}

Startsymbol: S

Die Ersetzungsregeln der Grammatik

Regelnummer	Regel
1	S -> ε
2	S -> BEFEHL S
3	S -> ANFRAGE S
4	S -> wenn nNOT ANFRAGE dann { S } nSONST S
5	S -> solangewie nNOT ANFRAGE tue { S } S
6	nNOT -> ε
7	nNOT -> not
8	nSONST -> ε
9	nSONST -> sonst { S }

Regelnummer	Regel
10	BEFEHL -> vor
11	BEFEHL -> drehe_links
12	BEFEHL -> drehe_rechts
13	BEFEHL -> nimm
14	BEFEHL -> gib
15	ANFRAGE -> vornefrei
16	ANFRAGE -> itemda
17	ANFRAGE -> blicktnach_links
18	ANFRAGE -> blicktnach_rechts
19	ANFRAGE -> blicktnach_oben
20	ANFRAGE -> blicktnach_unten
21	ANFRAGE -> itemsimrucksack

Zur Themenübersicht
Zum Seitenanfang
Zur vorigen Seite	Zur nächsten Seite

Hannah-Arendt-Gymnasium, Lengerich