Распознаватель Earley для парсера Earley

Question

Мне удалось создать распознаватель Эрли, все отлично работает. У меня есть все правильные ситуации. Но я могу использовать его только для того, чтобы решить, принято ли слово грамматикой. Как сделать это для разбора? Мне нужна статья или объяснение, мне кажется, мне нужно создавать ассоциации с ситуациями, в которых возникли новые ситуации. Любая помощь будет оценена.

Моя реализация основана именно на: http://www.cs.uvic.ca/~nigelh/Publications/PracticalEarleyParsing.pdf

Answer 1

Всякий раз, когда вы делаете вывод, следите за тем, откуда вы пришли, т.е. какие предметы использовались для формирования нового предмета. Затем можно найти лес синтаксического анализа, исследуя верхний элемент, охватывающий весь ввод. Если вы анализируете неоднозначные грамматики, вы должны также рассмотреть возможность упаковки неоднозначности, т.е. не рекомбинируйте (локально) эквивалентные анализы вместе.

Я действительно рекомендую превосходную книгу Клааса Сиккеля "Парсинг Схемы" для теоретической стороны вещей.

Answer 2

Разобрать генерацию леса у распознавателей Earley сложно. Есть статья "Распознавание не разбирается - разбор в стиле SPPF от кубических распознавателей", в котором объясняется, что версия синтаксического анализатора Earley неверна, а затем показано, как генерировать леса синтаксического анализа из распознавателей Earley.

http://www.sciencedirect.com/science/article/pii/S0167642309000951