CB 69 Compilerbau (Sommersemester 1998)
Prof. Debora Weber-Wulff

6. Übungsaufgabe (60 Punkte)

Datum: 8. bzw. 11. Juni 1998

Abgabetermin: 22. bzw. 25. Juni 1996 am Anfang der Übungsstunde

Lernziele: Eine kontextfreie Grammatik aufstellen

  1. (60 Punkte) Erstellen Sie eine kontextfreie Grammatik für Adalein!
Wie schreibt man nun eine Grammatik? Hauptsächlich dadurch, daß man viele andere Grammatiken liest, um Ideen für den eigenen Konstrukte zu sammeln. Dann werden die Eigenschaften geprüft, und fall der Grammatik noch nicht den gewünschten Form hat, kann man durch Verfahren wie in der Vorlesung vorgestellt - Herausnahme von Linksrekursion und Faktorisierung - etwas "Grammatik-Massage" betreiben. Hier ein paar Hinweise aus dem Drachenbuch, Aho/Sethi/Ullman:

Reguläre Ausdrücke vs. Kontextfreie Grammatiken

Jeder Konstrukt, der durch eine regulären Ausdruck beschrieben werden kann, kann auch durch einen kfr-Grammitik beschrieben werden. Z.B. beschreiben der RA (a|b)*abb und der Grammatik 
   A -> aA | bA | aB
   B -> bC
   C -> bD
   D -> \epsilon
die gleiche Sprache, die Menge von Zeichenreihen mit beliebig viele a und b, die mit abb endet.

Es gibt ein Verfahren (dort beschrieben), um aus einer NFSA eine kfr Grammatik zu erhalten. Warum braucht man überhaupt RA, wenn man sie genausogut mit kfr Grammatiken beschreiben kann?

  1. Die lexikalische Regeln einer Sprache sind oft sehr einfach, wir brauchen nicht so eine mächtige Beschreibung.
  2. RA sind meistens knapper und einfacher zu verstehen für Tokenklassen als kfr Grammatiken.
  3. Effizienter lexikalische Analysatoren können automatisch aus RA konstruiert werden, nicht jedoch für beliebige kfr Grammatiken.
  4. Das Aufteilen der syntaktische Struktur einer Sprache in lexikalische und syntaktische Analyse bietet eine gute Modulisierungsmöglichkit an.
RA sind am besten für Identifikatoren, Konstanten, Schlüsselwörter u sw. kfr Grammatiken sind sinnvoller für balanzierte Klammer, begin-end Schachtelungen, if-then-else Konstrukte use, da Verschachtelungen nicht durch RA dargestellt werden können.

Welche Sprache wird durch die Grammatik erzeugt?

Man macht es selten für große Compiler, aber man sollte wissen, wie man die Sprache einer Grammatik bestimmt. Es muß einen Beweis geführt werden mit zwei Teile. Erst mal muss man zeigen, daß jeder Zeichenreihe, die aus der Grammatik generierbar ist, in der Sprache liegt. Dann muß man zeigen, daß alle Zeichenreihen in der Sprache auch generierbar sind.
Debora Weber-Wulff < /a> <weberwu@tfh-berlin.de> Letzte Änderung: Mon Jun 8 09:20:26 1998