Стандартная версия CYK работает только с контекстно-свободными грамматиками, заданными в нормальной форме (CNF). Однако любая контекстно-свободная грамматика может быть преобразована (после конвертирования) в грамматику CNF, выражающую тот же язык (Sipser 1997).
Алгоритм работает следующим образом: на первом шаге записывается слово в первой строке и добавляется каждый нетерминальный символ в строку, под которой выводятся терминальные символы. После этого для каждой ячейки в сетке вертикально сверху вниз необходимо пройти к проверяемой ячейке, а вторая ячейка вверх по диагонали. Для каждого такого шага объединяются ячейки и проверяются на нахождение комбинации в грамматике. При условии нахождения, добавляется левый нетерминал в ячейку сетки. Если после всех шагов начальный символ содержится в последней строке, слово может быть получено по заданной грамматике[2].
Алгоритм динамического программирования требует, чтобы контекстно-свободная грамматика была преобразована в нормальную форму Хомского (CNF), потому что он проверяет возможность разбить текущую последовательность на две меньшие последовательности. Любая контекстно-свободная грамматика, не порождающая пустую строку, может быть представлена в CNF с использованием продукционных правил[3].
Псевдокод
На псевдокоде алгоритм выглядит следующим образом:
Алгоритм 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 -> RBRCеслиP[k,j,B] и P[i-k,j+k,C]
то присвоить P[i,j,A] = Истина
если для некоторого x из множества sP[n,1,x] = Истина, гдеs все индексы RsтовозвратитьS принадлежит языку
иначевозвратитьS не принадлежит языку
Younger, Daniel H. Recognition and parsing of context-free languages in time n3 (англ.) // Information and Computation. — Vol. 10, no. 2. — P. 189–208. — doi:10.1016/s0019-9958(67)80007-x.
Knuth, Donald E. The Art of Computer Programming Volume 2: Seminumerical Algorithms. — 3rd. — Addison-Wesley Professional. — 501 p. — ISBN 0-201-89684-2.
Lee, Lillian. Fast context-free grammar parsing requires fast Boolean matrix multiplication (англ.) // Journal of the ACM. — 2002. — Vol. 49, no. 1. — P. 1–15. — doi:10.1145/505241.505242.
Valiant, Leslie G. General context-free recognition in less than cubic time (англ.) // Journal of Computer and System Sciences. — 1975. — Vol. 10, no. 2. — P. 308–314. — doi:10.1016/s0022-0000(75)80046-8.
Lang, Bernard. Recognition can be harder than parsing (англ.) // Computational Intelligence (journal). — 1994. — Vol. 10, no. 4. — P. 486–494.