[小西ホームページ]   [目次・索引]   [前の授業]   [次の授業]

コンピュータIIL（情報科学入門）第6回

目次
6.1 コンパイラ（1）
6.1.1 コンパイラとは
6.1.2 逆ポーランド記法
6.1.3 式のコンパイル
6.1.4 コンパイルの例
6.2 演習6
6.3 レポート課題
6.4 参考文献
索引
オブジェクト・コード   逆ポーランド記法   原始プログラム   高級言語   後置記法   コンパイラ   コンパイル   前置記法   ソース・コード   中置記法   低級言語   目的プログラム  

6.1 コンパイラ（1）

6.1.1 コンパイラとは

機械語は人間にとって分かりにくいのでアセンブラが考え出された、ということは前回説明しました。 しかし、アセンブリ言語もそれほど分かりやすくはありません。 x と y を足すことを、機械語で 0x60 と書くよりは、アセンブリ言語で iadd と書くほうが多少ましですが、やはり x + y と書くのが一番です。 そこで開発されたのが、高級言語とコンパイラです。

高級言語 （ high level language ） とは、数式や英単語の組み合わせで記述できる、人間にとって分かりやすく設計されたプログラミング言語です。 JavaやCは高級言語です。 高級言語と比較するために、機械語とアセンブリ言語を 低級言語 （ low level language ） と呼ぶことがあります。

CPUは高級言語を直接理解することはできませんので、高級言語のプログラムを機械語に変換する必要があります。 この変換ソフトウェアが コンパイラ （ compiler ） です。 コンパイラで変換することを コンパイル （ compile ） と言います。 Javaでは、javacコマンドがコンパイラです。

なお、変換前のプログラムは、 原始プログラム （ source program ） または ソース・コード （ source code ） と呼ばれます。 変換後のプログラムは、 目的プログラム （ target program ） または オブジェクト・コード （ object code ） と呼ばれます。

6.1.2 逆ポーランド記法

x と y の和は、普通 x + y と書かれます。 しかし、これは絶対的なものではありません。 + x y と書いてもよいわけですし、 x y + でもよいわけです。

式の書き方で、+ x y のように演算子を前に置くものを、 前置記法 （ prefix notation ） と呼びます。 x + y のように演算子を中に置くものを、 中置記法 （ infix notation ） と呼びます。 x y + のように演算子を後に置くものを、 後置記法 （ postfix notation ） または 逆ポーランド記法 （ reverse Polish notation ） と呼びます。

中置記法は、式の普通の表記法です。 前置記法と後置記法は、プログラミングと深い関係があります。 以下では後置記法、すなわち逆ポーランド記法について説明します。

まず、逆ポーランド記法では括弧は不要です。 中置記法で括弧がなければ、( x * y ) + z と x * ( y + z ) は区別できません。 しかし、逆ポーランド記法では、それぞれ ( x y *) z + と x ( y z +) * となり、括弧を取り除いても大丈夫です。

次に、逆ポーランド記法は演算の順序を忠実に表します。 中置記法の x * ( y + z ) は、「 x に、 y に z を足したものを掛ける」という意味ですが、これは逆ポーランド記法の x y z + * と同じ順序です。

逆ポーランド記法の第3の特徴は、スタックを使って機械的に式の計算ができることです。 今、 x = 2, y = 3, z = 4 であるとします。 中置記法の x * ( y + z ) で式を計算しますと、

2 * (3 + 4) = 2 * 7
= 14

と、括弧に気を付けながら書き換えを行うことになります。 これに対して、逆ポーランド記法では、

というスタック操作でよいのです。 ここで、スタックの要素を { と } で囲み、右に伸びるように表現します。 逆ポーランド記法の x y z + * で計算しますと、

{} 2 3 4 + * → {2} 3 4 + *
→ {2, 3} 4 + *
→ {2, 3, 4} + *
→ {2, 7} *
→ {14}

となります。

6.1.3 式のコンパイル

コンパイラは、高級言語から機械語へ変換するソフトウェアですが、特に式については、大体次のように動きます。

  1. 式が文法的に正しいか確認する。
  2. 式を逆ポーランド記法に変換する。
  3. 逆ポーランド記法を命令の系列に変換する。

今日は、2. と 3. について説明します。 1. については次回触れます。

中置記法を逆ポーランド記法に変換するには、スタックを使いますと機械的にできます。 ここで、中置記法の演算は必ず括弧で囲むことにします。

変換方法は次の通りです。

例えば、中置記法の ( x * ( y + z )) は、

{} (x* (y+z)) → {}x* (y+z))
→ x{} * (y+z))
→ x{*} (y+z))
→ x{*}y+z))
→ x y{*} +z))
→ x y{*, +}z))
→ x y z{*, +}))
→ x y z+ {*})
→ x y z+ * {}

となり、逆ポーランド記法 x y z + * が得られます。

逆ポーランド記法を命令に変換する前に、命令セットを決めておきます。 今日扱う命令は次の通りです。

表 6.1  Java仮想マシンの命令
ニーモニック 命令長 第1バイト 第2バイト 命令
nop 1バイト 0x00
何もしない。
iconst_0 1バイト 0x03
整数0をスタックにプッシュする。
iconst_1 1バイト 0x04
整数1をスタックにプッシュする。
iconst_2 1バイト 0x05
整数2をスタックにプッシュする。
iconst_3 1バイト 0x06
整数3をスタックにプッシュする。
iconst_4 1バイト 0x07
整数4をスタックにプッシュする。
bipush 2バイト 0x10 byte 整数byteをスタックにプッシュする。
iload 2バイト 0x15 index 第index変数の値をスタックにプッシュする。
iload_1 1バイト 0x1b
第1変数の値をスタックにプッシュする。
iload_2 1バイト 0x1c
第2変数の値をスタックにプッシュする。
iload_3 1バイト 0x1d
第3変数の値をスタックにプッシュする。
istore 2バイト 0x36 index スタックからポップした値を第index変数に格納する。
istore_1 1バイト 0x3c
スタックからポップした値を第1変数に格納する。
istore_2 1バイト 0x3d
スタックからポップした値を第2変数に格納する。
istore_3 1バイト 0x3e
スタックからポップした値を第3変数に格納する。
iadd 1バイト 0x60
整数の足し算を行う。
isub 1バイト 0x64
整数の引き算を行う。
imul 1バイト 0x68
整数の掛け算を行う。
idiv 1バイト 0x6c
整数の割り算を行う。
irem 1バイト 0x70
整数の剰余算を行う。

逆ポーランド記法を命令の系列に変換することは、Java仮想マシンでは単純な置き換えでできます。 これは、Java仮想マシンにおける演算が、スタックの上で行われるからです。 実際の置き換えは次の通りです。

上記の例では、逆ポーランド記法 x y z + * が、アセンブリ言語 iload_1 , iload_2 , iload_3 , iadd , imul に変換されます。

6.1.4 コンパイルの例

今日の演習は次のプログラムから始めます。 

/*  1*/ class Ex6 {
/*  2*/     public static void main (String[] args) {
/*  3*/         int x = 2, y = 3, z = 4;
/*  4*/         x = ((x + y) * (x + z));
/*  5*/         System.out.println(x);
/*  6*/     }
/*  7*/ }

4行目の代入文の右辺に注目します。

例題1. 式 (( x + y ) * ( x + z )) を逆ポーランド記法で表し、アセンブリ言語に変換してください。 javacコマンドとjavapコマンドを実行しますと、アセンブリ言語が確認できます。

解答例1.

{} ((x+y) * (x+z)) → {} (x+y) * (x+z))
→ {}x+y) * (x+z))
→ x{} +y) * (x+z))
→ x{+}y) * (x+z))
→ x y{+} ) * (x+z))
→ x y+ {} * (x+z))
→ x y+ {*} (x+z))
→ x y+ {*}x+z))
→ x y+x{*} +z))
→ x y+x{*, +}z))
→ x y+x z{*, +} ))
→ x y+x z+ {*} )
→ x y+x z+ * {}

したがって、逆ポーランド記法では x y + x z + * となり、アセンブリ言語では iload_1 , iload_2 , iadd , iload_1 , iload_3 , iadd , imul となる。 

b04a001@AsiaA1:~/comp2l% javac Ex6.java
b04a001@AsiaA1:~/comp2l% javap -c Ex6
...
   6:   iload_1
   7:   iload_2
   8:   iadd
   9:   iload_1
   10:  iload_3
   11:  iadd
   12:  imul
...
b04a001@AsiaA1:~/comp2l%

6.2 演習6

次の式を逆ポーランド記法で表し、アセンブリ言語に変換してください。 プログラムEx6.javaを変更し、javacコマンドとjavapコマンドを実行しますと、アセンブリ言語が確認できます。

  1. (( x * y ) + z )
  2. ((( y + y ) + y ) + y )
  3. ( z * ( z * ( z * z )))

6.3 レポート課題

今日の演習6の答案をメールで提出してください。 メールの差出人は学内のアドレス（b04a001@twcu.ac.jpなど）とし、メールの宛先はkonishi@twcu.ac.jpとします。 メールの本文には、学生番号、氏名、科目名、授業日（11月4日）を明記してください。

6.4 参考文献

[小西ホームページ]   [目次・索引]   [前の授業]   [次の授業]
2005年11月4日更新
小西 善二郎 <konishi@twcu.ac.jp>
Copyright (C) 2005 Zenjiro Konishi. All rights reserved.