酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造1 2009年6月25日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2009/index.html

2009年6月25日 スタック（LIFO） プッシュ ポップ スタックポインタ スタックポインタ スタックポインタ

public class MyStack { private MyStack() } public MyStack(int aMaxSize) this.maxSize = aMaxSize; this.stackArray = new Object[aMaxSize]; this.stackPointer = 0; public void printAll() System.out.println("スタックの内容"); int count = 1; int position = this.stackPointer - 1; while(0 <= position) { System.out.println(count + "\t" + this.stackArray[position]); ++count; --position; System.out.println(); private int maxSize; private Object[] stackArray; private int stackPointer;

public void push(Object anObject) { if(this.isFull()){ System.err.println("エラー: スタックはいっぱいです"); return; // スタックオーバーフロー } this.stackArray[this.stackPointer] = anObject; this.stackPointer++; public boolean isFull() return (this.stackPointer == this.maxSize); public Object pop() { if(isEmpty()){ System.err.println("スタックは空です"); return null; // スタックアンダーフロー } --this.stackPointer; Object popObject = this.stackArray[this.stackPointer]; this.stackArray[this.stackPointer] = null; return popObject; public boolean isEmpty() return (0 == this.stackPointer);

連結リスト操作（挿入） リストを使ったスタック（push） 先頭 次 データ 次 データ データをそれぞれの要素に格納 要素どおし、つながってリストを形成 単純な連結リスト（線形リスト）データ挿入

連結リスト操作（削除） リストを使ったスタック（pop） 先頭 次 データ 単純な連結リスト（線形リスト）データ削除

ハノイの塔 一回に一枚の円盤しか動かしてはいけない。 移動の途中で円盤の大小を逆に積んではいけない。 常に大きい方の円盤が下になるようにする。 棒以外のところに円盤を置いてはいけない。

レジスタベースとスタックベース 普通に見かけるプロセッサ スタックマシン（Java VMなど） レジスタファイル＋演算器 スタック＋演算器

レジスタベースとスタックベース

Postscript プログラミング言語ではなくて、ページ記述言語 オペランドスタック、辞書スタックを持つ オブジェクトはリテラル、エグゼキュータブル A-WSでgsというコマンドで実行できる push/pop以外のスタック処理がある index 指定位置の内容をコピーしてpush rotate 指定位置までのスタックを配列とみて回転 [] , {}, () スタックから配列オブジェクトを切り出せる

[sakai@star ]$ gs GS> GS>(リンゴ) GS<1>(ミカン) GS<2>(サクランボ) GS<3>stack サクランボ ミカン リンゴ GS<3>= GS<2>(バナナ) GS<3>(ブルーベリー) GS<4>(イチゴ) GS<5>stack イチゴ ブルーベリー バナナ (リンゴ) (ミカン) (サクランボ) stack = (バナナ) (ブルーベリー) (イチゴ) (グレープフルーツ) count -1 1 {pop =} for quit (左下から続く) GS<5>(グレープフルーツ) GS<6>stack グレープフルーツ イチゴ ブルーベリー バナナ ミカン リンゴ GS<6>count -1 1 {pop =} for GS> GS>quit [sakai@star ]$ PostScript記述 教科書９６ページ 　のプログラムと 　　ほぼ同じ動作 (右上に続く…)

ありがちなプログラミング言語では規則をもとに構文解析を行っている RPN（逆ポーランド記法） 普通は 1 + 2 と入力して 3 という答えを得ます 同じ答えを得るために、RPNで書くと 1 2 + となります。 普通の書き方の(1 + 2) × (3 + 4) をRPNにすると 1 2 + 3 4 + ×　となります。 ありがちなプログラミング言語では規則をもとに構文解析を行っている 演算子には優先順位がある 括弧は優先度を変える 変わった言語、変わったプロセッサというものがありまして Forth, PostScriptといった言語、インテル x87 数値演算プロセッサ これらはスタックを基本的なデータ構造としている

RPNで記述するとき、日本語で数式の動作を (1 + 2) × (3 + 4) RPNでは 1 2 + 3 4 + (1 + 2) × (3 + 4) ÷(5×6 – 7×8) RPNでは 1 2 + 3 4 + × 5 6 × 7 8 × - ÷ PostScriptでは、三角関数まで定義されている。 GS>1 2 add 3 4 add mul = 21 GS>1 2 add 3 4 add mul 5 6 mul 7 8 mul sub div = -0.807692 GS>30 sin = 0.5 GS>45 cos = 0.707107 RPNで記述するとき、日本語で数式の動作を 読み上げることにかなり近い順序になる

呼ばれた関数の スタックフレーム PC fmt int_number dbl_number 呼んだ関数の スタックフレーム /* 可変長引数を持つ関数 */ int printf(const char *fmt,…); /* それの呼び出し */ printf(“%d %f \n”, int_number, dbl_number); C言語では引数はスタックに積まれて、 関数に渡される。呼び出し側の責任で 引数を積んだり降ろしたりする。 ← TOS 呼ばれた関数の スタックフレーム PC 呼ばれた関数にわかっていること 呼ばれた関数のスタックフレームの大きさ 関数の戻り先(呼び出し元PC) 第1引数がconst char *fmtであること つまりfmtが読める→以降の引数がわかる fmt int_number dbl_number 呼んだ関数の スタックフレーム

呼ばれた関数の スタックフレーム PC “/bin/ls” “ls” “-l” “/home/sakai” NULL 呼んだ関数の /* 可変長引数を持つ関数 */ int execl(const char *path, const char *arg, ...); /* それの呼び出し */ execl(“/bin/ls”, “ls”, “-l”, “/home/sakai”, NULL); ← TOS 呼ばれた関数の スタックフレーム 呼ばれた関数にわかっていること 呼ばれた関数のスタックフレームの大きさ 関数の戻り先(呼び出し元PC) 第1引数が“/bin/ls”であること 第2引数が”ls”であること 最後の引数は必ずNULLであること PC “/bin/ls” “ls” スタックに何らかのマークをpushし、 TOSからマークまでをリストとして渡す “-l” “/home/sakai” NULL 呼んだ関数の スタックフレーム

% PostScriptにおける配列の切り出し % [1 2 3 4 5 6 7 8 9 10] という配列を定義 GS>[ GS<1>1 GS<2>2 GS<3>3 GS<4>4 GS<5>5 GS<6>6 GS<7>7 GS<8>8 GS<9>9 GS<10>10 GS<11>] GS<1>== [1 2 3 4 5 6 7 8 9 10] GS> PostScriptでは、配列が定義できる。 スタック上の「マーク」と「マークまでを配列とする」 オペレータを組み合わせて使う。 このオペレータはマークまでをすべてpopし、 配列オブジェクトとしてふたたびpushする [ オブジェクトの並び ] は通常の配列 { オブジェクトの並び } は実行可能な配列(手続き) (文字の並び) は文字の配列（文字列） いずれも配列の基本的な性質は継承している

コンパイラとインタプリタ 高級言語で記述されたプログラムを，機械語あるいはアセンブリ言語のプログラムに翻訳する 翻訳の過程はおおむね次のようになる 字句解析 構文解析 意味解析 エラー診断 コード生成 インタプリタではコード生成しないで即実行

PostScriptインタープリタ PostScript言語を解釈し即実行 PostScriptはスタックベースの言語 構文解析が無い 字句解析によりオブジェクトを分類 実行可能な名前（オペレータ） リテラル（名前オブジェクト） それ以外のオブジェクト オペレータは辞書と呼ばれる連想記憶に定義 実行可能な名前は辞書から取り出され実行される 名前による参照が行われるため、束縛(binding)は動的 オペランドスタックの他に辞書を置くスタックが存在する

(ハードウェア)スタックプロセッサ ０オペランド、１オペランド形式の命令 レジスタ割り付けの必要性がない 演算対象のひとつはTOSなので命令語長が短い レジスタ割り付けの必要性がない .lp: fld dword [eax+ecx*4] ; xr, 0.4054, istep fld dword [eax+ecx*4+4] fld dword [eax+ecx*4+8] fld dword [eax+ecx*4+12] ; 3, 2, 1, 0, 0.4054, istep fmul st0, st5 fxch st1 ; 2, 3x, 1, 0 fxch st2 ; 1, 3x, 2x, 0 fxch st3 ; 0, 3x, 2x, 1x fxch st1 ; 3x, 0x, 2x, 1x fadd st0, st4 (左下から続く) fxch st2 ; 2x, 0x, 3x+, 1x fadd st0, st4 fxch st3 ; 1x, 0x, 3x+, 2x+ fxch st1 ; 0x, 1x+, 3x+, 2x+ fxch st2 ; 3x+, 1x+, 0x+, 2x+ fistp dword [edx+ecx*4+12] fistp dword [edx+ecx*4+4] fistp dword [edx+ecx*4] fistp dword [edx+ecx*4+8] add ecx, 4 jnz .lp (右上へ続く)