/ Compilerbau & Formale Sprachen

Grammatik Ableitungsschritte

Minimale Ableitungslänge in Chomsky-Normalform für ein Wort der Länge n: MinSchritte = 2·n − 1.

01 · Eingabe

Grammatik Ableitungsschritte berechnen

Minimale Ableitungslänge in Chomsky-Normalform für ein Wort der Länge n: MinSchritte = 2·n − 1.

Lösen für

MinSchritte = 2 · Wortlänge - 1

Wortlänge Wortlänge

Worum geht es?

Eine kontextfreie Grammatik in Chomsky-Normalform (CNF) erlaubt nur Produktionen der Gestalt A → BC oder A → a. Jede binäre Regel erzeugt aus einem Nichtterminal zwei Symbole — dadurch verdoppelt sich die Länge der Satzform schrittweise, bis n Terminale erreicht sind.

Für ein Wort der Länge n benötigt man dadurch genau n − 1 binäre Produktionen und n terminale Produktionen, also 2·n − 1 Ableitungsschritte. Das ist die Tiefenformel des CYK-Parsers und der Grund, warum der CYK-Algorithmus mit O(n³·|G|) skaliert.

Die Formel

Formel Ableitungslänge in CNF

MinSchritte = 2 · Wortlänge - 1

Umstellung:
    Wortlänge = (MinSchritte + 1) / 2

Die Variablen

Symbol	Bedeutung	Einheit	Erklärung
Wortlänge	Wortlänge	—	Länge des abzuleitenden Worts (n ≥ 1).
MinSchritte	Min. Ableitungsschritte	—	Minimale Ableitungsschritte in CNF.

Minimal-Beispiel

Ein Wort der Länge 4:

Rechnung Vier Zeichen

MinSchritte = 2 · 4 - 1
            = 7

Praxis-Beispiele

Beispiel 1 — Quelltext-Token-Stream

Ein Parser leitet eine Statement-Folge mit n = 50 Tokens in CNF ab:

Rechnung Statementfolge

MinSchritte = 2 · 50 - 1
            = 99

Beispiel 2 — Wortlänge aus Ableitungstiefe

Ein Trace zeigt 41 Ableitungsschritte:

Rechnung Rückwärts

Wortlänge = (41 + 1) / 2
          = 21

Beispiel 3 — Untergrenze für CYK

Ein Wort der Länge n = 200:

Rechnung CYK-Schranke

MinSchritte = 2 · 200 - 1
            = 399 Schritte