PowerPoint プレゼンテーション - NIPPON INSTITUTE of

【事例演習6】 数式インタプリタ
解 説
“インタプリタの基本的な仕組み”
インタプリタとコンパイラの相違
特殊問題向き言語
高水準言語
アセンブラ言語
アセンブラ
コンパイラ
構文解析&
コード生成
機械語コード
へ
直接変換
インタプリタ
構文解析&
コード生成
疑似コード
疑似コード
(P-Code)
(P-Codeまたは Byte-Code )
コードの最適化
機械語コード生成
機械語
(Intel用,Motorola用,PowerPC用…)
実行
ハードウェア方式
機械語の命令をCPUの論理回路
によって解釈・実行する方式
実行
ファームウェア方式
機械語の命令をマクロ命令と考え
,CPU内に格納されたさらに基本的
なマイクロコードプログラムによ
って評価・実行する方式
仮想マシン
P-Code | Byte-Code
の評価&実行
インタプリタ言語(例えばBASIC,Java等)で組んだ
アプリケーション・プログラム
この範囲はCPUに
依存しない
インタプリタ
機能1:コンパイル(構文解析と疑似コードの生成)
入力された文や式が構文規則(シンタックス)にしたがっているかチェックし,
疑似コードを生成する
疑似コード生成
疑似コード
P(Pseudo)-Code
アプリケーション・プログラムを疑似的なコードや基本的な関数の呼出しに形式に変換したもの
疑似コードの評価・実行
機能2:仮想マシン (Virtual Machine)
疑似コードや基本的な関数呼出しをプログラム的に評価・実行する
実行
Cコンパイラ
(Intel用)
Cコンパイラ
(Motorola用)
Cコンパイラ
(PowerPC用)
仮想マシンの機能を記述したCプログラムを翻訳した機械語コード
(Intel用,Motorola用,PowerPC用…)
JavaにおけるByte-codeの転送と評価・実行
サーバ
Java コンパイラ
コンパイルが生成した
Byte_code(疑似コード)
Java プログラム Byte-code(疑似コード)
Webブラウザ
Java仮想マシン
(Virtual Machine)
インタプリタの基本的な機能構造図
インタプリタ
本体
疑似コードを格納した
テーブルp_code_tbl
p_code_tbl
Parser
Evaluator
(仮想マシンとしての機能)
構文規則にしたがっているか
文 / 式をチェックし,
同時に疑似コードを生成する
regist_variable
変数の登録
get_syllable
一語の切出し
疑似コードを解釈し実行する
スタック操作
構文規則にしたがっているか解析し疑似コードを
生成するモジュール群
演算操作
命令アドレス
制御操作
Parser
(構文チェックと
疑似コード生成の機能)
擬似コードの生成方法とスタック上での操作との対応
計算式
a
+
b
[ a ]
ADD
①逆ポーランド表記に置換する
Aで示される番地から値をスタックの先頭に積む命令
スタック上の2つのオペランドに対して加算演算を
行い,その結果をスタック先頭に積む命令
②対応する順序で疑似コードを生成
a
b
+
[ a ]
[ b ]
Parser
ADD
スタック上でのこのような擬似命令を順に実行すると・・・
ADD演算の実行
Evaluator
< b >
< a >< +a <> b >
<a>
計算式で記述した計算が実行された
aで示される番地からもってきた値
a
+
b
-
c
対応する順序で疑似コードを生成
[ a ]
[ b ]
ADD
[ c ] SUBT
Parser
スタック上でのこのような擬似命令を順に実行すると・・・
SUBT演算の実行
Evaluator
< c >
<a>+<b>
< a > +-< <c>
b >
計算式で記述した計算が実行された
計算式
a
+
b
*
c
疑似コードを生成
[ a ]
[ b ] ?[c]
MULT
ADD
Parser
計算の優先度の高いものを一つ
のまとまりとして扱うと・・・
スタック上でのこのような擬似命令を順に実行すると・・・
Evaluator
MULT演算
ADD演算
< c >
< b ><*b<>c >
<a> +<<b>*<c>
a >
計算式で記述した計算が実行された
計算式
(
a
+
b
)*
c
疑似コードを生成
[ a ] ?[ b ]
ADD
[c]
MULT
Parser
計算の優先度の高いものを一つ
のまとまりとして扱うと・・・
スタック上でのこのような擬似命令を順に実行すると・・・
ADD演算
MULT演算
<<cb>>
< a ><+a<>b >
(<a>+<b>)*<c>
計算式で記述した計算が実行された
Evaluator
構文規則にしたがっているかの構文チェック,
および擬似コードを生成するプログラムの考え方
方針
計算の優先度が高いものは,一つの“まとまり”として扱い
その処理は“まとまり”に任せる
構文チェックと擬似コードの生成
例えば...
数式とは
+
項
項
-
+
・・・
-
+,- より優先度の高い演算を含むものは「項」として一つに
まとめて扱い,その構文チェックと擬似コード生成は「項」に任せる
項とは
*
因子
因子
/
*
・・・
/
*,/ より優先度の高い演算を含むものは「因子」として一つに
まとめて扱い,その構文チェックと擬似コード生成は「因子」に任せる
数字
因子とは
変数名
(
数式
)
構文チェックの方法
以下の構文図式(syntax Diagram)で示すように記述されているかチェックすればよい
+
項(term)
式(expression)::=
*
/
項(term)::=
因子(factor)
因子(factor) ::=
変数名(variable name)
定数(constant)
(
式(expression)
)
実は,構文図式は関数呼出しの手順に対応している
+
-
関数expression ( ) ::=
term ( )
*
/
関数term ( ) ::=
factor ( )
関数 factor ( )::=
variable_name ( )
constant ( )
(
再帰呼出し
expression ( )
)
疑似コード生成の方法
2つterm()が呼出された後に生成
ADD
+
-
関数expression ( ) ::=
SUBT
term ( )
2つfactor()が呼出された後に生成
*
/
関数term ( ) ::=
factor ( )
関数 factor ( )::=
variable_name ( )
MULT
DIVD
VALC: 変数のアドレス
CNST: 定数のアドレス
constant ( )
(
expression ( )
)
例えば,関数expression ( )
のプログラム手順
+
-
関数expression ( ) ::=
term ( )
関数expression ( )
項を解析する関数term()を呼び出す
//※ 関数term()を出るときには,必ず次の字句(1語)をsyllable_buffにもってきている
次の語が演算子“+”か“-”である間,繰り返す
逆ポーランド表記に置換するために演算子を一旦記憶する
次の一語を取り出しsyllable_buffに格納する
項を解析する関数term()を呼び出す
//※ 関数term()を出るときには,必ず次の字句(一語)を
syllable_buffにもってきている
一旦記憶した演算子を後に置いて疑似コードを生成する
Evaluator
(仮想マシンとしての機能)
疑似コードを評価・実行するスタックマシンとは!!
CPU
レジスタ群
レジスタA ( rA)
レジスタB ( rB)
rA, rBとスタック先頭の2語( Stack[TOS],
ハードウェア的に対応が取られる
主記憶
Stack[TOS-1])とは
スタック領域
TOS (Top of Stack:: スタックの先頭位置)
Offset(基底位置からの乖離)
BOS (Base of Stack:: スタックの基底位置)
Evaluatorにおける疑似コードの評価・実行手順
【182ページ参照】
p_code_tblのPC(プログラム カウンタ)が指す位置から疑似コードをフェッチする.
疑似コードを命令部とアドレス部に分解する.
疑似コードの判別
演算命令群
分岐命令群
論理及び関係命令群
ロード,および索引命令群
スタック,およびサブルーチン命令群
PCを一つ進める
No
Yes
PCの終わりか
終わり
質問?
情報処理実験 「数式インタプリタ」
解 説
“スタック操作の基本”
演算の種類によって異なるスタック操作
単項演算
2項演算
(+,-,*,/,剰余%,べき乗^な
ど)
(階乗П,sin,cos,tan等関数な
ど)
2項演算
単項演算
<b>
< a ><+
a ><b>
スタックの先頭
TOS(Top_of_Stack)
スタックの先頭
(pop後)
< <Пaa>>
スタックの先頭
関数call/return時のスタック操作
サンプルプログラム
int a = 12,
< a +p1-p2>=
+<p1>=33
a >=12 -54
[ #2: offset=4]
< x >=
> -54
< p2 >=87
< p1 >=21
Lex_Level
レジスタ
<c>
#2
< b >=21
#1
< a >=12
#0
// 変数xの確保
0
CSTC 0
// 変数a(=12)の確保
0
PUSH
1
CSTC 1
// 変数b(=21)の確保
1
NAMC #2:4 // xのアドレス作成
2
PUSH
// 変数cの確保
2
VALC #1:2 // aの値
3
MKSW #2: 1 // 関数fを呼出す
3
VALC #2:2 // p1の値
4
ADD
4
VALC #1: 3
// bの値を積む
5
CSTC 2
// 値87を積む
6
ENTR
stack基底
次の疑似コードの実行してゆく
※[ LL=#1 ]
関数f(関数No.=1) の疑似コード
7
-54
MSCW:関数1の位置
c;
int f (int p1,float p2) ※[ LL=#2 ]
{
int x;
CONST_TBL
x = a + p1 – p2;
0 12
return x;
1
21
}
2
87
f ( b, 87 );
疑似コード生成
3
疑似コード生成 :
< p2
p1 >=87
>=21
RCW:戻り位置=
b =21,
7
:
5
VALC #2:3 // p2の値
6
SUBT
7
STOR
8
RETN
質問?