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