【事例演習6】 　数式インタプリタ 　　　　　解　説 　　　　“インタプリタの基本的な仕組み”.

Presentation on theme: "　　【事例演習6】 　数式インタプリタ 　　　　　解　説 　　　　“インタプリタの基本的な仕組み”."— Presentation transcript:

1 　　【事例演習6】 　数式インタプリタ 　　　　　解　説 　　　　“インタプリタの基本的な仕組み”

2 インタプリタとコンパイラの相違 機械語 疑似コード 疑似コード コンパイラ 高水準言語 コードの最適化 機械語コード生成 （P-Code）
　コードの最適化 　機械語コード生成 　　　疑似コード 　　　　（P-Code） 　構文解析＆ 　コード生成 　　　　インタプリタ 　特殊問題向き言語 　　仮想マシン P-Code | Byte-Code の評価&実行 　　　構文解析＆ 　　　コード生成 　　　疑似コード （P-Codeまたは Byte-Code ） アセンブラ言語 　　アセンブラ 　機械語コードへ 　直接変換 　　　　機械語 　(Intel用,Motorola用,PowerPC用…） 実行 実行 　 　　ハードウェア方式 機械語の命令をCPUの論理回路 によって解釈・実行する方式 　　ファームウェア方式 機械語の命令をマクロ命令と考え，CPU内に格納されたさらに基本的なマイクロコードプログラムによって評価・実行する方式

3 機能１：コンパイル（構文解析と疑似コードの生成）
インタプリタ言語（例えばBASIC,Java等）で組んだ 　　　　　アプリケーション・プログラム この範囲はCPUに 依存しない インタプリタ 　機能１：コンパイル（構文解析と疑似コードの生成） 入力された文や式が構文規則（シンタックス）にしたがっているかチェックし， 疑似コードを生成する 　　　　　　　 疑似コード P(Pseudo)-Code 　　　アプリケーション･プログラムを疑似的なコードや基本的な関数の呼出しに形式に変換したもの 疑似コード生成 疑似コードの評価・実行 　　機能２：仮想マシン (Virtual Machine) 　　　疑似コードや基本的な関数呼出しをプログラム的に評価・実行する 実行 Cコンパイラ　　（Intel用） Cコンパイラ　（Motorola用） Cコンパイラ　（PowerPC用） 仮想マシンの機能を記述したCプログラムを翻訳した機械語コード 　　　　　　　　　　　(Intel用,Motorola用,PowerPC用…）

4 JavaにおけるByte-codeの転送と評価・実行
　　　　サーバ Java　コンパイラ コンパイルが生成した Byte_code(疑似コード） Java プログラム Byte-code（疑似コード） 　　　　Webブラウザ 　Java仮想マシン （Virtual　Machine)

5 インタプリタの基本的な機能構造図 Parser インタプリタ 本体 構文規則にしたがっているか 文 / 式をチェックし，
　　インタプリタ 　　　　本体 　構文規則にしたがっているか 　文 / 式をチェックし， 　同時に疑似コードを生成する 　get_syllable 　一語の切出し 　regist_variable 　　変数の登録 　　Parser 構文規則にしたがっているか解析し疑似コードを 生成するモジュール群 疑似コードを格納した テーブルp_code_tbl 疑似コードを解釈し実行する スタック操作 　演算操作 　命令アドレス 　制御操作 　　Evaluator 　（仮想マシンとしての機能） p_code_tbl

6 　　　Parser 　（構文チェックと 　　　　疑似コード生成の機能）

7 擬似コードの生成方法とスタック上での操作との対応
計算式 　　a b [ a ] Aで示される番地から値をスタックの先頭に積む命令 ADD 　 スタック上の２つのオペランドに対して加算演算を 　　　　　行い，その結果をスタック先頭に積む命令 　　a b + ①逆ポーランド表記に置換する ②対応する順序で疑似コードを生成 [ a ]　 [ b ] 　ADD Parser スタック上でのこのような擬似命令を順に実行すると・・・ ADD演算の実行 Evaluator < b > < a > + < b > < a >　 <a> aで示される番地からもってきた値 計算式で記述した計算が実行された

8 スタック上でのこのような擬似命令を順に実行すると・・・
[ a ] 　[ b ] ADD 　　a b　 c 対応する順序で疑似コードを生成 [ c ] SUBT Parser スタック上でのこのような擬似命令を順に実行すると・・・ SUBT演算の実行 Evaluator <a>+<b> - <c> < c > < a > + < b > 計算式で記述した計算が実行された

9 スタック上でのこのような擬似命令を順に実行すると・・・
計算式 計算の優先度の高いものを一つのまとまりとして扱うと・・・ 　a 　+ b ＊ ｃ 疑似コードを生成 [ a ]　 [ b ]　 [ｃ]　MULT 　　　　 　　　　？ ADD Parser スタック上でのこのような擬似命令を順に実行すると・・・ Evaluator < b > * < c > MULT演算 <a> + <b>*<c> ADD演算 < c >　 < b >　 < a >　 計算式で記述した計算が実行された

10 スタック上でのこのような擬似命令を順に実行すると・・・
計算式 計算の優先度の高いものを一つのまとまりとして扱うと・・・ （　a + b ）＊ ｃ 疑似コードを生成 [ｃ]　 MULT 　　　　 　　　　？ [ a ]　 [ b ]　ADD 　　　　 Parser スタック上でのこのような擬似命令を順に実行すると・・・ < a > + < b >　 ADD演算 (<a>+<b>)*<c> MULT演算 Evaluator < c >　 < b >　 < a >　 計算式で記述した計算が実行された

11 方針 構文規則にしたがっているかの構文チェック， および擬似コードを生成するプログラムの考え方
　　　　　および擬似コードを生成するプログラムの考え方 　　方針 　　計算の優先度が高いものは，一つの“まとまり”として扱い 　　　　　その処理は“まとまり”に任せる 構文チェックと擬似コードの生成　

12 例えば．．． 数式とは ・・・ + - 項 ＋，－ より優先度の高い演算を含むものは「項」として一つに
　項 ＋，－　より優先度の高い演算を含むものは「項」として一つに まとめて扱い，その構文チェックと擬似コード生成は「項」に任せる 因子 * / ・・・ 　項とは　 *，/ より優先度の高い演算を含むものは「因子」として一つに まとめて扱い，その構文チェックと擬似コード生成は「因子」に任せる 因子とは 数字　 変数名 ( 　数式　　）

13 構文チェックの方法 因子（factor） ：：= 変数名（variable name）
以下の構文図式（syntax Diagram)で示すように記述されているかチェックすればよい 式(expression)::= 　項(term) + - 項(term)::= 　因子(factor) * / 　因子（factor）　：：=　　　　　　　 　　　　　　　　　変数名（variable name）　 　　　　　　　　　　　　　　　　定数(constant) 　　　　　　　　　　　　　　 ( 　　式(expression) 　　　)

14 実は，構文図式は関数呼出しの手順に対応している
　　　　 　　　　　　　　　　+ 　　　　 　　　　　　　　　　　 - 　関数expression ( )　::=　　　　　 　 term ( ) 　　　　　　　　　　　　　　　　　　　 * 　　　　 　 　　　　　　　 / 　関数term　( ) ::= 　　　　　　　 factor （ ） 　関数 factor　( )::=　　　 　　　 variable_name （ ）　 　　　　　　　　　constant （ ） 　　　　　　 ( 　　 expression （ ) 　　 ) 再帰呼出し

15 疑似コード生成の方法 + - 関数expression ( ) ::= term ( ) * /
ADD　 SUBT　 ２つterm()が呼出された後に生成 　　　　 　　　　　　　　　　+ 　　　　 　　　　　　　　　　　 - 　関数expression ( )　::=　　　　　 　 term ( ) 　　　　　　　　　　　　　　　　　　　 * 　　　　 　 　　　　　　　 / 　関数term　( ) ::= 　　　　　　　 factor （ ） 　関数 factor　( )::=　　　 　　　 variable_name （ ）　 　　　　　　　　　constant （ ） 　　　　　　 ( 　　 expression （ ) 　　 ) MULT　 DIVD ２つfactor()が呼出された後に生成 VALC:　変数のｱﾄﾞﾚｽ　 CNST:　定数のｱﾄﾞﾚｽ

16 例えば，関数expression ( ) のプログラム手順
　　　　 　　　　　　　　　　+ 　　　　 　　　　　　　　　　　 - 　関数expression ( )　::=　　　　　 　 term ( ) 　関数expression ( )　 項を解析する関数term()を呼び出す //※ 関数term()を出るときには，必ず次の字句(1語)をsyllable_buffにもってきている 次の語が演算子“＋”か“－”である間，繰り返す 逆ポーランド表記に置換するために演算子を一旦記憶する 次の一語を取り出しsyllable_buffに格納する 項を解析する関数term（）を呼び出す //※ 関数term（）を出るときには，必ず次の字句（一語）を 　　　　　　　　　　　　　　　　 syllable_buffにもってきている 一旦記憶した演算子を後に置いて疑似コードを生成する

17 　　Evaluator （仮想マシンとしての機能）

18 疑似コードを評価・実行するスタックマシンとは！！
ＣＰＵ レジスタ群 　　　レジスタA　( rA) 　レジスタB 　( rB) rA, rBとスタック先頭の2語（ Stack[TOS], Stack[TOS-1]）とは ハードウェア的に対応が取られる 主記憶 スタック領域 TOS （Top of Stack：:　ｽﾀｯｸの先頭位置） Offset(基底位置からの乖離) BOS （Base of Stack：:　ｽﾀｯｸの基底位置）

19 Evaluatorにおける疑似コードの評価・実行手順
【182ページ参照】 　p_code_tblのPC（ﾌﾟﾛｸﾞﾗﾑ ｶｳﾝﾀ）が指す位置から疑似コードをフェッチする． 　疑似コードを命令部とアドレス部に分解する． 疑似コードの判別 　演算命令群 　分岐命令群 　論理及び関係命令群 　ロード，および索引命令群 　スタック，およびサブルーチン命令群 　PCを一つ進める No Yes 終わり PCの終わりか

20 質問？

21 　　情報処理実験　「数式インタプリタ」 　　　　　解　説 　　　　　　　“スタック操作の基本”

22 演算の種類によって異なるスタック操作 ２項演算 単項演算 < a > ＋ <b> < П a >
　　２項演算 (+,-,*,/,剰余%，べき乗＾など） 　　　単項演算 (階乗П,sin,cos,tan等関数など） < a > ＋ <b> スタックの先頭 （pop後） 2項演算 　　< П a > 単項演算 　　　< b > スタックの先頭 TOS(Top_of_Stack) 　　　< a > 　　　< a > スタックの先頭

23 関数call/return時のスタック操作
サンプルプログラム int a = 12, 　b =21, 　c; f ( b, 87 ); : ※[ LL=#1 ] int f (int p1,float p2) { int x; x = 　a + p1 – p2; return x; } ※[ LL=#2 ] CONST_TBL < a + p1>=33 　　< p2 >=87 　　< p1 >=21 < a +p1-p2>= -54 12 21 87 　　< x >= -54 　　　< a >=12 1 2 3 PUSH // 変数ｘの確保 NAMC #2:4 // xのｱﾄﾞﾚｽ作成 VALC #1:2　// aの値 VALC #2:2　// p1の値 ADD VALC #2:3　// 　p2の値 SUBT STOR RETN 1 2 3 4 5 6 7 8 疑似コード生成 　[ #2: offset=4] -54 　　< x > 　　< p2 >=87 疑似コード生成 　　< p1 >=21 MSCW：関数1の位置 RCW:戻り位置= 関数f(関数No.=1) の疑似コード 7 CSTC 0　　// 変数a(=12)の確保 CSTC // 変数b(=21)の確保 PUSH // 変数cの確保 MKSW #2: 1 　// 関数ｆを呼出す VALC #1: 3　　// bの値を積む CSTC 2　　　　// 値87を積む ENTR : 1 2 3 4 5 6 7 Lex_Levelﾚｼﾞｽﾀ #２ #１ #０ 　　　< c > 　　　< b >=21 　　　< a >=12 stack基底 次の疑似ｺｰﾄﾞの実行してゆく

24 質問？