Formale Grammatik

Formale Grammatiken sind mathematische Modelle von Grammatiken, die so genannte formale Sprachen erzeugen. Sie werden in der theoretischen Informatik, insbesondere in der Berechenbarkeitstheorie, und im Compilerbau angewandt.

Grundlagen

Ein Text (Zeichenkette) ist eine Folge von Zeichen (Terminalsymbole). In der Theorie sind Terminalsymbole häufig auf Kleinbuchstaben beschränkt, z. B. $aaaaabcc$, in der Praxis verwendet man jedoch auch andere Symbole wie Satzzeichen und Schlüsselwörter von Programmiersprachen, z. B. FOR, IF, PROGRAM, usw. Ein kleines Epsilon ($\varepsilon$) steht für ein leeres Wort (wie in Programmiersprachen die leere Zeichenkette, meist "" oder ''.)

Eine formale Grammatik erlaubt es zu entscheiden, ob ein Text dieser Grammatik folgt, also ob er „gültig“ ist. Eine Teilmenge von A* (Alphabet inklusive leeres Wort), die durch Anwendung der Grammatik entsteht, nennt man die Sprache dieser Grammatik. Einen Text, der der Grammatik folgt, nennt man auch ein Wort dieser Sprache. Umgekehrt erlaubt es eine Grammatik auch, alle Wörter ihrer Sprache zu erzeugen.

Formale Grammatiken werden häufig als Semi-Thue-System angegeben, (reguläre Grammatiken auch oft als regulärer Ausdruck). Die gängigen Notationen verwenden Pseudosymbole, sogenannte Nichtterminalsymbole, die im Text nicht auftauchen (oft werden hierfür Großbuchstaben verwendet). Diese Symbole wirken wie Platzhalter, die aufgrund von Regeln (sog. Produktionsregeln oder Produktionen) durch andere Platzhalter oder Terminalsymbole oder eine beliebige Kombination von Platzhaltern und Terminalsymbolen ersetzt werden. Die Regeln produzieren aus einer Folge von Terminalsymbolen und Nichtterminalsymbolen andere Folgen. Beispiele für solche Regeln wären (wobei beachtet werden muss, dass es sich bei | um ein sogenanntes Metazeichen handelt und für oder steht, d. h. für das Nichtterminalsymbol A kann entweder das Terminalsymbol a oder die Vereinigung des Terminal- und Nichterminalsymbols Aa verwendet werden):

• $A\rightarrow a\ \vert \ Aa$
• $B\rightarrow Ab$
• $C\rightarrow Bcc$

Ein Nichtterminalsymbol wird als Startsymbol definiert. Aufgrund der Regeln können dann gültige Texte produziert werden. Nimmt man $C$ als Startsymbol, so ergibt sich im Beispiel folgende Ableitung:

$C\rightarrow Bcc\rightarrow Abcc\rightarrow Aabcc\rightarrow Aaabcc\rightarrow ...\rightarrow aaa...aabcc$

Der obenstehende Text $aaaaabcc$ kann also durch sukzessive Anwendung der Regeln aus dem Startsymbol $C$ produziert werden. Alle Texte, die so produziert werden können, sind gültig im Sinne der formalen Grammatik (also Wörter der Sprache, die die Grammatik definiert).

Gültige Texte wären hier $abcc,aabcc,aaabcc,...$, der Text $bcbca$ ist dagegen ungültig.

Formale Definition

Eine formale Grammatik $G=(N,\Sigma ,P,S)$ ist ein 4-Tupel bestehend aus

• einer endlichen Menge $N$ von Nichtterminalsymbolen (auch Nichtterminale oder Variablen genannt)
• dem Alphabet $\Sigma$, einer endlichen Menge $\Sigma$ von Terminalsymbolen (auch Terminale)
• einer endlichen Menge $P$ von Produktionsregeln (auch Regeln oder Produktionen genannt)
• mindestens einem Startsymbol $S$, das zur Menge der Nichtterminalen gehört ($S\in N$)

Keine der Mengen $N$, $\Sigma$ und $P$ ist die leere Menge. Die Menge der Nichtterminalsymbole und die Menge der Terminalsymbole sind disjunkt. Es gibt also kein Symbol, das sowohl Nichtterminal- als auch Terminalsymbol ist.

Nichtterminale werden gewöhnlich durch Großbuchstaben, Terminale durch Kleinbuchstaben repräsentiert. Eine andere Möglichkeit ist es, alle Nichtterminale durch spitze Klammern zu kennzeichnen (<Nichtterminal>).

Eine Regel besteht aus einer linken (Prämisse) und einer rechten Seite (Konklusion), die jeweils ein Wort bestehend aus Terminalen und Nichtterminalen sind. Die linke Seite muss mindestens ein Nichtterminal beinhalten und die rechte Seite kann dabei im Gegensatz zur linken Seite auch das leere Wort (im Folgenden mit $\varepsilon$ symbolisiert) sein, also das Wort der Länge Null:

$P\subseteq \left(\left(N\cup \Sigma \right)^{*}N(N\cup \Sigma \right)^{*})\times \left(N\cup \Sigma \right)^{*}$

Eine Grammatik ist in Normalform genau dann wenn gilt:

$P\subseteq N^{+}\times \left(N\cup \Sigma \right)^{*}$

Eine Regel kann auf ein Wort, bestehend aus Terminalen und Nichtterminalen, angewendet werden, wobei ein beliebiges Vorkommen der linken Seite der Regel im Wort durch die rechte Seite der Regel ersetzt wird. Dies ist die Transitionsrelation und man sagt formal, dass ein Wort u unter der Grammatik G unmittelbar in ein Wort v übergeht ($u\Rightarrow _{G}v$).

Wendet man die Produktionen beginnend mit der Startvariablen $S$ an, bis man ein Wort $w_{n}$ nur bestehend aus Terminalen erhält, so nennt man die entstehende Folge von Wörtern $(w_{0},w_{1},\ldots ,w_{n})$ Ableitung von $w_{n}$. Das heißt also $w_{0}=S,w_{n}\in \Sigma ^{*}$ und $w_{0}\Rightarrow w_{1}\Rightarrow \ldots \Rightarrow w_{n}$. Typischerweise enthalten Wörter dieser Ableitung auch Nichtterminale. Ein solches Wort $w\in (V\cup \Sigma )^{*}$ nennt man auch Satzform.

Beispiel

Wir betrachten die Grammatik mit den Terminalen $\{a,b\}$, den Nichtterminalen $\{S,A,B\}$ mit dem Startsymbol $S$ und den Regeln

${\begin{matrix}S&\to &ABS\\S&\to &\varepsilon \\BA&\to &AB\\BS&\to &b\\Bb&\to &bb\\Ab&\to &ab\\Aa&\to &aa\end{matrix}}$

Sie definiert die Sprache aller Wörter der Form $a^{n}b^{n}$ mit $n\in \mathbb {N}$, d. h. $n$ Kopien von $a$ gefolgt von $n$ Kopien von $b$.

Es ist zu beachten, dass dies nicht die einzige Grammatik ist, die diese Sprache erzeugt. Man klassifiziert verschiedene Typen von Grammatiken in der so genannten Chomsky-Hierarchie. Die obige entspricht dem Chomsky-Typ 1 (kontextsensitiv), da auf der linken Seite der Erzeugungsregeln sowohl Nichtterminale als auch Terminale enthalten sind. Eine weitere Grammatik zur Erzeugung von $\{a^{n}b^{n}|n\in \mathbb {N} \}$ ist die mit diesen Regeln

${\begin{matrix}S&\to &ASB\ |\ \varepsilon \\A&\to &a\\B&\to &b\end{matrix}}$

oder auch nur schlicht:

${\begin{matrix}S&\to &aSb\ |\ \varepsilon \end{matrix}}$

Man sieht also, dass es zur Erzeugung einer Sprache mehrere (genaugenommen: abzählbar unendlich viele) Grammatiken gibt.

Die obige wäre z. B. vom Chomsky-Typ 2 (kontextfrei).

Von G erzeugte Sprache

Eine Grammatik $G$ erzeugt eine formale Sprache $L\left(G\right)$, die aus allen Wörtern besteht, die nur aus Terminalen bestehen und vom Startsymbol mit einer endlichen Anzahl von Schritten abgeleitet werden können:

$L\left(G\right):=\left\{w\in \Sigma ^{*}|S\Rightarrow _{G}^{*}w\right\}$

$\Rightarrow _{G}$ symbolisiert hierbei die so genannte Transitionsrelation, siehe dort. Der Stern in $\Rightarrow ^{*}$ bedeutet nach einer beliebigen Anzahl von Schritten, also die reflexiv-transitive Hülle der Relation $\Rightarrow$.

Siehe auch

• Kleenesche Hülle
• Graphgrammatik
• Erweiterte Backus-Naur-Form

Literatur

• Katrin Erk, Lutz Priese: Theoretische Informatik: eine umfassende Einführung. 2., erw. Auflage. Springer-Verlag, 2002, ISBN 3-540-42624-8, S. 53–61.