Алгоритм Кока — Янгера — Касами

Алгоритм Кока — Янгера — Касами (англ. Cocke — Younger — Kasami algorithm), алгоритм CYK либо CKY — алгоритм, позволяющий установить, можно ли в заданной контекстно-свободной грамматике вывести заданную строку, и если это так, то предоставить её вывод. Другими словами, это алгоритм синтаксического анализа строки. Алгоритм реализует синтаксический анализ снизу-вверх и основывается на методе динамического программирования. его открыватели: Джон Кок, Дэниел Янгер, Тадао Касами и Джейкоб Т. Шварц. Они использывали восходящий анализ и динамическое программирование.

Стандартная версия CYK работает только с контекстно-свободными грамматиками, заданными в нормальной форме (CNF). Однако любая контекстно-свободная грамматика может быть преобразована (после конвертирования) в грамматику CNF, выражающую тот же язык (Sipser 1997).

Псевдокод

На псевдокоде алгоритм выглядит следующим образом:

Алгоритм CYK: дано строка S из n символов: a1 ... an. дано грамматика, содержащая r нетерминальных символов R1 ... Rr. Содержит подмножество Rs начальных символов. опр массив P[n,n,r] булевских значений, инициализированных значениями Ложь. для каждого i = 1 : n для каждой продукции Rj -> ai присвоить P[1,i,j] = Истина для каждого i = 2 : n -- длина интервала для каждого j = 1 : n-i+1 -- начало интервала для каждого k = 1 : i-1 -- разбиение интервала для каждой продукции RA -> RB RC если P[k,j,B] и P[i-k,j+k,C] то присвоить P[i,j,A] = Истина если для некоторого x из множества s P[n,1,x] = Истина, где s все индексы Rs то возвратить S принадлежит языку иначе возвратить S не принадлежит языку