Kontextfreie Grammatik

Kontextfreie Grammatik

In der Theorie der formalen Sprachen ist eine kontextfreie Grammatik eine Grammatik, die nur solche Ersetzungsregeln enthält, bei denen immer genau ein Nichtterminal auf eine beliebig lange Folge von Nichtterminalen und Terminale abgeleitet wird. Dabei steht das zu ersetzende Nichtterminal allein (daher „kontextfrei“) auf der linken Seite der Ersetzungsregel. Die kontextfreien Grammatiken sind identisch mit den Typ-2-Grammatiken der Chomsky-Hierarchie.

Inhaltsverzeichnis

Definition

Eine kontextfreie Grammatik G ist ein 4-Tupel (N,T,P,S) mit folgenden Eigenschaften:

  • S \in N
  • N und T sind endliche, disjunkte Mengen
  • P ist eine endliche Teilmenge von N \times (N \cup T)^*

Hierbei bezeichnet X * die Kleenesche Hülle von X.

Erläuterung

Man bezeichnet N als Menge der Nichtterminale, T als Menge der Terminale, P als Menge der Produktionen oder Regeln und S als Startsymbol. Eine Regel (\alpha, \beta) \in P wird meist in der Form \alpha \rightarrow \beta notiert.

Gemäß der Definition gilt für alle solche Regeln, dass \alpha\in N ist, also dass auf der linken Seite der Ersetzungsregel genau ein Nichtterminal steht. Es ist deshalb in einer Regel nicht von anderen Symbolen umgeben und es stehen daher immer die gleichen Regeln zur Auswahl, egal welche Symbole das Nichtterminal α in einer Zeichenfolge umgeben. Kurz gesagt ist die Auswahl der Regeln unabhängig vom Kontext von α.

Von G erzeugte Sprache

Die kontextfreien Grammatiken erzeugen genau die kontextfreien Sprachen, d. h. jede Typ-2-Grammatik erzeugt eine kontextfreie Sprache und zu jeder kontextfreien Sprache existiert eine Typ-2-Grammatik, die diese erzeugt.

Die kontextfreie Sprache L, die durch die kontextfreie Grammatik G generiert wird, ist formal definiert als L(G) mit:

L(G) = \{ w | w\in T^*, S \rightarrow_G^* w \}

Das Symbol \rightarrow_G^* steht für eine Reihe von Produktionsanwendungen unter der Grammatik G, an deren Ende das Wort w der Sprache L(G) abgeleitet werden kann. Es gilt also L(G)\subset T^*.

Die kontextfreien Sprachen sind genau die Sprachen, die von einem nichtdeterministischen Kellerautomaten akzeptiert werden. Existiert auch ein deterministischer Kellerautomat, nennt man die Sprache auch deterministisch kontextfrei. Diese echte Teilmenge der kontextfreien Sprachen bildet die theoretische Basis für die Syntax der meisten Programmiersprachen.

Kontextfreie Sprachen können das leere Wort enthalten, z. B. durch eine Produktionsregel (S \rightarrow \varepsilon). Einige Sätze über kontextfreie Grammatiken fordern allerdings zusätzlich, dass das leere Wort von ihr nicht erzeugt werden darf. So gibt es z. B. nur zu den kontextfreien Grammatiken eine äquivalente Grammatik in Greibach-Normalform, wenn das leere Wort durch sie nicht erzeugt werden kann, da in jedem Ableitungsschritt genau ein Terminal erzeugt wird.

Normalformen

Für kontextfreie Grammatiken sind verschiedene Normalformen definiert. Unter der Chomsky-Normalform (CNF) sind die rechten Seiten der Nichtterminal-Produktionen eingeschränkt, d. h. auf der rechten Seite darf entweder ein einziges Terminal-Symbol oder genau zwei Nichtterminal-Symbole stehen. Wenn das Startsymbol auf der linken Seite steht, darf die rechte Seite der Produktion allerdings auch das leere Wort sein. Durch einen Algorithmus kann jede kontextfreie Grammatik in die CNF überführt werden.

Eine kontextfreie Grammatik ist in der Greibach-Normalform (GNF), wenn sie nicht das leere Wort erzeugt und die rechten Seiten der Produktionen mit maximal einem Terminal-Symbol beginnen und sonst nur Nichtterminal-Symbole enthalten. Jede kontextfreie Grammatik, die nicht das leere Wort erzeugt, kann mit einem Algorithmus in die GNF überführt werden.

Eigenschaften

Wortproblem

Das Wortproblem für kontextfreie Sprachen, also das Problem, ob ein Wort w von einer kontextfreien Grammatik erzeugt werden kann, ist entscheidbar.[1] Auf dem Weg der Lösung des Wortproblems kann zusätzlich ein Ableitungsbaum erzeugt werden. Dieser Ableitungsbaum wird auch Parse-Tree genannt, und ein Programm, welches einen Parse-Tree erzeugt, ist ein Parser. Für jede kontextfreie Grammatik kann automatisch ein Parser generiert werden (siehe auch CYK-Algorithmus). Die Worst-Case-Laufzeitkomplexität eines Parsers für eine beliebige kontextfreie Grammatik liegt in O(n3). Für Teilklassen von kontextfreien Grammatiken können Parser erzeugt werden, deren Laufzeit in O(n) liegt. Ein typischer Anwendungsfall eines effizienten kontextfreien Parsers mit linearer Laufzeit ist das Parsen eines Programmiersprachen-Quelltexts durch einen Compiler.

Wenn ein Wort w der Sprache L (w\in L(G)) durch die Grammatik G auf mehrere verschiedene Arten erzeugt werden kann, dann ist diese Grammatik mehrdeutig. Ein Parser kann bei einer mehrdeutigen Grammatik für ein gegebenes Wort nicht nur einen, sondern mehrere Ableitungsbäume erzeugen. Mehrdeutigkeit ist nicht problematisch, wenn nur das Wortproblem gelöst werden soll. Wird aber den unterschiedlichen Ableitungsbäumen eine unterschiedliche Bedeutung zugeordnet, dann kann ein Wort bei einer mehrdeutigen Grammatik mehrere unterschiedliche Bedeutungen haben. Ein Beispiel für die Notwendigkeit einer eindeutigen kontextfreien Grammatik ist ein Compiler, der für jede gültige Eingabe deterministisch und eindeutig ausführbaren Zielcode erzeugen muss.

Mehrdeutigkeit

Das Problem, ob eine (beliebige) kontextfreie Grammatik mehrdeutig oder nicht-mehrdeutig ist, ist nicht entscheidbar.[2] Es existieren aber Testverfahren, die für bestimmte Teilklassen der kontextfreien Grammatiken Mehrdeutigkeit bzw. Nicht-Mehrdeutigkeit feststellen können.[3] Je nach Testverfahren terminiert der Mehrdeutigkeits-Test nicht oder der Test liefert zurück, dass die Mehrdeutigkeit nicht festgestellt werden kann, falls die kontextfreie Eingabe-Grammatik nicht Element einer bestimmten Teilklasse von kontextfreien Grammatiken ist.

Äquivalenz

Das Problem, ob zwei kontextfreie Grammatiken G1 und G2 die gleiche Sprache generieren (also ob L(G1) = L(G2)), ist nicht entscheidbar.[4]

Teilmenge

Das Problem, ob die durch eine kontextfreie Grammatik G1 erzeugte Sprache auch von einer kontextfreien Grammatik G2 erzeugt wird (also ob L(G_1)\subseteq L(G_2)), ist nicht entscheidbar.[5]

Vereinigung

Die Vereinigung L(G_1) \cup L(G_2) der Sprachen zweier kontextfreier Grammatiken G1 = (N1,T1,P1,S1) und G2 = (N2,T2,P2,S2) kann ebenfalls von einer kontextfreien Grammatik erzeugt werden, nämlich G_1\cup G_2 := (N_1\cup N_2,T_1\cup T_2, P_1\cup P_2\cup\{S\rightarrow S_1, S\rightarrow S_2\}, S). (Dabei wird vorausgesetzt, dass N_1\cap N_2=\emptyset und S\notin N_1\cup N_2\cup T_1\cup T_2 gelten, was aber für alle G1,G2 erreicht werden kann.)

Schnitt

Das Problem, ob der Schnitt der Sprachen zweier kontextfreier Grammatiken G1,G2 ebenfalls von einer kontextfreien Grammatik erzeugt wird, ist nicht entscheidbar. [6]

Komplement

Das Komplement einer kontextfreien Grammatik ist im Allgemeinen nicht kontextfrei.

Beispiele

Sei G = (N,T,P,S) eine kontextfreie Grammatik mit

T = {x,y,z}

N = {S,A,B}

P enthält 4 Produktionen bzw. Produktionsregeln:

\begin{align}
S & \rightarrow & A \\
A & \rightarrow & x A y \\
A & \rightarrow & x B y \\
B & \rightarrow & z
\end{align}

w1 = xxzyy kann durch die Grammatik G mit folgender Ableitung erzeugt werden:

t(w1) = S(A(x,A(x,B(z),y),y))

t(w1) ist der Ableitungsbaum in Term-Schreibweise. Die Wurzel und die inneren Knoten sind mit Nichtterminal-Symbolen und die Blätter mit Terminal-Symbolen beschriftet.

Also ist w_1\in L(G).

Das Beispiel Wort w2 mit w2 = z ist nicht Teil der Sprache L(G), da das Nichtterminal B nicht das Startsymbol ist und über das Startsymbol jedes Wort der Sprache von den Terminal-Symbolen x und y eingeschlossen sein muss. In Formelschreibweise:

w_2\notin L(G)

Grammatik G ist nicht mehrdeutig.

Mehrdeutiges Beispiel

Ein Beispiel für eine mehrdeutige Grammatik ist G2 = (N2,T2,P2,S2).

T2 = {x,y}

N2 = {S2,A}

P2 enthält folgende Produktionen:

\begin{align}
S_2 & \rightarrow & A \\
A & \rightarrow & AA \\
A & \rightarrow & x A y \\
A & \rightarrow & \varepsilon
\end{align}

Für w3 = xy existieren unter anderem die Ableitungen S(A(x,A(ε),y)), S(A(ε),A(x,A(ε),y)) und S(A(x,A(ε),y),A(ε)). Also ist G2 mehrdeutig.

Erweiterung

Eine Erweiterung der kontextfreien Grammatiken bilden stochastische kontextfreie Grammatiken (SCFG), auch bekannt als probabilistische kontextfreie Grammatiken (PCFG). Hier wird jeder Produktionsregel eine Auftrittswahrscheinlichkeit zugeordnet: \rho\colon P\rightarrow\mathbb{R}^{\geq 0}, so dass für jedes \alpha'\in N gerade \sum_{\begin{smallmatrix}{\beta}\\(\alpha', \beta)\in P\end{smallmatrix}} \rho(\alpha', \beta) = 1 ist.

Diese Auftrittswahrscheinlichkeiten der einzelnen Regeln induzieren eine Wahrscheinlichkeitsverteilung auf der Menge der von der Grammatik erzeugten Wörter.

Eine stochastisch kontextfreie Grammatik kann beispielsweise dazu verwendet werden, für ein Eingabewort den wahrscheinlichsten Parse in einer syntaktisch mehrdeutigen Grammatik zu berechnen. Ein anderer Anwendungsfall ist das stochastische Samplen von Ableitungsbäumen unter den gegebenen Regelwahrscheinlichkeiten einer mehrdeutigen Grammatik. Die von einer SCFG erzeugte Sprache ist genau so definiert wie die Sprache einer CFG. SCFGs werden z.B. in der Bioinformatik und der Computerlinguistik eingesetzt.

Siehe auch

Einzelnachweise

  1. Schöning, 2001, S.21
  2. Alfred V. Aho and Jeffrey D. Ullman: The Theory of Parsing, Translation, and Compiling. Volume 1: Parsing. Prentice-Hall, 1972, ISBN 0-13-914556-7, S. 202.
  3. H. J. S. Basten: Ambiguity Detection Methods for Context-Free Grammars. 17.8.2007 (Master Thesis, http://homepages.cwi.nl/~paulk/thesesMasterSoftwareEngineering/2007/BasBasten.pdf).
  4. Schöning, 2001, S.137
  5. Schöning, 2001, S.137
  6. Schöning, 2001, S.137

Literatur

  • Taylor L. Booth und Richard A. Thomson: Applying probability measures to abstract languages. In: IEEE Transactions on Computers. C-22, Nr. 5, 1973, S. 442–450, doi:10.1109/T-C.1973.223746.
  • J. Baker: Trainable grammars for speech recognition. In: J. J. Wolf and D. H. Klatt (Hrsg.): Speech communication papers presented at the 97th meeting of the Acoustical Society of America. MIT, Cambridge, MA Juni 1979, S. 547–550 (JASA Vol. 65, issue S1, p. S132 ist nur der Abstract in einem Abstract-Band).
  • Uwe Schöning: Theoretische Informatik - kurzgefasst. 4. Auflage. Spektrum Akademischer Verlag, Berlin 2001, ISBN 3-8274-1099-1, S. 13, 51.

Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Kontextfreie Grammatiken — Die kontextfreien Grammatiken sind eine Klasse formaler Grammatiken und sind identisch mit den Typ 2 Grammatiken der Chomsky Hierarchie. Inhaltsverzeichnis 1 Definition 2 Normalformen 3 Von G erzeugte Sprache 4 Eigenschaften …   Deutsch Wikipedia

  • Kontextfreie Sprache — In der Theoretischen Informatik ist eine kontextfreie Sprache (engl. context free language, CFL) eine formale Sprache, die durch eine kontextfreie Grammatik beschrieben werden kann. Eine kontextfreie Grammatik erlaubt einen definierten… …   Deutsch Wikipedia

  • Grammatik — Allegorische Darstellung der Grammatik, ihre Disziplinen als Armeen. Aus Antoine Furetières Nouvelle Allegorique, Ou Histoire Des Derniers Troubles Arrivez Au Royaume D’Eloquence (1659). Die Grammatik (Sprachlehre, griechisch [τέχνη] γραμματική,… …   Deutsch Wikipedia

  • Typ2-Grammatik — Die kontextfreien Grammatiken sind eine Klasse formaler Grammatiken und sind identisch mit den Typ 2 Grammatiken der Chomsky Hierarchie. Inhaltsverzeichnis 1 Definition 2 Normalformen 3 Von G erzeugte Sprache 4 Eigenschaften …   Deutsch Wikipedia

  • Kontext-sensitive Grammatik — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen… …   Deutsch Wikipedia

  • Typ-0-Grammatik — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen… …   Deutsch Wikipedia

  • LL(k)-Grammatik — Dieser Artikel setzt Vorkenntnisse im Bereich Theoretische Informatik und Compilerbau voraus. Eine LL(k) Grammatik (im Kontrast zu LF(k) Grammatik auch schwache LL(k) Grammatik) ist eine spezielle kontextfreie Grammatik, welche die Grundlage… …   Deutsch Wikipedia

  • LR(k)-Grammatik — In der theoretischen Informatik und dem Compilerbau bezeichnet LR(k) Grammatik eine spezielle kontextfreie Grammatik, welche die Grundlage eines LR(k) Parsers bildet. Man nennt eine kontextfreie Grammatik LR(k) Grammatik, wenn jeder… …   Deutsch Wikipedia

  • Attributierte Grammatik — Eine Attributgrammatik ist eine kontextfreie Grammatik, die um Attribute, sowie Regeln und Bedingungen für diese Attribute, erweitert ist. Angewandt wird das Konzept im Compilerbau, um die Einhaltung von Regeln zu überprüfen, die mit… …   Deutsch Wikipedia

  • LF(k)-Grammatik — Dieser Artikel setzt Vorkenntnisse im Bereich Theoretische Informatik und Compilerbau voraus. Eine LF(k) Grammatik ist eine spezielle kontextfreie Grammatik, welche die Grundlage eines LF(k) Parsers bildet. Auf Grund der sehr engen Verwandtschaft …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”