Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


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 機能1:コンパイル(構文解析と疑似コードの生成)
インタプリタ言語(例えばBASIC,Java等)で組んだ      アプリケーション・プログラム この範囲はCPUに 依存しない インタプリタ  機能1:コンパイル(構文解析と疑似コードの生成) 入力された文や式が構文規則(シンタックス)にしたがっているかチェックし, 疑似コードを生成する         疑似コード P(Pseudo)-Code    アプリケーション・プログラムを疑似的なコードや基本的な関数の呼出しに形式に変換したもの 疑似コード生成 疑似コードの評価・実行   機能2:仮想マシン (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   スタック上の2つのオペランドに対して加算演算を      行い,その結果をスタック先頭に積む命令   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 * c 疑似コードを生成 [ a ]  [ b ]  [c] MULT          ? ADD Parser スタック上でのこのような擬似命令を順に実行すると・・・ Evaluator < b > * < c > MULT演算 <a> + <b>*<c> ADD演算 < c >  < b >  < a >  計算式で記述した計算が実行された

10 スタック上でのこのような擬似命令を順に実行すると・・・
計算式 計算の優先度の高いものを一つのまとまりとして扱うと・・・ ( a + b )* c 疑似コードを生成 [c]  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  2つterm()が呼出された後に生成                +                  -  関数expression ( ) ::=        term ( )                     *                /  関数term ( ) ::=         factor ( )  関数 factor ( )::=        variable_name ( )           constant ( )        (    expression ( )    ) MULT  DIVD 2つfactor()が呼出された後に生成 VALC: 変数のアドレス  CNST: 定数のアドレス

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

17   Evaluator (仮想マシンとしての機能)

18 疑似コードを評価・実行するスタックマシンとは!!
CPU レジスタ群    レジスタ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 演算の種類によって異なるスタック操作 2項演算 単項演算 < a > + <b> < П a >
  2項演算 (+,-,*,/,剰余%,べき乗^など)    単項演算 (階乗П,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 // 変数xの確保 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  // 関数fを呼出す VALC #1: 3  // bの値を積む CSTC 2    // 値87を積む ENTR : 1 2 3 4 5 6 7 Lex_Levelレジスタ #2 #1 #0    < c >    < b >=21    < a >=12 stack基底 次の疑似コードの実行してゆく

24 質問?


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

Similar presentations


Ads by Google