Das Cocke-Younger-Kasami-Verfahren wurde Ende der 1960er Jahre unabhängig voneinander von mehreren Leuten beschrieben:
J. Cocke, T. Kasami und D. H. Younger.
Es ist eine tabellenbasierte Methode.
Für ein Eingabewort der Länge n wird eine (Dreiecks-)Matrix der Größe n x n aufgebaut.
Der Algorithmus kann beliebige kontextfreie Grammatiken verarbeiten.
Diese müssen allerdings in Chomsky-Normalform (CNF) vorliegen.1
Die Eingabe wird einmal von links nach rechts betrachtet. Die Reihenfolge spielt jedoch keine Rolle,
da bei Grammaktiken in CNF Terminalsymbole durch Regeln der Form Nichtterminal -> Terminal eingeführt werden.
Alle weiteren Schritte bauen auf diese Präterminalebene auf.
Das Verfahren geht somit bottom-up vor.
Ausgehend von den abgeleiteteten Teilwörtern der Länge 1 werden auf den weiteren Ebenen Teilwörter der Länge 2, 3 usw. abgeleitet, bis schließlich das gesamte Wort abgeleitet werden konnte.
Alle Alternativen werden parallel verfolgt, die Zwischenschritte dabei in der Tabelle abgelegt.
Nach einmaliger Anwendung des Algorithmus sind alle Analysemöglichkeiten gefunden.
Der Algorithmus selbst entscheidet dabei nur, ob das untersuchte Wort mit G abgeleitet werden kann.
Weitere Schritte sind notwendig, um aus den Zwischenschritten den Linksparse zu bestimmen.
____
1 Eine Generalisierung des Verfahrens für beliebige kontextfreie Grammatiken ist möglich.
| 
Methode