9 Алгоритм Эрли
Алгоритм Эрли — это динамический алгоритм, который позволяет определить, выводится ли данное слово в данной контекстно-свободной грамматике. Вход: контекстно-свободная грамматика и слово. 3 Выход: true, если слово выводится в грамматике, false — иначе. Основная идея Эрли состоит в том, чтобы отслеживать этапы работы алгоритма в таблицах. Алгоритм использует три основные процедуры для работы: Predict, Scan и Complete: Predict пытается предсказать, какое правило будет использоваться при раскрытии некоторого нетерминала (спуск по дереву). Scan проверяет, может ли состояние соответствовать следующему термину. Если да, то добавляет это состояние в следующий набор состояний в качестве кандидата и перемещает точку в следующую позицию. Complete завершает процесс разбора, отслеживая правила, которые совпадали до расширения. Алгоритм Эрли используется для обработки текста, например, для проверки правильности предложения, а также в компиляторах для разбора кода и проверки его синтаксиса. 00:05 Введение в курс 00:51 Применение парсеров в нейросетях 02:31 Проблемы с грамматикой и переход к парсеру Эрли 03:37 Предыстория и неэффективность предыдущих парсеров 05:45 Введение в задачу и пример грамматики 11:04 Операции в дереве разбора 14:06 Заключение и индексация 15:15 Введение в шифрование блоков 17:03 Геометрический смысл ситуации 18:47 Пересчет правил и индексов 20:42 Математический смысл ситуации 25:29 Пример с правилами грамматики 28:00 Шифрование операций 34:18 Стартовые и конечные условия 36:00 Заключение и переход к алгоритму 37:00 Введение в доказательство леммы 38:03 База индукции 40:32 Переход 45:06 Преддикт 49:24 Компликт 55:52 Доказательство корректности 58:04 Введение в индукцию 01:00:00 Переход и случаи 01:02:07 Пример с альфа-штрих а 01:05:56 Пример с символом бета 01:09:00 Паттерны и выводы 01:14:21 Пустое слово 01:16:04 Цепочки и выводы 01:17:44 Правила грамматики 01:18:45 Последний шаг 01:20:06 Корректность алгоритма
Алгоритм Эрли — это динамический алгоритм, который позволяет определить, выводится ли данное слово в данной контекстно-свободной грамматике. Вход: контекстно-свободная грамматика и слово. 3 Выход: true, если слово выводится в грамматике, false — иначе. Основная идея Эрли состоит в том, чтобы отслеживать этапы работы алгоритма в таблицах. Алгоритм использует три основные процедуры для работы: Predict, Scan и Complete: Predict пытается предсказать, какое правило будет использоваться при раскрытии некоторого нетерминала (спуск по дереву). Scan проверяет, может ли состояние соответствовать следующему термину. Если да, то добавляет это состояние в следующий набор состояний в качестве кандидата и перемещает точку в следующую позицию. Complete завершает процесс разбора, отслеживая правила, которые совпадали до расширения. Алгоритм Эрли используется для обработки текста, например, для проверки правильности предложения, а также в компиляторах для разбора кода и проверки его синтаксиса. 00:05 Введение в курс 00:51 Применение парсеров в нейросетях 02:31 Проблемы с грамматикой и переход к парсеру Эрли 03:37 Предыстория и неэффективность предыдущих парсеров 05:45 Введение в задачу и пример грамматики 11:04 Операции в дереве разбора 14:06 Заключение и индексация 15:15 Введение в шифрование блоков 17:03 Геометрический смысл ситуации 18:47 Пересчет правил и индексов 20:42 Математический смысл ситуации 25:29 Пример с правилами грамматики 28:00 Шифрование операций 34:18 Стартовые и конечные условия 36:00 Заключение и переход к алгоритму 37:00 Введение в доказательство леммы 38:03 База индукции 40:32 Переход 45:06 Преддикт 49:24 Компликт 55:52 Доказательство корректности 58:04 Введение в индукцию 01:00:00 Переход и случаи 01:02:07 Пример с альфа-штрих а 01:05:56 Пример с символом бета 01:09:00 Паттерны и выводы 01:14:21 Пустое слово 01:16:04 Цепочки и выводы 01:17:44 Правила грамматики 01:18:45 Последний шаг 01:20:06 Корректность алгоритма