JavaでJVM言語を作ってみる(4) - 四則演算式をコンパイル
前回までは、JVMのコード生成について実験してきました。
今回は、ちょっとだけ解析器の方へ進んでみます。
最初は、四則演算＋αに限定して考えていきます。
四則演算の命令コード
JVMの命令コードには、直接四則演算を行う命令があります。第2回で説明したiconst_0と同様に、例えばiaddは、型i＝int、命令add（加算）＝int値の加算、のようになっています。JavaVM仕様の表記に倣うと"Tadd"のようになります。その他の算術演算は下記となります。
Tadd 加算(add): stack[1] + stack[0] → stack
Tsub 減算(subtract): stack[1] - stack[0] → stack
Tmul 乗算(multiply): stack[1] * stack[0] → stack
Tdiv 除算(divide): stack[1] / stack[0] → stack
Trem 剰余演算(remainder): stack[1] % stack[0] → stack
※T=i, l, f, d
算術演算命令には他にも"Tneg"や"iinc"などがありますが、ここでは割愛します。
手動コンパイル
算術演算ではどのようなコードを生成すれば良いのでしょうか。コンパイラの前に、手動で命令コードリストを作ってみましょう。
毎回BCELでの生成コードを書くのは冗長なので、以降は命令コードリストだけの説明をする場合は下記のように命令コードだけを書くようにします。ConstantPoolのエントリは番号を書かずに文字列表記のみに置き換えています。
# mainメソッド getstatic Field java/lang/System.out:Ljava/io/PrintStream; dup ldc String "5 = " # 式の文字列を出力 invokevirtual Method java/io/PrintStream.print:(Ljava/lang/String;)V iconst_5 # 5 → stack この値を結果として出力 invokevirtual Method java/io/PrintStream.println:(I)V return
これは、次のJavaコードと同等です。
System.out.print("5 = "); System.out.println(5); // "5 = 5"と出力される
さらに次からは、printより前とprintlnより後も省略します。
では、実際に計算式でやってみましょう。コメントはスタックのイメージを示しています。
5 + 2 + 4 = 11 -------------------------------- iconst_5 # → 5 iconst_2 # → 2 5 iadd # 5 + 2 → 7 iconst_4 # → 4 7 iadd # 7 + 4 → 11
この場合は、ただ頭から順番に
- 数値があったらスタックに積む
- 演算子があったら次の要素をスタックに積み計算を実行
のように処理していけば良さそうです。
補足：上記のような定数だけの算術演算のJavaコードをコンパイルした場合は、コンパイル時に値が決定するため、classファイルでは定数に置き換えられてしまいます。これはJavaに限らず、どのような言語でも行っている初歩的な最適化です。
今度は乗算を混ぜてみます。
5 + 2 * 4 = 13 -------------------------------- iconst_2 # → 2 iconst_4 # → 4 2 imul # 4 * 2 → 8 iconst_5 # → 5 8 iadd # 8 + 5 → 13
この場合は優先順位が異なるため、頭から順に処理するだけでは上手くいきません。
演算子や関数の評価順序は、プログラミング言語を設計する上で重要な問題です。書いたときにどちらとも取れるあいまいな表記については、言語仕様として評価順序を「未定義」とするケースもあります。すべての評価式を括弧でくくるような言語もあります。明快な表記を取るか、厳格な書式を取るか、設計する上で考えなければならない点です。
ここでは、コンパイラを単純にするために、
- 空の要素はスキップ
- 演算子があったら
- 数値があったらスタックに積む
というルールにします。
これに従うと、
5 + 2 * 4 = 13 -------------------------------- iconst_5 # → 5 iconst_2 # → 2 5 iconst_4 # → 4 2 5 imul # 4 * 2 → 8 5 iadd # 8 + 5 → 13
となります。スタックの深さが2で済んでいたのが、3になってしまいました。今回は単純さを優先するので、これで続けます。
四則演算プログラムのコンパイル
手動でコード生成を確認した部分を、自動化してみます。
- ミニコンパイラ"CalcGen"
import static org.apache.bcel.Constants.INVOKEVIRTUAL; import static org.apache.bcel.generic.InstructionConstants.*; import java.io.*; import java.util.*; import org.apache.bcel.*; import org.apache.bcel.classfile.*; import org.apache.bcel.generic.*; final class CalcBase { public static void main(String[] args) { // } } public final class CalcGen { static void generate(String exp) throws IOException { // class "Calc" final String className = "Calc"; ClassGen cg = new ClassGen(getBaseClass()); cg.setClassName(className); InstructionFactory factory = new InstructionFactory(cg); // method: public static void main(String[] args) Method mainMethod = cg.containsMethod("main", "([Ljava/lang/String;)V"); MethodGen mg = new MethodGen(mainMethod, className, cg.getConstantPool()); InstructionList il = mg.getInstructionList(); try { il.delete(il.getEnd()); } catch (TargetLostException ex) { // ignore } il.append(factory.createGetStatic(System.class.getName(), "out", Type.getType(PrintStream.class))); il.append(DUP); il.append(factory.createConstant(" " + exp + " = ")); il.append(factory.createInvoke(java.io.PrintStream.class.getName(), "print", Type.VOID, new Type[]{Type.STRING}, INVOKEVIRTUAL)); // 生成開始 LinkedList<String> q = new LinkedList<String>(Arrays.asList(exp.split(" "))); while (!q.isEmpty()) { final String s = q.poll(); if (which(s, "+", "-") && q.size() >= 3 && which(q.get(1), "*", "/", "%")) { q.addAll(3, Arrays.asList(s, "")); } else { if (which(s, "+", "-", "*", "/", "%")) { genCode(q.poll(), il, factory); } genCode(s, il, factory); } } // 生成終了 il.append(factory.createInvoke(java.io.PrintStream.class.getName(), "println", Type.VOID, new Type[]{Type.INT}, INVOKEVIRTUAL)); il.append(RETURN); // end of instructions mg.setMaxStack(); mg.setMaxLocals(); cg.replaceMethod(mainMethod, mg.getMethod()); // generate JavaClass c = cg.getJavaClass(); c.setSourceFileName(className + ".java"); c.dump(className + ".class"); } static void genCode(String s, InstructionList il, InstructionFactory factory) { if (s.trim().length() == 0) { // skip } else if (which(s, "+", "-", "*", "/", "%")) { // 演算子 il.append(InstructionFactory.createBinaryOperation(s, Type.INT)); } else if (s.matches("-?\\d+")) { // 定数 il.append(factory.createConstant(Integer.valueOf(s))); } else { throw new IllegalArgumentException("unexpected symbol: " + s); } } static boolean which(String s1, String... list) { for (final String s2 : list) { if (s2.equals(s1)) { return true; } } return false; } static JavaClass getBaseClass() { try { return Repository.lookupClass(CalcBase.class); } catch (ClassNotFoundException ex) { throw new RuntimeException(ex); } } public static void main(String[] args) { if (args.length > 0) { StringBuilder buffer = new StringBuilder(); for (final String arg : args) { buffer.append(' '); buffer.append(arg); } try { generate(buffer.substring(1).replace('x', '*')); } catch (IOException ex) { throw new RuntimeException(ex); } } } }
- 実行結果
# ※calcgen=java CalcGen(bcel.jarがパスに通っていること)
$ ./calcgen 5 + 2 x 4 && java Calc
5 + 2 * 4 = 13
$ javap -c Calc.class
Compiled from "CalcGen.java"
final class Calc {
Calc();
Code:
0: aload_0
1: invokespecial #8 // Method java/lang/Object."<init>":()V
4: return
public static void main(java.lang.String[]);
Code:
0: getstatic #27 // Field java/lang/System.out:Ljava/io/PrintStream;
3: dup
4: ldc #29 // String 5 + 2 * 4 =
6: invokevirtual #35 // Method java/io/PrintStream.print:(Ljava/lang/String;)V
9: iconst_5
10: iconst_2
11: iconst_4
12: imul
13: iadd
14: invokevirtual #39 // Method java/io/PrintStream.println:(I)V
17: return
}
$計算部分のコードは手動でコンパイルしたときと同じになりました。
本体は、「生成開始〜生成終了」の箇所です。
コマンドラインからの入力をひとつの文字列として（乗算演算子はワイルドカードなので、"x"を代替文字としています）、半角スペースでsplitしたものをキューとしています。ここが構文解析部分です。
キューから要素を取り出して判断を行っているのが字句解析部分です。
...でも、これでは毎回同じ結果が出力されるだけなので面白くありませんね。
最後に、式に変数を指定してコマンドライン引数でパラメータを代入できるようにしてみました。
引数1〜5を変数a,b,c,d,eに割り当てるようにしています。
- ミニコンパイラ"CalcGen" 変数バージョン
import static org.apache.bcel.Constants.INVOKEVIRTUAL; import static org.apache.bcel.generic.InstructionConstants.*; import java.io.*; import java.util.*; import org.apache.bcel.*; import org.apache.bcel.classfile.*; import org.apache.bcel.generic.*; final class CalcBase { public static void main(String[] args) { System.out.println("*** Calc ***"); final int a; final int b; final int c; final int d; final int e; int[] iargs = new int[5]; { int i = 0; for (String arg : args) { if (arg.matches("\\d+")) { iargs[i++] = Integer.parseInt(arg); } } i = 0; for (final int v : iargs) { if (i != 0) System.out.print(','); System.out.printf(" %s=%d", (char)('a' + i), v); ++i; } System.out.println(); } a = iargs[0]; b = iargs[1]; c = iargs[2]; d = iargs[3]; e = iargs[4]; } } public final class CalcGen { static void generate(String exp) throws IOException { // class "Calc" final String className = "Calc"; ClassGen cg = new ClassGen(getBaseClass()); cg.setClassName(className); InstructionFactory factory = new InstructionFactory(cg); // method: public static void main(String[] args) Method mainMethod = cg.containsMethod("main", "([Ljava/lang/String;)V"); MethodGen mg = new MethodGen(mainMethod, className, cg.getConstantPool()); InstructionList il = mg.getInstructionList(); try { il.delete(il.getEnd()); } catch (TargetLostException ex) { // ignore } il.append(factory.createGetStatic(System.class.getName(), "out", Type.getType(PrintStream.class))); il.append(DUP); il.append(factory.createConstant(" " + exp + " = ")); il.append(factory.createInvoke(java.io.PrintStream.class.getName(), "print", Type.VOID, new Type[]{Type.STRING}, INVOKEVIRTUAL)); // 生成開始 LinkedList<String> q = new LinkedList<String>(Arrays.asList(exp.split(" "))); while (!q.isEmpty()) { final String s = q.poll(); if (which(s, "+", "-") && q.size() >= 3 && which(q.get(1), "*", "/", "%")) { q.addAll(3, Arrays.asList(s, "")); } else { if (which(s, "+", "-", "*", "/", "%")) { genCode(q.poll(), il, factory); } genCode(s, il, factory); } } // 生成終了 il.append(factory.createInvoke(java.io.PrintStream.class.getName(), "println", Type.VOID, new Type[]{Type.INT}, INVOKEVIRTUAL)); il.append(RETURN); // end of instructions mg.setMaxStack(); mg.setMaxLocals(); cg.replaceMethod(mainMethod, mg.getMethod()); // generate JavaClass c = cg.getJavaClass(); c.setSourceFileName(className + ".java"); c.dump(className + ".class"); } static void genCode(String s, InstructionList il, InstructionFactory factory) { if (s.trim().length() == 0) { // skip } else if (which(s, "+", "-", "*", "/", "%")) { // 演算子 il.append(InstructionFactory.createBinaryOperation(s, Type.INT)); } else if (s.matches("[abcde]")) { // 変数 final int index = " abcde".indexOf(s); il.append(InstructionFactory.createLoad(Type.INT, index)); } else if (s.matches("-?\\d+")) { // 定数 il.append(factory.createConstant(Integer.valueOf(s))); } else { throw new IllegalArgumentException("unexpected symbol: " + s); } } static boolean which(String s1, String... list) { for (final String s2 : list) { if (s2.equals(s1)) { return true; } } return false; } static JavaClass getBaseClass() { try { return Repository.lookupClass(CalcBase.class); } catch (ClassNotFoundException ex) { throw new RuntimeException(ex); } } public static void main(String[] args) { if (args.length > 0) { StringBuilder buffer = new StringBuilder(); for (final String arg : args) { buffer.append(' '); buffer.append(arg); } try { generate(buffer.substring(1).replace('x', '*')); } catch (IOException ex) { throw new RuntimeException(ex); } } } }
- 実行結果
$ ./calcgen a - b / c x d + e && java Calc 8 32 8 7 2 *** Calc *** a=8, b=32, c=8, d=7, e=2 a - b / c * d + e = -18 $ ./calcgen a + b % c % a && java Calc 9 28 5 *** Calc *** a=9, b=28, c=5, d=0, e=0 a + b % c % a = 12 $ java Calc 100 51 32 *** Calc *** a=100, b=51, c=32, d=0, e=0 a + b % c % a = 119 $
四則演算だけという小規模ではありますが、作ろうとしているコンパイラがどのように動くのかは少しだけ見えてきた気がします。
ただ、この時点では四則演算でもまだカッコの対応がされていません。そしてプログラミング言語らしい機能を備えるには、さらにルールが複雑になり、解析器を自分で1から作っていくのは設計も実装も非常に大変そうです。
ここは素直に、先人たちの積み上げてきたものを利用させてもらうのが賢明でしょう。
次回は、解析器ジェネレータなどのツールについて見ていきます。
