¿Cómo reconstruyo el bosque de árboles de sintaxis del vector Earley?

9

Usar el vector Earley como un reconocedor es bastante sencillo: cuando se alcanza el final de la cadena, solo tiene que verificar si la producción axiomática completa comenzó en la posición 0. Si tiene al menos una, entonces se acepta la cadena.

Usar el vector Earley para reconstruir los árboles de análisis es menos obvio. En realidad, no puedo entender cómo funcionaría un procedimiento algorítmico, además, las únicas referencias que encontré eran vagas o super-técnicas. ¿Alguien podría arrojar algo de luz sobre eso?

Stefano Sanfilippo
fuente
2
Sería útil si enumerara las referencias que encontró, y que pensó que eran vagas, y que pensó que eran demasiado técnicas. De lo contrario, es probable que la respuesta sea un puntero a las referencias que ya encontró.
Wandering Logic
1
Puede ser que lo que llamas vector no sea lo que Earley llama vector en su artículo original. O puede ser que no juegue exactamente el mismo papel. Los autores introducen variaciones en los algoritmos. No hay forma de saberlo, ya que no da ninguna referencia a los documentos que ha estado utilizando ... y es posible que no tengamos acceso a ellos de todos modos. Lo que puede ayudar es ser más explícito sobre las definiciones. Al responder, supuse que usabas las mismas definiciones que Earley.
babou
@babou, lo que llamé "vector Earley" es la representación tabular de la estructura de datos construida por el analizador. Era el término utilizado por mi profesor de idiomas formales al referirse a él. Cabe señalar que mi idioma principal no es el inglés, por lo que esto podría ser solo un mal intento de traducir la terminología. La referencia técnica que mencioné es el artículo de Earley. Me acerqué, pero fue un poco intimidante para un verdadero principiante como yo.
Stefano Sanfilippo
Es posible que desee comprobar si su profesor utiliza "vector Earley" para referirse a la misma estructura que lo que Earley llama "vector" en su artículo. Puede ser útil para comunicarse. Por lo demás, como puede ver, debe mantener información adicional para poder recuperar los árboles de análisis, pero Earley realmente no entra en detalles. Ahora hay otros algoritmos y me temo que las complejidades del algoritmo de Earley ocultan de alguna manera las ideas clave de este tipo de técnicas. Buena suerte.
babou
¿Fue útil mi explicación o necesita una descripción más detallada de la parte técnica?
babou

Respuestas:

9

Estoy usando terminología y anotaciones del artículo de Earley . Es posible que la descripción que leas sea diferente.

Parece frecuente que los algoritmos generales de análisis de CF se presenten primero en forma de un reconocedor, y luego la gestión de la información necesaria para construir árboles de análisis y bosques de análisis se agrega como una idea de último momento. Una razón puede ser que mantener la información necesaria para construir el bosque compartido requiere un espacio cúbico donde n es la longitud de la cadena de entrada que se analiza, pero el requisito de espacio es solo el cuadrado O ( n 2 ) para el reconocimiento, cuando Esta información no se conserva. La razón de este aumento de la complejidad del espacio es bastante simple: el tamaño del bosque de análisis puede ser cúbico.O(n3)nO(n2)

O(n3)

O(ns+1)ses el tamaño de la regla más larga del lado derecho. Es por eso que otros algoritmos usan gramáticas en forma binaria (no necesariamente la Forma Normal de Chomsky (CNF)).

En realidad, Earley usa la forma binaria implícitamente , porque eso es necesario para la complejidad del tiempo cúbico. Este es uno de los principales roles de la regla punto en los estados. Pero esta forma binaria implícita produce parses y bosques de acuerdo con la gramática binarizada, no con la original, que, me temo, es una fuente importante de oscuridad. Esto se detalla más abajo.

Una buena manera de entender cómo se obtiene el bosque es probablemente mirarlo en un caso más simple, el algoritmo CYK . También se describe a menudo como un reconocedor, y el aspecto del analizador se agrega al final. Puedes mirar la descripción en wikipedia. La información necesaria para construir el bosque es lo que almacenan en la tabla de "backpointers". Los backpointers son esencialmente punteros a subcadenas (un símbolo asociado) que forman los constituyentes de una cadena de acuerdo con alguna regla. Dan todas las formas posibles de analizar una subcadena. Recuerde que CYK usa forma binaria, generalmente CNF, para que las cosas sean más simples. El analizador CYK tiene fundamentalmente la misma estructura de programación dinámica que Earley, pero es mucho más simple. Entonces comprenderlo bien puede ser de gran ayuda.

Volviendo al algoritmo de Earley, no creo que necesite el vector de Earley para decidir la aceptación o construir árboles y bosques. Lo que Earley llama vector en su artículo aparece solo en la página 97, en el tercer párrafo de la implementación. Es solo un dispositivo para acelerar la búsqueda de estados que apuntan hacia atrás en una determinada posición de cadena k, a fin de obtener una mejor complejidad. Pero toda la información está en los conjuntos de estados, implementados como listas de estados. Sin embargo, esta información no es suficiente para construir el bosque de árboles de análisis, porque el algoritmo no realiza un seguimiento de las formas en que se puede obtener un estado. De hecho, el vector incluso se usa para descartar eficientemente un estado ya encontrado, independientemente de cómo se encontró.

En la sección 7 del artículo de Earley, explica que para "convertir el reconocedor en un analizador sintáctico", es decir, para poder recuperar los árboles de análisis, es necesario realizar un seguimiento de la forma en que se realizan las terminaciones.

EαD.βgDDγ.fDγEαD.βgγD

fgfDγg

DEαD.βgwf+1gwf+1:gDDγDγ.fD

Suponiendo que mantuvo todos los punteros necesarios como se indica en el documento, puede obtener todas las representaciones de árbol compartidas a partir del último símbolo reconocido por el analizador, que por supuesto es el símbolo inicial de la gramática.

UXYZWUV

wf+1:gXwg+1:hYwh+1:iwh+1:jZUXYZwf+1:iwf+1:jU

wi+1:kwj+1:kVWUVwf+1:kW

wf+1:gwg+1:hXYUUXYZUXY.ZfShZWUV.fSk

Entonces, el bosque de árboles de sintaxis puede ser muy extraño, con una especie de subárboles gemelos siameses que pueden compartir los dos primeros bordes de algún nodo, pero no el tercer borde. En otras palabras, puede ser una estructura muy incómoda. Esto puede explicar por qué Earley lo llama " una representación factorizada de todos los posibles árboles de análisis ", sin ser más específico.

Cualquier intento de separar quirúrgicamente a los gemelos siameses, sin cambiar la gramática, dará como resultado una mayor complejidad. La forma correcta de hacerlo es binarizar la gramática.

Espero que esto ayude. Házmelo saber. Pero insisto en que una buena comprensión del análisis CYK puede ayudar. Existen otros algoritmos, más simples que los de Earley, que pueden analizar todos los lenguajes CF de manera eficiente.

Puede encontrar información más general sobre este tema del bosque de análisis en otras dos respuestas que di: /cstheory/7374#18006 y https://linguistics.stackexchange.com/questions/4619#6120 . Pero no entran en detalles específicos del algoritmo de Earley.

babou
fuente
Además del análisis CYK, también vale la pena analizar el análisis GLR.
Seudónimo
1
@ Seudónimo Conocer y comprender diversas formas de análisis general de la FQ ciertamente no hace daño, y sugiero lo mismo con las dos referencias al final de la respuesta. Sin embargo, mi elección de CYK no se debió al azar. Comparte con el algoritmo de Earley la propiedad de ser interpretativo, usando la gramática directamente, en lugar de usar tablas producidas compilando la gramática en un Automatismo Push-Down (como en GLR, GLL, GPrec). Por lo tanto, la relación entre el proceso de reconocimiento y la generación de árboles / bosques es más claramente visible. CKY es también el algoritmo más simple, con una excepción.
babou