Kontextfreie Grammatik

(Weitergeleitet von Typ-2-Grammatik)

In der Theorie der formalen Sprachen ist eine kontextfreie Grammatik (englisch context-free grammar, CFG) eine formale Grammatik, die nur solche Ersetzungsregeln enthält, bei denen immer genau ein Nichtterminalsymbol auf eine beliebig lange Folge von Nichtterminal- und Terminalsymbolen abgeleitet wird. Die Ersetzungsregeln haben also die Form (mit Nichtterminalsymbol und Zeichenkette bestehend aus Nichtterminal- und/oder Terminalsymbolen).

Weil die linke Seite einer Regel nur aus einem einzigen Nichtterminalsymbol besteht, hängt ihre Anwendbarkeit auf eine Zeichenkette nur davon ab, ob das Nichtterminalsymbol in der Zeichenkette vorkommt, nicht aber davon, in welchem Kontext es sich befindet, d. h. welche Zeichen links und/oder rechts davon stehen. Die Regeln sind also kontextfrei.

Die kontextfreien Grammatiken sind identisch mit den Typ-2-Grammatiken der Chomsky-Hierarchie.

Definition

Bearbeiten

Eine kontextfreie Grammatik   ist ein 4-Tupel   mit folgenden Eigenschaften:

  •   ist eine endliche Menge, genannt Vokabular,
  • einer Teilmenge  , von Terminalsymbolen (auch kurz Terminale genannt),
Dazu gehört die Differenzmenge   von Nichtterminalsymbolen (auch kurz Nichtterminale oder Variablen genannt).
  und   sind disjunkte Alphabete
  • eine endliche Menge an Produktionsregeln (kurz Produktionen)  ,
  • ein Startsymbol  .

Hierbei bezeichnet   die Kleenesche Hülle.

Erläuterung

Bearbeiten

Manche Autoren bezeichnen alternativ das Quadrupel   als Grammatik  , mit der Forderung, dass   und   zwei endliche, disjunkte Mengen sind, und  .

Gelegentlich werden die Nichtterminale (Variablen) abweichend mit   und die Terminale oder das Gesamtvokabular mit   bezeichnet.

Eine Regel   wird meist in der Form   notiert.

Gemäß der Definition gilt für eine Regel  , dass   ist, also dass auf der linken Seite der Ersetzungsregel genau ein Nichtterminal steht. Es ist in einer Regel auf der linken Seite nicht von anderen Zeichen umgeben, und es stehen daher für jede Zeichenkette, die dieses Nichtterminal enthält, immer die gleichen Regeln zur Auswahl, egal welche Zeichen das Nichtterminal   in einer Zeichenkette umgeben. Kurz gesagt ist die Auswahl der Regeln unabhängig vom Kontext von  .

Von G erzeugte Sprache

Bearbeiten

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.

Dabei werden die Produktionsregeln   so angewendet, dass in einem Wort   mit R als Infix (Teilwort, englisch substring), dieses durch Q ersetzt werden kann, so dass ein neues Wort   mit   als Infix entsteht. Die Menge   (als Teilmenge eines kartesischen Produktes eine Relation) wird dadurch erweitert zu

 .

Diese Ersetzungen können mehrfach vorgenommen werden: Wenn ein Wort   aus einem Wort   durch n-fache Anwendung von   hervorgeht, schreibt man  , ist dies bei beliebiger endlicher Anwendung der Fall, dann  . Die Relation   (Ableitung) steht für eine beliebige endliche Folge von Regelanwendungen bezüglich der Grammatik  . Siehe dazu auch: Homogene Relationen.

Die kontextfreie Sprache  , die durch die kontextfreie Grammatik   generiert wird, ist dann definiert als die Menge aller Wörter, die auf diese Weise aus dem Startsymbol abgeleitet werden können und die nur aus Terminalen bestehen:

 .

Es müssen vom Startsymbol   aus solange Nichtterminale mit Hilfe der Regeln ersetzt werden, bis nur noch Terminale übrig sind. Offenbar gilt  .

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  . 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

Bearbeiten

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

Bearbeiten

Wortproblem

Bearbeiten

Das Wortproblem für kontextfreie Sprachen, also das Problem, ob ein Wort   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   (s. Landau-Symbole). Für Teilklassen von kontextfreien Grammatiken können Parser erzeugt werden, deren Laufzeit in   liegt. Ein typischer Anwendungsfall eines effizienten kontextfreien Parsers mit linearer Laufzeit ist das Parsen eines Programmiersprachen-Quelltexts durch einen Compiler.

Wenn ein Wort   der Sprache L ( ) durch die Grammatik   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

Bearbeiten

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

Bearbeiten

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

Teilmenge

Bearbeiten

Das Problem, ob die durch eine kontextfreie Grammatik   erzeugte Sprache auch von einer kontextfreien Grammatik   erzeugt wird (also ob  ), ist nicht entscheidbar.[4]

Vereinigung

Bearbeiten

Die Vereinigung   der Sprachen zweier kontextfreier Grammatiken   und   kann ebenfalls von einer kontextfreien Grammatik erzeugt werden, nämlich

 .

Dabei wird vorausgesetzt, dass die beiden Nichtterminalmengen   und   disjunkt sind ( ), und   ein beliebiges zusätzliches Zeichen ist ( ), was aber für alle   erreicht werden kann.

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

Komplement

Bearbeiten

Das Komplement einer kontextfreien Grammatik ist im Allgemeinen nicht kontextfrei.

Beispiele

Bearbeiten

Sei   eine kontextfreie Grammatik mit   und

 

 

  enthält 4 Produktionen bzw. Produktionsregeln:

 

  kann durch die Grammatik   mit folgender Ableitung erzeugt werden:

 

  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  .

Das Beispiel Wort   mit   ist nicht Teil der Sprache  , da das Nichtterminal   nicht das Startsymbol ist und über das Startsymbol jedes Wort der Sprache von den Terminal-Symbolen   und   eingeschlossen sein muss. In Formelschreibweise:

 

Grammatik   ist nicht mehrdeutig.

Sprache der Palindrome

Bearbeiten

Die Grammatik   mit   gegeben als   erzeugt die Sprache aller Palindrome über dem Alphabet  .

Mehrdeutiges Beispiel

Bearbeiten

Ein Beispiel für eine mehrdeutige Grammatik ist   mit   und

 

 

  enthält folgende Produktionen:

 

Für   existieren unter anderem die Ableitungen  ,   und  . Also ist   mehrdeutig.

Binärbäume

Bearbeiten
 
Ein Binärbaum

Die Darstellung von Binärbaumen in pre-order als Zeichenkette kann mit einer kontextfreien Grammatik mit  ,   und folgenden Produktionsregeln definiert werden:

 

Der Binärbaum rechts hat dann die Pre-order-Darstellung F(B(A)(D(C)(E)))(G()(I(H)())).

Eine Darstellung mittels der Erweiterten Backus-Naur-Form ist

BinaryTree = Identifier, "(", BinaryTree, ")(", BinaryTree, ")" | [Identifier] ;
Identifier = Letter, { ( Letter | Digit ) } ;
Letter = "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" ;
Digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;

Erweiterung

Bearbeiten

Eine Erweiterung der kontextfreien Grammatiken bilden stochastische kontextfreie Grammatiken (SCFG), auch bekannt als probabilistische kontextfreie Grammatiken (PCFG). Hier wird jeder Produktionsregel eine Auftrittswahrscheinlichkeit zugeordnet:  , so dass für jedes   gerade   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

Bearbeiten

Literatur

Bearbeiten
  • John E. Hopcroft, Jeffrey D. Ullman: Introduction to automata theory, languages, and computation. Addison-Wesley, 1979, ISBN 0-201-02988-X, S. 77 ff.
  • 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.

Einzelnachweise

Bearbeiten
  1. Uwe Schöning: Theoretische Informatik- kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1, S. 13.
  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. August 2007 (cwi.nl [PDF] Master Thesis).
  4. a b c Schöning, 2001, S. 137.