Kontextfreie

Kontextfreiheit bezeichnet die Eigenschaft bestimmter formaler Sprachen, die durch kontextfreie Grammatiken erzeugt werden. Kontextfreie Sprachen spielen eine zentrale Rolle in der Formalen Sprachenlehre, in der Compilertechnik und beim Design von Programmiersprachen, da sie oft die Syntax von Ausdrücken und Programmen modellieren.

Eine kontextfreie Grammatik G besteht aus einem Vier-Tupel G = (N, Σ, P, S). N ist eine endliche Menge von Nicht-Terminalsymbolen, Σ eine endliche Menge von Terminalsymbolen, P eine endliche Menge von Produktionsregeln der Form A → α mit A ∈ N und α ∈ (N ∪ Σ)*, und S ∈ N ist das Startsymbol. Der Symbol ε kann als Regel zur Erzeugung des leeren Wortes verwendet werden. Die von G erzeugte Sprache L(G) besteht aus allen Strings über Σ, die sich ausgehend vom Startsymbol mithilfe der Regeln ableiten lassen.

Kontextfreie Sprachen werden durch endliche Kellerautomaten (Pushdown-Automaten) erkannt oder akzeptiert. Es besteht eine Gleichheit zwischen kontextfreien Grammatiken und kontextfreien Sprachen. Es gibt deterministische und nichtdeterministische Varianten; viele Grammatikformen verwenden spezielle Parser-Typen wie LL-, LR- oder LR(k)-Parser, die effizientes Parsing ermöglichen.

Beispiele für kontextfreie Grammatiken: S → SS | ( S ) | ε erzeugt korrekte verschachtelte Klammerausdrücke; S → a S b | ε erzeugt die Sprache { a^n b^n | n ≥ 0 }. Kontextfreie Sprachen sind abgeschlossen unter Vereinigung, Konkatenation und Kleene-Stern, aber nicht allgemein unter Schnitt oder Komplement. Sie bleiben jedoch abgeschlossen unter der Schnittmenge mit regulären Sprachen.

Anwendungen finden sich vor allem im Parserbau von Programmiersprachen, in der Spezifikation von Syntaxregeln mit Backus–Naur-Form und in Tools zur automatischen Code-Analyse und Übersetzung.