Drzewo wskaźników nadrzędnych — Parent pointer tree
W informatyce , w drzewo lub drzewo wskaźnik rodzic jest N -ary drzewo struktura danych , w której każdy węzeł posiada wskaźnik do swojego węzła nadrzędnego , ale nie wskaźniki do węzłów potomnych . W przypadku zastosowania do wykonania zestawu stosy , struktura ta jest nazywana spaghetti stos , stos kaktus lub Sahuaro stos (po Sahuaro , rodzaj kaktusa). Drzewa wskaźników nadrzędnych są również używane jako rozłączne struktury danych .
Strukturę można traktować jako zbiór pojedynczo powiązanych list, które dzielą część swojej struktury, w szczególności ich ogony. Z dowolnego węzła można przejść do przodków węzła, ale nie do żadnego innego węzła.
Użyj w kompilatorach
Kompilator dla języka takich jak C tworzy spaghetti stos jak otwiera i zamyka tabele symboli reprezentujących blokowe zakresów . Po otwarciu nowego zakresu bloku tablica symboli jest umieszczana na stosie. Po napotkaniu zamykającego nawiasu klamrowego zakres jest zamykany, a tablica symboli jest otwierana. Ale ta tablica symboli jest pamiętana, a nie niszczona. I oczywiście pamięta swoją tablicę symboli „rodzica” wyższego poziomu i tak dalej. Tak więc, gdy kompilator wykonuje później translacje na abstrakcyjnym drzewie składni , dla dowolnego danego wyrażenia, może pobrać tabelę symboli reprezentującą środowisko tego wyrażenia i może rozwiązać odwołania do identyfikatorów. Jeśli wyrażenie odnosi się do zmiennej X, jest najpierw wyszukiwane w tablicy symboli liścia reprezentującej najbardziej wewnętrzny zakres leksykalny, a następnie w rodzicu i tak dalej.
Użyj jako stosy połączeń
Termin stos spaghetti jest ściśle związany z implementacjami języków programowania, które obsługują kontynuacje . Stosy spaghetti są używane do implementacji rzeczywistego stosu uruchomieniowego zawierającego zmienne powiązania i inne funkcje środowiskowe. Gdy kontynuacja musi być obsługiwana, zmienne lokalne funkcji nie mogą zostać zniszczone po powrocie tej funkcji: zapisana kontynuacja może później ponownie wejść do tej funkcji i będzie oczekiwać nie tylko, że zmienne tam będą nienaruszone, ale również będzie oczekiwała całego stosu być obecny, aby funkcja mogła powrócić ponownie. Aby rozwiązać ten problem, ramki stosu mogą być dynamicznie przydzielane w strukturze stosu spaghetti i po prostu pozostawione do zbierania śmieci, gdy żadne kontynuacje nie odnoszą się już do nich. Ten typ struktury rozwiązuje również zarówno problemy z grzybkami skierowanymi w górę, jak i w dół , dzięki czemu w tym podłożu są łatwo implementowane najwyższej klasy domknięcia leksykalne .
Przykłady języków, które używają stosów spaghetti to:
- Języki mające kontynuacje pierwszej klasy, takie jak Scheme i Standard ML of New Jersey
- Języki, w których stos wykonania można sprawdzać i modyfikować w czasie wykonywania, takie jak Smalltalk
- Felix
- Cilk
Komputery typu mainframe korzystające z architektury Burroughs Large Systems i z systemem operacyjnym MCP mogą tworzyć wiele zadań w ramach tego samego programu. Ponieważ były to pierwotnie systemy oparte na ALGOL , muszą obsługiwać funkcje zagnieżdżone, a wynikiem tworzenia zadań jest rozwidlenie stosu, które Burroughs nieformalnie określił jako „stos saguaro”.
