python - Earley 解析器递归

Question

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

我已经做了自己的实现，但它与这个非常相似，它非常易读，总共大约 150 行（当然，我没有写它）：

那个对我来说看起来不错，并且在提供的测试用例中完美运行，但是语法非常简单

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

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

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

score 1 · Accepted Answer

是的，它对以下类型的规则组有一个预期的问题：

X1 ::= X2

X2 ::= X3

...

Xn ::= X1

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

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

我已经使用了这个实现，它工作正常。

1 回答 1