Hace poco estuve leyendo sobre el analizador Earley y creo que es uno de los algoritmos más elegantes que he visto hasta la fecha. Sin embargo, el algoritmo en su sentido tradicional es un reconocedor y no un analizador, lo que significa que puede detectar si una cadena coincide con un CFG particular pero no produce un árbol de análisis para él. Mi pregunta es cómo recuperar no un árbol de análisis , sino más bien el bosque de análisis de todos los análisis posibles de la cadena de entrada dada.
En "Técnicas de análisis: una guía práctica" de Grune y Jacob, ilustran un algoritmo que se puede utilizar para recuperar un bosque de análisis del resultado del reconocedor Earley, pero se basa en el método de análisis de Unger, cuyo tiempo de ejecución es O (n k + 1 ), donde k es la longitud de la producción más larga de la gramática. Esto significa que el tiempo de ejecución no es un polinomio en el tamaño de la gramática. Además, el documento original de Earley sobre el algoritmo, que sugiere un algoritmo para recuperar bosques de análisis, es incorrecto (ver, por ejemplo, la página 762 de este artículo de Tomita), aunque muchas fuentes todavía lo citan como la forma adecuada de recuperar el bosque de análisis. .
Mi pregunta es si es posible, en tiempo polinómico, recuperar un bosque de análisis para una cadena de entrada dada. He encontrado un documento aquí que proporciona un algoritmo para producir representaciones de bosque de análisis de tamaño cúbico para cualquier análisis utilizando una simulación de un PDA, por lo que parece que debería ser posible, pero aún no he encontrado ninguna manera de hacerlo. Idealmente, me gustaría hacer esto sin convertir la gramática de entrada a CNF (que de hecho resolvería el problema), ya que el bosque de análisis resultante sería bastante desordenado.
¡Gracias por cualquier ayuda que pueda ofrecer!
fuente
Respuestas:
Hacerlo, por supuesto, dependería de la representación correcta para un "bosque empaquetado" que represente todos los árboles de análisis para una oración dada.
Creo que el lugar donde desea comenzar a buscar es la tesis de Joshua Goodman (análisis de adentro hacia afuera, Harvard, 1999). Básicamente, la idea es que puede definir un algoritmo de análisis bajo un cierto semiring. Dependiendo de la semisección, podrá calcular todo tipo de cantidades y estructuras en lugar del árbol de análisis simple (como un reconocedor o un analizador sintáctico). Un semiring que podría definir (que Goodman hace en su tesis) es un semiring donde los valores son conjuntos de análisis. Cuando finalmente termine de analizar una oración, obtendrá todos los árboles de análisis en el nodo de análisis principal.
Nuevamente, debes tener cuidado de hacerlo posible a través de la representación correcta.
fuente
Hay un documento que describe cómo hacerlo:
Análisis estilo SPPF de Earley Recognisers por Elisabeth Scott
Describe cómo construir un bosque de análisis binarizado en tiempo cúbico.
fuente
Nunca necesitas CNF. Tiene el inconveniente de cambiar la estructura gramatical. Pero debe introducir no terminales intermedios para que ningún lado derecho sea más largo que 2 (2 formas) ya que la longitud de RHS determina la complejidad. El mejor intento de explicar eso intuitivamente es, si la memoria sirve, un documento de Beau Shiel, "Observaciones sobre el análisis libre de contexto", publicado en 1976 en una conferencia de lingüística computacional. El algoritmo de Earley usa la forma 2 implícitamente. Simplemente está oculto en el algoritmo. Con respecto a la recuperación y el manejo del bosque de análisis, debe buscar en la web "bosque de intersección de análisis". En realidad es muy sencillo. Muchos documentos están en la web, si obtiene (de citas o tablas de contenido) los títulos o autores para buscarlos directamente.
En realidad, puedes hacer mucho más que CF, y aún así obtener bosques parse en tiempo polinómico. La pregunta es, a veces: ¿qué puedes hacer con él una vez que lo tienes?
Un propósito del último artículo que menciona es mostrar que los algoritmos complejos (como GLR) no necesariamente compran nada en el tiempo o en el espacio, y pueden cambiar su bosque de análisis.
Un comentario sobre la enseñanza. Creo que Earley, seminal como era, es demasiado complicado para la enseñanza, y podría ser reemplazado por algoritmos más simples con esencialmente el mismo contenido educativo. La enseñanza se trata de conceptos o tecnología. En el algoritmo de Earley, los conceptos esenciales están ocultos en la complejidad de los detalles, y desde el punto de vista tecnológico está desactualizado. Fue un gran trabajo, pero no significa que sea el mejor enfoque pedagógico.
Puede haber más información en la literatura de lingüística computacional que en los canales informáticos habituales. No tengo el libro de Ceriel-Grune-Jacobs, pero me sorprendería que no tuvieran todas las referencias adecuadas (aunque no estoy seguro de sus criterios de selección).
Complemento después de una solicitud en un comentario (7 de julio de 2013)
Este complemento concorda la existencia de algoritmos más simples que los de Earley.
Como dije, buscar en la web el "bosque de intersección de análisis" debería darle rápidamente referencias, desde las cuales puede profundizar más.
La idea básica es que todos los caminos que se analizan con la construcción de un bosque compartido no son más que la antigua construcción de intersección de Bar Hillel, Perles y Shamir para un lenguaje regular y un lenguaje libre de contexto, utilizando un autómata finito y una gramática libre de contexto. Dada la gramática CF, aplica la construcción a un autómata trivial que reconoce solo su cadena de entrada. Eso es todo. El bosque compartido es solo la gramática de la intersección. Está relacionado con la gramática original a través de un homomorfismo, reconoce solo la cadena dada, pero con todos los árboles de análisis de la gramática original hasta ese homomorfismo (es decir, el cambio de nombre simple de no terminales).
La gramática resultante contiene muchas cosas inútiles, no terminales y reglas, que son inalcanzables desde el axioma (que no se encuentran en una cadena derivada del símbolo inicial) o que no son productivas (no pueden derivarse en un terminal cuerda).
Luego, o debe limpiarlo con un buen cepillo al final (posiblemente largo pero algorítmicamente simple), o puede intentar mejorar la construcción para que haya menos pelusa inútil para cepillar al final.
Por ejemplo, la construcción de CYK es exactamente eso, pero está organizada para que todas las reglas y no terminales creadas sean productivas, aunque muchas pueden ser inalcanzables. Esto es de esperar de una técnica de abajo hacia arriba.
Las técnicas de arriba hacia abajo (como las basadas en LR (k)) evitarán reglas inalcanzables y no terminales, pero crearán reglas improductivas.
Creo que gran parte del cepillado se puede lograr mediante el uso adecuado de punteros, pero no lo he visto en mucho tiempo.
Todos los algoritmos existentes realmente siguen esencialmente ese modelo. Así que ese es realmente el meollo del asunto, y es muy simple. Entonces, ¿por qué enterrarlo en complejidad?
Se proponen muchas "optimizaciones" en la literatura a menudo basadas en la familia LR (k), LL (k) de la construcción del analizador, posiblemente con algo de factorización estática de estas construcciones (Earley no tiene factorización estática). En realidad, podría aplicarse a todas las técnicas conocidas, incluidos los analizadores de precedencia antiguos. Puse "optimización" entre comillas porque generalmente no está claro qué está optimizando, o incluso si realmente lo está optimizando, o si el beneficio de la mejora vale la complejidad adicional de su analizador. Encontrará pocos datos objetivos, formales o experimentales, sobre esto (hay algunos), pero muchas más afirmaciones. No digo que no haya nada de interés. Hay algunas ideas inteligentes.
Ahora, una vez que conozca la idea básica, las "optimizaciones" o mejoras a menudo se pueden introducir de forma estática (posiblemente de forma incremental) mediante la construcción de un autómata push-down a partir de la gramática, siguiendo el tipo de técnica de construcción del analizador que le interesa y luego aplicando la construcción de productos cruzados para la intersección con ese autómata (casi lo mismo que hacerlo con la gramática) o con una gramática derivada de ese autómata.
Luego puede introducir campanas y silbatos, pero eso es principalmente detalles tecnológicos.
La Philosophiæ Naturalis Principia Mathematica de Isaac Newton es una gran pieza de física y matemáticas. No creo que esté en la lista de lectura de muchos estudiantes. En igualdad de condiciones, no creo que sea muy útil enseñar el algoritmo de Earley, aunque es una pieza histórica importante. Los estudiantes tienen suficiente para aprender como es. A riesgo de ser derribado por muchas personas, pienso lo mismo para el artículo Knuth LR (k). Es una excelente pieza de análisis teórico, y probablemente una lectura importante para un teórico. Dudo mucho que sea tan esencial para la construcción de analizadores dado el estado actual de la tecnología, tanto de hardware como de software. Los tiempos pasaron cuando el análisis fue una parte importante del tiempo de compilación, o cuando la velocidad de los compiladores era un problema crítico (conocía a una corporación que murió por los costos de compilación hace unos 30 años). El especialista en análisis puede querer aprender ese conocimiento especializado en algún momento, pero el estudiante promedio en informática, programación o ingeniería no lo necesita.
Si los estudiantes deben pasar más tiempo analizando, hay otras extensiones que podrían ser más útiles y más formativas, como las que se usan en la lingüística computacional. El primer papel de la enseñanza es extraer las ideas simples que estructuran el conocimiento científico, no forzar a los estudiantes a sufrir lo que los científicos de investigación tuvieron que sufrir (excepto los estudiantes de doctorado: es un rito de iniciación :-).
Licencia CC BY-SA 3.0 del autor
fuente
El documento que describe cómo construir un bosque de análisis binarizado en tiempo cúbico (mencionado en la publicación de Angelo Borsotti) es: "Análisis de estilo SPPF de Earley Recognizers" por Elizabeth Scott. Puede encontrarlo aquí: http://dx.doi.org/10.1016/j.entcs.2008.03.044
En este artículo se describe la construcción de un bosque de análisis compactado (SPPF) que representa todos los posibles árboles de análisis. Los subárboles se comparten siempre que sea posible, y los nodos correspondientes a diferentes derivaciones de la misma subcadena a partir del mismo no terminal se combinan.
fuente
Me gustaría hacer eco de las respuestas anteriores sugiriendo que lea este documento:
Sin embargo, me gustaría calificar diciendo que he implementado el algoritmo en este documento y creo que hay un error. En particular, la primera oración del segundo párrafo de la sección 4. Las etiquetas predecesoras que haga para lo que Earley llamaría la fase de "escaneo" deberían apuntar de p a q y no al revés.
En particular, la siguiente línea:
Debe leer "de p a q" y no "de q a p"
Implementé el algoritmo como se dice originalmente, lo que me dio errores en algunos casos de prueba hechos a mano, que se solucionaron una vez que cambié la dirección del puntero aquí.
fuente