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

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

第

10

Java

2013年6⽉19⽇

⾦岡 晃

授業計画

第

1

(4/10)

コンパイラの概要 第

2

(4/24)

コンパイラの構成 第

3

(5/1)

プログラミング⾔語の形式的な 記述

第

4

(5/8)

字句解析の概要と⾮決定性有限 オートマトン

第

5

(5/15)

決定性有限オートマトン・字句 解析プログラム

第

6

(5/22)

中間試験 第

7

(5/29)

構⽂解析の概要

/

第

8

(6/5)

下向き構⽂解析

/

第

9

(6/12)

中間表現と意味解析 第

10

(6/19)

Java

11

(6/26)

条件分岐⽂と繰り返し⽂の コード⽣成

第

12

(7/3)

関数呼び出しのコード⽣成 第

13

(7/10)

休講

(7/31)

【復習】第 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

第 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未満ならば、指定した

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

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

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

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

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

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

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

無条件分岐

invokestatic

<method>

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

メソッド呼び出しと復帰

構⽂⽊からバイトコードを⽣成

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

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

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

後置記法で表すと

dabc+*= ⁼

abc+*

構⽂⽊からバイトコードを⽣成：例題

z=y+1/(x‐1)

=

z +

y /

1 ‐

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

1 x int 12 4

x 1

本⽇の到達⽬標と概要

• 到達⽬標

– Java における⽬的プログラムと仮想マシンの関係性の理解

– キューとスタックの理解

– Java VM バイトコードの理解

• 概要

– コード⽣成と環境の依存 – Java の仕組み

– キューとスタック – スタックマシン

– Java VM バイトコード

– 構⽂⽊からコードを⽣成