Cuando miro el análisis de Earley, se ve muy elegante, y me pregunto por qué las técnicas GLR se vuelven populares. ¿Alguien sabe qué estaba mal con Earley al analizar que Tomita creó GLR? ¿Actuación? Cualquier publicación sobre estas discusiones es muy apreciada.
11
Respuestas:
Mejor tarde que nunca.
Si entiendo correctamente, Earley es de arriba hacia abajo y pasará tiempo y memoria creando artículos de Earley para cada producción en un S (i) dado. Esto significa que para el lenguaje natural, en S (0) creamos y verificamos un elemento Earley para cada palabra posible que comienza una oración, y hay bastantes de ellas.
Pero GLR es de abajo hacia arriba, por lo que suponiendo búsquedas de tabla / estado hash eficientemente, el primer token selecciona las siguientes transiciones en tiempo constante.
Esto es cierto específicamente para los lenguajes naturales, con la gran cantidad de producciones distintas. Pero no es realmente significativo para los lenguajes de programación, con el muy pequeño conjunto de producciones.
fuente