Kontextfreie Grammatik

Eine Grammatik enthält eine endliche Menge von Ersetzungsregeln (auch Produktionen genannt).

Mithilfe der Ersetzungsregeln bildest du aus schon vorhandenen Wörtern neue Wörter. Beispielsweise kannst du alle Wörter der Sprache

$L = \{\mathsf a^n\mathsf b^n ~|~ n \in \mathbb N \} = \{\mathsf{ab}, \mathsf{aabb}, \mathsf{aaabbb}, ... \}$

erzeugen, indem du folgende Ersetzungsregeln anwendest:

$S\rightarrow \mathsf aS\mathsf b$

$S \rightarrow \mathsf{ab}$

Hierbei ist $S$ das Startsymbol. Dies bedeutet, dass du immer mit dem Wort $S$ startest und in diesem Wort das Zeichen, das auf der linken Seite einer Ersetzungsregel steht, durch das Wort ersetzt, das auf der entsprechenden rechten Seite steht. Und dann in dem dadurch entstehenden Wort gegebenenfalls noch einmal und noch einmal usw.

Ersetzungsregeln anwenden

Um beispielsweise das Wort aaabbb zu erzeugen, startest du mit dem Startsymbol $S$. Als Erstes wendest du die erste Ersetzungsregel an und ersetzt das Zeichen $S$ durch das Wort $\mathsf aS\mathsf b$. Dann ersetzt du in diesem Wort das Zeichen $S$ noch einmal durch $\mathsf aS\mathsf b$ und erhältst das Wort $\mathsf{aa}S\mathsf{bb}$. Und zum Schluss wendest du die zweite Ersetzungsregel an und ersetzt in diesem Wort das Zeichen $S$ durch ab – fertig ist das Wort aaabbb.

Die Ableitungsfolge für das Wort aaabbb mit diesen Ersetzungsregeln lautet also

$S \rightarrow \mathsf aS\mathsf b \rightarrow \mathsf{aa}S\mathsf{bb} \rightarrow \mathsf{aaabbb}$

Die einzelnen Übergänge von einem Wort zum nächsten heißen Ableitungsschritte.

Auf diese Weise kannst du jedes Wort der Sprache $L$ erzeugen, je nachdem, wie oft du die erste Ersetzungsregel anwendest. Und andere Wörter über dem Alphabet $A$ = {a, b}, die nicht zur Sprache $L$ gehören, kannst du mit diesen Ersetzungsregeln nicht erzeugen. Die Grammatik mit diesen Ersetzungsregeln erzeugt also genau die Sprache $L$.

Das Gleiche mit anderen Ersetzungsregeln

Noch schnell ein anderes Beispiel. Die Grammatik mit folgenden Ersetzungsregeln erzeugt ebenfalls die Sprache $L = \{\mathsf a^n\mathsf b^n ~|~ n \in \mathbb N \}$ über dem Alphabet {a,b}.

$S \rightarrow \mathsf aX$

$X \rightarrow S\mathsf b$

$X \rightarrow \mathsf b$

Gib die Ableitungsfolge für das Wort aaabbb mit den Ersetzungsregeln dieser Grammatik an! Du kannst nicht viel falsch machen - du ersetzt ausgehend von dem Wort $S$ immer das Zeichen auf der linken Seite einer Ersetzungsregel durch das Wort auf der entsprechenden rechten Seite.

$S \rightarrow \mathsf aX \rightarrow …$

Doch halt! Du musst aufpassen, ob du $X$ durch $S\mathsf b$ oder durch b ersetzt – einmal falsch ersetzt, und du erhältst nicht das gewünschte Wort aaabbb!

Formale Definition

In den Beispielen von eben besteht bei allen Ersetzungsregeln die linke Seite immer nur aus einem einzigen Großbuchstaben – einem Zeichen, das nicht zu dem Alphabet gehört, aus dem die Wörter der Sprache gebildet sind. Eine so beschaffene Grammatik wird als kontextfreie Grammatik bezeichnet.

Kontextfreie Grammatiken spielen die Hauptrolle bei der Syntax von Programmiersprachen.

Eine kontextfreie Grammatik ist ein 4-Tupel $G = (V, T, P, S)$; hierbei sind

$V$ das Alphabet der Variablen oder Nichtterminalzeichen,

$T$ das Alphabet der Terminalzeichen,

$A = V \cup T$ das Gesamtalphabet,

$P\subseteq V\times A^*$ die Menge der Ersetzungsregeln oder Produktionen,

$S \in V$  das Startsymbol.

Die Terminalzeichen sind diejenigen Zeichen, aus denen zum Schluss die Wörter der erzeugten Sprache bestehen. Die Nichtterminalzeichen brauchst du auf dem Weg dorthin für den Ableitungsvorgang, sie kommen in den Wörtern der erzeugten Sprache nicht vor.

Die Bezeichnung kontextfrei deutet darauf hin, dass du die Ersetzungsregeln in jedem Kontext, also ohne das Drumherum in dem jeweiligen Wort zu berücksichtigen, anwenden kannst – im Gegensatz zu einer kontextsensitiven Grammatik, bei der dies nicht so ist.

Eine Grammatik heißt kontextfrei, wenn auf der linken Seite jeder Produktion nur ein einziges Nichtterminalzeichen steht.

Beispielgrammatik formal

Formal dargestellt lautet die Grammatik $G = (V, T, P, S)$ aus dem letzten Beispiel

$V = \{S, X\}$

$T = \{\mathsf a,\mathsf b\}$

$P = \{ (S,\mathsf aX), (X,S\mathsf b), (X,\mathsf b) \}$

$S = S$

Die Nichtterminalzeichen sind also $S$ und $X$, die Terminalzeichen sind a und b. Die Produktionen sind formal als Tupel geschrieben, beispielsweise $(S,\mathsf aX)$; anschaulicher ist es jedoch, $S \rightarrow \mathsf aX$ zu schreiben, denn eine Ersetzungsregel lässt sich auch als Ableitungsschritt auffassen. Das Startsymbol ist $S$.

Erzeugte Sprache

Du hast an verschiedenen Beispielen gesehen, wie du mit den Ersetzungsregeln einer Grammatik die Wörter einer Sprache erzeugen kannst. Hier nun die offizielle Definition:

Die Sprache $L(G)$, die von einer Grammatik $G$ erzeugt wird, besteht aus allen Wörtern, die nur aus Terminalzeichen bestehen und die sich aus dem Startsymbol in einem oder mehreren Ableitungsschritten ableiten lassen:

$L(G) = \{w \in T^* ~|~ S \stackrel*\rightarrow w\}$

Hierbei ist $T^*$ die Menge aller Wörter, die aus Terminalzeichen bestehen, und $\stackrel*\rightarrow$ bedeutet ableitbar in 0, 1 oder mehreren Schritten (wobei 0 Schritte hier nicht infrage kommt, weil das Startsymbol $S$ kein Terminalzeichen ist).

Kontextfreie Sprache

Der Einfachheit halber wird eine Sprache, die sich mit einer kontextfreien Grammatik erzeugen lässt, als kontextfreie Sprache bezeichnet. Korrekt müsste es vielleicht "von einer kontextfreien Grammatik erzeugbare Sprache" heißen. Aber der Kürze halber sagst du einfach "kontextfreie Sprache".

Du erinnerst dich sicher, dass du in ähnlicher Weise eine Sprache als "reguläre Sprache" bezeichnest, wenn es einen regulären Ausdruck gibt, der die Sprache erzeugt.

Du erinnerst dich auch daran, dass eine Sprache genau dann eine reguläre Sprache ist, wenn es einen (deterministischen oder nichtdeterministischen) endlichen Automaten gibt, der die Sprache erkennt. In ähnlicher Weise gilt:

Eine Sprache ist genau dann eine kontextfreie Sprache, wenn es einen nichtdeterministischen Stackautomaten gibt, der die Sprache erkennt.

In diesem Fall kommt es auf das "nichtdeterministisch" an. Die deterministischen Stackautomaten können weniger. Als Nächstes erfährst du, wie ein Stackautomat funktioniert.