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

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