Nadřazený ukazatel strom - Parent pointer tree

Zásobník špaget se zvýrazněným „aktivním“ rámečkem zásobníku

v počítačová věda, an ve stromu nebo nadřazený ukazatel strom je N-ary stromová datová struktura ve kterém má každý uzel a ukazatel k jeho nadřazený uzel, ale žádné ukazatele na podřízené uzly. Při použití k implementaci sady hromádky, struktura se nazývá a zásobník špaget, zásobník kaktusů nebo saguaro stack (po saguaro, druh kaktusu).^[1] Stromy nadřazeného ukazatele se také používají jako disjunktní datové struktury.

Strukturu lze považovat za soubor jednotlivě propojené seznamy že podíl část jejich struktury, zejména jejich ocasy. Z kteréhokoli uzlu lze přejít k předkům uzlu, ale ne k žádnému jinému uzlu.

Použití v kompilátorech

A překladač pro jazyk, jako je C při otevírání a zavírání vytváří zásobník špaget tabulky symbolů představující blok obory. Když je otevřen nový rozsah bloku, je do zásobníku vložena tabulka symbolů. Když dojde k uzavírací složené složené závorce, obor se zavře a tabulka symbolů se vyskočí. Ale tato tabulka symbolů je pamatována, spíše než zničena. A samozřejmě si pamatuje svoji vyšší úroveň „mateřské“ tabulky symbolů a tak dále. Když tedy kompilátor později provádí překlady přes abstraktní syntaxový strom, pro jakýkoli daný výraz může načíst tabulku symbolů představující prostředí daného výrazu a může vyřešit odkazy na identifikátory. Pokud výraz odkazuje na proměnnou X, je nejprve vyhledáván v tabulce symbolů listů představující nejvíce lexikální obor, poté v nadřazeném objektu atd.

Použít jako hromádky hovorů

Termín zásobník špaget je úzce spojena s implementací programovací jazyky ta podpora pokračování. Špagety se používají k implementaci skutečných zásobník za běhu obsahující proměnné vazby a další environmentální prvky. Když musí být podporována pokračování, nelze místní proměnné funkce zničit, když se tato funkce vrátí: uložené pokračování může později znovu vstoupit do této funkce a bude očekávat, že nejen proměnné tam budou neporušené, ale bude také očekávat celý zásobník být přítomen, aby se funkce mohla znovu vrátit. Chcete-li tento problém vyřešit, skládané rámečky může být dynamicky přiděleno ve struktuře zásobníku špaget a jednoduše zůstal odpadky shromážděny když na ně již nebude odkazovat žádné pokračování. Tento typ konstrukce řeší také nahoru a dolů funarg problémy, jako výsledek prvotřídní lexikální uzávěry jsou snadno implementovány v tomto substrátu.

Příklady jazyků, které používají špagetové balíčky, jsou:

• Jazyky, které mají prvotřídní pokračování, jako např Systém a Standardní ML z New Jersey
• Jazyky, kde je možné kontrolovat a upravovat spouštěcí zásobník za běhu, například Pokec
• Felixe
• Cilk

Sálové počítače za použití Burroughs Large Systems architektura a provozování MCP operační systém může v rámci jednoho programu vytvořit více úkolů. Protože to byly původně ALGOL -založené systémy tak musí podporovat vnořené funkce, výsledkem je, že vytvoření úlohy má za následek vidličku v zásobníku, která Burroughs neformálně popisován jako „saguaro stack“.

Viz také

• Burroughs velké systémy
• Trvalá datová struktura

Reference