最後の仕上げ、 「コード生成」を知る！
最後に、構文木で表現されているデータからコードを生成する処理の部分を実装しましょう。
木構造で構文が表現されているので、こちらも意外と簡単にコード生成ができてしまいます。具体的な作業としては、AbstractExpressionクラスを継承しているクラスについて、compileメソッドを正しく実装するということになります。
子要素が正しいかチェック：Programクラスのcompileメソッド
Programクラスのcompileメソッドは次のようになります。引数にはコンパイルした結果を保持するためのobjectCodeListを受け取ります。このクラスは子要素を1つだけ持つので、その子要素をnへ取り出します。nはExpressionかTermかNumberExpression型のインスタンスのはずなので、それをチェックしてから、nのcompileメソッドを呼び出しています。
public void compile(List<Byte> objectCodeList)
throws Exception {
List<AbstractExpression> children = getChildren();
AbstractExpression n = children.get(0);
if (n instanceof Expression
|| n instanceof Term
|| n instanceof NumberExpression) {
n.compile(objectCodeList);
} else {
throw new Exception();
}
}
加減演算子命令の生成：Expressionクラスのcompileメソッド
Expressionクラスのcompileメソッドは次のとおりです。子要素には被演算子が順に入っていますから、それらを取り出して子要素のcompileメソッドを呼び出しています。今回はスタック型の仮想マシンを用意しているので、先に被演算子の値をスタックに積んでから、演算子の処理に対応する命令は最後に追加する点には注意が必要です。
演算子の値をスタックに積むのは、子要素のcompileメソッド内で実現されているので、「rightOperand.compile(objectCodeList);」が実行された時点で、「objectCodeList」には、その処理に対応したバイナリコードが格納されています。
public void compile(List<Byte> objectCodeList)
throws Exception {
ArrayList children = getChildren();
AbstractExpression leftOperand
= (AbstractExpression)children.get(0);
leftOperand.compile(objectCodeList);
if (children.size() > 1) {
AbstractExpression rightOperand
= (AbstractExpression)children.get(1);
rightOperand.compile(objectCodeList);
if ("+".equals(getValue().getS())) {
objectCodeList.add(Compiler.IADD);
} else if ("-".equals(getValue().getS())) {
objectCodeList.add(Compiler.ISUB);
}
}
}
各命令のバイナリ値は、後で説明をするCompilerクラスに定義してあり、iadd命令の値は「Compile.IADD」、isub命令の値は「Compile.ISUB」と参照して使えるようになっています。Expressionクラスのvalueフィールドにある字句の値によって、objectCodeListへ追加する命令を、加算命令であるiaddにするか、減算命令であるisubにするかを切り替えています。
なお、今回のプログラムでは、構文木が木構造で表現されていることを利用して、AbstractExpressionを実装するクラスのcompileメソッドを用意して、再帰的に呼び出しています。これだけで、階層が深い複雑な構文木もコンパイルする処理が実現できています。ちょっと分かりにくいかもしれませんが、「leftOperand.compile(objectCodeList);」といった処理の部分が再帰的な呼び出しとなっているのです。
乗除演算子命令の生成：Termクラスのcompileメソッド
次に、Termクラスのcompileメソッドですが、これもExpressionのcompileメソッドと同様で、加減算命令の代わりに乗除算命令が使われている点だけが違います。
public void compile(List<Byte> objectCodeList)
throws Exception {
（略）
if ("*".equals(getValue().getS())) {
objectCodeList.add(Compiler.IMUL);
} else if ("/".equals(getValue().getS())) {
objectCodeList.add(Compiler.IDIV);
}
}
}
データ操作命令の生成：NumberExpressionクラスのcompileメソッド
NumberExpressionクラスのcompileメソッドは次のようになります。数値をdouble値で持っているため、byte値にキャストするといった処理が入っていますが、bipush命令をobjectCodeListへ追加してから、スタックに積む値を追加するという手順になっています。
public void compile(List<Byte> objectCodeList)
throws Exception {
double value = getValue().getN();
byte b = (byte)value;
objectCodeList.add(Compiler.BIPUSH);
objectCodeList.add(new Byte(b));
}
コンパイルを実際に実行するクラス：Compilerクラス
これらのコンパイルを実際に実行するクラスとしてCompilerクラスを用意しています。実際には、生成した構文木の情報や、出力するオブジェクトコードの情報をコンソール画面へ出力する処理などが入っていますが、ここではコンパイルに必要な処理だけ記載しています。
これまで用意したScannerクラス、Parserクラス、AbstractExpressionクラスを使って、字句解析、構文解析、オブジェクトコード生成、といった手順で処理をしています。
public class Compiler {
public static final Byte IADD = new Byte((byte)96);
public static final Byte ISUB = new Byte((byte)100);
public static final Byte IMUL = new Byte((byte)104);
public static final Byte IDIV = new Byte((byte)108);
public static final Byte BIPUSH = new Byte((byte)16);
public static final Byte PRINT = new Byte((byte)-48);
public void compile(String fileName)
throws Exception {
Scanner scanner = new Scanner(fileName);
List<Token> tokenList = scanner.createTokenList();
Parser parser = new Parser();
AbstractExpression ae = parser.execute(tokenList);
List<Byte> objectCodeList = new ArrayList<Byte>();
ae.compile(objectCodeList);
objectCodeList.add(PRINT);
byte[] code = new byte[objectCodeList.size()];
for (int i=0; i < code.length ; i++) {
code[i] = objectCodeList.get(i).byteValue();
}
try {
write("a.svm", code);
} catch (IOException e) {
e.printStackTrace();
}
}
private void write(String fileName, byte[] code)
throws IOException {
FileOutputStream fo = null;
try {
fo = new FileOutputStream(new File(fileName));
fo.write(code);
} finally {
if (fo != null) {
fo.close();
}
}
}
}
ここでは、ファイルへ書き出しをするに当たって、Byte型の配列に入っている値をbyte型の配列へ変換してから処理をするようにしています。なお、書き出すファイルはa.svmと固定値にするという仕様にしていましたから、そのとおりになっています。
起動を行うクラス：Svm1cクラス
最後は起動クラスSvm1cですが、コンパイルをコマンドラインから実行するためのクラスなので、単純なものとなっていますから、ここでは省略します。
そして、Javaでコンパイラを実行する。
以上でコンパイラに必要なクラスがすべて用意できました。javacコマンドを使ってすべてのクラスをコンパイルしてから、S1sプログラムのコンパイルから実行までをやってみましょう。その際の一連の作業は次のとおりです。
ソースコードファイルとして01.s1sから03.s1sまで用意して、Svm1cでコンパイルをしています。コンパイルをするたびにa.svmファイルが生成されるので、これをSvm1クラスで実行しています。
> type 01.s1s
main { 1+2 }
> java Svm1c 01.s1s
> java Svm1 a.svm
3
> type 02.s1s
main { 1+2*3 }
> java Svm1c 02.s1s
> java Svm1 a.svm
7
> type 03.s1s
main { (1+2)*3 }
> java Svm1c 03.s1s
> java Svm1 a.svm
9
ところで、S1sの文法上では減算、除算が可能なように定義しましたが、肝心のSvm1クラス、Aluクラスで実現されている仮想マシンではこれらをサポートしていません。ですから、ちょっとした拡張をする必要があります。それらについては、それほど難しいものではありませんから、読者の皆さんの課題として残しておきます。
もしも、コンパイラ専門書が読めたなら……
以上でコンパイラの基礎について解説が終わりました。本連載では、字句リストや構文木を用意して、コンパイラの内部処理の入出力に使いました。これにより、各処理について理解しやすかったはずです。もっと手軽に作成するのであれば、字句解析をしながら、構文木を生成しないでオブジェクトコードを出力するような実装というのも可能です。
ただし、一緒にしてしまうと各フェイズについての理解があいまいになりますし、バグがあったときに原因がどこにあるのか切り分けるのが大変になります。機能のわりには作成したクラス数は多いのですが、その分、各クラスの役割は分かりやすかったのではないでしょうか。とはいえ、クラス構成については好みなどもありますから、今回紹介したもの以外にも、こうするとよいのではないか、と検討してみると面白いのではないかと思います。
さて、今回で「Javaでコンパイラの基礎を理解する」の連載は終了となります。連載を通して読んでいただいた皆さん、ありがとうございました。本連載を読まれた方なら、コンパイラ専門書の入り口付近はすらすらと読めるようになっているはずです。
本格的なコンパイラ作成に興味を持ったら、ぜひ専門書の方も読んでみてください。コンパイラ技術はちょっと特殊な部分もありますが、効率よいテキスト処理などにも応用させることができますから、意外と役に立つ技術です。本連載を通して1人でも多くの人がコンパイラの実装に興味を持ってくれれば、幸いです。
今回作成したソースはここからダウンロードできます。添付してあるプログラムは文字コードがUTF-8となっていますので、コンパイルする際はjavacコマンドに「-encoding UTF-8」とオプションを付けてコンパイルしてください。
筆者紹介
小山博史（こやま ひろし）
Webシステムの運用と開発、コンピュータと教育の研究に従事する傍ら、オープンソースソフトウェア、Java技術の普及のための活動を行っている。Ja-Jakartaプロジェクトへ参加し、コミッタの一員として活動を支えている。また、長野県の地域コミュニティである、SSS(G)やbugs(J)の活動へも参加している。
Copyright © ITmedia, Inc. All Rights Reserved.