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

Суббота, 24 марта 2018
НГУ, ауд. 2128, НГУ, новый корпус

Описание

Достижимый (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}.