parsing - 在 Earley 算法中需要一些解释

Question

如果有人可以为我说明 ono wikipedia 中提到的示例，我将非常高兴：

http://en.wikipedia.org/wiki/Earley_algorithm

考虑语法：

P → S      # the start rule
S → S + M | M
M → M * T | T
T → number

并输入：

2 + 3 * 4

Earley 算法的工作原理如下：

 (state no.) Production          (Origin) # Comment
 ---------------------------------
 == S(0): • 2 + 3 * 4 ==
 (1)  P → • S         (0)    # start rule
 (2)  S → • S + M     (0)    # predict from (1)
 (3)  S → • M         (0)    # predict from (1)
 (4)  M → • M * T     (0)    # predict from (3)

这只是第一组 S(0) 但我的问题是：为什么算法在步骤 (4) 中从 (3) 进行预测，但它忽略了 (2) 的预测？

我希望有人理解想法并可以帮助我

Answer 1

使用 (2) 进行预测不会产生新的产生式，因为点旁边的符号是 S。因此，只会再次得到产生式 (2) 和 (3)，不会添加信息。