Практический разбор Earley (Aycock & Horspool 2002): Как добавить обратные указатели?

Question

Я уже кодировал парсер Earley с указателями назад, но он не очень хорошо обрабатывает грамматику, допускающую обнуление. Я также реализовал решение Aycock & Horspool 2002, которое позволяет PREDICT пропускать нетерминальный токен, если он обнуляем. К сожалению, это не говорит вам, какой именно путь должен пройти токен, чтобы попасть в эпсилон.

Моя идея (довольно глупо):

Для каждого недействительного нетерминала создайте список путей для этого нетерминала, чтобы добраться до epsilon.

Каждый раз, когда вы пропускаете обнуляемый нетерминал, добавляйте обратный указатель с именем NULL.

Когда вы расширяете дерево, каждый раз, когда вы сталкиваетесь с NULL, вы создаете список деревьев, по одному для каждого пути в списке для этого обнуляемого нетерминала.

Наконец, вы просматриваете список деревьев и избавляетесь от дубликатов.

Я думаю, что это значительно увеличило бы временную сложность моего алгоритма, но я не могу придумать более эффективный метод для генерации всех возможных деревьев разбора.

Кто-нибудь может предложить более эффективный метод реализации Aycock & Horspool 2002 для создания деревьев разбора?

Answer 1

Вы слышали о Марпе?

В основном это улучшения, сделанные Эрли, Айкоком, Хорспулом и Лео, авторами (Джеффри Кеглером).

Возможно, вас заинтересует раздел " Теория " в блоге автора и статья автора о Марпе.

Надеюсь это поможет.