¿Cómo implementar una pila estructurada por gráficos?

Question

Ok, entonces me gustaría hacer un generador de analizadores GLR. Sé que existen tales programas mejor de lo que probablemente haré, pero lo hago por diversión/aprendizaje, así que eso no es importante.

He estado leyendo sobre el análisis de GLR y creo que ahora tengo una comprensión de alto nivel decente. Pero ahora es el momento de ponerse a trabajar.

La pila estructurada por gráficos (GSS) es la estructura de datos clave para usar en los analizadores GLR. Conceptualmente, sé cómo funciona GSS, pero ninguna de las fuentes que analicé hasta ahora explica cómo implementar GSS. Ni siquiera tengo una lista autorizada de operaciones para apoyar. ¿Alguien puede indicarme algún buen código de muestra/tutorial para GSS? Google no ayudó hasta ahora. Espero que esta pregunta no sea demasiado vaga.

Answer 1

La pregunta que hace no es trivial. Veo dos formas principales de hacer esto:

1. La representación directa. Su estructura de datos se representa en la memoria como objetos/estructuras de nodo, donde cada nodo tiene una referencia/puntero a las estructuras debajo de él en la pila (también se pueden hacer las referencias bidireccionales, como alternativa). Esta es la forma en que las listas y los árboles se representan normalmente en la memoria. Es un poco más complicado en este caso, porque a diferencia de un árbol o una lista, donde uno solo necesita mantener una referencia al nodo raíz o nodo principal para realizar un seguimiento del árbol, aquí tendríamos que mantener una lista de referencias a todos los nodos de "nivel superior".

2. La representación de la lista de adyacencia. Esto es similar a la forma en que a los matemáticos les gusta pensar en gráficos: G = (V, E). Mantiene una lista de bordes, indexados por los vértices que son el origen y los puntos de terminación para cada borde.

La primera opción tiene la ventaja de que la travesía puede ser más rápida, siempre que el GSS no sea demasiado plano. Pero la estructura es un poco más difícil de trabajar. Tendrás que lanzar muchos de tus propios algoritmos.

La segunda opción tiene la ventaja de ser más sencilla para trabajar. La mayoría de los algoritmos en los libros de texto parecen asumir algún tipo de representación de listas de adyacencia, lo que hace que sea más fácil aplicar la riqueza de los algoritmos de gráficos que existen.

Algunos recursos:

Hay varios tipos de lista de adyacencia, por ejemplo, basada en tablas hash, basadas en arreglos, etc. La página wikipedia adjacency list es un buen lugar para comenzar.

Here's a blog post de alguien que ha estado lidiando con el mismo problema. El código es clojure, que puede o no ser familiar, pero merece la pena examinar la discusión, incluso si no.

Debo mencionar que creo que me gustaría que hubiera más información sobre la representación de Gráficos acíclicos dirigidos (o Gráficos de pilas estructuradas, si lo prefiere), dada la amplia aplicación de este tipo de modelo. Creo que hay espacio para encontrar mejores soluciones.

Answer 2

En primer lugar, si no lo ha hecho ya, debe leer el artículo de McPeak sobre GLR http://www.cs.berkeley.edu/~smcpeak/papers/elkhound_cc04.ps. Es un documento académico, pero brinda buenos detalles sobre GSS, GLR y las técnicas utilizadas para implementarlos. También explica algunos de los problemas peludos con la implementación de un analizador GLR.

Tiene tres partes para implementar una pila estructurada por gráficos.

I. La estructura de datos de gráfico en sí

II. Las pilas

III. Uso de GLR de un GSS

Tienes razón, google no es de mucha ayuda. Y a menos que le guste leer libros de algoritmos, tampoco serán de mucha ayuda.

I. La estructura de datos del gráfico

respuesta de Rob sobre "la representación directa" sería más fácil de implementar. Se parece mucho a una lista enlazada, excepto que cada nodo tiene una lista de los siguientes nodos en lugar de uno solo.

Esta estructura de datos es un gráfico dirigido, pero como dice McPeak, el GSS puede tener ciclos para epsilon-gramáticas.

II. Las pilas

Una pila estructurada por gráficos es conceptualmente solo una lista de pilas regulares. Para una gramática no ambigua, solo necesitas una pila. Necesitas más stacks cuando hay un conflicto de análisis para que puedas tomar ambas acciones de análisis al mismo tiempo y mantener el diferente estado que crean ambas acciones. El uso de un gráfico le permite aprovechar el hecho de que estas pilas comparten elementos.

Puede ser útil comprender cómo implementar una única pila con una lista vinculada primero. El encabezado de la lista enlazada es la parte superior de la pila. Al presionar un elemento en la pila solo se crea una nueva cabeza y se apunta a la cabeza anterior. Saltar un elemento de la pila es simplemente mover el puntero a la cabeza-> siguiente.

En un GSS, el principio es el mismo. Presionar un elemento es simplemente crear un nuevo nodo principal y apuntarlo a la cabeza anterior. Si tiene dos operaciones de cambio, empujará dos elementos en la cabeza anterior y luego tendrá dos nodos de cabeza. Conceptualmente, esto es solo dos pilas diferentes que suceden comparten cada elemento excepto los superiores. Hacer estallar un elemento es simplemente mover el puntero de la cabeza por la pila siguiendo cada uno de los siguientes nodos.

III. Uso de GLR del GSS

Aquí es donde el documento de McPeak es una lectura útil.

El algoritmo GLR aprovecha el GSS fusionando los cabezales de pila que tienen el mismo elemento de estado. Esto significa que un elemento de estado puede tener más de un hijo. Al reducir, el algoritmo GLR tendrá que explorar todas las rutas posibles desde el cabezal de pila.

Puede optimizar GLR manteniendo la profundidad determinista de cada nodo. Esta es solo la distancia desde una división en la pila. De esta forma, no siempre tiene que buscar una división de pila.

¡Esta es una tarea difícil! ¡Buena suerte!