Родительское дерево указателей

Стопка спагетти с выделенной «активной» рамкой стопки

В информатике внутридеревьевое , или родительское дерево указателей представляет собой N -арную древовидную структуру данных в которой каждый узел имеет указатель на родительский узел , но не имеет указателей на дочерние узлы . При использовании для реализации набора стеков структура называется стеком спагетти , стеком кактуса или стеком сагуаро (по имени сагуаро , разновидности кактуса). Деревья родительских указателей также используются в качестве структур данных с непересекающимися наборами .

Структуру можно рассматривать как набор односвязных списков, имеющих общую часть структуры, в частности хвосты. Из любого узла можно перейти к предкам узла, но не к любому другому узлу.

Использование в компиляторах

Компилятор создает такого языка, как C, спагетти-стек, открывая и закрывая таблицы символов, блоков представляющие области . Когда открывается новая область блока, таблица символов помещается в стек. При обнаружении закрывающей фигурной скобки область видимости закрывается и таблица символов извлекается. Но эта таблица символов запоминается, а не уничтожается, и она запоминает свою «родительскую» таблицу символов более высокого уровня и так далее. Таким образом, когда компилятор позже выполняет переводы абстрактного синтаксического дерева для любого заданного выражения, он может получить таблицу символов, представляющую среду этого выражения, и может разрешить ссылки на идентификаторы. Если выражение ссылается на переменную X, сначала она ищется в таблице конечных символов, представляющей самую внутреннюю лексическую область видимости, затем в родительской и так далее.

Использовать в качестве стеков вызовов

Термин «стек спагетти» тесно связан с реализациями языков программирования , поддерживающими продолжения . Стеки спагетти используются для реализации фактического стека времени выполнения, содержащего привязки переменных и другие функции среды. Когда необходимо поддерживать продолжения, локальные переменные функции не могут быть уничтожены, когда эта функция возвращается: сохраненное продолжение может позже повторно войти в эту функцию и ожидать, что не только переменные там останутся нетронутыми, но также будет ожидаться, что весь стек присутствовать, чтобы функция могла вернуться снова. Чтобы решить эту проблему, кадры стека можно динамически распределять в структуре стека спагетти и просто оставлять для сбора мусора , когда на них больше не ссылаются никакие продолжения. Этот тип структуры также решает проблемы как восходящего, так и нисходящего движения первоклассные лексические замыкания , в результате чего в этом субстрате легко реализуются .

Примеры языков, использующих стопки спагетти:

• Языки, имеющие первоклассные продолжения, такие как Scheme и Standard ML of New Jersey.
• Языки, в которых стек выполнения можно проверять и изменять во время выполнения, например
  • Смолток
  • Феликс
  • Том

Мэйнфреймы, использующие архитектуру больших систем Burroughs и работающие под управлением операционной системы MCP, могут создавать несколько задач в одной и той же программе. Поскольку изначально это были системы, основанные на АЛГОЛЕ, они должны поддерживать вложенные функции , и в результате создание задачи приводит к разветвлению стека, который Берроуз неофициально назвал «стеком Сагуаро».

См. также

• Постоянная структура данных