Семинар 7. Контекстно-свободные грамматики

Достижимый (reachable) нетерминал. Определение, поиск обходом за O(G). Зануляющийся (nullable) нетерминал. Определение, реккурентное условие. Поиск за O(N G). Хранение для правил кол-ва нетерминалов, пока не отмеченных как nullable. Очередь nullable нетерминалов. Определение всех nullable нетерм. за O(G). Выводящий (generating) нетерминал. Определение, реккурентное условие. Аналогия с nullable нетерминалами (если стереть терминалы из правил). Поиск за O(G). Полезный (useful) нетерминал. Определение. Поиск: ищем и удаляем сначала все негенерирующие, потом все недостижимые нетерм.

Нормальная форма Хомского. Определение. Построение: удаление eps-правил, цепных правил, разбиение длинных правил, устранение терминалов. Дерево разбора слова, дерево разбора/вывода.

Если успеем: Парсер CYK: R[l, r, A] - можно ли из нетерминала A вывести подстроку S[l:r). Динамика назад, переходы. Время работы O(G N^3).

Лемма о разрастании для КС-языков. Дерево разбора в НФХ. При длине слова > 2^|N| на каком-то пути вниз есть два одинаковых нетерминала. Формулировка леммы. Применение к {0^n 1^n 2^n}.