Родительское дерево указателей - Parent pointer tree
В информатике , в дерево или родительский указатель дерево представляет собой N - позиционной древовидная структура данных , в которой каждый узел имеет указатель на его родительский узел , но не указатели на дочерние узлы . При использовании для осуществления набор стеков , структура называется спагетти стек , стек кактуса или sahuaro стека (после того , как sahuaro , своего рода кактуса). Деревья родительских указателей также используются как структуры данных с непересекающимися наборами .
Структуру можно рассматривать как набор односвязных списков, которые разделяют часть своей структуры, в частности, их хвосты. Из любого узла можно перейти к предкам узла, но не к любому другому узлу.
Использование в компиляторах
Компилятор для языка , таких как C создает стек спагетти , как он открывает и закрывает таблицу символов , представляющий блок области . Когда открывается новая область видимости блока, таблица символов помещается в стек. Когда встречается закрывающая фигурная скобка, область видимости закрывается и открывается таблица символов. Но эта таблица символов запоминается, а не уничтожается. И, конечно же, он запоминает свою «родительскую» таблицу символов более высокого уровня и так далее. Таким образом, когда компилятор позже выполняет трансляции абстрактного синтаксического дерева для любого данного выражения, он может получить таблицу символов, представляющую среду этого выражения, и может разрешить ссылки на идентификаторы. Если выражение относится к переменной X, оно сначала ищется в таблице листовых символов, представляющей самую внутреннюю лексическую область видимости, затем в родительской и так далее.
Использовать как стеки вызовов
Термин « стек спагетти» тесно связан с реализациями языков программирования, которые поддерживают продолжения . Стеки спагетти используются для реализации фактического стека времени выполнения, содержащего привязки переменных и другие функции среды. Когда должны поддерживаться продолжения, локальные переменные функции не могут быть уничтожены при возврате из этой функции: сохраненное продолжение может позже повторно войти в эту функцию и будет ожидать, что не только переменные там останутся нетронутыми, но и весь стек присутствовать, чтобы функция могла вернуться снова. Чтобы решить эту проблему, кадры стека можно динамически выделять в структуре стека спагетти и просто оставлять для сбора мусора, когда к ним больше не относятся никакие продолжения. Этот тип структуры также решает как восходящие, так и нисходящие проблемы funarg , в результате чего первоклассные лексические замыкания легко реализуются в этой подложке.
Примеры языков, в которых используются стопки спагетти:
- Языки, имеющие первоклассные продолжения, такие как Scheme и Standard ML of New Jersey
- Языки, на которых стек выполнения можно проверять и изменять во время выполнения, например Smalltalk.
- Феликс
- Силк
Мэйнфреймы, использующие архитектуру Burroughs Large Systems и работающие под управлением операционной системы MCP, могут запускать несколько задач в одной программе. Поскольку изначально это были системы на основе Алгола, они должны поддерживать вложенные функции, и в результате создание задачи приводит к возникновению вилки в стеке, которую Берроуз неофициально назвал «стеком сагуаро».
