Formale Grammatik

Formale Grammatiken sind mathematische Modelle von Grammatiken, die zur eindeutigen Erzeugung und Beschreibung formaler Sprachen dienen. Sie werden in der theoretischen Informatik, insbesondere in der Berechenbarkeitstheorie, und im Compilerbau zum einen angewendet, um eindeutig festzulegen, ob ein Wort Element einer Sprache ist und zum anderen, um Eigenschaften dieser formalen Sprachen zu untersuchen bzw. zu beweisen. Formale Grammatiken werden mithilfe von Semi-Thue-Systemen angegeben in der Chomsky-Hierarchie klassifiziert.

Beschreibung 
Mit einer formalen Grammatik lassen sich ausgehend von einem Startsymbol  (auch Startvariable genannt) Produktionsregeln aus einer Regelmenge  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  einer Grammatik, bestehend aus der disjunkten Vereinigung eines Alphabets  von Terminalsymbolen mit einer Menge von Nichtterminalsymbolen , 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 , die auch  geschrieben werden. Man wendet sie auf eine Zeichenfolge  an, indem ein Vorkommen der Zeichenfolge  in  durch  ersetzt wird. Auf der linken Seite der Regel muss immer mindestens ein Nichtterminalsymbol stehen. Eine Menge von Regeln mit gleicher linker Seite, also , wird abkürzend auch als  geschrieben.

Zum Beispiel kann man mit der Regelmenge  die Zeichenfolge  entweder zu  oder zu  ableiten.

Ebenso wie auf eine gegebene Zeichenfolge mehrere Regeln gleichzeitig anwendbar sein können, muss es nicht immer nur eine Stelle in der Zeichenfolge geben, auf die eine Regel passt. Formale Grammatiken schreiben keine Reihenfolge vor. Alle nur aus Terminalsymbolen bestehenden Wörter, die sich aus dem Startsymbol ableiten lassen, zählen zur von der Grammatik beschriebenen Sprache.

Definition 
Eine formale Grammatik wird dargestellt durch das 4-Tupel , worin:
 , einer endlichen Menge von Symbolen, welche als Symbolmenge oder Vokabular bezeichnet wird,
 , einer Teilmenge von , auch Alphabet genannt und deren Elemente Terminalsymbole heißen,
 , einer endlichen Menge von Produktionsregeln, sowie
 , dem Startsymbol.

Das 4-Tupel wird je nach Konvention auch so definiert, dass  der Menge der Nichtterminalsymbolen entspricht, sodass  ist.

Hierbei bezeichnet  die Kleenesche Hülle einer Menge  von Zeichen (oder auch Wörtern).

Die Menge  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:
.

Es ergibt 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.  durch  ersetzen.

Manche Autoren bezeichnen alternativ das Quadrupel  als Grammatik . Es finden sich darüber hinaus folgende abweichenden Bezeichnungen:
  für die Terminalzeichen, hier ,
  für das gesamte Vokabular (Symbolmenge) aller Symbole, hier ,
  für die Nichtterminalzeichen (Variablen), hier ,
  für das leere Wort, hier .

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

,
wobei hier  die Konkatenation von Wörtern bezeichnet.

Gibt es nun eine Folge von Wörtern , bei der gilt, dass für jede natürliche Zahl  mit  das Wort  in  übergeht (), so ist  in  Schritten aus  ableitbar, was durch  dargestellt wird. Eine solche Wortfolge  wird Ableitung oder Rechnung von  in  der Länge  genannt. Weiterhin heißt  in  ableitbar, wenn es mindestens ein  gibt, so dass  in  Schritten aus  ableitbar ist. Wenn  in  ableitbar ist, so wird dies durch die Schreibweise  dargestellt. Dabei wird zusätzlich definiert, dass für jedes Wort  gilt, dass  ist, so dass die Relation  die reflexiv-transitive Hülle der Relation  ist.

Nun ist die von der Grammatik  erzeugte formale Sprache  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:

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  aus  abzuleiten. Zwei Grammatiken  und  sind genau dann äquivalent, wenn die durch  und  erzeugten Sprachen gleich sind:

Wenn alle Terminalzeichen in den Wörten der formalen Sprachen vorkommen, dann müssen die Terminalzeichen übereinstimmen. Die Nichtterminalzeichen sind dagegen völlig frei.

Beispiele 
 sei eine Grammatik mit den Terminalsymbolen , den Nichtterminalsymbolen , dem Startsymbol  und mit den Regeln

Dabei ist  das leere Wort, welches ein Wort der Länge 0 ist. Diese Grammatik  definiert die Sprache aller Wörter der Form  mit . So sind auf Grund der folgenden Ableitungen die Wörter ,  und  Elemente der durch  beschriebenen Sprache:
 , mittels Regel (2),
 , mittels der Regeln (1), (4) und (6),
 , mittels der Regeln (1),(1),(4),(3), (5), (6) und (7).

Es gibt aber noch andere Möglichkeiten, um das Wort  aus  abzuleiten.

Eine weitere Grammatik, die dieselbe Sprache beschreibt, ist die kontextfreie Grammatik  mit den Regeln:

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, die sich durch Gemeinsamkeiten auszeichnen. Die bekannteste Klassifikation beschrieben Noam Chomsky und Marcel Schützenberger mit der Chomsky-Hierarchie.

Chomsky-Hierarchie 
Die Chomsky-Hierarchie teilt die Grammatiken nach der Art der Produktionsregeln in Klassen vom Typ 0 bis 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.: ). Bei rechtsregulären Grammatiken darf hingegen die rechte Seite aus höchstens einem Terminalsymbol bestehen, dem höchstens ein Nichtterminal folgt (Bsp.: ).

Die zugehörigen Sprachklassen sind abnehmend umfangreich. Es besteht folgende echte Inklusionsbeziehung:

Für die Sprachklassen  von Typ  mit  gilt: .

Weitere Sprachklassen 
Von der Chomsky-Hierarchie abgesehen haben sich weitere Klassen an 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

Weblinks 
 Website zum Thema Grammatik

Einzelnachweise 

Theorie formaler Sprachen
Compilerbau