В информатике , в дерево или родительский указатель дерево представляет собой N - позиционной древовидная структура данных , в которой каждый узел имеет указатель на его родительский узел , но не указатели на дочерние узлы . При использовании для осуществления набора стеков , структура называется спагетти стеком , стек кактус или цереуса стека (после Saguaro , своего рода кактуса). [1] Деревья родительских указателей также используются как структуры данных с непересекающимися наборами .
Структуру можно рассматривать как набор односвязных списков, которые разделяют часть своей структуры, в частности, их хвосты. Из любого узла можно перейти к предкам узла, но не к любому другому узлу.
Использование в компиляторах [ править ]
Компилятор для языка , таких как C создает стек спагетти , как он открывает и закрывает таблицу символов , представляющий блок области . Когда открывается новая область видимости блока, таблица символов помещается в стек. Когда встречается закрывающая фигурная скобка, область видимости закрывается и открывается таблица символов. Но эта таблица символов запоминается, а не уничтожается. И, конечно же, он запоминает свою «родительскую» таблицу символов более высокого уровня и так далее. Таким образом, когда компилятор позже выполняет переводы по абстрактному синтаксическому деревудля любого данного выражения он может получить таблицу символов, представляющую среду этого выражения, и может разрешить ссылки на идентификаторы. Если выражение относится к переменной X, оно сначала ищется в таблице листовых символов, представляющей самую внутреннюю лексическую область видимости, затем в родительской и так далее.
Использовать в качестве стека вызовов [ править ]
Термин « стек спагетти» тесно связан с реализациями языков программирования, которые поддерживают продолжения . Стеки спагетти используются для реализации фактического стека времени выполнения, содержащего привязки переменных и другие функции среды. Когда должны поддерживаться продолжения, локальные переменные функции не могут быть уничтожены при возврате из этой функции: сохраненное продолжение может позже повторно войти в эту функцию и будет ожидать, что не только переменные там останутся нетронутыми, но и весь стек присутствовать, чтобы функция могла вернуться снова. Чтобы решить эту проблему, кадры стека могут быть выделены динамически.в структуре стека спагетти и просто оставлены для сборки мусора, когда к ним больше не относятся никакие продолжения. Этот тип структуры также решает как восходящие, так и нисходящие проблемы funarg , в результате чего первоклассные лексические замыкания легко реализуются в этой подложке.
Примеры языков, в которых используются стопки спагетти:
- Языки, имеющие первоклассные продолжения, такие как Scheme и Standard ML of New Jersey
- Языки, на которых стек выполнения можно проверять и изменять во время выполнения, например Smalltalk.
- Феликс
- Силк
Мэйнфреймы, использующие архитектуру Burroughs Large Systems и работающие под управлением операционной системы MCP, могут запускать несколько задач в одной программе. Так как они были первоначально Алгол систем на основе так должны поддерживать вложенные функции , результатом является то , что результаты создания задачи в вилке в стеке, который Burroughs неофициально описывается как «цереуса стека.».
См. Также [ править ]
Ссылки [ править ]
- ^ Clinger, W .; Hartheimer, A .; Ост, Э. (1988). «Стратегии реализации продолжений». Материалы конференции ACM 1988 г. по LISP и функциональному программированию - LFP '88 . С. 124–131. DOI : 10.1145 / 62678.62692 . ISBN 089791273X.
