Kontextfreie Grammatik

Grundidee und Definition

Eine kontextfreie Grammatik (CFG) ist eine formale Grammatik der Theorie der formalen Sprachen. Sie enthält ausschließlich Ersetzungsregeln der Form V → w. Dabei ist V genau ein Nichtterminalsymbol und w eine beliebig lange Folge aus Nichtterminal- und/oder Terminalsymbolen. Die Regel kann angewendet werden, sobald V vorkommt; die Zeichen links oder rechts davon spielen keine Rolle. Daher heißen die Regeln kontextfrei. Kontextfreie Grammatiken sind identisch mit den Typ-2-Grammatiken der Chomsky-Hierarchie.

Formal ist eine Grammatik G ein 4-Tupel (V,T,P,S):

• V ist eine endliche Menge, das Vokabular.
• T ⊆ V ist die Menge der Terminalsymbole, also der endgültigen Zeichen.
• N := V \ T ist die Menge der Nichtterminale, auch Variablen genannt.
• P ⊆ N × V* ist die endliche Menge der Produktionsregeln.
• S ∈ N ist das Startsymbol.

N und T sind disjunkte Alphabete. V* bezeichnet die Kleenesche Hülle, also die Menge aller endlichen Zeichenketten über V einschließlich des leeren Wortes ε. Alternativ wird eine Grammatik als (N,T,P,S) angegeben, wobei V := N ∪ T gilt. Eine Regel wird meist als α → β geschrieben; wegen der Definition besteht α immer aus genau einem Nichtterminalsymbol.

Erzeugte Sprache und Ableitungen

Produktionsregeln ersetzen ein vorkommendes Teilwort. Wenn R → Q eine Regel ist und ein Wort die Form uRv besitzt, darf daraus uQv entstehen. Die Ein-Schritt-Ableitungsrelation lautet:

↝G := {(uRv,uQv) | u,v ∈ V* und (R,Q) ∈ P}.

Mehrfache Regelanwendungen werden mit ↝Gⁿ für genau n Schritte und mit ↝G* für eine beliebige endliche Anzahl von Schritten bezeichnet. Die von G erzeugte Sprache ist

L(G) = {w | w ∈ T* und S ↝G* w}.

Man beginnt beim Startsymbol S und ersetzt Nichtterminale so lange, bis nur noch Terminale vorhanden sind. Deshalb gilt L(G) ⊆ T*. Kontextfreie Grammatiken erzeugen genau die kontextfreien Sprachen: Jede Typ-2-Grammatik erzeugt eine solche Sprache, und zu jeder kontextfreien Sprache gibt es eine entsprechende Typ-2-Grammatik.

Kontextfreie Sprachen sind genau die Sprachen, die von nichtdeterministischen Kellerautomaten akzeptiert werden. Falls eine Sprache auch von einem deterministischen Kellerautomaten akzeptiert wird, heißt sie deterministisch kontextfrei. Diese echte Teilmenge bildet die theoretische Grundlage für die Syntax der meisten Programmiersprachen.

Das leere Wort ε kann zur Sprache gehören, beispielsweise durch S → ε. Manche Sätze über kontextfreie Grammatiken schließen jedoch aus, dass ε erzeugt wird. Das ist etwa für die Umwandlung in die Greibach-Normalform erforderlich.

Normalformen und wichtige Eigenschaften

Normalformen schränken die Gestalt der Regeln ein und erleichtern die Verarbeitung einer Grammatik.

In der Chomsky-Normalform (CNF) steht auf der rechten Seite einer Nichtterminal-Produktion entweder genau ein Terminalsymbol oder genau zwei Nichtterminale. Wenn das Startsymbol links steht, darf die rechte Seite zusätzlich das leere Wort sein. Jede kontextfreie Grammatik kann durch einen Algorithmus in die CNF überführt werden.

In der Greibach-Normalform (GNF) erzeugt die Grammatik nicht das leere Wort. Die rechten Seiten beginnen mit höchstens einem Terminalsymbol und enthalten danach nur Nichtterminale. Jede kontextfreie Grammatik, die ε nicht erzeugt, kann algorithmisch in GNF überführt werden.

Das Wortproblem ist entscheidbar: Für ein Wort w kann festgestellt werden, ob w ∈ L(G) gilt. Dabei kann auch ein Ableitungsbaum, ein Parse-Tree, erzeugt werden. Ein Programm, das einen solchen Baum erzeugt, heißt Parser. Für jede kontextfreie Grammatik kann automatisch ein Parser generiert werden, beispielsweise mit dem CYK-Algorithmus. Die Worst-Case-Laufzeit für eine beliebige kontextfreie Grammatik liegt bei O(n³); für bestimmte Teilklassen sind Parser mit O(n) möglich. Ein solcher linearer Parser wird etwa beim Parsen des Quelltexts einer Programmiersprache durch einen Compiler verwendet.

Eine Grammatik ist mehrdeutig, wenn ein Wort ihrer Sprache auf mehrere verschiedene Arten erzeugt werden kann und somit mehrere Ableitungsbäume besitzt. Für das reine Wortproblem ist dies nicht unbedingt problematisch. Wenn die verschiedenen Bäume aber unterschiedliche Bedeutungen haben, kann ein Wort mehrere Bedeutungen erhalten. Für Compiler ist daher eine eindeutige Interpretation wichtig.

Nicht entscheidbar sind dagegen: die Frage, ob eine beliebige kontextfreie Grammatik mehrdeutig ist, die Äquivalenz zweier Grammatiken L(G₁) = L(G₂), sowie die Teilmengenfrage L(G₁) ⊆ L(G₂). Für bestimmte Teilklassen existieren jedoch Mehrdeutigkeitstests. Die Vereinigung zweier kontextfreier Sprachen ist wieder kontextfrei. Unter disjunkten Nichtterminalmengen kann eine neue Grammatik ein zusätzliches Startsymbol S mit den Regeln S → S₁ und S → S₂ verwenden. Ob der Schnitt zweier kontextfreier Sprachen wieder kontextfrei ist, ist nicht entscheidbar; das Komplement einer kontextfreien Grammatik ist im Allgemeinen nicht kontextfrei.

Typische Beispiele

Ein Beispiel ist die Grammatik mit T = {x,y,z}, N = {S,A,B} und den Produktionen S → A, A → xAy, A → xBy und B → z. Das Wort w₁ = xxzyy kann abgeleitet werden; sein Ableitungsbaum in Term-Schreibweise ist t(w₁) = S(A(x,A(x,B(z),y),y)). Daher gilt w₁ ∈ L(G). Das Wort w₂ = z gehört dagegen nicht zur Sprache, weil B nicht das Startsymbol ist und die von S erzeugten Wörter von x und y eingeschlossen werden: w₂ ∉ L(G). Die Grammatik G ist nicht mehrdeutig.

Die Grammatik G({S,a,b},{a,b},P,S) mit den Regeln S → ε | a | b | aSa | bSb erzeugt die Sprache aller Palindrome über dem Alphabet {a,b}.

Ein Beispiel für Mehrdeutigkeit ist G₂ mit N₂ = {S₂,A}, T₂ = {x,y} und den Regeln S₂ → A, A → AA, A → xAy und A → ε. Für w₃ = xy gibt es unter anderem die Ableitungen S₂(A(x,A(ε),y)), S₂(A(A(ε),A(x,A(ε),y))) und S₂(A(A(x,A(ε),y),A(ε))). Deshalb ist G₂ mehrdeutig.

Auch die Pre-order-Darstellung von Binärbäumen lässt sich durch eine kontextfreie Grammatik beschreiben. Mit S → I(S)(S) | I | ε, I → LE, E → LE | DE | ε, Regeln für die Buchstaben A bis Z in L und für die Ziffern 0 bis 9 in D entsteht beispielsweise die Zeichenkette F(B(A)(D(C)(E)))(G()(I(H)())).

Stochastische Erweiterung

Eine Erweiterung sind stochastische beziehungsweise probabilistische kontextfreie Grammatiken (SCFG oder PCFG). Jeder Produktionsregel wird eine Auftrittswahrscheinlichkeit zugeordnet:

ρ : P → ℝ≥0.

Für jedes Nichtterminal α′ müssen die Wahrscheinlichkeiten aller Regeln mit diesem Nichtterminal auf der linken Seite zusammen 1 ergeben: Σ ρ(α′,β) = 1, wobei über alle (α′,β) ∈ P summiert wird. Daraus entsteht eine Wahrscheinlichkeitsverteilung über den von der Grammatik erzeugten Wörtern.

SCFGs können in einer syntaktisch mehrdeutigen Grammatik den wahrscheinlichsten Parse für ein Eingabewort bestimmen oder Ableitungsbäume entsprechend den Regelwahrscheinlichkeiten stochastisch erzeugen. Ihre erzeugte Sprache ist wie bei einer gewöhnlichen CFG definiert. Anwendungsgebiete sind unter anderem Bioinformatik und Computerlinguistik.