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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

См. также[править | править код]

Примечания[править | править код]

  1. John E. Hopcroft. Introduction to automata theory, languages, and computation. — Reading, Mass.: Addison-Wesley, 1979. — x, 418 pages с. — ISBN 0-201-02988-X, 978-0-201-02988-8.
  2. The CYK Algorithm • Computer Science and Machine Learning. www.xarg.org. Дата обращения: 4 октября 2022. Архивировано 4 октября 2022 года.
  3. Michael Sipser. Introduction to the theory of computation. — 2nd ed. — Boston: Thomson Course Technology, 2006. — xix, 431 pages с. — ISBN 0-534-95097-3, 978-0-534-95097-2.

Литература[править | править код]

  • 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.