python - Earley 解析器递归

Question

Earley 解析器是否有预期的简单循环问题？

我已经做了自己的实现，但它与这个非常相似，可读性很强，总共大约 150 行(当然，我没有写它):

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

我觉得那个不错，并且在提供的测试用例中工作得很好，但是语法非常简单

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

好像不行。它应该生成任意数量的“ident”标记，假设 E 是起始非终端而 ident 是终端。但是这个语法，以及任何类似风格的语法，都被解析器完全忽略了。

这是 Earley 算法中的问题(我认为不是)，还是这个实现中的问题；如果它是基于实现的，是否有(相对)简单的解决方案或是否需要重建算法？

Answer 1

是的，这种规则组存在预期的问题:

X1::= X2

X2::= X3

...

Xn::= X1

在这种情况下，如果您不检查已经添加到 Earley 图表的状态，算法可能会进入无限递归循环。

在您上面介绍的情况下，它不能进入​​无限循环，因为规则 E::= E E 的扩展将受到您输入的限制。在此处检查实现情况:

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

我已经使用过这个实现，它运行良好。