Kontextfreie Grammatiken und Ableitungsbäume
Lesen anpassen
Nach dieser Lektion kannst du
kontextfreie Grammatiken lesen und für einfache Sprachen selbst aufstellen,
Ableitungsbäume, Links- und Rechtsableitungen zu einem Wort angeben,
Mehrdeutigkeit erkennen und an einer Ausdrucksgrammatik mit Vorrang beheben,
eine Grammatik in Chomsky-Normalform bringen und mit dem CYK-Algorithmus in entscheiden, ob ein Wort dazugehört,
mit dem Pumping-Lemma für kontextfreie Sprachen zeigen, dass nicht kontextfrei ist.
Vorausgesetzt: Grammatiken und die Chomsky-Hierarchie, Grenzen endlicher Automaten: das Pumping-Lemma
Ein Compiler liest den Text a + a * a und muss entscheiden, ob er zuerst addiert oder zuerst multipliziert. Dazu reicht es nicht zu wissen, ob der Text ein erlaubter Ausdruck ist; der Compiler braucht seine Struktur: welche Teile zusammengehören. Dazu kommen Klammern, die beliebig tief geschachtelt sein dürfen.
Mit endlichen Automaten geht das nicht. Schon die Sprache , ein Modell für „gleich viele öffnende wie schließende Klammern“, ist nicht regulär, wie das Pumping-Lemma zeigt. Kontextfreie Grammatiken sind das Werkzeug, mit dem Programmiersprachen tatsächlich beschrieben werden. Sie erzeugen solche Sprachen und liefern zu jedem Wort einen Baum, der seine Struktur zeigt.
Eine Grammatik hat die Variable und die beiden Regeln und . Man beginnt mit und ersetzt so lange ein durch eine rechte Seite, bis keine Variable mehr übrig ist. Welche Wörter entstehen?
Kontextfreie Grammatik
Eine kontextfreie Grammatik ist ein Tupel mit einer endlichen Menge von Variablen, einem Alphabet von Terminalen (), einem Startsymbol und einer endlichen Menge von Regeln der Form mit und .
„Kontextfrei“ heißt: Links steht genau eine Variable, und sie darf ersetzt werden, egal was links und rechts von ihr steht. Ein Ableitungsschritt ersetzt ein Vorkommen von nach einer Regel ; heißt „in null oder mehr Schritten“. Jedes Wort aus mit heißt Satzform. Die erzeugte Sprache ist . Mehrere Regeln mit derselben linken Seite fasst man mit zusammen: .
Wir schreiben Variablen groß und Terminale klein.
Klammerwörter und ein Gegenbeispiel
Klammerwörter und ein Gegenbeispiel
Liest man a als öffnende und b als schließende Klammer, erzeugt mit den Regeln genau die korrekt geschachtelten Klammerwörter. Eine Ableitung von :
Die Palindrome über erzeugt . Gegenbeispiel: Eine Regel wie ist nicht kontextfrei, denn links steht nicht eine einzelne Variable: darf hier nur ersetzt werden, wenn links davon ein a steht.
Ableitungsbaum
Ein Ableitungsbaum zu ist ein geordneter Baum mit diesen Eigenschaften:
- Die Wurzel ist mit beschriftet, jeder innere Knoten mit einer Variablen.
- Hat ein innerer Knoten die Kinder (von links nach rechts), dann ist eine Regel; für hat er ein einziges Kind .
- Die Blätter sind Terminale oder . Von links nach rechts gelesen ergeben sie das erzeugte Wort.
Bäume schreiben wir hier in Klammerform: ist ein Knoten mit den Kindern in der Klammer. Der Baum zu in ist .
Links- und Rechtsableitung
Ein Baum legt fest, welche Regeln wo angewandt werden, aber nicht, in welcher Reihenfolge. Bei einer Linksableitung wird in jedem Schritt die am weitesten links stehende Variable ersetzt, bei einer Rechtsableitung die am weitesten rechts stehende. Zu jedem Ableitungsbaum gibt es genau eine Linksableitung und genau eine Rechtsableitung.
Beispiel mit der Ausdrucksgrammatik , , und dem Wort :
| Schritt | Linksableitung | Rechtsableitung |
|---|---|---|
| 1 | ||
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | ||
| 6 | ||
| 7 | ||
| 8 |
Beide gehören zu demselben Baum .
In der Linksableitung oben steht nach Schritt 4 die Satzform . Welche Satzform kommt in einer Linksableitung nach ?
Mehrdeutigkeit
Eine Grammatik heißt mehrdeutig, wenn es ein Wort mit zwei verschiedenen Ableitungsbäumen gibt, gleichwertig: mit zwei verschiedenen Linksableitungen. Die einfache Ausdrucksgrammatik ist mehrdeutig:
| Baum | Linksableitung | Bedeutung | |
|---|---|---|---|
| 1 | |||
| 2 |
Für einen Compiler ist das fatal: Mit ergibt der erste Baum , der zweite .
Vorrang in die Grammatik einbauen
Vorrang in die Grammatik einbauen
Die Grammatik , , von oben erzeugt dieselben Ausdrücke, ist aber eindeutig. Jede Variable steht für eine Vorrangstufe: für Summen, (Term) für Produkte, (Faktor) für ein a oder einen geklammerten Ausdruck. Ein kann nur durch entstehen; ein unterhalb davon gehört deshalb zu einem und bindet stärker.
Dass links rekursiv ist ( steht links in der rechten Seite), macht linksassoziativ: hat nur den Baum, der entspricht. Mehrdeutigkeit ist eine Eigenschaft der Grammatik, nicht der Sprache. Es gibt aber auch kontextfreie Sprachen, die nur mehrdeutige Grammatiken haben, etwa ; man nennt sie inhärent mehrdeutig.
Zwei Ableitungen heißt nicht mehrdeutig
Zwei Ableitungen heißt nicht mehrdeutig
„Das Wort hat in der Vorranggrammatik eine Linksableitung und eine davon verschiedene Rechtsableitung, also ist die Grammatik mehrdeutig.“
Fast jedes Wort hat viele Ableitungen, die sich nur in der Reihenfolge der Schritte unterscheiden. Mehrdeutig ist eine Grammatik erst, wenn ein Wort zwei verschiedene Bäume hat. Vergleiche deshalb nur Ableitungen derselben Art, zum Beispiel zwei Linksableitungen.
Chomsky-Normalform
Eine kontextfreie Grammatik ist in Chomsky-Normalform (CNF), wenn jede Regel die Form oder hat (, ). Zusätzlich ist erlaubt, wenn auf keiner rechten Seite vorkommt.
Zu jeder kontextfreien Grammatik gibt es eine Grammatik in Chomsky-Normalform, die dieselbe Sprache erzeugt.
Die Konstruktion besteht aus fünf Schritten, von denen keiner die Sprache ändert:
- Neues Startsymbol: Füge hinzu. Dann steht das Startsymbol nie rechts.
- ε-Regeln entfernen: Bestimme die Variablen, aus denen ableitbar ist. Füge zu jeder Regel alle Varianten hinzu, in denen einige dieser Variablen gestrichen sind (außer der Variante mit leerer rechter Seite), und lösche dann alle Regeln außer . Eine Ableitung, die eine Variable später zu macht, nimmt jetzt gleich die gekürzte Regel.
- Kettenregeln entfernen: Gilt nur über Kettenregeln und ist keine Kettenregel, füge hinzu; lösche danach alle Kettenregeln.
- Terminale auslagern: In jeder rechten Seite der Länge mindestens ersetze ein Terminal a durch eine neue Variable mit der Regel .
- Lange Regeln aufspalten: Ersetze mit durch , , …, mit neuen Variablen .
Danach hat jede Regel eine der erlaubten Formen.
Klammerwörter in Chomsky-Normalform
Klammerwörter in Chomsky-Normalform
Ausgangspunkt ist : .
Neues Startsymbol, weil rechts vorkommt:
CYK-Algorithmus
Der Algorithmus von Cocke, Younger und Kasami entscheidet für eine Grammatik in CNF und ein Wort mit , ob ist. Er berechnet für jedes Teilwort die Menge aller Variablen, aus denen es ableitbar ist.
Die Idee: Aus wird ein Wort der Länge mindestens nur über eine Regel abgeleitet. Dann leitet einen vorderen Teil und den Rest ab. Also ist genau dann, wenn es eine Regel und ein mit gibt, sodass und . Kürzere Teilwörter kommen zuerst dran; das ist dynamische Programmierung.
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 0 | |
| 4 | 1 | |
| 5 | 2 | |
| 6 | 2 | |
| 7 | 3 | |
| 8 | 4 | |
| 9 | 0 |
Das leere Wort prüft man getrennt: Es liegt genau dann in , wenn eine Regel ist.
CYK für
CYK für
Grammatik: die CNF von . Zeile der Tabelle enthält die Mengen der Teilwörter der Länge , Spalte deren Anfangsposition. Das Wort ist ; das Zeichen steht für die leere Menge.
| Länge | ||||||
|---|---|---|---|---|---|---|
| 1 | ||||||
| 2 | ||||||
| 3 | ||||||
| 4 | ||||||
| 5 | ||||||
| 6 |
Einige Einträge im Detail. : Teilwort , einzige Aufteilung mit , ; die Regeln und liefern . : Teilwort ; für ist und , also wegen . : für ist und , also . : für ist und , also wegen und . Weil , gilt .
Im CYK-Algorithmus für ein Wort der Länge : Wie viele Aufteilungspunkte werden für das Feld geprüft?
Pumping-Lemma für kontextfreie Sprachen
Ist kontextfrei, dann gibt es ein , sodass jedes mit eine Zerlegung hat mit
- und ,
- für alle .
Hier wird an zwei Stellen gleichzeitig gepumpt. Die Idee: Ist lang genug, hat der Ableitungsbaum zu einer CNF-Grammatik einen Pfad, auf dem mehr Variablen liegen, als die Grammatik hat. Eine Variable kommt doppelt vor. Den Teilbaum unter dem oberen kann man durch den unter dem unteren ersetzen oder umgekehrt; und sind die Teile, die dabei verschwinden oder sich wiederholen.
Anwendung: ist nicht kontextfrei. Zum gegebenen wähle . Für jede Zerlegung mit kann nicht zugleich ein a und ein c enthalten, denn dazwischen stehen Zeichen b. Mit entsteht : Es hat weniger als Zeichen (wegen ), aber von dem Buchstaben, den nicht berührt, noch alle . Also kommen nicht alle drei Buchstaben gleich oft vor, und .
Zusammenfassung
Eine kontextfreie Grammatik hat Regeln mit einer einzelnen Variablen links; sie erzeugt etwa , Klammerwörter und Palindrome.
Ein Ableitungsbaum zeigt die Struktur eines Wortes. Zu jedem Baum gehört genau eine Links- und genau eine Rechtsableitung.
Mehrdeutig ist eine Grammatik, wenn ein Wort zwei verschiedene Bäume hat; für Ausdrücke behebt man das mit einer Variablen pro Vorrangstufe.
Jede kontextfreie Grammatik lässt sich in Chomsky-Normalform bringen: neues Startsymbol, ε-Regeln und Kettenregeln entfernen, Terminale auslagern, lange Regeln aufspalten.
Der CYK-Algorithmus füllt eine Tabelle von kurzen zu langen Teilwörtern und entscheidet in bei fester Grammatik.
Das Pumping-Lemma für kontextfreie Sprachen pumpt zwei Teile gleichzeitig; damit ist nicht kontextfrei.
Übungen
Welches Wort erzeugt mit ?
Welche Regel ist in Chomsky-Normalform nicht erlaubt (Variablen groß, Terminale klein)?
Wie viele verschiedene Ableitungsbäume hat das Wort in der Grammatik ?
Führe den CYK-Algorithmus mit der CNF von (, , , , ) für das Wort durch. Gib die ganze Tabelle an und entscheide.
Beweise, dass die Grammatik genau die Sprache erzeugt.
Bringe die Grammatik (Palindrome gerader Länge) in Chomsky-Normalform. Gib die Grammatik nach jedem der fünf Schritte an.