コンパイラとプログラミング⾔語
第12週 関数呼び出しのコード⽣成
2013年7⽉3⽇
⾦岡 晃
【復習】第 11 週
条件分岐⽂と繰り返し⽂のコード⽣成
コンパイラとプログラミング⾔語
授業計画
第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) 期末試験
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>
のローカル変数のエリアへ格納する
ローカル変数の操作
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命令からオフセットだけ離れた命令
に制御が移る。そうでなければ次の命令に制御が移る。<address>は分岐オフ
Java VM バイトコード：フロー制御（２）
goto <address> 指定した<address>を分岐オフセットとして、このgoto命令からオフセットだ
け離れた命令に制御が移る。<address>は、分岐オフセットを表す16ビット の符号付き整数である。
goto_w <address> 指定した<address>を分岐オフセットとして、このgoto_w命令からオフセッ
トだけ離れた命令に制御が移る。基本的にはgoto命令と同じだが、分岐先が 16ビットの符号付き整数で表現できないほど離れている場合に⽤いる。
<address>は、分岐オフセットを表す32ビットの符号付き整数である。
無条件分岐
invokestatic
<method>
スタティックメソッドを呼び出し、引数の値を順にスタックに積んでクラス メソッドを呼び出す。返戻値がある場合は、それがスタックの先頭に積まれ た状態で戻る。<method>はメソッドのエントリ番号を⽰す指定するコード である。
ireturn オペランドスタックの先頭の整数値をポップして、返戻値とし（呼び出し元
のメソッドのオペランドスタックにプッシュして）、実⾏中のメソッドを終 了して呼び出し元に戻る。
メソッド呼び出しと復帰
Java VM バイトコード：条件分岐その２
if_icmpeq <address> オペランドスタックから2つの整数値をポップし、両⽅の値が等しければ、
指定した<address>に制御が移る。そうでなければ次の命令に制御が移る。
if_icmpne <address> オペランドスタックから2つの整数値をポップし、両⽅の値が異なる場合、
指定した<address>に制御が移る。そうでなければ次の命令に制御が移る。
if_icmplt <address> オペランドスタックから2つの整数値をポップし、先頭の値＜1つ
前の値の場合、指定した<address>に制御が移る。そうでなければ 次の命令に制御が移る。
if_icmpgt <address> オペランドスタックから2つの整数値をポップし、先頭の値＞1つ
前の値の場合、指定した<address>に制御が移る。そうでなければ 次の命令に制御が移る。
if_icmple <address> オペランドスタックから2つの整数値をポップし、先頭の値≦1つ
前の値の場合、指定した<address>に制御が移る。そうでなければ 次の命令に制御が移る。
if_icmpge <address> オペランドスタックから2つの整数値をポップし、先頭の値≧1つ
前の値の場合、指定した<address>に制御が移る。そうでなければ 次の命令に制御が移る。
Java VM バイトコード：算術演算その 2
iinc 形式：iinc index, value
indexにあるローカル変数の値をvalueだけ増加させ、indexが⽰すエリアにそ
の値を格納する
0: iconst_3 1: istore_1 2: iconst_4 3: istore_2 4: iload_2 5: iconst_3
6: if_icmplt 11 9: iconst_2
10: istore_1 11: return
分岐をつかったコード例（３）
class Test03{
public static void main(String[] arg){
int i;
int j;
i=3;
j=4;
if(j>=3){
i=2;
} } }
ソースコード バイトコード
繰り返しをつかったコード例（３）
class Test05{
public static void main(String[] arg){
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 20 11: iinc 2, -1 14: iinc 1, 1
17: goto 6
20: return
第 12 週
関数呼び出しのコード⽣成
コンパイラとプログラミング⾔語
本⽇の到達⽬標と概要
• 到達⽬標
– Java VM バイトコードにおける関数呼び出しの理解
• 概要
– 関数呼び出しに関する Java VM バイトコード
– バイトコードにおける関数呼び出しの実現
Java VM バイトコード：フロー制御（２）
goto <address> 指定した<address>を分岐オフセットとして、このgoto命令からオフセットだ
け離れた命令に制御が移る。<address>は、分岐オフセットを表す16ビット の符号付き整数である。
goto_w <address> 指定した<address>を分岐オフセットとして、このgoto_w命令からオフセッ
トだけ離れた命令に制御が移る。基本的にはgoto命令と同じだが、分岐先が 16ビットの符号付き整数で表現できないほど離れている場合に⽤いる。
<address>は、分岐オフセットを表す32ビットの符号付き整数である。
無条件分岐
invokestatic
<method>
スタティックメソッドを呼び出し、引数の値を順にスタックに積んでクラス メソッドを呼び出す。返戻値がある場合は、それがスタックの先頭に積まれ た状態で戻る。<method>はメソッドのエントリ番号を⽰す指定するコード である。
ireturn オペランドスタックの先頭の整数値をポップして、返戻値とし（呼び出し元
のメソッドのオペランドスタックにプッシュして）、実⾏中のメソッドを終
メソッド呼び出しと復帰
エントリ番号
分岐をつかったコード例、の前に
invokestatic <method>
<method>はメソッドのエントリ番号を⽰す指定するコードである。
プログラム中に登場するクラス、メソッドはそれぞれ別のバイトコードが 構成され、それぞれのコードは1つのエントリとしてまとまる。エントリは コンパイル時に分けられ、エントリ番号が振られる。バイトコード上では、
エントリ番号で指定されて呼び出しなどを受ける。
スタックマシンはエントリごとに構成される
（スタック、変数エリアもエントリごと）
分岐をつかったコード例（３）を⾒る
class Test03{
public static void main(String[] arg){
int i;
int j;
i=3;
j=4;
if(j>=3){
i=2;
} } }
ソースコード クラスにエントリ番号0（＃0）
0: aload_0
1: invokespecial #1 4: return
0: iconst_3 1: istore_1 2: iconst_4 3: istore_2 4: iload_2 5: iconst_3
6: if_icmplt 11 9: iconst_2
10: istore_1 11: return mainメソッドに
エントリ番号1（＃1）
呼んでる
関数呼び出しをつかったコード例（１）
public class Test06{
public static void main(String[] args){
int i=3;
int j=4;
int k=0;
k = Test06.testAdd(i,j);
}
public static int testAdd(int i, int j){
return (i+j);
} }
ソースコード
0: iconst_3 1: istore_1 2: iconst_4 3: istore_2 4: iconst_0 5: istore_3 6: iload_1 7: iload_2
8: invokestatic #2 11: istore_3
12: return mainメソッドに エントリ番号1（＃1）
0: iload_0 1: iload_1 2: iadd 3: ireturn testAddメソッドに
エントリ番号2（＃2）
呼んでる（いくつ引数 があるか知っ ている）
関数呼び出しをつかったコード例（２）
public class Test07{
public static void main(String[] args){
int i=3;
int j=4;
int k=0;
k = Test07.testMulp1(i,j);
}
public static int testMulp1(int i, int j){
return (i*j+1);
} }
ソースコード
mainメソッドに エントリ番号1（＃1）
testMulp1メソッドに エントリ番号2（＃2）
呼んでる（いくつ引数 があるか知っ ている）
まとめ
コンパイラとプログラミング⾔語
⾔語処理系
• コンパイラ、リンケージエディタ、エディタ、デバッガ、実⾏時ラ イブラリなど、プログラムの開発・翻訳（コンパイル）・実⾏に関 係するプログラム群の総称
• 処理系とも呼ぶ
エディタ
プログラムソース
プログラムソース
・・・
コンパイラ
コンパイラ
プログラム⽬的
プログラム⽬的
リンケージ エディタ ライブラリ実⾏時
プログラム実⾏
実⾏
デバッガ
コンパイラの論理的な構成
プログラムソース ⽬的
プログラム
コンパイラ
字句解析 構⽂
解析 意味
解析 最適化 コード
⽣成
中間情報（中間語、名前表）
コンパイラの開発における重要なポイント
プログラムソース ⽬的
プログラム
コンパイラ
字句解析 構⽂
解析 意味
解析 最適化 コード
⽣成
中間情報（中間語、名前表）
プログラム⾔語の⽂法の
出来の良し悪しが最重要事項
→ ⾔語の仕様範囲と⽂法を厳密に定める必要
⽂法の形式的な記述⽅式
• バッカス記法
• 構⽂図式
字句解析の概要
• ソースプログラムからトークンを取り出して構⽂解析に渡す
プログラムソース ⽬的
プログラム
コンパイラ
字句解析 構⽂
解析 意味
解析 最適化 コード
⽣成
トークン トークン
中間情報（中間語、名前表）
字句解析の流れ
プログラムソース
字句解析
構⽂解析
⽂字（列）
読み取り 字句
読み取り トークントークン
• ⼈間から⾒るとプログラム
• コンピュータから⾒ると⽂字列 ただの⽂字列
扱い 意味を持つ
要素に分割
分割されたトークンの集まりが
⽂法として間違っていないかチェック
（ここでBNFを使って定義された
⽂法と照らし合わせる）
• 正規表現
• 有限オートマトン
構⽂解析
プログラムソース ⽬的
プログラム
コンパイラ
字句解析 構⽂
解析 意味
解析 最適化 コード
⽣成
トークン トークン
中間情報（中間語、名前表）
構⽂解析
• 字句解析が出⼒したトークンを読み込みながら、そのトークンの列 がプログラム⾔語の⽂法で許されているパターンと合うかを解析す る
プログラムソース 字句解析 トークントークン 構⽂解析
構⽂⽊
構⽂⽊
名前表
• 許されているパターンであれば、トークンの列は構⽂規則 に従って構成され、字句を葉とする構⽂⽊が⽣成される。
• 構⽂解析の結果、ソースプログラムの構造は構⽂⽊として 出⼒され、名前や数字などの情報は名前表に出⼒される。
構⽂解析法
上向き構⽂解析法
（bottom-up parser)
下向き構⽂解析法
（top-down parser)
⼊⼒した記号列が構⽂規則の 右辺と⼀致した場合に左辺の 記号に置き換えていく
記号列として次に何が来るの かを仮定しながら構⽂解析を
進めていく a ＊ ( b + c )
名前 名前
因⼦
項 式
名前 因⼦
項 式
因⼦
項
因⼦
項
上向き 式
解析法構⽂
下向き構⽂
解析法
LL 構⽂解析
⼊⼒された記号列の先頭（最も左）の⾮終端記号に適⽤すべき
⽣成規則を、それ以降の記号列を調べることによって⼀意に決 定することが可能となるようにする
LL： Left to right scan
Left most derivation
LL(k)構⽂解析
先読み記号を最⼤k個まで許すことを意味する
k=1 のとき、バックトラックのない下向き構⽂解析が可能。
そのとき、LL(1)構⽂解析を可能にする⽂法をLL(1)⽂法という
構⽂⽊の表現⽅法：⼆分⽊と四つ組
• ⼆分⽊
– ⼆項演算⼦から成る式や代⼊⽂で利⽤される
– 演算⼦というノード（節点）が 2 つの⼦を持つ。
– 2 つの⼦がオペランド
– 変数や定数は⼦を持たない（葉ノード）
• 四つ組
– 演算⼦、 2 つのオペランド、演算結果の保管先アドレス、という 4 つのデータを 1 つの組として保管する⽅法
– ⼆分⽊に⽐べ、メモリ消費が少ない
=
a +
b c
+
b
c tmp#1=
tmp#1
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
6 $wk2 int 32 4
コンパイラの論理的な構成
プログラムソース ⽬的
プログラム
コンパイラ
字句解析 構⽂
解析 意味
解析 最適化 コード
⽣成
中間情報（中間語、名前表）
• 名前表を利⽤したエラーチェック
– ある識別⼦がプログラム中に現れたときに、構⽂的には正しく
ても、意味が不明になるケースが現れたらエラーを返す
コンパイラの論理的な構成
プログラムソース ⽬的
プログラム
コンパイラ
字句解析 構⽂
解析 意味
解析 最適化 コード
⽣成
中間情報（中間語、名前表）
⽬的プログラムを出⼒する、コンパイラの最終フェーズ
コンピュータが読むため、⽬的プログラムの形式は コンピュータの種類などの環境に強く依存
本講義ではJavaをターゲットにする
Java の仕組み
• コンパイラの種類とバイトコードの実⾏
– Java コンパイラ → インタプリタ
– 動的コンパイラ（ Just‐In‐Time コンパイラ） → 実⾏
– ネイティブコンパイラ → 実⾏
ソースコード バイトコード
（クラスファ イル）
コンパイラ
字句解析 構⽂
解析 意味
解析 コード
⽣成
中間情報（中間語、名前表）
