仮想的なスタックマシンが次の命令をもつとする。
push a データ a をスタックに積む。
dup スタックの最上部のデータを複製してスタックに積む。
swap スタックの最上部の2つのデータの位置を交換する。
add スタックの最上部の2つのデータをスタックから取り除き、その2つのデータの和をスタックに積む。
sub スタックの最上部のデータ a とその直下のデータ b をスタックから取り除き、b-a をスタックに積む。
cmp x スタックの最上部の2つのデータを取り除き、その2つのデータが等しくなければ、ラベル x へプログラムの制御を移す。
このスタックマシン上で、次のプログラムが終了したときに、スタックの最上部にある値はどれか。
push 5
L1: dup
push 1
sub
dup
push 1
cmp L1
L2: add
swap
dup
push 5
cmp L2
add
① 8 ② 10 ③ 12 ④ 15 ⑤ 20
④
スタックは後入れ先出し (LIFO = Last In First Out) であることに注意する。
(便宜上 スタックの状態を左から順に表記する。)
push 5 ・・・5
dub ・・・5, 5
push 1 ・・・ 1, 5, 5
sub ・・・4, 5
dup ・・・4, 4, 5
push 1 ・・・1, 4, 4, 5
cmp ・・・ 1, 4を取り除き、等しくないので L1へ。
スタックは 4, 5
dup ・・・4, 4, 5
push 1 ・・・1, 4, 4, 5
sub ・・・3, 4, 5
dub ・・・3, 3, 4, 5
push 1 ・・・1, 3, 3, 4, 5
cmp ・・・ 1, 3を取り除き、等しくないので L1へ。
スタックは 3, 4, 5
dup ・・・3, 3, 4, 5
push 1 ・・・1, 3, 3, 4, 5
sub ・・・2, 3, 4, 5
dup ・・・2, 2, 3, 4, 5
push 1 ・・・ 1, 2, 2, 3, 4, 5
cmp ・・・ 1, 2を取り除き、等しくないので L1へ。
スタックは 2, 3, 4, 5
dup ・・・2, 2, 3, 4, 5
push 1 ・・・1, 2, 2, 3, 4, 5
sub ・・・1, 2, 3, 4, 5
dup ・・・1, 1, 2, 3, 4, 5
push 1・・・1, 1, 1, 2, 3, 4, 5
cmp ・・・ 1, 2を取り除き、等しいので次のステップへ。
スタックは 1, 2, 3, 4, 5
add ・・・3, 3, 4, 5
swap ・・・3, 3, 4, 5
dup ・・・3, 3, 3, 4, 5
push 5 ・・・5, 3, 3, 3, 4, 5
cmp ・・・5, 3を取り除き、等しくないので L2へ。
スタックは 3, 3, 4, 5
add ・・・6, 4, 5
swap ・・・4, 6, 5
dup 4, 4, 6, 5
push 5 ・・・5, 4, 4, 6, 5
cmp ・・・5, 4を取り除き、等しくないので L2へ。
スタックは 4, 6, 5
add ・・・10, 5
swap ・・・5, 10
dup ・・・ 5, 5, 10
push 5 ・・・5, 5, 5, 10
cmp ・・・5, 5を取り除き、等しいので次のステップへ。
スタックは 5, 10
add 15
よって、スタックの最上部は15。
問題は、1～5までの和を求めるスタックマシンである。
| 目次 | Ⅲ－２ |