compiler construction - Recursos de algoritmo de análisis GLR
compiler-construction parsing (4)
Adrian Johnstone publica mucho trabajo sobre versiones avanzadas de algoritmos GLR. Su sitio web de publicaciones probablemente será un recurso interesante.
Estoy escribiendo un generador de analizador GLR y me gustaría recibir algunos consejos sobre los recursos relacionados con este algoritmo tanto en Internet como en la variedad de árboles muertos (libros para aquellos que no están familiarizados con el habla geek).
Sé que Bison puede generar analizadores GLR, y dado que está bajo la GPL puedo examinar su código, sin embargo, sería bueno tener una descripción completa del algoritmo.
Entonces, ¿alguien sabe de algún buen recurso que pueda usar? Gracias.
Algunas cosas buenas que he encontrado antes en línea:
- un artículo sobre Elkhound , otro analizador GLR de código abierto: Scott McPeak, George C. Necula. Elkhound: un generador rápido y práctico de analizador GLR . En Actas de la Conferencia sobre Constructor de Compiladores (CC04), abril de 2004.
y para más detalles:
- el informe técnico UCB / CSSD-2-1214 , que es una versión ampliada del documento anterior;
- el documento al que se hace referencia en la documentación de Bison : Elizabeth Scott, Adrian Johnstone y Shamsa Sadaf Hussain. Analizadores de LR generalizados estilo Tomita . TR-00-12, Royal Holloway, Universidad de Londres, Departamento de Ciencias de la Computación, diciembre de 2000.
Y sé de un tercer analizador GLR de código abierto: DParser .
La mejor descripción que he visto, con imágenes que ilustran cada paso del algoritmo, se encuentra en este libro:
Para pseudocódigo, vaya a la fuente: LR Generalized Parsing by Tomita, página 70 o menos. El artículo de Farshi contiene una descripción compacta.
Es una de las técnicas que probé para qb.js ( qbasic en javascript ).
Por lo que sé, funciona igual que un analizador LALR, excepto cuando encuentra una ambigüedad.
Cuando lo hace, esencialmente se divide en análisis separados correspondientes a las posibles opciones en ese punto, y continúa con ellos en tándem: cuando un análisis falla (debido a encontrar un elemento ilegal), simplemente se elimina, porque debe haber sido un Supongo mal en una ambigüedad anterior.
Al final, todos menos un análisis deberían haber muerto, y el que sobrevive es el análisis "correcto" de esos puntos ambiguos.