Vorausschau

Einführung > Vorausschau

Die Entscheidung darüber mit welcher Produktion oder Verzweigung innerhalb einer Produktion die Analyse eines Textes fortgesetzt wird, häng stets davon ab, welche Token im Text folgen. Am effizientesten arbeitet ein Parser, wenn bereits das nächstfolgende Token diese Entscheidung ermöglicht. Wenn stets die Vorausschau um nur ein Token zum Analysieren des Textes ausreicht, so nennt man den Parser LL(1)-konform. Es ist eine Kunst des Entwicklers die Grammatik - die Menge der Produktionen - eines Textes so zu formulieren, dass der Parser LL(1)-konform wird.

Der TextTransformer bietet eine große Unterstützung bei dieser Aufgabe, da er automatisch Hinweise und Fehlermeldungen generiert, wenn die Grammatik nicht LL(1)-konform ist. TETRA erlaubt jedoch auch die Vorausschau um beliebig viele Token, wenn dies erforderlich sein sollte. Zur Formulierung einer solchen Vorausschau dienen erneut die bereits bekannten Produktionen. Eine Produktion kann versuchsweise auf einen Text angewendet werden, um zu testen, ob sie ihn parsen kann oder nicht. Abhängig vom Ergebnis dieses Tests kann die Analyse des Textes dann auf verschiedene Weise fortgesetzt werden. (Bei der  versuchsweisen Anwendung von Produktionen werden keine semantischen Aktionen ausgeführt.)

Die Vorausschau sei nochmals an den konkreten Beispiel einer förmlichen Anrede am Anfang eines Briefes erläutert. Sie lautet entweder

Sehr geehrter Herr NAME

oder

Sehr geehrte Frau NAME

Um diese kurzen Texte zu parsen, könnte man zunächst auf die Idee kommen, folgende Produktionen zu formulieren (Das Zeichen "|" trennt Alternativen voneinander, bedeutet also "oder"):

Anrede ::= AnredeBeginn NAME

AnredeBeginn ::=   "Sehr" "geehrter" "Herr"

                | "Sehr"  "geehrte" "Frau"

Bei dieser Formulierung ist eine Vorausschau um zwei Token erforderlich. Erst nachdem das Wort "Sehr" erkannt ist kann durch das folgende Wort entschieden werden, welche Alternative von AnredeBeginn zu wählen ist und es muss wieder vor das Wort "Sehr" zurückgegangen werden, um mit der Verarbeitung des Textes zu beginnen 

Besser sind folgende Produktionen:

Anrede ::= "Sehr" Ehrung NAME

Ehrung ::   "geehrter" "Herr"

         | "geehrte" "Frau"

Bei dieser Formulierung entscheidet stets das nächst Wort eindeutig, wie in den Produktionen fortzufahren ist.

Erstaunlich viele Texte lassen sich nach diesem LL(1)-Prinzip parsen, wenn man die Regeln entsprechend entwirft.

Dennoch gibt es Fälle bei denen eine Vorausschau um nur ein Token prinzipiell nicht ausreicht.  Im TextTransformer ist es möglich in solchen Fällen beliebig weit im Text voraus-zuschauen. Z.B. könnte es nötig sein schon vor dem Parsen eines Satzes zu wissen, ob es sich um einen Fragesatz handelt oder nicht. Der Fragesatz ist aber erst am Ende des Satzes durch das Fragezeichen zu identifizieren. Das ließe sich folgendermaßen bewerkstelligen:

IF( Fragesatz() )

Fragesatz

ELSE

Normalsatz

END

Fragesatz :: FragesatzWortfolge "?"

Normalsatz ::= NormalsatzWortfolge ( "." | "!" )

Diese Seite gehört zur TextTransformer Dokumentation