besoin d'une explication dans l'algorithme Earley

Question

Je serais très heureux si quelqu'un peut clairement pour moi par exemple mentionné ono wikipedia:

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

considèrent la grammaire:

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

et entrée:

2 + 3 * 4 

L'algorithme d'Earley fonctionne comme ceci:

(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) 

c'est seulement le premier ensemble S (0), mais ma question est: pourquoi algorithme prédit à partir (3) à l'étape (4) mais ommits prédiction de (2)?

J'espère que quelqu'un comprend idée et peut me aider

Answer 1

L'utilisation (2) pour la prédiction ne va pas créer de nouvelles productions, parce que le symbole à côté du point est S. Par conséquent, ne ferait que les productions se (2) et (3) encore, qui n'ajoutent aucune information.