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.
11
Réponses:
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.
la source