Formale Grammatik

Formale Grammatiken sind mathematische Modelle von Grammatiken, die so genannte formale Sprachen erzeugen und besonders in der theoretischen Informatik, insbesondere bei Berechenbarkeitstheorie und dem Compilerbau Anwendung finden.

Grundlagen

Eine formaler Text besteht aus Symbolen, die Terminalsymbole genannt werden. In der formalen Theorie werden hier oft etwa Kleinbuchstaben verwendet, in Programmiersprachen jedoch noch andere Symbole wie Satzzeichen und Schlüsselwörter wie FOR, IF, PROGRAM, ... .

Ein Text ist eine Folge von Kleinbuchstaben, also etwa $aaaaabcc$ .

Eine formale Grammatik erlaubt die Unterscheidung von grammatisch korrekten, also gültigen, Texten von ungültigen.

Formale Grammatiken verwenden Pseudosymbole, sogenannte Nichtterminalsymbole, die im Text nicht auftauchen. In der Theorie verwendet man oft Großbuchstaben. Diese Symbole wirken wie Platzhalter, die aufgrund von Regeln 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

$A\rightarrow a$
$A\rightarrow 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:

$C\rightarrow Bcc\rightarrow Abcc\rightarrow Aabcc\rightarrow Aaabcc\rightarrow ...\rightarrow aaaaabcc$

Der obenstehende Text $aaaaabcc$ kann also durch sukzessive Anwendung der Regeln aus dem Startsymbol $C$ produziert werden. Die Regeln heißen daher auch Produktionsregeln oder Produktionen. Alle Texte, die so produziert werden können, sind gültig im Sinne der formalen Grammatik.

Gültige Texte wären hier $abcc,aabcc,aaabcc,...$

Der Text $bcbca$ ist ungültig.

Definition

Eine formale Grammatik $G$ ist gegeben durch ein 4-Tupel, bestehend aus einer endlichen Menge $N$ von Non-terminalsymbolen (im Folgenden kurz Nichtterminale, oft aber auch Variablen genannt), einer endlichen Menge $\Sigma$ von Terminalsymbolen (im Folgenden kurz Terminale genannt) (wobei das Alphabet $\Sigma$ und die Nichtterminale N disjunkt sind), einer endlichen Menge $P$ von Produktionsregeln (im Folgenden kurz Regeln, oft auch Produktionen, genannt) und einem Startsymbol $S$ , welches zu den Nichtterminalen gehört:

$G=\left(N,\Sigma ,P,S\right)$ , $S\in N$ , $N\cap \Sigma =\emptyset$

Nichtterminale werden gewöhnlich durch Großbuchstaben, Terminale durch Kleinbuchstaben repräsentiert.

Eine Regel besteht aus einer linken und einer rechten Seite, 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(N\cup \Sigma \right)^{*}\cdot N\cdot \left(N\cup \Sigma \right)^{*}\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 rechten Seite der Regel ersetzt wird. Für solche Produktionen hat sich folgende Schreibweise eingebürgert:

$w\rightarrow w'$

Für w, w' gilt dann die so genannte Transitionsrelation, eine Folge von Anwendungen solcher Regeln bezeichnet man als Ableitung.

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 $\Rightarrow ^{*}$ bedeutet nach beliebiger Anwendung der Produktionsregeln. Also die reflexiv-transitive Hülle der Relation $\Rightarrow$ .

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}|n\in N_{0}$ , d.h. $n$ Kopien von $a$ gefolgt von $n$ Kopien von $b$ .

Hierbei ist zu beachten, dass dies nicht die einzige Grammatik ist, die diese Sprache erzeugt. Eine weitere Grammatik zur Erzeugung von $a^{n}b^{n}|n\in N_{0}$ 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: beliebig viele) Grammatiken gibt.

Man klassifiziert verschiedene Typen von Grammatiken in der so genannten Chomsky-Hierarchie. Die obige wäre z.B Typ2

Siehe auch