Home > Informatik > Folge 26

26.3 Kontextfreie Grammatiken

26.1 - 26.2 - 26.3 - 26.4 - 26.5

Beispiel

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

Ein Syntaxdiagramm 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,s0) mit

N = endliche Menge von Nichtterminalzeichen

T = endliche Menge von Terminalzeichen

P = endliche Menge von Produktionsregeln

s0= 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,s0 ) mit
N = { expr }
T = { +, *, num, id, (, ) }
s0 = 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.

Seitenanfang -
26.1 - 26.2 - 26.3 - 26.4 - 26.5