Earley解析器递归
Earley解析器在处理简单循环时会有预期的问题吗？
我自己做了一个实现，但跟这个差不多，这个实现很容易读，大约150行代码（当然，这不是我写的）：
http://www.nightmare.com/rushing/python/earley.py
我觉得这个看起来不错，在提供的测试案例中运行得很好，但这个非常简单的语法
E : [[E,E],[ident]]
似乎不太管用。它应该能生成任意数量的“ident”标记，假设E是起始非终结符，而ident是终结符。但这个语法，以及任何类似风格的语法，解析器完全没有处理。
这是Earley算法的问题吗（我觉得不是），还是这个实现的问题；如果是实现方面的问题，有没有（相对）简单的解决办法，还是说需要重建算法？
1 个回答
2
是的，这里有一个预期的问题，涉及到一些规则的组合，比如：
X1 ::= X2
X2 ::= X3
...
Xn ::= X1
在这种情况下，如果你没有检查已经添加到Earley图表的状态，算法可能会陷入无限递归的循环。
不过在你上面提到的情况中，它不会进入无限循环，因为规则E ::= E E的扩展会受到你输入的限制。你可以在这里查看具体的实现：
https://en.wikipedia.org/wiki/Earley_parser#The_algorithm
我已经使用过这个实现，它运行得很好。