Formale Grammatik

Grundidee und Bedeutung

Eine formale Grammatik ist ein mathematisches Modell zur eindeutigen Erzeugung und Beschreibung einer formalen Sprache. Sie wird vor allem in der theoretischen Informatik, der Berechenbarkeitstheorie und im Compilerbau verwendet. Mit ihr lässt sich festlegen, ob ein Wort zu einer Sprache gehört; außerdem können Eigenschaften formaler Sprachen untersucht und bewiesen werden.

Ausgangspunkt ist ein Startsymbol S. Auf dieses und auf die daraus entstehenden Zeichenfolgen werden Produktionsregeln aus einer Regelmenge P angewandt. Eine solche schrittweise Ersetzung heißt Ableitung. Die Reihenfolge der anwendbaren Regeln ist grundsätzlich nicht vorgeschrieben.

Das Vokabular V besteht aus Terminalsymbolen und Nichtterminalsymbolen. Terminalsymbole bilden das Alphabet T und sind die Zeichen, aus denen die fertigen Wörter bestehen. Nichtterminalsymbole, zusammengefasst in N, dienen als Hilfszeichen während der Ableitung und können weiter ersetzt werden. Das Startsymbol muss ein Nichtterminalsymbol sein. Alle nur aus Terminalsymbolen bestehenden Wörter, die sich aus S ableiten lassen, bilden die von der Grammatik erzeugte Sprache.

Formale Definition und Produktionsregeln

Eine formale Grammatik wird als 4-Tupel G = (V, T, P, S) dargestellt. Dabei gilt:

• V ist eine endliche Symbolmenge, auch Vokabular genannt. • T ⊂ V ist das Alphabet; seine Elemente heißen Terminalsymbole. • P ⊂ (V* ∖ T*) × V* ist eine endliche Menge von Produktionsregeln. • S ∈ V ∖ T ist das Startsymbol.

X* bezeichnet die Kleenesche Hülle einer Menge X, also die Menge aller endlichen Wörter über X einschließlich des leeren Wortes ε. Die Menge der Nichtterminalsymbole lautet N = V ∖ T. Da die linke Seite einer Regel nicht ausschließlich aus Terminalsymbolen bestehen darf, gilt (V* ∖ T*) = VNV.

Eine Produktionsregel ist ein geordnetes Paar (α, β), geschrieben als α → β. Bei ihrer Anwendung wird ein Vorkommen von α in einem Wort durch β ersetzt. Auf der linken Seite muss mindestens ein Nichtterminalsymbol vorkommen. Mehrere Regeln mit derselben linken Seite können verkürzt als α → β₁ | … | βₙ notiert werden. Beispielsweise erlaubt X → + | −, die Zeichenfolge 1X2 entweder zu 1+2 oder zu 1−2 abzuleiten.

Je nach Konvention werden die Bezeichnungen anders verwendet. Manche Autoren schreiben G = (N, T, P, S) und behandeln N und T als disjunkte Mengen. Für Terminalzeichen findet sich auch Σ, während V manchmal nur die Nichtterminalsymbole bezeichnet. Das leere Wort ε wird teilweise λ genannt. Manche Definitionen schließen außerdem S auf den rechten Seiten der Regeln aus, indem sie dort statt V* die Menge (V ∖ {S})* verwenden.

Ableitung und erzeugte Sprache

Eine Regel R → Q bedeutet: Kommt R als zusammenhängender Teil, also als Infix, in einem Wort w ∈ V* vor, darf dieses Vorkommen durch Q ersetzt werden. Das entstehende Wort w′ wurde dann aus w abgeleitet. Dies wird als w ↝₍R→Q₎ w′ oder, ohne Angabe der Regel, als w ↝G w′ geschrieben; häufig steht dafür auch das Zeichen ⇒.

Die Übergangsrelation berücksichtigt jeden möglichen Kontext u und v: ↝ := {(u ∘ R ∘ v, u ∘ Q ∘ v) | (R,Q) ∈ P, u,v ∈ V*}. Dabei bezeichnet ∘ die Konkatenation, also das Aneinanderfügen von Wörtern.

Eine Folge w₀, w₁, …, wₙ, in der jeweils wᵢ ↝G wᵢ₊₁ gilt, heißt Ableitung oder Rechnung der Länge n. Die Schreibweise w₀ ↝Gⁿ wₙ bedeutet, dass wₙ in genau n Schritten aus w₀ entsteht. w ↝G* w′ besagt, dass dies in einer beliebigen endlichen Zahl n ∈ ℕ₀ von Schritten möglich ist. Auch null Schritte sind zugelassen, sodass stets w ↝G* w gilt. ↝G* ist damit die reflexiv-transitive Hülle von ↝G.

Die von G erzeugte formale Sprache ist genau L(G) := {w ∈ T* | S ↝G* w}. Sie enthält also alle und nur die vollständig aus Terminalsymbolen bestehenden Wörter, die in endlich vielen Schritten aus S hervorgehen. Die Reihenfolge der Regelanwendungen und die Zahl verschiedener Ableitungswege sind für die Zugehörigkeit unerheblich.

Zwei Grammatiken G₁ und G₂ heißen genau dann äquivalent, wenn sie dieselbe Sprache erzeugen: G₁ ist äquivalent zu G₂ ⇔ L(G₁) = L(G₂). Die Nichtterminalsymbole äquivalenter Grammatiken können völlig verschieden sein. Wenn alle Terminalzeichen in den Wörtern der Sprachen vorkommen, müssen dagegen die Terminalzeichen übereinstimmen.

Typisches Beispiel

Die Grammatik G₁ besitzt die Terminalzeichen {a,b}, die Nichtterminalzeichen {S,A,B}, das Startsymbol S und unter anderem die Regeln S → ABS, S → ε, BA → AB, BS → b, Bb → bb, Ab → ab und Aa → aa. Dabei ist ε das leere Wort der Länge 0.

G₁ erzeugt genau die Sprache aller Wörter der Form aⁿbⁿ mit n ∈ ℕ₀: Auf n Zeichen a folgen ebenso viele Zeichen b. Beispiele für Ableitungen sind:

• S ↝ ε. • S ↝ ABS ↝ Ab ↝ ab. • S ↝ ABS ↝ ABABS ↝ ABAb ↝ AABb ↝ AAbb ↝ Aabb ↝ aabb.

Für ein Wort wie aabb kann es mehrere gültige Ableitungen geben. Dieselbe Sprache wird wesentlich kürzer durch die kontextfreie Grammatik G₂ mit S → aSb | ε beschrieben. Dies zeigt, dass verschiedene und unterschiedlich aufgebaute Grammatiken äquivalent sein können. Jede rekursiv aufzählbare Sprache wird sogar von abzählbar unendlich vielen Grammatiken erzeugt. Es gibt jedoch auch Sprachen, die von keiner Grammatik erzeugt werden können.

Chomsky-Hierarchie

Die bekannteste Einteilung formaler Grammatiken ist die von Noam Chomsky und Marcel Schützenberger beschriebene Chomsky-Hierarchie. Sie unterscheidet nach der erlaubten Form der Produktionsregeln vier Typen:

• Typ 0: Phrasenstrukturgrammatiken sind uneingeschränkte formale Grammatiken. • Typ 1: Bei kontextsensitiven Grammatiken wird genau ein Nichtterminalsymbol durch eine Zeichenfolge ersetzt. Auf der linken Seite darf es von weiteren Symbolen umgeben sein, die den notwendigen Kontext festlegen. • Typ 2: Bei kontextfreien Grammatiken steht links jeweils genau ein Nichtterminalsymbol. Es kann unabhängig von seinem Kontext ersetzt werden. • Typ 3: Auch bei regulären Grammatiken steht links genau ein Nichtterminalsymbol. Bei linksregulären Grammatiken besteht die rechte Seite aus höchstens einem Nichtterminalsymbol, auf das höchstens ein Terminalsymbol folgt, etwa X → Ya. Bei rechtsregulären Grammatiken steht höchstens ein Terminalsymbol vor höchstens einem Nichtterminalsymbol, etwa X → aY.

Die zugehörigen Sprachklassen Lₙ sind unterschiedlich umfangreich und echt ineinander enthalten: L₃ ⊂ L₂ ⊂ L₁ ⊂ L₀. Damit ist jede Typ-3-Sprache auch vom Typ 2, jede Typ-2-Sprache auch vom Typ 1 und jede Typ-1-Sprache auch vom Typ 0; die Umkehrungen gelten jeweils nicht allgemein.

Weitere Grammatikklassen

Neben der Chomsky-Hierarchie gibt es weitere wichtige Klassen. Monotone Grammatiken beschreiben dieselbe Sprachklasse wie kontextsensitive Grammatiken. Wachsend kontextsensitive Grammatiken sind etwas strenger und beschreiben nur eine Teilklasse der kontextsensitiven Sprachklasse.

Deterministisch kontextfreie Grammatiken erzeugen die deterministisch kontextfreien Sprachen. Diese werden auch durch LR(k)-Grammatiken beschrieben, die im Compilerbau wichtig sind. Weitere dort bekannte Klassen sind LL(k)-Grammatiken und LF(k)-Grammatiken.