Kontextfreie Grammatiken

Eine kontextfreie Grammatik (CFG, Typ 2 in der Chomsky-Hierarchie) ist eine Grammatik, deren Produktionsregeln die Form

\[ A \rightarrow \alpha \]

haben, wobei \( A \) ein einzelnes Nichtterminal ist und \( \alpha \in (V \cup \Sigma)^* \) eine beliebige Folge von Terminalen und Nichtterminalen. Der Name „kontextfrei“ rührt daher, dass \( A \) unabhängig vom Kontext ersetzt werden kann.

Sprache: \( L = \{a^n b^n \mid n \geq 1\} \). Diese Sprache ist nicht regulär, lässt sich aber kontextfrei beschreiben:

S → aSb | ab

Ableitung von aaabbb:

S ⇒ aSb ⇒ aaSbb ⇒ aaabbb

Die rekursive Regel S → aSb sorgt dafür, dass jedes erzeugte a von einem entsprechenden b „eingerahmt“ wird – daher die gleiche Anzahl.

Eine kleine Grammatik für arithmetische Ausdrücke mit Plus, Mal und Klammern:

E → E + T | T
T → T * F | F
F → ( E ) | zahl

Diese Grammatik beachtet automatisch die Operatorvorrangregeln (Mal vor Plus) und die Linksassoziativität. Sie ist die Grundlage für jeden Taschenrechner-Parser.

Kontextfreie Sprachen werden durch Kellerautomaten (Pushdown-Automaten, PDA) erkannt. Ein PDA hat zusätzlich zum endlichen Zustandsraum einen Stack als unbegrenzten Hilfsspeicher. Für \( \{a^n b^n\} \) legt der Automat bei jedem gelesenen a ein Symbol auf den Stack und entfernt es bei jedem gelesenen b wieder. Ist der Stack am Ende leer und das Wort vollständig gelesen, akzeptiert er.

Eine Ableitung in einer CFG lässt sich als Ableitungsbaum (Parsebaum) darstellen. Die Wurzel ist das Startsymbol, innere Knoten sind Nichtterminale, Blätter Terminale. Eine Grammatik heißt mehrdeutig, wenn ein Wort mehrere unterschiedliche Ableitungsbäume besitzt. Mehrdeutigkeit ist in Compilern unerwünscht und wird durch sorgfältige Grammatikgestaltung vermieden.

Programmiersprachen werden üblicherweise durch kontextfreie Grammatiken in Backus-Naur-Form (BNF) beschrieben. Der Parser baut zur Eingabe einen Ableitungsbaum auf. Gängige Verfahren sind LL(1) (rekursiver Abstieg, top-down) und LR(1) (yacc, bison, bottom-up). Beide arbeiten in linearer Zeit \( \mathcal{O}(n) \).

Linksrekursive Regeln verursachen Endlosschleifen in rekursiv-absteigenden Parsern. Mehrdeutige Grammatiken erzeugen ungewollte Mehrdeutigkeiten (z. B. „dangling else“). Versuch, Sprachen wie \( a^n b^n c^n \) kontextfrei zu beschreiben (geht nicht!).

Zusammenfassung: Kontextfreie Grammatiken erlauben Regeln \( A \rightarrow \alpha \) und erzeugen genau die kontextfreien Sprachen, die von Kellerautomaten erkannt werden. Sie sind die Grundlage des Compilerbaus.

Abitur-Tipp: Bei einer kontextfreien Grammatik immer einen Ableitungsbaum für ein konkretes Wort zeichnen – das sichert sicher Punkte in der Prüfung.