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

Slides:



Advertisements
Similar presentations
【事例演習5】  字句解析     解 説  “ハッシュを用いた字句解析の方法”.
Advertisements

プログラミング演習II 2004年11月 30日(第6回) 理学部数学科・木村巌.
コンパイラ 2012年10月25日
コンパイラ 2011年11月14日
アルゴリズムとデータ構造 2012年6月27日
アルゴリズムとデータ構造1 2005年7月8日
アルゴリズムとデータ構造 2010年7月5日
アルゴリズムとプログラミング (Algorithms and Programming)
コンパイラ 第9回 コード生成 ― スタックマシン ―
プログラミング言語論 第6回 型 情報工学科 篠埜 功.
第2回:Javaの変数と型の宣言 プログラミングII 2007年10月2日.
アルゴリズムとデータ構造 2011年6月13日
プログラミング論 II 電卓,逆ポーランド記法電卓
アルゴリズムとデータ構造 2011年6月9日
アルゴリズムとデータ構造1 2009年6月25日
  【事例演習6】  数式インタプリタ      解 説     “インタプリタの基本的な仕組み”.
プログラミング演習Ⅰ 課題2 10進数と2進数 2回目.
アルゴリズムとデータ構造 2011年6月20日
コンパイラ 2011年10月27日
プログラミング言語入門 手続き型言語としてのJava
アルゴリズムとデータ構造 2012年6月28日
アルゴリズムとデータ構造 2011年6月27日
アルゴリズムとデータ構造 2013年6月17日
アルゴリズムとデータ構造1 2005年7月26日
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造1 2006年6月16日
プログラミング 4 記憶の割り付け.
プログラミング言語入門.
アルゴリズムとデータ構造 2010年6月28日
プログラミング言語論 第五回 理工学部 情報システム工学科 新田直也.
アルゴリズムとデータ構造1 2005年7月1日
アルゴリズムとデータ構造1 2009年6月29日
コンパイラ資料 実行時環境.
アルゴリズムとデータ構造1 2009年7月9日
アルゴリズムとデータ構造1 2005年7月5日
アルゴリズムとデータ構造1 2005年6月24日
アルゴリズムとデータ構造 2010年6月21日
アルゴリズムとデータ構造 2010年7月26日
コンパイラ 2011年10月20日
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
プログラミング言語論 第六回 理工学部 情報システム工学科 新田直也.
アルゴリズムとデータ構造 2011年6月23日
アルゴリズムとプログラミング (Algorithms and Programming)
コンパイラ 2012年10月1日
プログラミング言語論 第十一回 理工学部 情報システム工学科 新田直也.
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造 2012年7月2日
アルゴリズムとデータ構造 2012年6月11日
アルゴリズムとデータ構造1 2008年7月24日
アルゴリズムとデータ構造 2011年6月28日
コンパイラ 2012年11月1日
アルゴリズムとデータ構造1 2006年6月23日
アルゴリズムとデータ構造 2013年7月1日
アルゴリズムとデータ構造1 2009年7月2日
アルゴリズムとデータ構造 2013年7月2日
アルゴリズムとデータ構造1 2009年6月15日
オブジェクト指向言語論 第五回 知能情報学部 新田直也.
オブジェクト指向言語論 第九回 知能情報学部 新田直也.
コンパイラ 2012年10月11日
アルゴリズムとデータ構造 2012年6月21日
プログラミング 4 文字列.
アルゴリズムとデータ構造 2010年6月17日
Javaとは Javaとはオブジェクト指向言語でJava VM(Java仮想マシン)と呼ばれるプログラム上で動作します。
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
アルゴリズムとデータ構造1 2005年7月12日
アルゴリズムとデータ構造1 2007年7月6日
情報処理Ⅱ 小テスト 2005年2月1日(火).
1.2 言語処理の諸観点 (1)言語処理の利用分野
オブジェクト指向言語論 第九回 知能情報学部 新田直也.
オブジェクト指向言語論 第六回 知能情報学部 新田直也.
Presentation transcript:

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

スタック(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);

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

レジスタベースとスタックベース 普通に見かけるプロセッサ スタックマシン(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記述 教科書96ページ  のプログラムと   ほぼ同じ動作 (右上に続く…)

ありがちなプログラミング言語では規則をもとに構文解析を行っている 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)は動的 オペランドスタックの他に辞書を置くスタックが存在する

(ハードウェア)スタックプロセッサ 0オペランド、1オペランド形式の命令 レジスタ割り付けの必要性がない 演算対象のひとつは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 (右上へ続く)

スタックベースのVLIWチップ