Алгоритм Кока — Янгера — Касами (англ. Cocke — Younger — Kasami algorithm), алгоритм CYK либо CKY — алгоритм, позволяющий установить, можно ли в заданной контекстно-свободной грамматике вывести заданную строку, и если это так, то предоставить её вывод. Другими словами, это алгоритм синтаксического анализа строки. Алгоритм реализует синтаксический анализ снизу-вверх и основывается на методе динамического программирования.
На псевдокоде алгоритм выглядит следующим образом:
Алгоритм 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 не принадлежит языку
Эта статья слишком короткая. |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .