Введение

Алгоритм разбора контекстно-свободных языков

В информатике, алгоритм Эрли (Earley parser) — это алгоритм разбора строк, принадлежащих к заданному контекстно-свободному языку, хотя (в зависимости от варианта) он может испытывать проблемы с некоторыми грамматиками, допускающими порождение пустой строки. Алгоритм, названный в честь его изобретателя, Джея Эрли, является табличным парсером, использующим динамическое программирование; он в основном применяется для разбора в вычислительной лингвистике. Впервые он был представлен в его диссертации в 1968 году (а позже опубликован в сокращенной, более удобочитаемой форме в журнале). Парсеры Эрли привлекательны тем, что они могут разбирать все контекстно-свободные языки, в отличие от LR-парсеров и LL-парсеров, которые чаще используются в компиляторах, но способны обрабатывать только ограниченные классы языков. В общем случае, алгоритм Эрли выполняется за кубическое время, где n — длина разбираемой строки, за квадратичное время для однозначных грамматик и за линейное время для всех детерминированных контекстно-свободных грамматик. Он особенно эффективно работает с правилами, записанными леворекурсивно.

Распознаватель Эрли

Следующий алгоритм описывает распознаватель Эрли. Распознаватель можно модифицировать для построения дерева разбора по мере распознавания, и таким образом превратить его в анализатор.

Создание парсового леса

В диссертации Эрли кратко описывается алгоритм построения деревьев разбора путем добавления набора указателей от каждого нетерминала в элементе Эрли обратно к элементам, которые вызвали его распознавание. Но Томита заметил, что это не учитывает связи между символами, поэтому, если мы рассмотрим грамматику S → SS | b и строку bbb, она отмечает только, что каждое S может соответствовать одному или двум b, и таким образом генерирует ложные выводы для bb и bbbb, а также два правильных вывода для bbb. Другой метод – строить лес разбора по мере выполнения, дополняя каждый элемент Эрли указателем на общий упакованный лес разбора (SPPF) с меткой в виде тройки (s, i, j), где s – символ или элемент LR(0) (правило продукции с точкой), а i и j указывают на участок входной строки, полученный этим узлом. Содержимое узла – это либо пара указателей на дочерние узлы, представляющая одно выведение, либо список "упакованных" узлов, каждый из которых содержит пару указателей и представляет одно выведение. Узлы SPPF уникальны (существует только один узел с данной меткой), но могут содержать более одного выведения для неоднозначного разбора. Таким образом, даже если операция не добавляет элемент Эрли (потому что он уже существует), она все равно может добавить выведение в лес разбора элемента. Предсказанные элементы имеют нулевой указатель SPPF. Сканер создает узел SPPF, представляющий нетерминал, который он сканирует. Затем, когда сканер или завершитель продвигают элемент, они добавляют выведение, дочерними узлами которого являются узел из элемента, точка которого была продвинута, и узел для нового символа, над которым было выполнено продвижение (нетерминал или завершенный элемент). Узлы SPPF никогда не маркируются завершенным элементом LR(0): вместо этого они маркируются символом, который производится, чтобы все выведения были объединены под одним узлом, независимо от того, из какого альтернативного правила продукции они получены.

Оптимизация

Филипп Маклин и Р. Найджел Хорспул в своей статье "Более быстрый парсер Эрли" объединяют парсинг Эрли с LR-парсингом и достигают улучшения на порядок величины.

ОКамм

Simple Earley Реализация простого алгоритма синтаксического анализа, подобного алгоритму Earley, с документацией.

Ржавчина

Santiago – инструментарий для лексического и синтаксического анализа для Rust, реализующий алгоритм Earley.

Вольфрам

properEarleyParser Базовая минимальная реализация парсера Эрли на языке программирования Wolfram с несколькими основными тестами.