Zur Themenübersicht    

1. Grundlagen und Grammatik des Rekursiv Parser und das fertiges Programm



1. Grundlagen

Nun wollen wir uns mit der zweiten Möglichkeit des Parsen beschäftigen. Das Parsen durch rekursiven Abstieg.
Dieses Konzept arbeitet nicht mehr mit den bekannten Automaten.
Beim Parsen durch rekursiven Abstieg werden alle durch die Grammatik erzeugbaren Ausdrücke erzeugt. Entsteht dabei der zu prüfende Ausdruck gehört er zur Sprache.
Dazu wird zunächst das Startsymbol der Reihe nach nach allen möglichen Ersetzungsregeln ersetzt. Die so entstandenen Ausdrücke werden rekursiv an dieselbe Methode weitergegeben.
Hier wird nun wieder (in diesen neu entstandenen Ausdrücken) das erste Nichtterminalsymbol der Reihe nach nach allen möglichen Ersetzungsregeln ersetzt. Usw.
Damit nicht unnötig viele Ausdrücke erzeugt werden, wird vor dem Ersetzen überprüft, ob aus dem aktuellen Ausdruck überhaupt noch der gesuchte hervorgehen kann. Falls dies sowieso nicht mehr möglich ist kann der Rekursionszweig bereits enden.
Sobald der zu prüfende Ausdruck entstanden ist, endet die Rekursion und der Ausdruck gehört zur Sprache.
Wenn der Ausdruck durch keinen der Ersetzungsvorgänge entsteht, gehört der Ausdruck auch nicht zur Sprache.


2. Grammatik

Um unsere Sprache durch rekursiven Abstieg zu Parsen wird keine vorrauschauende Grammatik mehr benötigt.
Daher bietet sich diese leichte Abwandelung der vorrauschauenden Grammatik an:

Nichtterminalsambole:
{S; 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
S1
 S -> ε
S2
 S -> BEFEHL S
S3
 S -> ANFRAGE S
S4
 S -> wenn not ANFRAGE dann { S } S
S5
 S -> wenn ANFRAGE dann { S } S
S6
 S -> wenn not ANFRAGE dann { S }sonst { S } S
S7
 S -> wenn ANFRAGE dann { S }sonst { S } S
S8
 S -> solangewie not ANFRAGE tue { S } S
S9
 S -> solangewie ANFRAGE tue { S } S
Regelnummer
 Regel
B1
 BEFEHL -> vor
B2 BEFEHL -> drehe_links
B3 BEFEHL -> drehe_rechts
B4 BEFEHL -> nimm
B5 BEFEHL -> gib
A1
 ANFRAGE -> vornefrei
A2 ANFRAGE -> itemda
A3 ANFRAGE -> blicktnach_links
A4 ANFRAGE -> blicktnach_rechts
A5 ANFRAGE -> blicktnach_oben
A6 ANFRAGE -> blicktnach_unten
A7 ANFRAGE -> itemsimrucksack


3. Das fertige Programm

Das fertiege Programm kann hier im Delphi-Code heruntergeladen werden. Es enthält die beiden neuen Ansätze zum Parsen.

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

    © 2004 LK 13 If und G. Kubitz  Hannah-Arendt-Gymnasium, Lengerich