Árbol de punteros padre

En informática , un árbol de punteros internos o de padres es una estructura de datos de árbol N -ario en la que cada nodo tiene un puntero a su nodo padre , pero ningún puntero a los nodos hijos . Cuando se utiliza para implementar un conjunto de pilas , la estructura se denomina pila de espagueti , pila de cactus o pila de saguaro (por el saguaro , un tipo de cactus). ^{[ 1 ]} Los árboles de punteros de padres también se utilizan como estructuras de datos de conjuntos disjuntos .

La estructura puede considerarse como un conjunto de listas enlazadas simples que comparten parte de su estructura, en particular, sus colas. Desde cualquier nodo, se puede acceder a sus ancestros, pero no a ningún otro nodo.

Un compilador para un lenguaje como C crea una pila de símbolos compleja al abrir y cerrar tablas de símbolos que representan ámbitos de bloques . Cuando se abre un nuevo ámbito de bloque, se inserta una tabla de símbolos en la pila. Al encontrar la llave de cierre, el ámbito se cierra y la tabla de símbolos se extrae. Sin embargo, esta tabla de símbolos se conserva, en lugar de destruirse, y recuerda su tabla de símbolos "padre" de nivel superior, y así sucesivamente. De este modo, cuando el compilador realiza posteriormente traducciones sobre el árbol de sintaxis abstracta , para cualquier expresión dada, puede recuperar la tabla de símbolos que representa el entorno de dicha expresión y resolver referencias a identificadores. Si la expresión hace referencia a una variable X, primero se busca en la tabla de símbolos hoja que representa el ámbito léxico más interno, luego en la tabla padre, y así sucesivamente.

El término pila de espaguetis está estrechamente relacionado con las implementaciones de lenguajes de programación que admiten continuaciones . Las pilas de espaguetis se utilizan para implementar la pila de ejecución real que contiene las vinculaciones de variables y otras características del entorno. Cuando se deben admitir continuaciones, las variables locales de una función no se pueden destruir cuando esta finaliza: una continuación guardada puede volver a entrar en esa función y esperará no solo que las variables estén intactas, sino también que toda la pila esté presente para que la función pueda volver a finalizar. Para resolver este problema, los marcos de pila se pueden asignar dinámicamente en una estructura de pila de espaguetis y simplemente dejarlos para que el recolector de basura los elimine cuando ninguna continuación los utilice. Este tipo de estructura también resuelve los problemas de argumentos de funciones ascendentes y descendentes , lo que permite implementar fácilmente cierres léxicos de primera clase en este sustrato.

Ejemplos de lenguajes que utilizan pilas de espagueti son:

• Lenguajes que tienen continuaciones de primera clase como Scheme y Standard ML de Nueva Jersey.
• Lenguajes en los que la pila de ejecución puede ser inspeccionada y modificada en tiempo de ejecución, como por ejemplo:
  • Charla informal
  • Félix
  • Cilk

Las computadoras centrales que utilizan la arquitectura del conjunto de instrucciones del Burroughs B6500 y sus sucesores , con el sistema operativo MCP , pueden generar múltiples tareas dentro del mismo programa. Dado que originalmente eran sistemas basados ​​en ALGOL , deben admitir funciones anidadas , lo que resulta en una bifurcación en la pila que Burroughs describió informalmente como una "pila saguaro".

• Estructura de datos persistente