En informática , un árbol de puntero principal o en árbol es una estructura de datos de árbol N -ary en la que cada nodo tiene un puntero a su nodo principal , pero no a los nodos secundarios . Cuando se usa para implementar un conjunto de pilas , la estructura se llama pila de espaguetis , pila de cactus o pila de sahuaro (después del sahuaro , una especie de cactus). [1] Los árboles de punteros principales también se utilizan como estructuras de datos de conjuntos disjuntos .
La estructura se puede considerar como un conjunto de listas enlazadas individualmente que comparten parte de su estructura, en particular, sus colas. Desde cualquier nodo, se puede atravesar a los antepasados del nodo, pero no a ningún otro nodo.
Usar en compiladores
Un compilador para un lenguaje como C crea una pila de espaguetis a medida que abre y cierra tablas de símbolos que representan ámbitos de bloque . Cuando se abre un nuevo alcance de bloque, se coloca una tabla de símbolos en una pila. Cuando se encuentra la llave de cierre, se cierra el osciloscopio y se abre la tabla de símbolos. Pero esa tabla de símbolos se recuerda, en lugar de destruirse. Y, por supuesto, recuerda su tabla de símbolos "padre" de nivel superior y así sucesivamente. Por lo tanto, cuando el compilador realiza más tarde traducciones sobre el árbol de sintaxis abstracta , para cualquier expresión dada, puede buscar la tabla de símbolos que representa el entorno de esa expresión y puede resolver referencias a identificadores. Si la expresión se refiere a una variable X, primero se busca en la tabla de símbolos de hoja que representa el ámbito léxico más interno, luego en el padre y así sucesivamente.
Usar como pilas de llamadas
El término pila de espaguetis está estrechamente asociado con implementaciones de lenguajes de programación que admiten continuaciones . Las pilas de espagueti se utilizan para implementar la pila de tiempo de ejecución real que contiene enlaces de variables y otras características ambientales. Cuando se deben admitir continuaciones, las variables locales de una función no se pueden destruir cuando esa función regresa: una continuación guardada puede volver a ingresar más tarde en esa función, y esperará que no solo las variables estén intactas, sino que también esperará que toda la pila estar presente para que la función pueda volver de nuevo. Para resolver este problema, los marcos de pila se pueden asignar dinámicamente en una estructura de pila de espagueti, y simplemente dejarlos para que sean recolectados como basura cuando ya no haya continuaciones que los refieran. Este tipo de estructura también resuelve los problemas del funarg ascendente y descendente , como resultado, los cierres léxicos de primera clase se implementan fácilmente en ese sustrato.
Ejemplos de lenguajes que usan pilas de espaguetis son:
- Idiomas que tienen continuaciones de primera clase, como Scheme y Standard ML of New Jersey
- Idiomas en los que la pila de ejecución se puede inspeccionar y modificar en tiempo de ejecución, como Smalltalk
- Felix
- Cilk
Las computadoras mainframe que utilizan la arquitectura Burroughs Large Systems y ejecutan el sistema operativo MCP pueden generar múltiples tareas dentro del mismo programa. Dado que estos eran originalmente sistemas basados en ALGOL , por lo que deben admitir funciones anidadas , el resultado es que la creación de tareas da como resultado una bifurcación en la pila, que Burroughs describió informalmente como una "pila saguaro".
Ver también
Referencias
- ^ Clinger, W .; Hartheimer, A .; Ost, E. (1988). "Estrategias de implementación para continuaciones". Actas de la conferencia ACM de 1988 sobre LISP y programación funcional - LFP '88 . págs. 124-131. doi : 10.1145 / 62678.62692 . ISBN 089791273X.