Эрли Парсер Рекурсия

Question

У парлера Earley ожидаемые проблемы с простыми циклами?

Я сделал свою собственную реализацию, но она очень похожа на эту, которая очень удобочитаема и имеет в общей сложности около 150 строк (и я, конечно, не писал ее):

http://www.nightmare.com/rushing/python/earley.py

Это хорошо для меня выглядит и отлично работает в предоставленном тестовом примере, но очень простая грамматика

E : [[E,E],[ident]]

не похоже на работу. Он должен генерировать произвольное количество токенов "identif ", предполагая, что E является начальным нетерминалом, а identif ier является терминалом. Но эта грамматика и любая подобная грамматика стиля полностью игнорируются синтаксическим анализатором.

Это проблема в алгоритме Эрли (я так не думаю) или проблема в этой реализации; если это основано на реализации, есть ли (относительно) простое решение или алгоритм должен быть перестроен?

Answer 1

Да, у него ожидаемая проблема с группами правил такого рода:

X1:: = X2

X2:: = X3

...

Xn:: = X1

В этом случае алгоритм может войти в бесконечный цикл рекурсии, если вы не проверяете состояния, которые вы уже добавили в диаграмму Эрли.

В представленном выше случае он не должен входить в бесконечный цикл, так как расширения правила E::= E E будут ограничены вашим вводом. Проверьте реализацию здесь:

https://en.wikipedia.org/wiki/Earley_parser

Я уже использовал эту реализацию, и она отлично работает.