Алгоритм CYK: парсинг за O(n^3)

Как компьютер понимает код? Рекурсивный descent парсер делает экспоненциальное число попыток в худшем случае. CYK доказал в 1965 году: распознать любой КС-язык можно за $O(n^3)$ - и это сделало теоретическую CS практической.

• **Stanford NLP Parser** (2003-2015) - dominировал на English parsing benchmarks, основан на Probabilistic CYK с вероятностными КС-грамматиками (PCFG)
• **Биоинформатика**: RNA secondary structure prediction (Nussinov algorithm, 1978) - прямое применение CYK-DP для нахождения оптимальных структур молекул
• **ANTLR** (парсер-генератор для Java, используется в Hadoop, Spark, Hibernate) внутренне использует LL(*) - эволюцию идей из той же семьи chart parsing

Динамическое программирование в парсинге

GPT-4 токенизирует текст за миллисекунды. Но внутри этого процесса - та же идея, что в задаче 1975 года: как проверить, принадлежит ли строка контекстно-свободному языку. Ответ нашли Cocke, Younger и Kasami независимо: разбей задачу на подзадачи, сохраняй результаты, не повторяй вычисления.

Рекурсивный парсер без мемоизации для строки длины n может делать экспоненциальное число вызовов. CYK сводит это к $O(n^3 |G|)$ через таблицу dynamic programming - треугольную матрицу подстрок. Каждая ячейка T[i][j] хранит множество нетерминалов, из которых можно вывести подстроку с позиции i длиной j.

В NLP: inside algorithm (Inside-Outside для PCFG) - прямое расширение CYK для probabilistic parsing. Stanford Parser и ранние версии систем машинного перевода Google используют вариации CYK с вероятностями. DP-структура та же - к ячейкам таблицы добавляются log-вероятности.

Заполнение CYK-таблицы

Алгоритм требует грамматику в нормальной форме Хомского: правила вида A -> BC или A -> a. Никаких epsilon-правил, никаких цепочек A -> B. CNF - не ограничение, это стандартизация: любую КС-грамматику можно привести к CNF без изменения языка.

Тройной цикл дает O(n^3) по длине строки, умноженное на |G| (размер грамматики). Для практических грамматик языков программирования n - длина кода в токенах (сотни-тысячи), |G| - сотни правил. CYK слишком медленен для production парсеров - но идеален для доказательства алгоритмической разрешимости.

Распознавание vs Парсинг

Базовый CYK отвечает на вопрос 'да/нет': принадлежит ли строка языку. Это распознавание. Парсинг - сложнее: построить дерево разбора. Расширение простое: вместо хранения множества нетерминалов в T[i][j] хранить указатель на то, из каких двух частей получена запись - backpointer.

Probabilistic CYK (PCFG) - та же идея с весами. Каждое правило A->BC имеет вероятность P(A->BC). T[i][j][A] хранит лучшую (max log-prob) деривацию. Это inside algorithm в inside-outside для обучения PCFG. Stanford NLP Parser (2003-2015) доминировал на English NLP benchmarks именно с PCFG + CYK.

CYK в контексте современных парсеров

O(n^3) - теоретически красиво, практически медленно. GCC парсит миллионы строк кода, Rust компилятор обрабатывает огромные codebase. Ни один production compiler не использует CYK. Зачем тогда изучать?

CYK доказывает: задача парсинга для любого КС-языка решаема за полиномиальное время. Это теоретический фундамент. На практике используют LL(k), LR(1), GLR - они быстрее на типичных языках программирования. Но для неоднозначных грамматик (natural language!) CYK и его производные незаменимы.

Earley algorithm (1970) - обобщение CYK для произвольных КС-грамматик без требования CNF, O(n^3) в общем случае, O(n^2) для однозначных грамматик. Используется в некоторых NLP системах. Chart parsing - общее название класса алгоритмов включая CYK и Earley.

Связанные темы

CYK соединяет теорию грамматик с алгоритмами:

• Нормальная форма Хомского — CYK требует CNF как предусловие
• Динамическое программирование — CYK - образцовое применение DP к задаче распознавания
• LL/LR парсеры — Практические альтернативы CYK для детерминированных грамматик

Ключевые идеи

• **CYK** - распознаватель КС-языков за $O(n^3 |G|)$ через DP-таблицу T[i][j] = множество нетерминалов для подстроки. Требует CNF.
• **Заполнение снизу вверх**: сначала одиночные символы, затем подстроки растущей длины. Три вложенных цикла - длина, начало, точка разбиения.
• **Backpointers** превращают распознавание в парсинг: храни (k, B, C) для каждого A в T[i][j], восстанавливай дерево обратным ходом.
• **Ограничение**: O(n^3) слишком медленно для production компиляторов (там LR(1) = O(n)). Незаменим для неоднозначных грамматик и probabilistic NLP.

Вопросы для размышления

• CYK гарантирует полиномиальное время для любого КС-языка. Существуют ли языки, для которых парсинг принципиально быстрее или медленнее?
• Как probabilistic CYK (PCFG) изменился с появлением нейросетевых NLP систем (BERT, GPT)? Какую роль играет грамматика в современном NLP?
• Если реализовать CYK для Python-кода, какой будет практическое n (длина файла)? Насколько применим O(n^3) на практике?

Связанные уроки

• fl-14-cnf-gnf — CYK требует грамматику в нормальной форме Хомского (CNF)
• alg-21-dp — CYK - классическое применение динамического программирования
• fl-17-ll-lr — Понимание CYK помогает осмыслить LL/LR парсеры как специализации
• fl-16-pumping-cf — Лемма о накачке дополняет теорию КС-языков
• comp-10-cfg
• comp-12-lr-parsing