Kontextfrei

Kontextfrei bezeichnet in der Informatik formale Sprachen, die durch kontextfreie Grammatiken erzeugt werden. Die Theorie der kontextfreien Sprachen ist ein zentraler Bestandteil der formalen Sprachen und der Parsertechnik in Compilern und Textverarbeitungssystemen.

Eine kontextfreie Grammatik G besteht aus vier Komponenten: einer endlichen Menge Nichtterminalsymbolen V, einer endlichen Menge Terminalsymbolen Σ, einer Menge Produktionsregeln R und dem Startsymbol S ∈ V. Jede Regel hat die Form A → α, wobei A ein Nichtterminal ist und α eine Zeichenkette aus Terminal- und/oder Nichtterminalsymbolen, möglicherweise auch ε für die leere Wortfolge. Die von G erzeugte Sprache L(G) umfasst alle Wörter über Σ, die aus dem Startsymbol ableitbar sind.

Kontextfreie Sprachen gehören zur Chomsky-Hierarchie und lassen sich durch Pushdown-Automaten erkennen. Sie lassen sich in der Praxis oft effizient analysieren, etwa durch LL- oder LR- Parser, die in vielen Compiler- und Entwicklungswerkzeugen eingesetzt werden. Typische Grammatiken beschreiben die Syntax von Programmiersprachen und formalen Sekvenzen, die verschachtelte Strukturen oder rekursive Muster enthalten.

Anwendungen und Varianten: Kontextfreie Grammatiken dienen der formalen Spezifikation von Syntax. Parsergeneratoren wie Yacc, Bison oder ANTLR erzeugen aus CFGs Parsercode. Varianten umfassen deterministische kontextfreie Grammatiken (DCFG) und Normalformen wie die Chomsky-Normalform, die Parsing-Algorithmen vereinfacht. Einschränkungen zeigen sich daran, dass nicht alle Sprachen kontextfrei sind, zum Beispiel { a^n b^n c^n | n ≥ 0 }.