Kontextfreie Sprache

Sprachklasse Typ 2. Sie wird von kontextfreien Grammatiken erzeugt und von Kellerautomaten erkannt und ist die Grundlage für die Syntax von Programmiersprachen und den Compilerbau.

Kontextfreie Grammatik

G = (Σ, N, P, S). Jede Regel hat links genau ein Nichtterminal, rechts ein beliebiges Wort aus Terminalen und Nichtterminalen. Jede Typ-3-Grammatik ist kontextfrei, also REG ⊂ kfS, und die Inklusion ist echt (Quelle - Automatentheorie Zusammenfassung).

Normalformen

• ε-Regeln eliminieren: Nichtterminale bestimmen, aus denen ε ableitbar ist. Für jede Regel, die eines davon enthält, eine Variante ohne dieses Nichtterminal hinzufügen, dann alle ε-Regeln streichen. Das Ergebnis erzeugt dieselben Wörter ohne ε.
• Chomsky-Normalform (CNF): nur Regeln A → BC oder A → a. Vorgehen: Terminale in längeren Regeln durch neue Variablen ersetzen, lange rechte Seiten in Zweierketten zerlegen, Kettenregeln A → B auflösen.
• Greibach-Normalform (GNF): nur Regeln A → aB₁…Bₘ, rechts also immer zuerst ein Terminal.
• Zu jeder kontextfreien Grammatik ohne ε gibt es eine äquivalente in CNF und in GNF.

Ableitungsbaum und Mehrdeutigkeit

• Jede Ableitung lässt sich als Ableitungsbaum (Parsebaum) darstellen. Daraus entsteht ein Syntaxbaum (Termbaum): Innere Knoten sind Operatoren, Blätter sind Operanden. Aus dem Syntaxbaum erzeugt ein Compiler den Objektcode.
• Eine Grammatik ist mehrdeutig, wenn ein Wort zwei verschiedene Ableitungsbäume hat. Dann kann derselbe Programmtext unterschiedlich übersetzt werden. Beim Sprachentwurf muss die Grammatik deshalb eindeutig sein (Quelle - Automatentheorie Zusammenfassung).

EBNF und Syntaxdiagramme

• Die erweiterte Backus-Naur-Form (EBNF) ist gleich mächtig wie kontextfreie Grammatiken, aber kompakter, weil sie Regex-Operatoren wie Auswahl | und Wiederholung {…} in den Regeln erlaubt.
• Reguläre Definition: Eine EBNF baut schrittweise (top-down) einen regulären Ausdruck auf.
• Syntaxdiagramme: grafische Form von Grammatiken bzw. EBNF, ein Standardwerkzeug in Sprachspezifikationen.

Kellerautomat (PDA)

Kontextfreie Sprachen werden genau von Kellerautomaten erkannt (PDA = kfS): endliche Automaten mit zusätzlichem Stack. Deterministische Kellerautomaten sind echt schwächer (DPDA ⊊ PDA), prüfen die Syntax aber in linearer Zeit und sind deshalb die Grundlage des Compilerbaus. Details, Abschlusseigenschaften und Beispiele → Kellerautomat (Quelle - Automatentheorie Zusammenfassung).

Eigenschaften

• Abgeschlossen unter Vereinigung, Konkatenation, Kleene-Stern und Spiegelung, nicht unter Durchschnitt und Komplement.
• Pumping-Lemma (kontextfrei): Zu L gibt es eine Konstante n. Jedes z ∈ L mit |z| ≥ n lässt sich schreiben als z = uvwxy mit |vx| ≥ 1 und |vwx| ≤ n, sodass uvⁱwxⁱy ∈ L für alle i ≥ 0. Damit ist z.B. {aᵏbᵏcᵏ} nicht kontextfrei.

Beispiele aus der Quelle

Umformung in Chomsky-Normalform (S. 21–23, zwei Beispiele):

1. Störende Terminale ersetzen: Für jedes Terminal a eine neue Variable Cₐ (bzw. Xₐ) mit Cₐ → a einführen und a in allen längeren Regeln durch Cₐ ersetzen. Aus S → bA wird S → C_bA, C_b → b.
2. Kettenregeln ersetzen: Zu jeder Variablen X die Menge U(X) der über Kettenregeln erreichbaren Variablen bilden (z.B. S → A, A → X₁A | B, B → 1 ergibt S → X₁A | 1) und die Kettenregeln streichen.
3. Lange rechte Seiten verkürzen: X → Y₁…Yₙ mit n ≥ 3 wird zu X → Y₁Z₁, Z₁ → Y₂Z₂, …, Zₙ₋₂ → Yₙ₋₁Yₙ. Beispiel: A → C_bAA wird zu A → C_bD₁, D₁ → AA. Für jede alte Regel werden neue Zᵢ gewählt.

Pumping-Lemma-Beweis (S. 26): L = {aᵏbᵏcᵏ} ist nicht kontextfrei. Man wählt z = aⁿbⁿcⁿ. Wegen |vwx| ≤ n können v und x nicht zugleich a's und c's enthalten. In jedem der fünf Fälle (nur a's; a's und b's; nur b's; nur c's; b's und c's) hat uv⁰wx⁰y = uwy zu wenige einer Buchstabensorte. Das ist ein Widerspruch.

Reguläre Definition (S. 28): Eine kontextfreie Grammatik, die schrittweise einen regulären Ausdruck aufbaut, z.B. Angestelltendatei → Angestelltensatz*, Angestelltensatz → Anr Name Geschlecht Kinder, Anr → Ziffer Ziffer Ziffer Ziffer, Name → Vorname Nachname, Geschlecht → m | w, Kinder → Kind* …

Syntaxdiagramme (S. 28): Alternative A ::= α₁ | … | αₖ als parallele Zweige. Eine Umgehung um β bedeutet optional (β kommt 0- oder 1-mal vor), eine Rückschleife mit Umgehung bedeutet beliebige Wiederholung {β}*.

Beispiele zu Kellerautomaten (DPDA für gleich viele a und b) → Kellerautomat.

Verwandt

• Reguläre Sprache – echte Teilklasse (Typ 3)
• Chomsky-Hierarchie – Einordnung (Typ 2)
• Endlicher Automat – der Kellerautomat erweitert ihn um einen Stack
• Wissensbasierte Bildanalyse – Syntaxanalyse (top-down/bottom-up) mit Grammatiken für Bildstrukturen
• Kellerautomat – der Automat, der kontextfreie Sprachen erkennt