CYKAlgorithmus

Der CYK-Algorithmus, auch Cocke–Younger–Kasami-Algorithmus genannt, ist ein Parsing-Verfahren für kontextfreie Grammatiken in Chomskys Normalform. Er entscheidet, ob ein gegebener String von einer CFG erzeugt wird, und kann auf Wunsch eine Parse-Struktur liefern. Die Grammatik muss in CNF vorliegen, d. h. alle Regeln haben die Formen A → BC oder A → a (mit gegebenen Terminalsymbolen) oder, in einigen Fassungen, S → ε für den leeren String.

Der Ablauf basiert auf dynamischer Programmierung. Gegeben sei ein Eingabewort w der Länge n. Es wird eine Tabelle P aufgebaut, in der P[i, j] die Menge der Nichtterminale A enthält, die w-Substring von i bis j (inklusiv) ableiten kann. Zunächst werden für alle i mit Länge 1 alle A ermittelt, die A → w[i] erfüllen. Danach werden Zellen für längere Teilstrings l von 2 bis n gefüllt: Für jedes i gilt j = i + l − 1. Es werden alle möglichen Zerlegungen k zwischen i und j geprüft; wenn A → BC und B ∈ P[i, k] sowie C ∈ P[k+1, j] gilt, wird A zu P[i, j] hinzugefügt. Zur Rückgewinnung einer Parse-Struktur werden Backpointer verwendet.

Die Komplexität beträgt in CNF-Form O(n^3) Zeit und O(n^2) Speicher. Der Algorithmus ist korrekt und vollständig für CNF-Grammatiken und liefert, falls vorhanden, eine Beweisstruktur (Parse-Baum oder Baumfamilie). Er ist besonders nützlich in Compilern und der natürlichen Sprachverarbeitung, wird jedoch durch die CNF-Voraussetzung eingeschränkt. Alternatives Parsen umfasst Funktionen wie den Earley-Parser, der ohne CNF arbeiten kann.