|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。
スタックマシン（''stack machine''）とは、メモリがスタックの形式になっている計算モデルを意味する。 スタックマシンを実装あるいはシミュレートしている実在のコンピュータもスタックマシンと呼ぶ。 加えて、スタックマシンは「0オペランド」命令セットのマシンも意味する。0オペランドマシンでは、命令は暗黙のうちにスタックのトップにある値を使って演算を行い、結果をスタックのトップに置く。そのようなマシンでも、メモリの任意の位置の読み書きをする "load" 命令や "store" 命令がある（ただし、アドレスは明示的に指定せず、スタックのトップにある値をアドレスとして使用する）。 スタックマシン（0オペランド命令セット）がアキュムレータマシン（1オペランド命令セット）やレジスタマシン（2オペランド命令セット、3オペランド命令セット）に比較して優れているのは、0オペランド命令セットで書かれたプログラムのコード密度が他の命令セットで書かれた同じプログラムに比較して一般に高い点である。 コールスタックを使って入れ子になったサブルーチン呼び出しの局所変数群を管理する方式のコンピュータをスタックマシンとは呼ばない（普通は）。 == 計算のスタックモデル == 計算機科学のオートマトン理論における「スタックマシン」は、メモリにランダムアクセスすることができず、LIFO型のスタックしか持たない計算モデルである。これは純粋に理論上のモデルであり、実在のコンピュータではメモリは任意のアドレスを指定してアクセスできる。 スタックマシンはいくつかのスタックを持つ。プログラムの初期入力はスタック1の初期状態として与えられ、他のスタックは初期状態では空である。スタックマシンの各時点の状態はリード状態かライト状態であり、各状態にはスタックからリード（ポップ）すべき値の個数かスタックにライト（プッシュ）すべき値の個数が付与される。さらにライト状態には書き込むべきシンボルが指定され、次に遷移すべき状態が指定される。リード状態ではアルファベットそれぞれについて、リード結果としてその文字を読んだときに遷移すべき次の状態が指定される。さらにリード状態ではスタックが空だったときの遷移先状態も指定される。スタックマシンは特別な停止状態に到達したとき停止する。 スタックを1つしか持たないスタックマシンは、計算モデルとしては非常に弱い。例えば、1-スタックマシンでは、0n1n（0の並びの後に同じ個数の1が並ぶ言語）のような単純な言語も認識できない。1-スタックマシンの計算能力は、有限オートマトンよりも高いが、決定性プッシュダウン・オートマトンよりも低い。 一方、複数のスタックを持つスタックマシンはチューリングマシンと等価である。例えば、2-スタックマシンでは、チューリングマシンをエミュレートできる（チューリングマシンのヘッド位置から左側のテープをひとつのスタックが代替し、右側のテープをもうひとつのスタックが代替する）。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「スタックマシン」の詳細全文を読む スポンサード リンク
|