コンパイラとプログラミング言語
第12週 関数呼び出しのコード生成
2014年6月25日 金岡 晃
授業計画
第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)
期末試験
【復習】第 11 週
条件分岐文と繰り返し文のコード生成
コンパイラとプログラミング言語
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命令からオフセットだけ離れた命令
に制御が移る。そうでなければ次の命令に制御が移る。 は分岐オフ
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）
呼んでる
（いくつ引数 があるか知っ ている）
まとめ
コンパイラとプログラミング言語
授業用 Web サイト
• http://www.klab.is.sci.toho-u.ac.jp/classes/
• 金岡が受け持っている講義の資料（この講 義以外も）をアップロードしています
• 「コンパイラとプログラミング言語」の ページも作成しました
• これまでの講義資料を PDF 化してすべて載
せてあります。
言語処理系
• コンパイラ、リンケージエディタ、エディタ、デバッガ、実行時ラ イブラリなど、プログラムの開発・翻訳（コンパイル）・実行に関 係するプログラム群の総称
• 処理系とも呼ぶ
エディタ
ソース プログラム
ソース プログラム
・・
・
コンパイラ
コンパイラ
目的 プログラム
目的 プログラム
リンケージ エディタ
実行時 ライブラリ
実行 プログラム
実行 デバッガ
コンパイラの論理的な構成
ソース
プログラム 目的
プログラム コンパイラ
字句 解析
構文 解析
意味
解析 最適化 コード 生成
中間情報（中間語、名前表）
コンパイラの開発における重要なポイント
ソース
プログラム 目的
プログラム コンパイラ
字句 解析
構文 解析
意味
解析 最適化 コード 生成
中間情報（中間語、名前表）
プログラム言語の文法の
出来の良し悪しが最重要事項
→ 言語の仕様範囲と文法を厳密に定める必要
文法の形式的な記述方式
• バッカス記法
• 構文図式
字句解析の概要
• ソースプログラムからトークンを取り出して構文解析に渡す
ソース
プログラム 目的
プログラム コンパイラ
字句 解析
構文 解析
意味
解析 最適化 コード 生成
トークン
中間情報（中間語、名前表）
字句解析の流れ
ソース プログラム
字句解析
構文
文字（列） 解析
読み取り 字句
読み取り トークン
• 人間から見るとプログラム
• コンピュータから見ると文字列 ただの文字列
扱い
意味を持つ 要素に分割
分割されたトークンの集まりが 文法として間違っていないかチェック
（ここで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 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 コンパイラ） → 実行 – ネイティブコンパイラ → 実行
ソースコード バイトコード
（クラスファ イル）
コンパイラ 字句 解析
構文 解析
意味 解析
コード 生成
中間情報（中間語、名前表）
