Русская Википедия:Алгоритм Кока — Янгера — Касами
Алгоритм Кока — Янгера — Касами (Шаблон:Lang-en), алгоритм CYK либо CKY — алгоритм, позволяющий установить, можно ли в заданной контекстно-свободной грамматике вывести заданную строку, и если это так, то предоставить её вывод. Другими словами, это алгоритм синтаксического анализа строки. Алгоритм реализует синтаксический анализ снизу-вверх и основывается на методе динамического программирования. его открыватели: Джон Кок, Дэниел Янгер, Тадао Касами и Джейкоб Т. Шварц. Они использовали восходящий анализ и динамическое программирование.
Стандартная версия CYK работает только с контекстно-свободными грамматиками, заданными в нормальной форме (CNF). Однако любая контекстно-свободная грамматика может быть преобразована (после конвертирования) в грамматику CNF, выражающую тот же язык (Sipser 1997).
Является одним из самых эффективных алгоритмов синтаксического анализа с точки зрения асимптотической сложности в наихудшем случае, хотя существуют и другие алгоритмы с лучшим средним временем выполнения во многих практических сценариях[1].
Описание
Алгоритм работает следующим образом: на первом шаге записывается слово в первой строке и добавляется каждый нетерминальный символ в строку, под которой выводятся терминальные символы. После этого для каждой ячейки в сетке вертикально сверху вниз необходимо пройти к проверяемой ячейке, а вторая ячейка вверх по диагонали. Для каждого такого шага объединяются ячейки и проверяются на нахождение комбинации в грамматике. При условии нахождения, добавляется левый нетерминал в ячейку сетки. Если после всех шагов начальный символ содержится в последней строке, слово может быть получено по заданной грамматике[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 -> 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 не принадлежит языку
См. также
Примечания
Литература
Шаблон:Формальные языки Шаблон:Дописать
