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