Formale Grammatik

Formale Grammatiken s​ind mathematische Modelle v​on Grammatiken, d​ie zur eindeutigen Erzeugung u​nd Beschreibung formaler Sprachen dienen. Sie werden i​n der theoretischen Informatik, insbesondere i​n der Berechenbarkeitstheorie, u​nd im Compilerbau z​um einen angewendet, u​m eindeutig festzulegen, o​b ein Wort Element e​iner Sprache i​st und z​um anderen, u​m Eigenschaften dieser formalen Sprachen z​u untersuchen bzw. z​u beweisen. Formale Grammatiken werden mithilfe v​on Semi-Thue-Systemen angegeben i​n der Chomsky-Hierarchie klassifiziert.

Beschreibung

Mit einer formalen Grammatik lassen sich ausgehend von einem Startsymbol ${\displaystyle S}$ (auch Startvariable genannt) Produktionsregeln aus einer Regelmenge ${\displaystyle P}$ anwenden, die aus dem Startsymbol neue Zeichenfolgen (Wörter) erzeugen, welche wiederum weiter ersetzt werden können. Diesen Vorgang nennt man auch Ableitung.

Das Vokabular ${\displaystyle V}$ einer Grammatik, bestehend aus der disjunkten Vereinigung eines Alphabets ${\displaystyle T}$ von Terminalsymbolen mit einer Menge von Nichtterminalsymbolen ${\displaystyle N}$, gibt dabei vor, welche Symbole dafür verwendet werden können. Die Menge der Terminalsymbole definiert, aus welchen Zeichen Wörter bestehen, die nicht weiter abgeleitet werden können. Diese Wörter ergeben zusammengenommen die von der Grammatik beschriebene formale Sprache. Das Startsymbol muss dagegen ein Nichtterminalsymbol sein. Zusätzliche Nichtterminalsymbole erlauben differenziertere Regeln.

Produktionsregeln sind definitionsgemäß geordnete Paare ${\displaystyle (\alpha ,\beta )}$, die auch ${\displaystyle \alpha \rightarrow \beta }$ geschrieben werden. Man wendet sie auf eine Zeichenfolge ${\displaystyle w}$ an, indem ein Vorkommen der Zeichenfolge ${\displaystyle \alpha }$ in ${\displaystyle w}$ durch ${\displaystyle \beta }$ ersetzt wird. Auf der linken Seite der Regel muss immer mindestens ein Nichtterminalsymbol stehen. Eine Menge von Regeln mit gleicher linker Seite, also ${\displaystyle \alpha \rightarrow \beta _{1},\;\ldots ,\alpha \rightarrow \beta _{n}}$, wird abkürzend auch als ${\displaystyle \alpha \rightarrow \beta _{1}\;|\;\ldots \;|\;\beta _{n}}$ geschrieben.

Zum Beispiel kann man mit der Regelmenge ${\displaystyle X\rightarrow +\;|\;-}$ die Zeichenfolge ${\displaystyle 1X2}$ entweder zu ${\displaystyle 1+2}$ oder zu ${\displaystyle 1-2}$ ableiten.

Ebenso w​ie auf e​ine gegebene Zeichenfolge mehrere Regeln gleichzeitig anwendbar s​ein können, m​uss es n​icht immer n​ur eine Stelle i​n der Zeichenfolge geben, a​uf die e​ine Regel passt. Formale Grammatiken schreiben k​eine Reihenfolge vor. Alle n​ur aus Terminalsymbolen bestehenden Wörter, d​ie sich a​us dem Startsymbol ableiten lassen, zählen z​ur von d​er Grammatik beschriebenen Sprache.

Definition

Eine formale Grammatik wird dargestellt durch das 4-Tupel ${\displaystyle G=(V,T,P,S)}$, worin:[1]

• ${\displaystyle V}$, einer endlichen Menge von Symbolen, welche als Symbolmenge oder Vokabular bezeichnet wird,
• ${\displaystyle T\subset V}$, einer Teilmenge von ${\displaystyle V}$, auch Alphabet genannt und deren Elemente Terminalsymbole heißen,
• ${\displaystyle P\subset \left(V^{*}\setminus T^{*}\right)\times V^{*}}$, einer endlichen Menge von Produktionsregeln, sowie
• ${\displaystyle S\in V\setminus T}$, dem Startsymbol.

Hierbei bezeichnet ${\displaystyle X^{*}}$ die Kleenesche Hülle einer Menge ${\displaystyle X}$ von Zeichen (oder auch Wörtern).

Die Menge ${\displaystyle N=V\setminus T}$ ist die Menge von Nichtterminalsymbolen (auch Nonterminale oder Metasymbole genannt), insbesondere gehört das Startzeichen zu ihr. Das Wort auf der linken Seite der Regelpaare darf nicht ausschließlich aus Terminalzeichen bestehen, was man auch durch eine Konkatenation ausdrücken kann:

${\displaystyle \left(V^{*}\setminus T^{*}\right)=V^{*}NV^{*}}$.

Es macht wenig Sinn, wenn das Wort auf der rechten Seite das Startsymbol enthält. Manche Autoren berücksichtigen das, indem sie die zugehörige Menge entsprechend beschränken, d. h. ${\displaystyle V^{*}}$ durch ${\displaystyle (V\setminus \{S\})^{*}}$ ersetzen.

Manche Autoren bezeichnen alternativ das Quadrupel ${\displaystyle (N,T,P,S)}$ als Grammatik ${\displaystyle G}$. Es finden sich darüber hinaus folgende abweichenden Bezeichnungen:[2]

• ${\displaystyle \Sigma }$ für die Terminalzeichen, hier ${\displaystyle T}$,
• ${\displaystyle \Sigma }$ für das gesamte Vokabular (Symbolmenge) aller Symbole, hier ${\displaystyle V}$,
• ${\displaystyle V}$ für die Nichtterminalzeichen (Variablen), hier ${\displaystyle N}$,[3]
• ${\displaystyle \lambda }$ für das leere Wort, hier ${\displaystyle \epsilon }$.[3]

Die von einer Grammatik beschriebene Sprache

Eine Regel ${\displaystyle R\rightarrow Q\in P}$ einer gegebenen Grammatik ${\displaystyle G}$ besagt, dass in einem Wort ${\displaystyle w\in V^{\ast }}$ mit R als Infix, R durch Q ersetzt werden kann, so dass ein neues Wort ${\displaystyle w^{\prime }}$ mit ${\displaystyle Q}$ als Infix entsteht. Man spricht hierbei auch davon, dass ${\displaystyle w}$ in ${\displaystyle w^{\prime }}$ mit der Grammatik ${\displaystyle G}$ bzw. durch die Regel ${\displaystyle R\rightarrow Q}$ übergeht, oder auch, dass ${\displaystyle w^{\prime }}$ aus ${\displaystyle w}$ abgeleitet wurde. Dies kann durch ${\displaystyle w\rightsquigarrow _{R\rightarrow Q}w^{\prime }}$ notiert werden (häufig auch ${\displaystyle \Rightarrow }$ anstatt ${\displaystyle \rightsquigarrow }$). Soll nur ausgedrückt werden, dass in der Grammatik ${\displaystyle G}$ das Wort ${\displaystyle w^{\prime }}$ aus ${\displaystyle w}$ entstehen kann, ohne eine Regel zu benennen, schreibt man stattdessen ${\displaystyle w\rightsquigarrow _{G}w^{\prime }}$ (ist die Grammatik aus dem Kontext offensichtlich, auch einfach ${\displaystyle w\rightsquigarrow w^{\prime }}$). Demnach ist ein solcher Übergang von ${\displaystyle w}$ in ${\displaystyle w^{\prime }}$ eine Transitionsrelation, die eine natürliche Erweiterung von ${\displaystyle P}$ auf alle möglichen ${\displaystyle V^{*}}$-Kontexte darstellt, nämlich:

${\displaystyle \rightsquigarrow \;:=\;\{(u\circ R\circ v,u\circ Q\circ v)|(R,Q)\in P,u,v\in V^{*}\}}$,

wobei hier ${\displaystyle \circ }$ die Konkatenation von Wörtern bezeichnet.

Gibt es nun eine Folge von Wörtern ${\displaystyle w_{0},w_{1},\ldots ,w_{n}\in V^{\ast }}$, bei der gilt, dass für jede natürliche Zahl ${\displaystyle i}$ mit ${\displaystyle 0\leq i<n}$ das Wort ${\displaystyle w_{i}}$ in ${\displaystyle w_{i+1}}$ übergeht (${\displaystyle w_{i}\rightsquigarrow _{G}w_{i+1}}$), so ist ${\displaystyle w_{n}}$ in ${\displaystyle n}$ Schritten aus ${\displaystyle w_{0}}$ ableitbar, was durch ${\displaystyle w_{0}\rightsquigarrow _{G}^{n}w_{n}}$ dargestellt wird. Eine solche Wortfolge ${\displaystyle w_{0},w_{1},\ldots ,w_{n}}$ wird Ableitung oder Rechnung von ${\displaystyle w_{0}}$ in ${\displaystyle w_{n}}$ der Länge ${\displaystyle n}$ genannt. Weiterhin heißt ${\displaystyle w}$ in ${\displaystyle w^{\prime }}$ ableitbar, wenn es mindestens ein ${\displaystyle n\in \mathbb {N} _{0}}$ gibt, so dass ${\displaystyle w^{\prime }}$ in ${\displaystyle n}$ Schritten aus ${\displaystyle w}$ ableitbar ist. Wenn ${\displaystyle w}$ in ${\displaystyle w^{\prime }}$ ableitbar ist, so wird dies durch die Schreibweise ${\displaystyle w\rightsquigarrow _{G}^{\ast }w^{\prime }}$ dargestellt. Dabei wird zusätzlich definiert, dass für jedes Wort ${\displaystyle w\in V^{\ast }}$ gilt, dass ${\displaystyle w\rightsquigarrow _{G}^{\ast }w}$ ist, so dass die Relation ${\displaystyle \rightsquigarrow _{G}^{\ast }}$ die reflexiv-transitive Hülle der Relation ${\displaystyle \rightsquigarrow _{G}}$ ist.

Nun ist die von der Grammatik ${\displaystyle G}$ erzeugte formale Sprache ${\displaystyle L(G)}$ diejenige Sprache, die aus allen Wörtern besteht, die zum einen nur aus Terminalsymbolen bestehen und die zum anderen vom Startsymbol mit einer endlichen Anzahl von Schritten abgeleitet werden können:

${\displaystyle L\left(G\right):=\left\{w\in T^{*}|S\rightsquigarrow _{G}^{*}w\right\}}$

Dabei ist es egal, in welcher Reihenfolge die Produktionsregeln auf die abgeleiteten Wörter angewandt werden, oder ob es mehrere Möglichkeiten gibt, um ein Wort ${\displaystyle w}$ aus ${\displaystyle S}$ abzuleiten. Zwei Grammatiken ${\displaystyle G_{1}}$ und ${\displaystyle G_{2}}$ sind genau dann äquivalent, wenn die durch ${\displaystyle G_{1}}$ und ${\displaystyle G_{2}}$ erzeugten Sprachen gleich sind:

${\displaystyle G_{1}\mathrm {\ ist\ {\ddot {a}}quivalent\ zu\ } G_{2}:\Longleftrightarrow L(G_{1})=L(G_{2})}$

Wenn a​lle Terminalzeichen i​n den Wörten d​er formalen Sprachen vorkommen, d​ann müssen d​ie Terminalzeichen übereinstimmen. Die Nichtterminalzeichen s​ind dagegen völlig frei.

Beispiele

${\displaystyle G_{1}}$ sei eine Grammatik mit den Terminalsymbolen ${\displaystyle \{a,b\}}$, den Nichtterminalsymbolen ${\displaystyle \{S,A,B\}}$, dem Startsymbol ${\displaystyle S}$ und mit den Regeln

${\displaystyle {\begin{matrix}S&\to &ABS&\,(1)\\S&\to &\varepsilon &\,(2)\\BA&\to &AB&\,(3)\\BS&\to &b&\,(4)\\Bb&\to &bb&\,(5)\\Ab&\to &ab&\,(6)\\Aa&\to &aa&\,(7)\end{matrix}}}$

Dabei ist ${\displaystyle \varepsilon }$ das leere Wort, welches ein Wort der Länge 0 ist. Diese Grammatik ${\displaystyle G_{1}}$ definiert die Sprache aller Wörter der Form ${\displaystyle a^{n}b^{n}}$ mit ${\displaystyle n\in \mathbb {N} _{0}}$. So sind auf Grund der folgenden Ableitungen die Wörter ${\displaystyle \varepsilon }$, ${\displaystyle ab}$ und ${\displaystyle aabb}$ Elemente der durch ${\displaystyle G_{1}}$ beschriebenen Sprache:

• ${\displaystyle S\rightsquigarrow \varepsilon }$, mittels Regel (2),
• ${\displaystyle S\rightsquigarrow ABS\rightsquigarrow Ab\rightsquigarrow ab}$, mittels der Regeln (1), (4) und (6),
• ${\displaystyle S\rightsquigarrow ABS\rightsquigarrow ABABS\rightsquigarrow ABAb\rightsquigarrow AABb\rightsquigarrow AAbb\rightsquigarrow Aabb\rightsquigarrow aabb}$, mittels der Regeln (1),(1),(4),(3), (5), (6) und (7).

Es gibt aber noch andere Möglichkeiten, um das Wort ${\displaystyle aabb}$ aus ${\displaystyle S}$ abzuleiten.

Eine weitere Grammatik, die dieselbe Sprache beschreibt, ist die kontextfreie Grammatik ${\displaystyle G_{2}}$ mit den Regeln: ${\displaystyle {\begin{matrix}S&\to &aSb\ |\ \varepsilon \end{matrix}}}$

Jede rekursiv aufzählbare Sprache wird von mehreren (und zwar abzählbar unendlich vielen) Grammatiken erzeugt. Allerdings gibt es auch Sprachen, die sich von keiner Grammatik erzeugen lassen.

Klassen von Grammatiken

Grammatiken werden Klassen zugeordnet, d​ie sich d​urch Gemeinsamkeiten auszeichnen. Die bekannteste Klassifikation beschrieben Noam Chomsky u​nd Marcel Schützenberger m​it der Chomsky-Hierarchie.

Chomsky-Hierarchie

Die Chomsky-Hierarchie t​eilt die Grammatiken n​ach der Art d​er Produktionsregeln i​n Klassen v​om Typ 0 b​is Typ 3 ein:

• Typ-0-Grammatiken: Phrasenstrukturgrammatiken sind uneingeschränkte formale Grammatiken.
• Typ-1-Grammatiken: Kontextsensitive Grammatiken dürfen nur aus Regeln bestehen, in denen genau ein Nichtterminalsymbol durch eine Zeichenfolge ersetzt wird. Dieses Symbol darf auf der linken Seite der Regel auch von weiteren Symbolen umgeben sein, die einen Kontext angeben, innerhalb dessen die Ersetzung stattfinden muss.
• Typ-2-Grammatiken: In kontextfreien Grammatiken darf dagegen auf den linken Seiten der Regeln jeweils nur genau ein Nichtterminalsymbol stehen. Das Symbol kann dann unabhängig vom Kontext ersetzt werden.
• Typ-3-Grammatiken: Bei regulären Grammatiken enthalten die linken Seiten der Regeln ebenfalls nur genau ein Nichtterminalsymbol. Bei linksregulären Grammatiken darf die rechte Seite der Regel aus höchstens einem Nichtterminalsymbol bestehen, dem höchstens ein Terminalsymbol folgt (Bsp.: ${\displaystyle X\to Ya}$). Bei rechtsregulären Grammatiken darf hingegen die rechte Seite aus höchstens einem Terminalsymbol bestehen, dem höchstens ein Nichtterminal folgt (Bsp.: ${\displaystyle X\to aY}$).

Die zugehörigen Sprachklassen s​ind abnehmend umfangreich. Es besteht folgende e​chte Inklusionsbeziehung:

Für die Sprachklassen ${\displaystyle L_{n}}$ von Typ ${\displaystyle n}$ mit ${\displaystyle n\in \{0,1,2,3\}}$ gilt: ${\displaystyle L_{3}\subset L_{2}\subset L_{1}\subset L_{0}}$.

Weitere Sprachklassen

Von d​er Chomsky-Hierarchie abgesehen h​aben sich weitere Klassen a​n Grammatiken etabliert:

• Monotone Grammatiken beschreiben die gleiche Sprachklasse wie die kontextsensitiven Grammatiken. Etwas strenger sind die wachsend kontextsensitiven Grammatiken, die eine Teilklasse der kontextsensitiven Sprachklasse beschreiben.
• Deterministisch kontextfreie Grammatiken beschreiben die deterministisch kontextfreien Sprachen. Sie werden auch durch die LR(k)-Grammatiken beschrieben, welche für den Compilerbau von Bedeutung sind. Andere im Compilerbau bekannte Grammatiken sind LL(k)-Grammatiken und LF(k)-Grammatiken.

Siehe auch

• Graphgrammatik
• Backus-Naur-Form und Erweiterte Backus-Naur-Form
• Syntaxtheorie zu (formalen) Grammatiken in der Linguistik
• Kommunizierendes Grammatik-System

Literatur

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

Weblinks

• Website zum Thema Grammatik

Einzelnachweise

1. Peter Bachmann: Grundlagen der Theoretischen Informatik. Cottbus 2001, S. 47 (PDF [abgerufen am 12. Februar 2011] Vorlesungsskript).
2. Während die Bedeutung von ${\displaystyle T,N}$ und ${\displaystyle \epsilon }$ bzw. ${\displaystyle \lambda }$ im gegebenen Fall jeweils klar ist, muss man sich bei ${\displaystyle V}$ (ebenso wie dem häufig benutzten ${\displaystyle \Sigma }$) durch Überprüfung des Kontexts klarmachen, was gemeint ist; wobei man sich auf das Grammatik-Quadrupels nicht verlassen kann.
3. Klaus Reinhardt: Prioritatszahlerautomaten und die Synchronisation von Halbspursprachen (Memento des Originals vom 17. Januar 2018 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis., Fakultät Informatik der Universität Stuttgart; Doktorarbeit 1994. Das Grammatik-Quadrupel ist hier wörtlich mit ${\displaystyle (V,\Sigma ,P,S)}$ angegeben, damit ist in der hier gewählten Bezeichnungsweise ${\displaystyle (N,T,P,S)}$ gemeint.