В информатике дерево внутренних или родительских указателей — это N -арная древовидная структура данных , в которой каждый узел имеет указатель на свой родительский узел , но не имеет указателей на дочерние узлы . При использовании для реализации набора стеков структура называется спагетти-стеком , стеком кактусов или стеком сагуаро (в честь сагуаро — разновидности кактуса). [1] Деревья родительских указателей также используются как структуры данных непересекающихся множеств .
Структуру можно рассматривать как набор односвязных списков , которые разделяют часть своей структуры, в частности, свои хвосты. Из любого узла можно перейти к предкам узла, но не к любому другому узлу.
Компилятор для такого языка, как C, создает спагетти-стек, когда он открывает и закрывает таблицы символов, представляющие области действия блока . Когда открывается новая область действия блока, таблица символов помещается в стек. Когда встречается закрывающая фигурная скобка, область действия закрывается, а таблица символов извлекается. Но эта таблица символов запоминается, а не уничтожается, и она запоминает свою более высокую «родительскую» таблицу символов и так далее. Таким образом, когда компилятор позже выполняет переводы по абстрактному синтаксическому дереву , для любого данного выражения он может извлечь таблицу символов, представляющую среду этого выражения, и может разрешить ссылки на идентификаторы. Если выражение ссылается на переменную X, оно сначала ищется в конечной таблице символов, представляющей самую внутреннюю лексическую область действия, затем в родительской и так далее.
Термин «спагетти-стек» тесно связан с реализациями языков программирования , которые поддерживают продолжения . Спагетти-стеки используются для реализации фактического стека времени выполнения , содержащего привязки переменных и другие функции среды. Когда продолжения должны поддерживаться, локальные переменные функции не могут быть уничтожены при возврате этой функции: сохраненное продолжение может позже повторно войти в эту функцию и будет ожидать не только того, что переменные там будут целыми, но и того, что будет присутствовать весь стек, чтобы функция могла снова вернуться. Чтобы решить эту проблему, кадры стека могут быть динамически выделены в структуре спагетти-стека и просто оставлены для сбора мусора , когда на них больше не ссылаются продолжения. Этот тип структуры также решает как восходящую, так и нисходящую проблемы фунаргов , в результате чего первоклассные лексические замыкания легко реализуются в этом субстрате.
Примеры языков, использующих спагетти-стеки:
Мейнфрейм-компьютеры, использующие архитектуру Burroughs Large Systems и работающие под управлением операционной системы MCP, могут порождать несколько задач в одной и той же программе. Поскольку изначально это были системы на основе ALGOL, им приходилось поддерживать вложенные функции , и в результате создание задачи приводило к разветвлению в стеке, который Burroughs неформально описывал как «стек сагуаро».