WikiSort.ru - Программирование

Алгоритм Кока — Янгера — Касами (англ. 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 не принадлежит языку

См. также

• Алгоритм Эрли

Литература

• Younger, Daniel H. Recognition and parsing of context-free languages in time n³ (англ.) // 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.

• Lange, Martin, Leiß, Hans. To CNF or not to CNF? An Efficient Yet Presentable Version of the CYK Algorithm (англ.) // Informatica Didactica. — 2009. — Vol. 8. Архивировано 29 ноября 2014 года.
• Sipser, Michael. Introduction to the Theory of Computation. — 1st. — IPS, 1997. — ISBN 0-534-94728-X.
• 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.

Эта статья слишком короткая. Пожалуйста, дополните её ещё хотя бы несколькими предложениями и уберите это сообщение. Если статья останется недописанной, она может быть выставлена к удалению. Для указания на продолжающуюся работу над статьёй используйте шаблон {{subst:L}}.