仮想マシン ()
仮想マシン 復習 仮想マシンの概要 hsm 仮想マシン
プログラム言語の処理系 ( コンパイラ ) 原始プログラム (Source program) コンパイラ (Compiler) 目的プログラム (Object code) 原始言語 (Source language) 解析 合成 目的言語 (Object Language) コンパイルする / 翻訳する (to compile / to translate)
コンパイラのフェーズ 原始プログラム (Source program) 字句解析 (Scanning) 構文解析 (Parseing) 意味解析 (Semantic Analysis) コード生成 (Code Generation) 目的プログラム (Object code) 4
T Diagram プログラム言語 Cで記述した機能 f f C コンパイラ Pentium 用の C コンパイラ C M_pentium プログラム 言語 M_pentium で記述した機能 f (Pentium の機械語 ) f M_pentium M_pentium 計算機 Pentium 5
ある機能 f の実現 (Implementation) f を機械語 (Pentium) で記述する Pentium の上で実行 f M_pentium M_pentium 6
C 言語による言語処理過程 機能 f の実現 fをc 言語のプログラムとして記述する C Compilerでコンパイルする機械語 (Pentium) によるfに変換された! Pentiumの上で実行 f f C C M_pentium M_pentium M_pentium 7
Java 言語による言語処理過程 機能 f の実現 Javacでコンパイルする Javaバイトコードよるfに変換された!(F.class) Jvm(Java virtual machine) 上で実行 f f Java Java Java Byte Code Java byte code Java byte code Java byte code M_pentium M_PowerPC M_pentium M_PowerPC 8
コンパイラ インタプリタ方式と仮想マシン 原始プログラムをその言語に適した仮想的な計算機 ( 仮想機械, Virtual Machine) の機械語に変換する 現実の計算機の機械語に変換するより容易にコンパイラを作成可能 VM を用いる利点 欠点 移植性が高い ( マシン独立 ) 目的コードが小さい 実行速度が遅い JIT (Just In Time) コンパイラ技術など 9
Java 言語の例 Test.java public class Test{ } Java コンパイラ (javac Test.java) Test.class bb 7 b6 578 b6b 9 b57 Java 仮想機械 (java Test)
Java 言語の例 Test.java public class Test{ public static void main(string[] arg){ int i=; int j=4; System.out.println(i+j); } Test.class の内容 ( 一部 ) od h Test.class で表示 84 949 56 4 5 6 7 8 d a5 b7 b 9 6 9 Test.class を逆アセンブル javap c Test で表示 : iconst_ : istore_ : iconst_4 : istore_ 4: getstatic #; 7: iload_ 8: iload_ 9: iadd : invokevirtual #; : return
演習で作るコンパイラの例 test.hcc Int main() { int i j; i = ; j = 4; putint(i+j); } test.hsm PUSH LDC STV LDC 4 STV LDV LDV AD WRI POP HLT Test.class を逆アセンブル javap c Test で表示 : iconst_ : istore_ : iconst_4 : istore_ 4: getstatic #; 7: iload_ 8: iload_ 9: iadd : invokevirtual #; : return
Hsm (HiStackMachine) の概要 () 演習で用いる仮想機械 ( スタックマシン ) 構成プログラム P 命令列の置き場 プログラムカウンタ (pc) 次に実行する命令を指示 スタック (S) 演算対象 ( 被演算数 演算結果 ) を置く 記憶域 スタックポインタ (sp) スタックトップを指す フレームポインタ (fp) 関数 ( 手続き ) のフレームの開始アドレス ( 後の講義で説明 )
Hsm (HiStackMachine) の概要 () 命令セット () ロード ストア命令 ロード命令 : スタックトップに値を置く ストア命令 : 記憶域として確保した所に値を保存する 記憶域の確保 開放の命令 () 演算命令 算術演算 関係演算 ( 論理演算はない ) () ジャンプ命令 制御命令 無条件ジャンプ 条件ジャンプ 停止命令 (4) 入出力命令 入力 出力 4
hsm の構成図 命令 pc 命令 命令 命令 5 4 5 命令 4 命令 5 sp - 4 P pc = のとき 命令 を実行する pc = のとき 命令 を実行する pc = n のとき命令 n を実行する 値をロードする場合には sp sp+ として S[sp] に置く S 5
hsm の実行例 HLT.. プログラムの終了 LDC N N をスタックトップの上に積む sp++ ; S[sp] N ; pc++ 注 : sp は スタックトップ ( 一番最後に値をロードした場所 ) を指す解釈と 次に値をロードする場所 ( 一番最後に値をロードした場所の一段上 ) を指す解釈が可能 本講義 演習では前者の解釈を採用する 6
実行例 () LDC pc LDC HLT 5 4 5 sp - 4 P S 7
実行例 () LDC pc LDC HLT 5 4 5 sp 4 P S 8
実行例 () LDC pc LDC HLT 5 4 5 sp 4 P S 9
演算命令 SB 引き算命令 : sp-- ; S[sp] S[sp]-S[sp+]; pc++ NEG 符号反転命令 : S[sp] -S[sp]; pc++; LE 関係演算命令 <= sp-- ; if (S[sp] <= S[sp+) then S[sp] else S[sp] ; pc++ 算術演算 : AD, SB,ML,DV, NEG +, -, *, /, 反転関係演算 : EQ, NEQ, LT,LE,GT,GE ==,!=, <, <=, >, >=
実行例 (4) LDC pc LDC SB HLT 5 4 5 sp 4 P S
実行例 (5) LDC pc LDC SB HLT 5 4 5 sp 4 - P S
練習問題 () +5*- を計算する hsm マシン語のプログラムを書け そのプログラムの動作をシミュレートせよ
ロード命令 ストア命令 ( 暫定版 ) STV N ストア命令 S[N] S[sp]; sp--; pc++ LDV N ロード命令 sp++; S[sp] S[N]; pc++ LDC N 即値ロード命令 sp++; S[sp] N; pc++ Hsm の web ページの説明では STV p q s[base(p)+q]=s[t];t=t-;pc=pc+; となっている p= のときは base(p)= である P が 以外の場合については後の講義で説明する 4
メモリの確保と開放 PUSH N メモリを確保 sp sp+n; pc++ POP N メモリを開放 sp sp-n; pc++ 4 つ分の領域を確保 5 5 sp - 4 sp 4 PUSH 4 5
練習問題 () 次のプログラムの動作を説明せよ PUSH LDC 6 STV LDV LDV ML STV 7 POP HLT () () PUSH LDC STV LDC 5 STV LDV LDV ML LDV LDV ML AD STV POP HLT 6
練習問題 (). 次のプログラムと同等の動作をする hsm マシン語プログラムを書け ( 変数用の記憶域を確保し それを利用すること ) c = ; b = 5; a = c * (-) + b * c;. 上記プログラムおよび これまで出てきた例を hsm 仮想機械で実行せよ http://cis.k.hosei.ac.jp/~nakata/lecturecompiler /HiStackMachine-ALL/index.html http://cis.k.hosei.ac.jp/~nakata/lecturecompiler /JavaHiStackMachine-ALL/index.html 7
演習問題 (Problem ) () 練習問題 ()- を行え (p) 実行結果を確かめるために hsm(swing/java 版 ) を用いて a,b,c の最終的な結果が記憶域に保存された状態のスナップショットを取ること 変数の保存 参照についての説明は 以下にもある http://cis.k.hosei.ac.jp/~nakata/lecturecompiler /HiStackMachine-ALL/node8.html () 整数, 四則演算, 括弧からなる中置記法の式を hsm マシン語プログラムに翻訳するコンパイラを JavaCC 使って作成せよ 次のページにあるテストプログラムで確認すること http://cis.k.hosei.ac.jp/~asasaki /lecturecompiler/problem.htm なお プログラムの提出は下記にある提出指針に従うこと http://cis.k.hosei.ac.jp/~asasaki /lecturecompiler/guideline.htm ( 準備中 ) 8
コンパイラ作成の流れと プログラムの実行 +*5 cs7k4.class JavaCC/javac cs7k4.jj LDC LDC LDC 5 ML AD HLT コンパイラ作成の流れ hsm プログラムのコンパイル 実行の流れ 9
再提出レポート等についての注意 再提出レポートは 他のレポートとは別に提出してください 前回との差分がわかるように 最初に提出したものも一緒に提出してください