Pourquoi Tomita a créé GLR et n'a pas utilisé Earley?

11

Quand je regarde l'analyse Earley, elle a l'air très élégante, et je me demande pourquoi les techniques GLR deviennent populaires? Est-ce que quelqu'un sait ce qui n'allait pas avec Earley en analysant que Tomita a créé GLR? Performance? Toute publication sur ces discussions est très appréciée.

Wickoo
la source
5
GLR permet une analyse déterministe sur des parties de la grammaire. Voir par exemple Elkhound ( scottmcpeak.com/elkhound ), où cette idée est adoptée. Pour les langues naturelles cependant, il n'est pas si clair que GLR soit meilleur qu'Earley.
Sylvain
1
@Sylvain: sonne comme une réponse pour moi ...
Joshua Grochow

Réponses:

5

Mieux vaut tard que jamais.

Si je comprends bien, Earley est de haut en bas et passera du temps et de la mémoire à créer des articles Earley pour chaque production à un S (i) donné. Cela signifie que pour le langage naturel, dans S (0), nous créons et vérifions un élément Earley pour chaque mot possible qui commence une phrase, et il y en a beaucoup.

Mais GLR est de bas en haut, donc en supposant des recherches de table / état hachées efficacement, le premier jeton sélectionne la ou les transitions suivantes en temps constant.

Cela est vrai spécifiquement pour les langues naturelles, avec le grand nombre de productions distinctes. Mais pas vraiment significatif pour les langages de programmation, avec le très petit ensemble de productions.

Jeff
la source