algorithm - Earley 无法处理图表中已包含的 epsilon 状态

Question

我已经实现了 Earley parser使用队列来处理状态。该队列使用顶级规则播种。对于队列中的每个状态，其中一个操作(预测、扫描、完成)是通过向队列中添加新状态来执行的。 不添加重复状态。

我遇到的问题最好用以下语法来描述:

当解析 A 时，会发生以下情况:

如您所知，A 不会完全解析。这是因为 epsilon 状态的完成只会发生一次，因为它不会添加到队列中。

我如何调整我的算法以支持这些 epsilon 状态？

编辑:请注意，使用终端时这不是问题，因为将创建新图表集以插入扫描状态。由于该状态不存在，因此将对其进行处理。

Answer 1

论文中"Practical Earley Parsing"由 John Aycock 和 R. Nigel Horspool 提出，作者提出以下方法作为处理可空非终结符的方法:

If [A→ ... •B ..., j] is in S_i, add [B→ • a, i]to S_i for all rules B → a.If B is nullable, also add [A → ... B • ..., j] to S_i.

(强调原文。)所以在你的例子中，在A→ • B B 的预测中会产生以下规则:

(1) B → •
(2) A → B • B
(3) A → B B •

关键是这发生在预测阶段。在预测阶段，如果“点后”符号可以为空(直接和通过转移)，则将点向右移动并添加该规则。

所以基本上:

A → • B B 产生(B → • 和A → B • B)每个都在排队和处理
A → B • B 产生 (A → B B • )，它被排队和处理