Earley не может обрабатывать эпсилон-состояния, уже содержащиеся в диаграмме

Question

Я реализовал парсер Earley, используя очередь для обработки состояний. Очередь засевается с помощью правила верхнего уровня. Для каждого состояния в очереди одна из операций (прогнозирование, сканирование, завершение) выполняется путем добавления новых состояний в очередь. Дубликаты состояний не добавляются.

Проблема, которую я имею, лучше всего описана следующей грамматикой:

B B; B -> эпсилон>

При разборе Aпроисходит следующее:

Как вы можете сказать, Aне будет полностью решена. Это связано с тем, что завершение с состоянием epsilon произойдет только один раз, поскольку оно не добавлено в очередь.

Как я могу адаптировать свой алгоритм для поддержки этих эпсилон-состояний?

Изменить: Обратите внимание, что это не проблема при использовании терминалов, поскольку будет создан новый набор диаграмм для вставки отсканированного состояния. Поскольку состояние там уже не существует, оно будет обработано.

Answer 1

В статье "Практический разбор Эрли" Джона Айкока и Р. Найджела Хорспула, спрятанной в разделе 4, содержится утверждение о том, как обращаться с правилами, допускающими обнуление:

Если [A→ ... •B ..., j] находится в S _i, добавьте [B→ • a, i]
в S _i для всех правил B → a.
Если B обнуляем, также добавьте [A → ... B • ..., j] к S _i

Итак, в вашем примере, в предсказании A → • BB будут получены следующие правила:

(1) B → •
(2) A → B • B
(3) A → BB •

Ключ в том, что это происходит на этапе прогнозирования. На этапе прогнозирования, если символ "после точки" обнуляется (как напрямую, так и посредством переноса), тогда переместите точку вправо и добавьте это правило.

Итак, в основном:

A → • BB производит (B → • и A → B • B), каждый из которых ставится в очередь и обрабатывается
A → B • B производит (A → BB •), который ставится в очередь и обрабатывается