Earley 无法处理图表中已包含的 epsilon 状态
Earley cannot handle epsilon-states already contained in chart
我已经实现了 Earley parser 使用队列来处理状态。该队列使用顶级规则播种。对于队列中的每个状态，其中一个操作（预测、扫描、完成）是通过向队列中添加新状态来执行的。 不添加重复状态。
我遇到的问题最好用以下语法来描述：
解析 A 时，会发生以下情况：
如您所知，A 不会完全解析。这是因为 epsilon 状态的完成只会发生一次，因为它不会添加到队列中。
如何调整我的算法以支持这些 epsilon 状态？
编辑：请注意，使用终端时这不是问题，因为将创建新图表集以插入扫描状态。由于该状态不存在，因此将对其进行处理。
在 John Aycock 和 R. Nigel Horspool 的论文 "Practical Earley Parsing" 中，作者提出以下方法作为处理可空非终结符的方法：
If [A→ ... •B ..., j] is in Si, add [B→ • a, i]
to Si for all rules B → a.
If B is nullable, also add [A → ... B • ..., j] to Si.
（强调原文。）因此在您的示例中，在 A→ • B B 的预测中，将产生以下规则：
(1) B → •
(2) A → B • B
(3) A → B B •
关键是这发生在预测阶段。在预测阶段，如果 'post dot' 符号可以为空（直接和通过转移），则将点向右移动并添加该规则。
所以基本上：
A → • B B 产生 (B → • 和 A → B • B ) 每个都在排队和处理
A → B • B 生成 (A → B B •) 并进行排队和处理
我已经实现了 Earley parser 使用队列来处理状态。该队列使用顶级规则播种。对于队列中的每个状态，其中一个操作（预测、扫描、完成）是通过向队列中添加新状态来执行的。 不添加重复状态。
我遇到的问题最好用以下语法来描述：
解析 A 时，会发生以下情况：
如您所知，A 不会完全解析。这是因为 epsilon 状态的完成只会发生一次，因为它不会添加到队列中。
如何调整我的算法以支持这些 epsilon 状态？
编辑：请注意，使用终端时这不是问题，因为将创建新图表集以插入扫描状态。由于该状态不存在，因此将对其进行处理。
在 John Aycock 和 R. Nigel Horspool 的论文 "Practical Earley Parsing" 中，作者提出以下方法作为处理可空非终结符的方法：
If [A→ ... •B ..., j] is in Si, add [B→ • a, i] to Si for all rules B → a. If B is nullable, also add [A → ... B • ..., j] to Si.
（强调原文。）因此在您的示例中，在 A→ • B B 的预测中，将产生以下规则：
(1) B → •(2) A → B • B
(3) A → B B •
关键是这发生在预测阶段。在预测阶段，如果 'post dot' 符号可以为空（直接和通过转移），则将点向右移动并添加该规则。
所以基本上：
A → • B B 产生 (B → • 和 A → B • B ) 每个都在排队和处理
A → B • B 生成 (A → B B •) 并进行排队和处理