нужно некоторое объяснение в алгоритме Эрли

Question

Я был бы очень рад, если бы кто-то смог прояснить для меня пример, упомянутый в Википедии:

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

Алгоритм Эрли работает следующим образом:

 (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), но мой вопрос: почему алгоритм прогнозирует из (3) на шаге (4)) но он пропускает предсказание из (2)?

Я надеюсь, что кто-то понимает идею и может помочь мне

Answer 1

Использование (2) для прогнозирования не приведет к созданию новых произведений, потому что символом рядом с точкой является S. Следовательно, будет только получать производные (2) и (3) снова, которые не добавляют информацию.