Анализатор Earley
-
Обзор алгоритма синтаксического анализа Earley
- Алгоритм Эрли — это метод динамического программирования для распознавания контекстно-свободных грамматик.
- Он был разработан Джеем Эрли в 1968 году и используется для создания синтаксического анализатора.
- Алгоритм может быть модифицирован для создания дерева синтаксического анализа.
-
Алгоритм и его реализация
- Алгоритм Эрли использует динамическое программирование сверху вниз и точечную запись для описания состояний.
- Он генерирует набор состояний для каждой входной позиции и использует предсказание, сканирование и завершение для обработки состояний.
- Псевдокод алгоритма адаптирован из работы Дэниела Джурафски и Джеймса Х. Мартина.
-
Примеры и оптимизация
- Приведен пример простой арифметической грамматики и построение леса синтаксического анализа.
- Филипп Маклин и Р. Найджел Хорспул улучшили алгоритм, объединив его с парсингом LR.
-
Реализации и языки программирования
- Представлены реализации алгоритма на различных языках программирования, включая C, C++, Haskell, Java, C#, JavaScript, OCaml, Perl, Python, Rust и другие.
-
Ресурсы и история
- Указаны ссылки на архивы компилятора Accent и ресурсы по реализации алгоритма на различных языках программирования.
Полный текст статьи: