スタックマシン

スタックマシン

スタックマシン（stack machine）とは、メモリがスタックの形式になっている計算モデルを意味する。 スタックマシンを実装あるいはシミュレートしている実在のコンピュータもスタックマシンと呼ぶ。

加えて、スタックマシンは「0オペランド」命令セットのマシンも意味する。0オペランドマシンでは、命令は暗黙のうちにスタックのトップにある値を使って演算を行い、結果をスタックのトップに置く。そのようなマシンでも、メモリの任意の位置の読み書きをする "load" 命令や "store" 命令がある（ただし、アドレスは明示的に指定せず、スタックのトップにある値をアドレスとして使用する）。

スタックマシン（0オペランド命令セット）がアキュムレータマシン（1オペランド命令セット）やレジスタマシン（2オペランド命令セット、3オペランド命令セット）に比較して優れているのは、0オペランド命令セットで書かれたプログラムのコード密度が他の命令セットで書かれた同じプログラムに比較して一般に高い点である。

計算のスタックモデル

スタックマシンはいくつかのスタックを持つ。プログラムの初期入力はスタック1の初期状態として与えられ、他のスタックは初期状態では空である。スタックマシンの各時点の状態はリード状態かライト状態であり、各状態にはスタックからリード（ポップ）すべき値の個数かスタックにライト（プッシュ）すべき値の個数が付与される。さらにライト状態には書き込むべきシンボルが指定され、次に遷移すべき状態が指定される。リード状態ではアルファベットそれぞれについて、リード結果としてその文字を読んだときに遷移すべき次の状態が指定される。さらにリード状態ではスタックが空だったときの遷移先状態も指定される。スタックマシンは特別な停止状態に到達したとき停止する。

スタックを1つしか持たないスタックマシンは、計算モデルとしては非常に弱い。例えば、1-スタックマシンでは、0n1n（0の並びの後に同じ個数の1が並ぶ言語）のような単純な言語も認識できない。1-スタックマシンの計算能力は、有限オートマトンよりも高いが、決定性プッシュダウン・オートマトンよりも低い。

一方、複数のスタックを持つスタックマシンはチューリング機械と等価である。例えば、2-スタックマシンでは、チューリング機械をエミュレートできる（チューリング機械のヘッド位置から左側のテープをひとつのスタックが代替し、右側のテープをもうひとつのスタックが代替する）。

引用元 ： Wikipedia http://ja.wikipedia.org/wiki/%E3%83%A1%E3%82%A4%E3%83%B3%E3%83%9A%E3%83%BC%E3%82%B8