簡単な仮想計算機を作ろう（準備編）：Javaでコンパイラの基礎を理解する（2）（2/2 ページ）
教育界、技術者コミュニティでJava言語の教育と啓蒙に長年携わってきた筆者が、Javaを通してコンパイラの仕組みを分かりやすく紹介する。（編集部）
仮想計算機もどきを設計する
さて、後置記法という式の表現方法を見てみました。次は、本連載でコンパイラがターゲットとするコンピュータについて設計をしてみましょう。コンピュータの設計をするといっても、ハードウェアから設計して実装まではできませんので、簡単な仮想計算機ソフトウェアとして実装することにします。
最初に、作成する仮想計算機の機能について決める必要があります。あまり複雑なことまで実装する必要はないので、ここでは非常に単純な機能しか考えないことにします。そこでここでは、オペランドとなるデータの範囲は0から127までの整数だけを対象とします。この値を表現するには7bitあれば十分ですが、コンピュータにとっては区切りが良い1byte（8bit）を使って表現することにします。
次に、サポートする命令語を決めておく必要があります。コンピュータの命令としては本来、データを操作するためのデータ操作命令と、四則演算などをするための演算命令と、処理の流れを制御するためのフロー制御命令といったものが必要です。
ここでも動作原理を理解できればいいので、オペランドとなるデータを操作するためのデータ操作命令としてbipushを用意し、算術演算命令としては加算を計算するためのiadd、乗算を計算するためのimulだけを用意します。フロー制御命令は省略します。ただし、これらの命令だけでは計算結果を見られないので、printという特別な命令を用意しておきます。
コンピュータでは基本的に数値しか扱えませんので、これらの命令を意味する数値を割り当てておく必要があります。命令を表現するためには、単純に1byte（8bit）を使うことにして、命令によってオペランドを取るか、取らないかを決めておくことにします。
| 分類 | 値（16進数） | 命令 | オペランド | 実行内容 |
|---|---|---|---|---|
| データ操作命令 | 0x10 | bipush | 整定数 | 整数をスタックに積む |
| 演算命令 | 0x60 | iadd | なし | 整数の加算 |
| 0x68 | imul | なし | 整数の乗算 | |
| 特別な命令 | 0xD0 | なし | スタックのトップを表示する | |
| 表2 命令の一覧 | ||||
非常に単純な機能しか用意していないので、仮想計算機というのには物足りないかもしれません。「仮想計算機もどき」という表現がぴったりでしょう。とはいうものの、これだけでも動作原理を理解するには十分です。名前を付けておいた方がなにかと便利なので、「サンプル仮想計算機1号」ということで「Svm1」としておきます。
さて、ここで命令の実行内容にスタックという用語が出てきました。実際の仮想計算機の実装方法にはいくつかあるのですが、ここではスタックを利用する仮想スタックマシンの考えを採用します。一般的な仮想スタックマシンは、次に示す図6のような構成になります。
変数を保持するための領域や、演算対象となるオペランドを一時的に置いておくためのオペランドスタックを用意し、演算を処理するための演算装置も用意します。実際のハードウェアでは、変数領域やオペランドスタックについて、メインメモリ上に用意するのか、別途用意するのか、などを考える必要があります。
しかし、仮想スタックマシンはソフトウェアで実現するので、そういった点については深く考える必要はありません。そのため、図6では、これらをメモリとして用意することだけを示しています。仮想スタックマシンの場合、演算はオペランドスタック上の値に対して行われ、スタックへ変数領域から値を読み込んだり、スタック上の値を変数領域へ書き込んだりするためには、loadやstoreなどの命令を用意するという形になります。
ちなみに、今回の仮想計算機「Svm1」では、変数領域を用意しないので、次のような構成となります。データ操作命令では、スタックへ直接整数値を積み、演算命令としてはスタック上の値を使って加算や乗算をして結果をスタックへ積むものだけを用意しています。printという特別な命令はスタックの一番上に積まれている値を表示するものです。全体的に非常に単純だということが分かるでしょう。
アセンブリコードにすると
次に、この仮想計算機で実行するプログラムの例を考えてみます。目標は「1 * 2 + (3 + 4) * 5 + 6」や「1 + 2 * (3 + 4) + 5 * 6」のような式を計算できることでしたが、手始めにもっと簡単な算術式から考えてみましょう。
例を見るとすぐに理解できると思うので、まずは後置記法で「1 2 +」（中置記法で「1 + 2」）と表現される算術式を計算するプログラムは、「Svm1」のアセンブリコードではどのように記述することになるのかを見てみましょう。
1行に1命令を書くことにすると、次のようになります。重要なのは、「1 2 +」の各文字とアセンブリコードの各行が順番に対応しているという点です。整定数nが出てきたら、機械的に「bipush n」という行を書き、演算子（例えば、「+」）が出てきたら、機械的にその演算子に対応する命令行（iaddの行）を書くだけでプログラムができてしまうのです。
ここでは、整定数1と「bipush 1」、整定数2と「bipush 2」、加算+と「iadd」が対応しています。ただし、最後の「print」は実際に計算結果がどうなったかを表示するために特別に追加しています。
bipush 1 bipush 2 iadd print
何度も説明をしていますが、後置記法で式を表現すればかっこや演算子の優先度については考える必要がありません。このため、演算命令としては加算と乗算しか持っていない「Svm1」でも、かなり複雑な加算と乗算の算術式を計算できます。しかも、後置記法の算術式は、簡単に「Svm1」のアセンブリコードへ変換できます。
このような変換が可能な背景には、「オペランドが先に現れ、左から順に文字を読んで計算ができる」ということと、「仮想スタックマシンの相性が非常に良い」ということがあります。後置記法の式の計算では、スタックというデータ構造を上手に利用できるのです。本をただせば、「Svm1」のアセンブリコードへ簡単に変換できるように、後置記法を使うことにしているともいえるので、当たり前といえば当たり前なのですが、これを理解すると「なるほど」と思うはずです。
それでは、ほかの算術式についてもアセンブリコードへ変換してみましょう。中置記法から後置記法へ変換して、アセンブリコードを書けばいいだけなので、本当に簡単にできるはずです。
bipush 1 bipush 2 bipush 3 imul iadd print
bipush 1 bipush 2 iadd bipush 3 imul print
オブジェクトコードにすると
実際には、これらをマシン語にする必要がありますから、表を参照しながら手動でオブジェクトコード（マシン語コード）化してみると、次のようなプログラムができます。ただし、図8では16進数の「0xD0」（print）の値を10進数の「-48」としています。これは、仮想スタックマシンをJavaで実装する予定であることと関係しています。Javaでは、byte型データの範囲が-128から127になるため、最上位bitが1となるデータについては負の数として扱う必要があるからです。
また、値を表示するprint命令を、「Svm1」オブジェクトコードでは最後に追加していますが、算術式には含まれていない点にも注意してください。
Javaとして仮想計算機もどきを実装する
以上、算術式を後置記法で表現する方法、本連載がターゲットとする仮想計算機「Svm1」の設計、「Svm1」が計算できるアセンブリコードやオブジェクトコードの例、について解説しました。
高級プログラミング言語だけではなく、アセンブリ言語を使ったり、OS周りのプログラミングやハードウェアの設計をしたことがあれば簡単にイメージがわくはずですが、そういった経験がないと、これだけではまだイメージがつかみ切れないでしょう。
実際に仮想スタックマシンを実装してみると、もっと具体的にイメージできるようになってきますから、次回は実際に「Svm1」をプログラミング言語Javaのプログラムとして実装してみることにします。
また、「スタックという用語は勉強したことがあるけど、そのときは何の役に立つのか正直なところよく分からなかった」という読者もいるかと思いますので、スタックについても解説をします。待ち切れない読者は自分で実装をしてみてください。それほど難しくはないはずです。それでは、次回をお楽しみに。
参考文献
▼『オートマトン・言語理論の基礎』 近代科学社
▼『JAVAバーチャルマシン』 オライリー・ジャパン
▼『プログラミング言語Java』 ピアソンエデュケーション
▼『The Java Language Specification, Third Edition』 Addison - Wesley
▼『JAVAによるパーサ構築技法』 ピアソンエデュケーション ピアソンエデュケーション
▼『オブジェクト指向における再利用のためのデザインパターン』 ソフトバンク パブリッシング
▼『Java言語で学ぶデザインパターン入門』 ソフトバンク パブリッシング
▼『JavaCC―コンパイラ・コンパイラ for Java』 テクノプレス
▼『スモールコンパイラの制作で学ぶプログラムの仕組み』 技術評論社
▼『コンパイラ入門』 ソフトバンククリエイティブ
筆者紹介
小山博史（こやま ひろし）
Webシステムの運用と開発、コンピュータと教育の研究に従事する傍ら、オープンソースソフトウェア、Java技術の普及のための活動を行っている。Ja-Jakartaプロジェクトへ参加し、コミッタの一員として活動を支えている。また、長野県の地域コミュニティである、SSS(G)やbugs(J)の活動へも参加している。
Copyright © ITmedia, Inc. All Rights Reserved.