recursos de algoritmo de análisis GLR

I am writing a GLR parser generator y me gustaría obtener 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 lenguaje geek).recursos de algoritmo de análisis GLR

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.

Fuente

2010-01-25 ljs

Proyecto muy bueno (Terse, no el generador de analizadores), voy a seguir su progreso con interés. –

Lamentablemente me han distraído muchas cosas, por lo que el proyecto se ha estancado pero ... ¡más trabajo comenzará pronto! – ljs

algunas cosas buenas que he encontrado antes en línea:

un artículo sobre Elkhound, otra fuente abierta GLR analizador Scott McPeak, George C. Necula. Elkhound: A Fast, Practical GLR Parser Generator. En las actas de la Conferencia sobre Compiler Constructor (CC04), abril de 2004.

y para más detalles:

la UCB/CSSD-2-1214 technical report, que es una versión ampliada del papel por encima;
el documento al que se hace referencia en el Bison documentation: Elizabeth Scott, Adrian Johnstone y Shamsa Sadaf Hussain. Tomita-Style Generalised LR Parsers. TR-00-12, Royal Holloway, Universidad de Londres, Departamento de Ciencias de la Computación, de diciembre de 2000.

Y sé de una tercera fuente abierta GLR analizador: DParser.

Fuente

2010-01-26 00:43:37

¡Excelente! Gracias. – ljs

Por lo que sé, funciona igual que un analizador LALR, excepto cuando se encuentra con una ambigüedad.

Cuando lo hace, esencialmente se divide en pares separados correspondientes a las opciones posibles en ese punto, y continúa con ellos en tándem: cuando un análisis falla (debido a encontrar un elemento ilegal), simplemente se cae, porque debe haber sido una suposición errónea de una ambigüedad anterior.

Al final, todos menos uno han muerto, y el que queda es el análisis "correcto" de esos puntos ambiguos.

Fuente

2010-01-25 00:30:10

¿Es realmente tan simple como eso?¿O hay algoritmos GLR alternativos específicos por ahí? – ljs

Eso es básicamente por mi lectura del manual de Bison (http://www.gnu.org/software/bison/manual/bison.html#GLR-Parsers). De hecho, es bastante claro cómo funcionan los analizadores de GLR. –

Puede que le resulte un poco más complicado que esto. –

La mejor descripción que he visto, con imágenes que ilustran cada paso del algoritmo, está contenida en este libro:

http://books.google.ca/books?id=05xA_d5dSwAC&lpg=PA381&dq=generalized%20deterministic%20parsers&pg=PA381#v=onepage&q=generalized%20deterministic%20parsers&f=false

Para pseudocódigo, ir a la fuente: Generalizado análisis sintáctico LR por Tomita, página 70 más o menos. El documento de Farshi contiene una descripción compacta.

http://books.google.ca/books?id=PvZiZiVqwHcC&lpg=PP1&dq=generalized%20lr%20parsing&pg=PA70#v=onepage&q=&f=false

Es una de las técnicas que probé para qb.js (qbasic in javascript).

Fuente

2010-03-09 13:44:56

Adrian Johnstone publica mucho trabajo en versiones avanzadas de algoritmos GLR. Su publications website probablemente sea un recurso interesante.

Fuente

2010-11-04 14:30:05

recursos de algoritmo de análisis GLR

Respuesta

Cuestiones relacionadas