連載

2007年2月23日

簡単な仮想計算機を作ろう（実装編）：Javaでコンパイラの基礎を理解する（3）（2/3 ページ）

教育界、技術者コミュニティでJava言語の教育と啓蒙に長年携わってきた筆者が、Javaを通してコンパイラの仕組みを分かりやすく紹介する。（編集部）

[小山博史，株式会社ガリレオ] PC用表示関連情報

LINE

Hatena

前のページへ | 次のページへ

仮想スタックマシンをJavaで実装する

　すでに何度か説明しましたが、後置記法で表現された式というのは、スタックを使うと、非常に簡単に計算ができてしまいます。そして、このスタックというデータ構造を実現することは、これまでの説明からも分かるように、それほど難しくはありません。

　それでは、前回の仮想スタックマシンSvm1の図（図7）を思い浮かべながら、後置記法で表現された式を評価して計算をする仮想スタックマシンの実装を考えてみましょう。

前回の図7　仮想スタックマシン「Svm1」のフロー

設計～クラス、フィールド、メソッドを決める～

　まず、プログラムのコードはメモリ上にロードしておく必要がありますから、その領域としてbyte型の配列を用意します。ここでは256bytesのサイズで、codeという名前を付けました。実際のプログラムのコード長は、「1 2 +」を計算するのか、「1 2 3 + +」を計算するのか、といった内容によって変わります。後者の式の方が長いので、codeの領域をより多く使用するのは推測できるはずです。

　つまり、計算する式によってプログラムのコード長は変化しますから、プログラムの終了を何らかの方法で判定できるようにしておく必要があります。ここでは、プログラムの長さを保持することとし、codeLengthというint型のフィールドを用意します。

　次に、計算で使用するオペランドスタックを用意します。ここでは、Java SE 5以降で使えるオートボクシング機能によるスタックも使ってみることにします。java.util.Stackを使用してbyte型のデータをスタックすることにします。フィールド名はoperandStackとします。

　また、演算装置も用意します。これは、2つのパラメータを受け取って演算を行い、その結果を返すメソッドを持つAluクラスとして実装します。ALU（Arithmetic Logic Unit）は四則演算と論理演算を含むのが一般的ですが、ここではSvm1に必要な加算と乗算のみ用意することにします。

　さて、プログラムの実行の基本は、プログラムコード（命令）を順番に実行していくことになります。ですから、今回の例では、後置記法で表現された式を計算するというのは、メモリ上にロードしたプログラム（式）を先頭から順に読み込んで実行（評価）するということになります。このためには、どこまでプログラムを実行したかを記録しながら処理を進める必要があります。そこで、int型のフィールドpcをプログラムカウンタとして用意します。

　仮想スタックマシンが提供するメソッドとしては、プログラムを仮想スタックマシンへロードするloadメソッドと、ロードしたプログラムを実行するexecuteメソッドを用意します。なお、命令の判定を実行する部分は若干複雑になるので、executeCommand()メソッドを用意してexecuteメソッドとは別にします。

　また、仮想スタックマシン起動用にmain()メソッドも用意することにします。以上をまとめると、Svm1のクラス図は次のようになります。

図3　Svm1クラス図

　それでは、実際にJavaでプログラムを作成してみましょう。完全なコードは後に示すことにします。

演算装置［Aluクラス］

　最初に、Aluクラスについて解説しておきます。解説といっても、次のように単純なものです。byte型の加算や乗算はJavaでサポートされているので、それを使っています。ただし、演算の結果がint型となってしまうので、ここではbyte型にキャストしています。計算結果がbyte型の範囲外の値となる計算は対象外として考えているということになります。

public class Alu {
    public byte add(byte a, byte b) {
        return (byte)(a + b);
    }
    public byte multiply(byte a, byte b) {
        return (byte)(a * b);
    }
}

Alu.java

仮想スタックマシン［Svm1クラス］のフィールド

　次に、Svm1クラスについて説明をします。まず、フィールドは次のようになります。これはクラス図からすぐに分かるはずです。

    private byte[] code = new byte[256];
    private int codeLength = 0;
    private Stack<Byte> operandStack = new Stack<Byte>();
    private Alu alu = new Alu();
    private int pc;

Svm1のフィールド

　では、メソッドを順番に見ていきましょう。

プログラムを仮想スタックマシンへロード［loadメソッド］

　最初はloadメソッドです。コンパイラが生成したプログラムはファイルに保存することになりますから、それを読み込んで実行できるようにしておきます。ということで、ここではファイルからプログラムをロードすることにしますが、対象とするプログラムはcodeに入り切るように256bytes以内ということを前提にしておき、これより大きなプログラムを読み込むことは考えません。

　例示しているプログラムでは、FileInputStreamを使ってバイトデータを読み込んでいます。readメソッドで一度に読み込むbyte数は最大8bytesまでにしています。読み込んだバイトデータはフィールドcodeに保存されるように指定しています。また、読み込んだバイトデータの長さはcodeLengthに記録しています。

     public void load(String fileName) throws IOException {
          FileInputStream is = null;
          try {
               is = new FileInputStream(new File(fileName));
               int len = 0;
               while ((len = is.read(code, len, 8)) != -1) {
                    codeLength += len;
               }
          } finally {
               if (is != null) {is.close();}
          }
     }

load()メソッド

ロードしたプログラムを実行［executeメソッド］

　次に、executeメソッドについて説明します。このメソッドでは、プログラムコードをフィールドcodeから1byteずつ読み込んで、読み込んだ値に応じて処理を行うようにします。値を読み込んで実行したら、プログラムカウンタを進めます。

　条件分岐や繰り返しといった制御がある場合は、処理を戻す必要が出てくるので、プログラムカウンタの値を小さくすることになりますが、今回はこれについて考える必要はありません。値に応じて処理を行う部分については若干処理が多いので、executeCommandメソッドと別に表現することにします。

　すると、次のようにpcを1ずつ増加させてexecuteCommandメソッドを呼び出すだけの、非常に簡単な繰り返し処理で実現できます。

    public void execute() {
        for (pc=0 ; pc<codeLength ; pc++) {
            executeCommand(code[pc]);
        }
    }

execute()メソッド

命令の判定を実行［executeCommandメソッド］

　executeCommandメソッドでは、パラメータcommandに渡されたバイトコードの値によって実行する処理が変わります。

　commandが「16」の場合は、続くコードにある値をオペランドスタックへ積む（push）する処理を行います。

　commandが「96」の場合は、オペランドスタックに積まれている値を2つ取り出して（pop）、それぞれの値を加算した結果をオペランドスタックへ積みます。

　commandが「104」の場合は、「96」とほぼ同様の処理を行いますが、オペランドスタックへは取り出した値を乗算した結果を積むという点が異なります。

　commandが「-48」の場合は、オペランドスタックの一番上に積まれている値をコンソール画面へ出力します。

　これらの処理を具体的なJavaのコードとすると次のようになります。

    public void executeCommand(byte command) {
        byte a;
        byte b;
        switch (command) {
        case 16:
            operandStack.push(code[++pc]);
            break;
        case 96:
            b = operandStack.pop();
            a = operandStack.pop();
            operandStack.push(alu.add(a, b));
            break;
        case 104:
            b = operandStack.pop();
            a = operandStack.pop();
            operandStack.push(alu.multiply(a, b));
            break;
        case -48:
            System.out.print(operandStack.peek());
            break;
        }
    }

executeCommand()メソッド

　最後に起動メソッドについてですが、仮想スタックマシンの動作や処理とはあまり関係ありませんし、処理内容もそれほど難しいわけではありませんので、説明は省略します。今回の例では、読み込むファイルをコマンドラインで指定できるように作成してあります。以上でSvm1のプログラムは完成ですが、かなり簡単に作れたと思いませんか？

いよいよ仮想スタックマシンを動かす！