スパゲッティスタック

スパゲッティスタック（spaghetti stack; 他に cactus stack, saguaro stack, in-treeとも）とは、子ノードが親ノードへのポインタを持ち、親ノードは子ノードへのポインタを持たないようなN分木である。ノードのリストが親のポインタをたどって葉から親へ向かうとき、スパゲッティスタックは連結リストのスタックのように振る舞う。リンクがある連結リストと比較して、他のノード唯一の親ノードへのポインタのみをもち、それぞれの親ノードは他の子を無視する（親ノードから子ノードへのポインタが無いためどうやってもアクセスできない）。スパゲッティスタックは実行過程のようにレコードが動的にプッシュ・ポップされるもののポップされたレコードが使用時に残るという状況で発生する。例えばC言語のようなコンパイラはブロックスコープ表現がシンボルテーブルを開閉するようなスパゲッティスタックを作る。新たなブロックスコープが開かれた時、シンボルテーブルはスタックにプッシュされる。閉じ中括弧が検出されたとき、スコープは閉じられ、シンボルテーブルがポップされる。しかしシンボルテーブルは破壊されるのではなく記憶される。そしてもちろんスタックは親のシンボルテーブルなども記憶している。そのためコンパイラが抽象構文木についてあとで翻訳を行うとき、与えられた任意の表現に対してスパゲッティスタックはその表現の環境で表現するシンボルテーブルを呼び出すことができ、識別子への参照を解決することが出来る。もし表現が変数Xを参照するときは、それは最も内部の静的スコープを表現する葉のシンボルテーブルをまずシークし次にその親のシンボルテーブルをシークしていく。類似のデータ構造は素集合森において見られる（素集合データ構造を参照）。