コンパイラとプログラミング言語

(1)

コンパイラとプログラミング言語

第11週条件分岐文と繰り返し文のコード生成

2014年6月18日金岡晃

(2)

授業計画

第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- 8/5)

期末試験

(3)

【復習】第 10 週

JAVA 仮想マシンとその機械語

コンパイラとプログラミング言語

(4)

コンパイラの論理的な構成

ソース

プログラム目的

プログラムコンパイラ

字句解析

構文解析

意味

解析最適化コード生成

中間情報（中間語、名前表）

目的プログラムを出力する、コンパイラの最終フェーズ

コンピュータが読むため、目的プログラムの形式はコンピュータの種類などの環境に強く依存

本講義ではJavaをターゲットにする

(5)

Java の仕組み

•

コンパイラの種類とバイトコードの実行

– Java

コンパイラ

→

インタプリタ

–

動的コンパイラ（

Just-In-Time

コンパイラ）

→

実行

–

ネイティブコンパイラ

→

実行

ソースコードバイトコード

（クラスファイル）

コンパイラ字句解析

構文解析

意味解析

コード生成

中間情報（中間語、名前表）

(6)

• コンパイラを各計算機の環境ごとにつくらないといけない

• 目的プログラムは各環境に応じたものを用意しなければならない

• 実行プログラムは各環境に応じたものになる

仮想計算機と Java

エディタ

ソースプログラム

・・

・

コンパイラ

目的プログラム

リンケージ

エディタ実行

プログラム

コンパイルした環境と同じ計算機環境で実行するようにコンパイルされる

環境に依存しない仮想的に考えられた計算機（バーチャルマシン、仮想計算機）と、

仮想計算機用のプログラムを実行可能なソフトを計算機とOSの組ごとに作成すれば、

プログラム作成者は1つのプログラムを作るだけで様々な環境でプログラムが実行できる

Javaの場合、JavaVM

(7)

スタックマシン

0 1 2 3 4

・・・・・・

変数エリア

load系の命令

store系の命令

データ

データデータ

・・・

オペランドスタック

演算系の

命令演算器

(8)

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, …

オペランドスタックの先頭の値をポップして、インデックス<n>

のローカル変数のエリアへ格納する

ローカル変数の操作

(9)

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つオペランドスタックから捨てるための命令である。

スタック操作

(10)

Java VM バイトコード：算術演算

iadd オペランドスタックから2つの整数値をポップし、加算した結果をオペランドスタックにプッシュする

isub オペランドスタックから2つの整数値をポップし、先頭の値を減数、1つ前の値を被減数として減算した結果をオペランドスタックにプッシュする imul オペランドスタックから2つの整数値をポップし、乗算した結果をオペラン

ドスタックにプッシュする

idiv オペランドスタックから2つの整数値をポップし、先頭の値を除数、1つ前の値を被除数として除算した結果をオペランドスタックにプッシュする ineg オペランドスタックの先頭の値の符号を反転させる。

(11)

Java VM

バイトコード：フロー制御（１）条件分岐

ifeq <address> オペランドスタックの先頭の値をポップし、これが0ならば、指定した

<address>を分岐オフセットとして、このifeq命令からオフセットだけ離れた命

令に制御が移る。そうでなければ次の命令に制御が移る。<address>は分岐オフセットを表す16ビットの符号付き整数である。

ifge <address> オペランドスタックの先頭の値をポップし、これが0以上であれば、指定した

<address>を分岐オフセットとして、このifge命令からオフセットだけ離れた命令

に制御が移る。そうでなければ次の命令に制御が移る。<address>は分岐オフセットを表す16ビットの符号付き整数である。

ifgt <address> オペランドスタックの先頭の値をポップし、これが0より大きければ、指定した

<address>を分岐オフセットとして、このifgt命令からオフセットだけ離れた命令

ifle <address> オペランドスタックの先頭の値をポップし、これが0以下ならば、指定した

<address>を分岐オフセットとして、このifle命令からオフセットだけ離れた命令

iflt <address> オペランドスタックの先頭の値をポップし、これが0未満ならば、指定した

<address>を分岐オフセットとして、このiflt命令からオフセットだけ離れた命令

に制御が移る。そうでなければ次の命令に制御が移る。は分岐オフ

(12)

Java VM

バイトコード：フロー制御（２）

goto <address> 指定した<address>を分岐オフセットとして、このgoto命令からオフセットだ

け離れた命令に制御が移る。<address>は、分岐オフセットを表す16ビットの符号付き整数である。

goto_w <address> 指定した<address>を分岐オフセットとして、このgoto_w命令からオフセッ

トだけ離れた命令に制御が移る。基本的にはgoto命令と同じだが、分岐先が 16ビットの符号付き整数で表現できないほど離れている場合に用いる。

<address>は、分岐オフセットを表す32ビットの符号付き整数である。

無条件分岐

invokestatic

スタティックメソッドを呼び出し、引数の値を順にスタックに積んでクラスメソッドを呼び出す。返戻値がある場合は、それがスタックの先頭に積まれた状態で戻る。<method>はメソッドのエントリ番号を示す指定するコードである。

ireturn オペランドスタックの先頭の整数値をポップして、返戻値とし（呼び出し元

のメソッドのオペランドスタックにプッシュして）、実行中のメソッドを終了して呼び出し元に戻る。

メソッド呼び出しと復帰

(13)

バイトコード生成と後置記法

d=a*(b+c)

=

d *

a +

b c

iload 1 iload 2 iload 3 iadd imul istore 4

エントリ番号 名前 データ型番地領域長

1 a int 12 4

2 b int 16 4

3 c int 20 4

4 d int 24 4

後置記法で表すと

dabc+*= ⁼_{後に持ってくる}^{は代入なので最} abc+*

(14)

第

11

週

条件分岐文と繰り返し文のコード生成

コンパイラとプログラミング言語

(15)

本日の到達目標と概要

•

到達目標

– Java VM

バイトコードにおける分岐と繰り返しの理解

•

概要

–

分岐に関する

Java VM

バイトコード

–

バイトコードにおける繰り返しの実現

(16)

Java VM

バイトコード：条件分岐その２

if_icmpeq <address> オペランドスタックから2つの整数値をポップし、両方の値が等しければ、

指定した<address>に制御が移る。そうでなければ次の命令に制御が移る。

if_icmpne <address> オペランドスタックから2つの整数値をポップし、両方の値が異なる場合、

指定した<address>に制御が移る。そうでなければ次の命令に制御が移る。

if_icmplt <address> オペランドスタックから2つの整数値をポップし、先頭の値＞1つ

前の値の場合、指定した<address>に制御が移る。そうでなければ次の命令に制御が移る。

if_icmpgt <address> オペランドスタックから2つの整数値をポップし、先頭の値＜1つ

if_icmple <address> オペランドスタックから2つの整数値をポップし、先頭の値≧1つ

if_icmpge <address> オペランドスタックから2つの整数値をポップし、先頭の値≦1つ

(17)

分岐をつかったコード例（１）

0: iconst_3 1: istore_1 2: iconst_4 3: istore_2 4: iload_1 5: iconst_2

6: if_icmple 5 9: iconst_5

10: istore_2 11: return class Test01{

public static void main(String[] arg){

int i;

int j;

i=3;

j=4;

if(i>2){

j = 5;

} } }

(18)

分岐をつかったコード例（２）

0: iconst_3 1: istore_1 2: iconst_4 3: istore_2 4: iload_1 5: iload_2 6: iadd 7: istore_3 8: iload_3 9: iconst_5

10: if_icmplt 5 13: iconst_5

14: istore_3 15: return class Test03{

int i;

int j;

int k;

i=3;

j=4;

k=i+j;

if(k>=5){

k=5;

} } }

(19)

分岐をつかったコード例（３）

class Test03{

int i;

int j;

i=3;

j=4;

if(j>=3){

i=2;

} } }

(20)

Java VM バイトコード：算術演算その 2

iinc 形式：iinc index, value

indexにあるローカル変数の値をvalueだけ増加させ、indexが示すエリアにそ

の値を格納する

(21)

繰り返しをつかったコード例（１）

0: iconst_3 1: istore_1 2: iconst_4 3: istore_2 4: iconst_0 5: istore_3 6: iload_3

7: bipush 10 9: if_icmpge 9 12: iinc 3, 1

15: goto 6

18: return class Test02{

int i;

int j;

i=3;

j=4;

for(int k=0;k<10;k++){

; } } }

(22)

繰り返しをつかったコード例（２）

0: iconst_3 1: istore_1 2: iconst_4 3: istore_2 4: iconst_0 5: istore_3 6: iload_3

7: bipush 10 9: if_icmpge 12 12: iinc 1, 1 15: iinc 3, 1

18: goto 6

21: return class Test02{

int i;

int j;

i=3;

j=4;

for(int k=0;k<10;k++){

i++;

} } }

(23)

繰り返しをつかったコード例（３）

class Test05{

int i;

int j;

i=3;

j=4;

for(i=0;i<5;i++){

j--;

} } }

0: iconst_3 1: istore_1 2: iconst_4 3: istore_2 4: iconst_0 5: istore_1 6: iload 1 7: iconst_5 8: if_icmpge **

9: iinc 2,-1 10: iinc 1,1 11: goto 6

(24)

本日の到達目標と概要

•

到達目標

– Java VM

バイトコードにおける分岐と繰り返しの理解

•

概要

–

分岐に関する

Java VM

バイトコード

–