| 目次 | 索引 |
|---|---|
h2 コンパイラ toc-compilers
h3 逆ポーランド記法 toc-reverse-polish
x と y の和は、普通 x + y と書かれます。
しかし、これは絶対的なものではありません。
+ x y と書いてもよいわけですし、x y + でもよいわけです。
式の書き方で、+ x y のように演算子を前に置くものを、
index 前置記法 prefix notation せんちきほう
と呼びます。
x + y のように演算子を中に置くものを、
index 中置記法 infix notation ちゆうちきほう
と呼びます。
x y + のように演算子を後に置くものを、
index 後置記法 postfix notation こうちきほう
または
index 逆ポーランド記法 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}
となります。
h3 式のコンパイル toc-expression-compile
前回、コンパイラは、
高級言語で書かれたプログラムを機械語に変換するソフトウェアだと説明しました。
コンパイラは、式については大体次のように動きます。
1. 式が構文規則に従っているか確認する。
2. 式を逆ポーランド記法に変換する。
3. 逆ポーランド記法を命令の系列に変換する。
1. については前回触れましたので、今日は 2. と 3. についてです。
中置記法を逆ポーランド記法に変換するには、
スタックを使いますと機械的にできます。
ここで、中置記法の演算は必ず括弧で囲むことにします。
すなわち、中置記法は構文規則
<式> ::= <変数> | (<式> <演算子> <式>)
<変数> ::= 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 + * {}
となり、逆ポーランド記法 x y z + * が得られます。
逆ポーランド記法を命令の系列に変換することは、
Java 仮想マシンでは単純な置き換えでできます。
これは、Java 仮想マシンにおける演算が、
スタックの上で行われるからです。
実際の置き換えは次の通りです。
・逆ポーランド記法の変数 x を命令 iload_1 に置き換える。
・逆ポーランド記法の変数 y を命令 iload_2 に置き換える。
・逆ポーランド記法の変数 z を命令 iload_3 に置き換える。
・逆ポーランド記法の演算子 + を命令 iadd に置き換える。
・逆ポーランド記法の演算子 * を命令 imul に置き換える。
上記の例では、逆ポーランド記法 x y z + * がアセンブリ言語
iload_1, iload_2, iload_3, iadd, imul
に変換されます。
なお、今日扱う命令は次の通りです。
ニーモニック 命令長 第 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 整数の剰余算を行う。
h3 コンパイルの例 toc-compile-examples
今日の演習は次のプログラムから始めます。
/* 1*/ class Ex7 {
/* 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 Ex7.java
b04a001@AsiaA1:~/comp2l% javap -c Ex7
...
6: iload_1
7: iload_2
8: iadd
9: iload_1
10: iload_3
11: iadd
12: imul
...
b04a001@AsiaA1:~/comp2l%
h2 演習 7 toc-exercises
次の式を逆ポーランド記法で表し、アセンブリ言語に変換してください。
プログラム Ex7.java を変更し、
javac コマンドと javap コマンドを実行しますと、
アセンブリ言語が確認できます。
1. ((x * y) + z)
2. (((y + y) + y) + y)
3. (z * (z * (z * z)))
今日の演習7の答案をkonishi@twcu.ac.jpあてにメールで送ってください。 メールには、学生番号、氏名、科目名、授業日（11月5日）を明記してください。