TI2—Kapitel 6.3

6.3 Rechnerübung: Gute kontextfreie Grammatiken entwerfen

Benutzen Sie die App drawManualGrammar.html, um mit kontextfreien Grammatik zu experimentieren:

Diese besteht aus folgenden Teilen:

Dem Eingabefenster für die Grammatik links oben. Hier können Sie Ihre eigene Grammatik eingeben.
Dem Eingabefenster für das Eingabewort.
Der Backtrack-Baum. Jeder Pfad im Backtrack-Baum ist der Versuch, das Eingabewort aus den Grammatikregeln per Linksableitung abzuleiten. Die Pfade, die in Sackgassen enden, sind rot markiert.
Der Ableitungsbaum. Für jeden Knoten $w$ im Backtrack-Baum stellt der Pfad von Wurzel nach $w$ eine Linksableitung dar. Wenn Sie auf $w$ klicken, sehen Sie den entsprechenden Ableitungsbaum. Per Default wird die erste erfolgreiche Linksableitung in einen Ableitungsbaum umgewandelt und angezeigt (wenn es denn überhaupt eine erfolgreiche Ableitung gibt).

Übungsaufgabe 6.3.1 Geben Sie folgende Grammatik in die App ein:

S ->; ;
S ->; "("S")"S ;
S ->; "(" S "]" S;

Was ist die erzeugte Sprache? Können Sie sie in Worten beschreiben? Erzeugen Sie Wörter in dieser Sprache, für die der Backtrack-Baum viele rote Sackgassen enthält. Schreiben Sie eine äquivalente Grammatik (d.h., die die gleiche Sprache erzeugt), für die es keine oder nur sehr kurze Sackgassen gibt. Testen Sie die beiden Grammatiken mit "großen" Eingabewörtern und schauen Sie, ob Sie Laufzeitunterschiede bemerken. (Hier erweist sich mein ineffizienter Code als Vorteil: eine schlechte Grammatik wird sofort bestraft).

Übungsaufgabe 6.3.2 Schreiben Sie eine kontextfreie Grammatik für die Sprache aller "korrekten" URLs; also Folgen von mindestens zwei Labels, die durch . separiert sind. Sie können den "Regelvorschlag" ganz links unten in der App reinkopieren, um automatisch Regeln für alphanumerische Zeichen zu bekommen (allerdings verschlechtert das die Laufzeit; ich habe erstmal gar nicht auf Effizienz geachtet). Geben Sie das Eingabewort a.aaaaa.aaaa.aaaa.aaaa.aaaa ein. Wie sieht Ihr Backtrack-Baum aus? Hat er viele Sackgassen? Können Sie Ihre Grammatik so abändern, dass sie zwar noch die gleiche Sprache erzeugt, aber keine / nur wenige Sackgassen hat?

Übungsaufgabe 6.3.3 Entwerfen Sie eine Grammatik für arithmetische Ausdrücke im Racket-Stil, also

(* (+ 2 3) (- 4 (* 2 4) 5)
(+ 1 2 (* 2))

Leidet Ihre Grammatik an langen Sackgassen? Wenn ja, können Sie die Grammatik abändern? Haben Sie mittlerweile ein Schema erkannt, welche Konstrukte lange Sackgassen begünstigen?

Übungsaufgabe 6.3.4 Wiederholen Sie die vorherige Übung für arithmetische Ausdrücke in der uns geläufigen Infix-Notation. Hierbei sollten die Konventionen Punkt-vor-Strich beachtet werden. Im Ableitungsbaum von

2+3*(5+4)

sollte sich das wiederspiegeln.

Übungsaufgabe 6.3.5 (Challenge) Geben Sie die Grammatik hier ein:

S ->; "("S")"S;
S ->; "["S"("S;
S ->; ;

Überlegen Sie, was diese "bedeutet". Sie sehen, die Grammatik ist nicht eindeutig. Das Wort [([()( hat zwei verschiedene Ableitungsbäume. Können Sie eine äquivalente eindeutige Grammatik schreiben?

Übungsaufgabe 6.3.6 (Challenge) Die folgende Grammatik hat User babou auf StackExchange vorgeschlagen als Beispiel für eine eindeutige Grammatik, bei der Sie exponentiell große Backtrack-Bäume bekommen können:

S ->;  "a" X "b" | "a" X "c";
X ->; "a" | "a" X | "a" X X;

Das ist aber keine Kunst, da die Grammatik uneindeutig ist. Können Sie eine eindeutige Grammatik angebene, die ähnlich exponentielles Verhalten zeigt? Exponentiell heißt: mit jedem zusätlichen Zeichen des Eingabewortes kann die Größe des Backtrack-Baumes um einen Faktor $R \gt 1$ wachsen.

Übungsaufgabe 6.3.7 (Super-Challenge; ich hab selbst keine Lösung). Finden Sie eine kontextfreie Sprache $L$, für die jede Grammatik, die $L$ erzeugt, unter exponentiell großen Backtrack-Bäumen leidet.