コンパイラとプログラミング言語 第 10 週 Java 仮想マシンとその機械語 2014 年 6 月 11 日 金岡晃
授業計画 第 1 週 (4/9) コンパイラの概要 第 8 週 (5/28) 下向き構文解析 / 構文解析プログラム 第 2 週 (4/16) コンパイラの構成 第 9 週 (6/4) 中間表現と意味解析 第 3 週 (4/23) プログラミング言語の形式的な記述 第 10 週 (6/11) Java 仮想マシンとその機械語 第 4 週 (4/30) プログラミング言語の形式的な記述 第 11 週 (6/18) 条件分岐文と繰り返し文のコード生成 第 5 週 (5/7) 第 6 週 (5/14) 第 7 週 (5/21) 字句解析の概要と非決定性有限オートマトン 決定性有限オートマトン 字句解析プログラム 中間試験 構文解析の概要 / 上向き構文解析 第 12 週 (6/25) 第 13 週 (7/2) 第 14 週 (7/9) (7/23-8/5) 関数呼び出しのコード生成 休講 休講 期末試験 1
コンパイラとプログラミング言語 復習 第 9 週 中間表現と意味解析 2
構文解析とその出力 字句解析が出力したトークンを読み込みながら そのトークンの列がプログラム言語の文法で許されているパターンと合うかを解析する 構文木 ソースプログラム 字句解析 トークン 構文解析 名前表 許されているパターンであれば トークンの列は構文規則に従って構成され 字句を葉とする構文木が生成される 構文解析の結果 ソースプログラムの構造は構文木として出力され 名前や数字などの情報は名前表に出力される 実際はどうやって出力される? 3
構文解析法 上向き構文解析法 (bottom-up parser) 入力した記号列が構文規則の右辺と一致した場合に左辺の記号に置き換えていく 上向き構文解析法 式 項 因子 式 下向き構文解析法 下向き構文解析法 (top-down parser) 記号列として次に何が来るのかを仮定しながら構文解析を進めていく 項 因子 名前 式 項 因子 名前 項 因子 名前 a * ( b + c ) 4
構文木の表現方法 : 二分木と四つ組 二分木 二項演算子から成る式や代入文で利用される 演算子というノード ( 節点 ) が 2 つの子を持つ 2 つの子がオペランド 変数や定数は子を持たない ( 葉ノード ) 四つ組 演算子 2 つのオペランド 演算結果の保管先アドレス という 4 つのデータを 1 つの組として保管する方法 二分木に比べ メモリ消費が少ない = a + + b c tmp#1 = tmp#1 a b c 5
二分木による構文木表現 二項演算子から成る式や代入文で利用される 演算子というノード ( 節点 ) が 2 つの子を持つ 2 つの子がオペランド 変数や定数は子を持たない ( 葉ノード ) d=a*(b+c) = d * a + b c z=y+1/(x-1) = z + y / 1 - x 1 6
四つ組 演算子 2つのオペランド 演算結果の保管先アドレス という4つのデータを1つの組として保管する方法 1. 演算子の情報 2. 第 1オペランドの情報 3. 第 2オペランドの情報 4. 演算結果の保存先 二分木に比べ メモリ消費が少ない d=a*(b+c) = d * a + + b c tmp#1 * a tmp#1 tmp#2 = tmp#2 d b c 7
コンパイラの論理的な構成 コンパイラ ソースプログラム 字句解析 構文解析 意味解析 最適化 コード生成 目的プログラム 中間情報 ( 中間語 名前表 ) 8
意味解析 名前表を利用したエラーチェック ある識別子がプログラム中に現れたときに 構文的には正しくても 意味が不明になるケースが現れたらエラーを返す 例 データ宣言部の処理に 同じ名前を複数回宣言していないかという二重宣言のチェック 実行部の処理に 宣言されていない名前を用いてないかのチェック 代入の場合 左辺は利用可能な名前かどうかのチェック 演算や代入処理に合わせて型の整合をとるためのチェック 9
名前表 ソースプログラム中のデータ宣言部より ユーザが名前を付けた変数や配列 関数についての情報がまとめられた表 書かれる情報例 形式 : 変数 配列 関数 ユーザ定義型など 型 : 整数 実数 文字列 ポインタなど 語長 :1バイト 4バイト 8バイト 種類 : グローバル 仮引数 メモリ上の番地 エントリ番号名前データ型番地領域長 1 a int 12 4 2 b int 16 4 3 c int 20 4 4 d int 24 4 5 $wk1 int 28 4 6 $wk2 int 32 4 10
コンパイラとプログラミング言語 第 10 週 JAVA 仮想マシンとその機械語 11
本日の到達目標と概要 到達目標 Javaにおける目的プログラムと仮想マシンの関係性の理解 キューとスタックの理解 Java VM バイトコードの理解 概要 コード生成と環境の依存 Javaの仕組み キューとスタック スタックマシン Java VM バイトコード 構文木からコードを生成 12
コンパイラの論理的な構成 コンパイラ ソースプログラム 字句解析 構文解析 意味解析 最適化 コード生成 目的プログラム 中間情報 ( 中間語 名前表 ) 目的プログラムを出力する コンパイラの最終フェーズ コンピュータが読むため 目的プログラムの形式はコンピュータの種類などの環境に強く依存 本講義では Java をターゲットにする 13
Java の仕組み コンパイラ ソースコード 字句解析 構文解析 意味解析 コード生成 バイトコード ( クラスファイル ) 中間情報 ( 中間語 名前表 ) コンパイラの種類とバイトコードの実行 Java コンパイラ インタプリタ 動的コンパイラ (Just-In-Time コンパイラ ) 実行 ネイティブコンパイラ 実行 14
仮想計算機と Java ソースプログラム コンパイラ 目的プログラム エディタ ソースプログラム コンパイラ 目的プログラム リンケージエディタ 実行プログラム コンパイルした環境と同じ計算機環境で実行するようにコンパイルされる コンパイラを各計算機の環境ごとにつくらないといけない 目的プログラムは各環境に応じたものを用意しなければならない 実行プログラムは各環境に応じたものになる 環境に依存しない仮想的に考えられた計算機 ( バーチャルマシン 仮想計算機 ) と 仮想計算機用のプログラムを実行可能なソフトを計算機と OS の組ごとに作成すれば プログラム作成者は 1 つのプログラムを作るだけで様々な環境でプログラムが実行できる Java の場合 JavaVM 15
キューとスタック データを保存するデータ構造 スタック キュー 7 プッシュ 5 8 2 9 7 5 8 2 9 ポップ 5 8 2 9 7 7 エンキュー (Enqueue) 5 8 2 9 7 5 8 2 9 7 5 8 2 9 デキュー (Dequeue) LIFO(Last In First Out) FIFO(First In First Out) 16
スタックマシン 変数エリア 0 load 系の命令 演算系の命令 演算器 1 2 3 4 store 系の命令 データ データ データ オペランドスタック 17
Java VM バイトコード : データ操作 (1) ローカル変数の操作 ローカル変数を保持数変数エリア領域から 値を計算に使うために オペランドスタックに積む命令 計算結果があるオペランドスタックの先頭の値を ローカル変数を保持する領域に格納する命令 18 iload iload_<n> istore istore_<n> 形式 :iload index index は符号なし 1 バイト整数 ローカル変数へアクセスできるインデックス index にあるローカル変数の値をオペランドスタックへプッシュする 形式 :iload_0, iload_1, インデックス <n> のローカル変数の値をオペランドスタックへプッシュする 形式 :istore index index は符号なしの 1 バイトの整数で ローカル変数へアクセスできるインデックスである オペランドスタックの先頭の値をポップして ローカル変数の index が示すエリアにその値を格納する 形式 :istore_0, istore_1, オペランドスタックの先頭の値をポップして インデックス <n> のローカル変数のエリアへ格納する
Java VM バイトコード : データ操作 (2) 定数値の処理 定数を計算に用いる場合 直接値をオペランドスタックに積む命令 iconst_m1 iconst_<i> bipush<n> sipush<n> オペランドスタックに -1 を積む 形式 :iconst_1, iconst_2, <i> は 1,2,3,4,5 のいずれかである 整定数 i をスタックに積む 整定数 n をオペランドスタックに積む <n> は符号付整数で -128 <n> 127 の範囲である 整定数 n をオペランドスタックに積む <n> は符号付整数で -32768 <n> 32767 の範囲である スタック操作 pop オペランドスタックの先頭の 1 ワードをポップする データを 1 つオペランドスタックから捨てるための命令である 19
Java VM バイトコード : 算術演算 iadd isub imul idiv ineg オペランドスタックから 2 つの整数値をポップし 加算した結果をオペランドスタックにプッシュする オペランドスタックから 2 つの整数値をポップし 先頭の値を減数 1 つ前の値を被減数として減算した結果をオペランドスタックにプッシュする オペランドスタックから 2 つの整数値をポップし 乗算した結果をオペランドスタックにプッシュする オペランドスタックから 2 つの整数値をポップし 先頭の値を除数 1 つ前の値を被除数として除算した結果をオペランドスタックにプッシュする オペランドスタックの先頭の値の符号を反転させる 20
Java VM バイトコード : フロー制御 (1) 条件分岐 ifeq <address> ifge <address> ifgt <address> ifle <address> iflt <address> 21 オペランドスタックの先頭の値をポップし これが 0 ならば 指定した <address> を分岐オフセットとして この ifeq 命令からオフセットだけ離れた命令に制御が移る そうでなければ次の命令に制御が移る <address> は分岐オフセットを表す 16 ビットの符号付き整数である オペランドスタックの先頭の値をポップし これが 0 以上であれば 指定した <address> を分岐オフセットとして この ifge 命令からオフセットだけ離れた命令に制御が移る そうでなければ次の命令に制御が移る <address> は分岐オフセットを表す 16 ビットの符号付き整数である オペランドスタックの先頭の値をポップし これが 0 より大きければ 指定した <address> を分岐オフセットとして この ifgt 命令からオフセットだけ離れた命令に制御が移る そうでなければ次の命令に制御が移る <address> は分岐オフセットを表す 16 ビットの符号付き整数である オペランドスタックの先頭の値をポップし これが 0 以下ならば 指定した <address> を分岐オフセットとして この ifle 命令からオフセットだけ離れた命令に制御が移る そうでなければ次の命令に制御が移る <address> は分岐オフセットを表す 16 ビットの符号付き整数である オペランドスタックの先頭の値をポップし これが 0 未満ならば 指定した <address> を分岐オフセットとして この iflt 命令からオフセットだけ離れた命令に制御が移る そうでなければ次の命令に制御が移る <address> は分岐オフセットを表す 16 ビットの符号付き整数である
Java VM バイトコード : フロー制御 (2) 無条件分岐 goto <address> goto_w <address> 指定した <address> を分岐オフセットとして この goto 命令からオフセットだけ離れた命令に制御が移る <address> は 分岐オフセットを表す 16 ビットの符号付き整数である 指定した <address> を分岐オフセットとして この goto_w 命令からオフセットだけ離れた命令に制御が移る 基本的には goto 命令と同じだが 分岐先が 16 ビットの符号付き整数で表現できないほど離れている場合に用いる <address> は 分岐オフセットを表す 32 ビットの符号付き整数である メソッド呼び出しと復帰 invokestatic <method> ireturn 22 スタティックメソッドを呼び出し 引数の値を順にスタックに積んでクラスメソッドを呼び出す 返戻値がある場合は それがスタックの先頭に積まれた状態で戻る <method> はメソッドのエントリ番号を示す指定するコードである オペランドスタックの先頭の整数値をポップして 返戻値とし ( 呼び出し元のメソッドのオペランドスタックにプッシュして ) 実行中のメソッドを終了して呼び出し元に戻る
構文木からバイトコードを生成 d=a*(b+c) = d * a + b c エントリ番号名前データ型番地領域長 1 a int 12 4 2 b int 16 4 3 c int 20 4 4 d int 24 4 iload 1 iload 2 iload 3 iadd imul istore 4 23
バイトコード生成と後置記法 d=a*(b+c) dabc+*= = は代入なので最後に持ってくる = 後置記法で表すと abc+* d * a + b c エントリ番号名前データ型番地領域長 1 a int 12 4 2 b int 16 4 3 c int 20 4 4 d int 24 4 iload 1 iload 2 iload 3 iadd imul istore 4 24
構文木からバイトコードを生成 : 例題 z=y+1/(x-1) = z + y / 1 - x 1 エントリ番号名前データ型番地領域長 1 x int 12 4 2 y int 16 4 3 z int 20 4 25
本日の到達目標と概要 到達目標 Javaにおける目的プログラムと仮想マシンの関係性の理解 キューとスタックの理解 Java VM バイトコードの理解 概要 コード生成と環境の依存 Javaの仕組み キューとスタック スタックマシン Java VM バイトコード 構文木からコードを生成 26