26.3 Kontextfreie Grammatiken

Beispiel

Betrachten wir uns noch einmal die Abbildung eines Syntaxdiagramms für arithmetische Ausdrücke:

Ein Syntaxdiagramm für arithmetische Ausdrücke (expr) mit fünf Produktionsregeln

Ein Syntaxdiagramm zu zeichnen kann mitunter recht aufwändig sein. Es gibt aber eine einfachere Möglichkeit, eine Sprache zu definieren. Ja richtig, die arithmetischen Ausdrücke sind ja eine Sprache, nämlich die Sprache eines Kellerautomaten. Kommen wir nun zum Hauptthema der Folge 26, nämlich zu den kontextfreien Grammatiken.

Kontextfreie Grammatiken

Am besten lernt man etwas Neues, indem man sich einfach mal ein Beispiel anschaut. Die kontextfreie Grammatik, die äquivalent zum obigen Syntaxdiagramm ist, sieht so aus:

P1: expr ---> expr + expr
P2: expr ---> expr * expr
P3: expr ---> num
P4: expr ---> id
P5  expr ---> ( expr )

Eine fast ähnliche Darstellung hatten wir bereits auf der letzten Seite gesehen. In dem Kasten sind sogenannte Produktionsregeln dargestellt und mit P1 bis P5 durchnummeriert. Dabei stehtexpr für "arithmetischer Ausdruck" bzw. "expression". Ein arithmetischer Ausdruck kann also ein arithmetischer Ausdruck sein, nach dem ein Plus-Zeichen bzw. Mal-Zeichen und ein weiterer arithmetischer Ausdruck kommt (P1 bzw. P2). Ein arithmetischer Ausdruck kann aber auch einfach eine Zahl sein (P3) oder eine Variable (P4). Schließlich kann ein arithmetischer Ausdruck aus einem geklammerten arithmetischen Ausdruck bestehen (P5).

Formale Definition einer Grammatik

Unter einer Grammatik versteht man ein 4-Tupel G = (N,T,P,s₀) mit

N = endliche Menge von Nichtterminalzeichen

T = endliche Menge von Terminalzeichen

P = endliche Menge von Produktionsregeln

s₀= Startsymbol, dabei gilt: $s_{0} \in N$.

Terminalzeichen sind die "fertigen", nicht mehr veränderbaren Worte oder Zeichen einer Sprache. Im Deutschen wären etwa Begriffe wie "Hund", "Katze", "jagt", "ist" etc. Terminalzeichen. In unserer Beispielgrammatik für arithmetische Ausdrücke wären die Operatoren "+" und "*" sowie Zahlen, Variablennamen und Klammern Terminalzeichen.
Bei den bisher verwendeten Beispielen sind auch Begriffe wie num und id Terminalzeichen, obwohl sie ja eigentlich noch nicht ganz terminal sind, sondern durch konkrete Zahlen und Variablennamen ersetzt werden müssten.
Nichtterminalzeichen sind grammatikalische Oberbegriffe, im Deutschen zum Beispiel Satz, Verb, Substantiv, Objekt etc. und in unserer Beispielgrammatik der Ausdruck expr.
Produktionsregeln schreiben vor, wie man aus einem Nichtterminal eine Kette von Terminalen und Nichtterminalen produziert.
Das Startsymbol ist quasi der Startzustand der Grammatik; die erste Produktionsregel fängt immer mit dem Startsymbol auf der linken Seite an.

Formale Definition einer kontextfreien Grammatik

Unter einer kontextfreien Grammatik versteht man eine Grammatik, bei der alle Produktionsregeln die Form haben:

$A \to$ a*

Dabei ist $A \in N$ und a* eine Zeichenkette aus $N \cup T$.

$A$ ist also ein Nichtterminal, das durch die Produktionsregel zu einer Zeichenkette aus Nichtterminalen und Terminalen erweitert wird. Bei einer kontextfreien Grammatik steht auf der linken Seite einer Produktionsregel stets genau ein Nichtterminal. Nicht mehr und nicht weniger.

Wenden wir diese Definition auf unsere Beispiel-Grammatik zur Erzeugung arithmetischer Ausdrücke an, so erhalten wir:

G = ( N,T,P,s₀ ) mit
N = { expr }
T = { +, *, num, id, (, ) }
s₀ = expr
P = {P1, P2, P3, P5, P5}

Zur Abgrenzung: kontextsensitive Grammatiken

"Richtige" Sprachen wie zum Beispiel Deutsch oder Englisch beruhen nicht auf kontextfreien Grammatiken, sondern auf kontextsensitiven Grammatiken.

Bei einer kontextfreien Grammatik steht grundsätzlich nur ein Nichtterminal auf der linken Seite jeder Produktionsregel, und sonst nichts.

Bei einer kontextsensitiven Grammatik können mehrere Zeichen auf der linken Seite stehen, Terminale und Nichtterminale. Mit anderen Worten: Was aus einem Nichtterminal auf der linken Seite wird, kann von den links und rechts stehenden Terminalen und/oder Nichtterminalen abhängen, von dem Kontext also, in dem das Nichtterminal steht.

aA ---> aAb
bA ---> aABb

Hier sehen wir zwei (selbstausgedachte) Produktionsregeln einer kontextsensitiven Grammatik. Das "Schicksal" des Nichtterminals A auf der linken Seite hängt von dem Terminal ab, das links von ihm steht, also vom Kontext (Zusammenhang).

Rekursion in den Produktionsregeln

Bei einer Produktionsregel wie

expr ===> expr + expr

ist die Rekursion auffällig. Das Nichtterminal, das auf der linken Seite der Produktion steht, kann auch auf der rechten Seite auftauchen, sogar mehrfach. Die wiederholte Anwendung einer solchen Produktion führt dann zu theoretisch unendlich langen Ausdrücken.

Reguläre Ausdrücke und kontextfreie Grammatiken

Kontextfreie Grammatiken und Kellerautomaten gehören zusammen. Die Sprache eines Kellerautomaten kann auch durch eine kontextfreie Grammatik erzeugt werden.

Determinierte endliche Automaten und reguläre Sprachen bzw. Ausdrücke gehören ebenfalls zusammen, wie wir gesehen haben. Aber gibt es auch kontextfreie Grammatiken, die reguläre Ausdrücke erzeugen können?

Reguläre Grammatik

Unter einer regulären Grammatik versteht man eine kontextfreie Grammatik, bei der die Produktionsregeln die folgende Form haben:

$A \to \alpha B$

$A \to \alpha$

oder

$A \to B \alpha$

$A \to \alpha$

Im ersten Fall spricht man von einer rechtslinearen Grammatik, im zweiten Fall von einer linkslinearen Grammatik.

Ein Beispiel aus dem NRW-Abitur von 2012

Diese alte Abituraufgabe ist nach den schlimmen Waldbränden in Australien im Januar 2020 wieder ganz aktuell. Es geht um Waldbrände und vorbeugende Maßnahmen der Feuerwehr, um Waldbrände zu verhindern. Ausgangsmaterial für diese Aufgabe ist der folgende determinierte endliche Automat:

Der Waldbrand-DEA

Der Startzustand dieses Automaten ist 1, der Endzustand 4. Wenn der Automat im Endzustand angekommen ist, ist der Wald wirklich in Gefahr zu brennen oder er brennt sogar schon. Die Symbole sind folgendermaßen zu deuten:

h = heiß und sonnig
t = trocken (dabei muss es nicht unbedingt heiß sein)
s = leichter Regen (Sprüh-, Nieselregen)
r = starker Regen

Betrachten wir mal ein typisches Beispiel. Im Zustand 1 ist der Wald völlig ungefährdet. Nun ist es eine Tag Periode lang heiß (h). Der Wald gerät in den Zustand 3. Ist es noch eine weitere Periode lang heiß, gerät der Wald in den Zustand 4, was "höchste" Gefährdungsstufe mit einer sehr hohen Waldbrandgefahr bedeutet. Durch einen leichten Regen (s) gelangt der Wald wieder in die weniger gefährliche Stufe 3. Fällt weiterhin ein leichter Regen (s), gelangt der Wald in die Stufe 2, und mit noch mehr Regen (leicht oder stark ist jetzt egal) sogar in die Ausgangsstufe 1.

In der ursprünglichen Abituraufgabe sollten die Schüler(innen) den Automaten gründlich analysieren, eine passende Übergangstabelle aufstellen und den Automaten um weitere Funktionen erweitern, was uns hier aber nicht weiter interessiert.

In der Aufgabe e) sollten die Schüler(innen) dann eine reguläre Grammatik entwickeln, welche die Sprache des DEAs produziert. In den Erwartungen zu dieser Aufgabe findet sich dann als Lösungsvorschlag folgende Grammatik:

Die Waldbrand-Grammatik

Hier handelt es sich eindeutig um eine rechtslineare Grammatik; alle 21 Produktionen haben auf der rechten Seite entweder ein Terminal {r, s, h, t} oder ein Terminal, gefolgt von einem Nichtterminal.

Laut Übergangsdiagramm des DEA führt beispielsweise die Zeichenfolge

h s t t

in den Endzustand 4. Wie kann man diese Zeichenfolge mit Hilfe der Grammatik generieren?

S ===> h B

h B ===> h s A

h s A ===> h s t B

h s t B ====> h s t t

Übung 26.3-1

Leiten Sie durch geschickte Anwendung der Produktionsregeln folgenden Ausdruck her:

r t s h s t h

Lösungsvorschlag auf den Seiten für Lehrer(innen) / Nähere Infos dazu

Seitenanfang -
26.1 - 26.2 - 26.3 - 26.4 - 26.5