9 Алгоритм Эрли

Алгоритм Эрли — это динамический алгоритм, который позволяет определить, выводится ли данное слово в данной контекстно-свободной грамматике. Вход: контекстно-свободная грамматика и слово. 3 Выход: true, если слово выводится в грамматике, false — иначе. Основная идея Эрли состоит в том, чтобы отслеживать этапы работы алгоритма в таблицах. Алгоритм использует три основные процедуры для работы: Predict, Scan и Complete: Predict пытается предсказать, какое правило будет использоваться при раскрытии некоторого нетерминала (спуск по дереву). Scan проверяет, может ли состояние соответствовать следующему термину. Если да, то добавляет это состояние в следующий набор состояний в качестве кандидата и перемещает точку в следующую позицию. Complete завершает процесс разбора, отслеживая правила, которые совпадали до расширения. Алгоритм Эрли используется для обработки текста, например, для проверки правильности предложения, а также в компиляторах для разбора кода и проверки его синтаксиса.

Видео 9 Алгоритм Эрли автора Сталинский Букварь