Javaで簡単なインタプリタを書いてみよう (1)
と思う．手持ちのコードがあればいつかなにかの役に立つかもしれない．大昔にバイト先でlex,yaccを使って，C++で特殊な用途のインタプリタを書いたことがあるのだけど，最近はいろいろと状況が違いそうなので，まずは復習から．
お手軽にやるにはパーザジェネレータを使いたいところだが，何がいいのかよくわからない．検索してみてよく見かけるのは，昔からあるjavaccと国産の¬＜＞＜∪∪(notavacc)．どっちでもいいような気がするが，とりあえず¬＜＞＜∪∪を使ってみよう．そのうち乗り換えるかも．
¬＜＞＜∪∪
¬＜＞＜∪∪ は，おそらく横倒しに読むとなんとなくjavaccに見えるという理由で名前づけられたパーザジェネレータ．読み方は「ノタバシーシー」でいいんだと思う．javaccがLL(k)なのに対して，LALR(∞)でパーズする，らしい．それぞれ記述できる言語の範囲が微妙に違うらしいのだが，よくわからない．勉強不足で恥ずかしい．まあ，これから書くのはいずれにしろおもちゃだから，どちらをつかっても問題は無いだろう．
とりあえず簡単な計算機を書いてみる．
まずは，計算機を書いてみよう．¬＜＞＜∪∪のチュートリアルに，加減乗除のできる計算機がのっているので，それを参考に，変数を導入できるものを考えてみる．イメージとしては
> pi = 3.14 3.14 > r = 10 10.0 > pi * r * r 314.0
みたいな感じで書けるものを目指す．
文法を定義する
基本的にチュートリアルからのパクリ．数値リテラルを，浮動小数点数を受けられるように拡張し，expression の上にstatementを設け，代入を処理できるようにしてある．
// ExpressionParser.notavacc
$parser ExpressionParser; // 出力クラス名を定義
$token NUMBER = SUBNUMBER | SUBNUMBER '.' SUBNUMBER | '.' SUBNUMBER ;
$subtoken SUBNUMBER = '0'..'9'+ ; // 数値リテラル
$white $token SPACE = ( ' ' | '\t' | '\n' | '\r')+ ; // ホワイトスペース
$token IDENTIFIER = IDENTIFIER_START IDENTIFIER_PART* ; // 変数
$subtoken IDENTIFIER_START = '$' | 'A'..'Z' | '_' | 'a'..'z' | '\u0080'..'\uffff' ;
$subtoken IDENTIFIER_PART = '0'..'9' | IDENTIFIER_START ;
$parsable
Root { cont:statement }
// 文は代入か，式
statement = Assignment { left:IDENTIFIER "=" right:expression }
| expression
;
// 式は加算，減算
expression = Addition { left:expression "+" right:term }
| Subtraction { left:expression "-" right:term }
| term
;
// タームは，乗除算
term = Multiplication { left:term "*" right:factor }
| Division { left:term "/" right:factor }
| factor
;
// ファクタは，括弧式，数値リテラル，マイナス式，変数
factor = Paren { "(" cont:expression ")" }
| NUMBER
| Negative { "-" cont:factor }
| IDENTIFIER
;
ドライバ
構文木を処理するメインクラスはDriverという名前にした．標準入力と標準出力を使う．
import java.io.*;
import java.util.*;
public class Driver {
ExpressionParser p = new ExpressionParser();
PrintStream pw;
LineNumberReader lnr;
Map<String, Double> env = new HashMap<String, Double>();
public Driver(PrintStream pw, LineNumberReader lnr) {
this.pw = pw;
this.lnr = lnr;
}
public static void main(String[] args) {
Driver d = new Driver(System.out,
new LineNumberReader(new InputStreamReader(System.in)));
d.start();
}
...startがメインループ．いわゆるeval-printループになっている．一行読んで評価し，出力する．
void start() {
while (true) {
try {
// プロンプトの出力
pw.print("> "); pw.flush();
String line = lnr.readLine();
if (line == null)
break;
// 構文木の作成
ExpressionParser.Node expr = p.parseRoot("test", line, 8);
// 評価
double v = eval(expr);
// 結果の表示
pw.println(v); pw.flush();
} catch (Exception e) {
e.printStackTrace();
}
}
}evalは，式を再起的に評価する．
public double eval(ExpressionParser.Node node) {
if (node instanceof ExpressionParser.Token) {
ExpressionParser.Token token = (ExpressionParser.Token) node;
if (token.getSymbolID() == ExpressionParser.TOKEN_NUMBER) {
String image = token.getImage();
return Double.parseDouble(image);
} else if (token.getSymbolID() == ExpressionParser.TOKEN_IDENTIFIER) {
String image = token.getImage();
if (!env.containsKey(image))
return 0.0;
return env.get(image);
}
} else if (node instanceof ExpressionParser.Addition) {
ExpressionParser.Addition n = (ExpressionParser.Addition) node;
return eval(n.left()) + eval(n.right());
} else if (node instanceof ExpressionParser.Subtraction) {
ExpressionParser.Subtraction n = (ExpressionParser.Subtraction) node;
return eval(n.left()) - eval(n.right());
} else if (node instanceof ExpressionParser.Multiplication) {
ExpressionParser.Multiplication n = (ExpressionParser.Multiplication) node;
return eval(n.left()) * eval(n.right());
} else if (node instanceof ExpressionParser.Division) {
ExpressionParser.Division n = (ExpressionParser.Division) node;
return eval(n.left()) / eval(n.right());
} else if (node instanceof ExpressionParser.Paren) {
ExpressionParser.Paren n = (ExpressionParser.Paren) node;
double v = eval(n.cont());
return v;
} else if (node instanceof ExpressionParser.Negative) {
ExpressionParser.Negative n = (ExpressionParser.Negative) node;
double v = - eval(n.cont());
return v;
} else if (node instanceof ExpressionParser.Assignment) {
ExpressionParser.Assignment n = (ExpressionParser.Assignment) node;
double v = eval(n.right());
assign(n.left(), v);
return v;
} else if (node instanceof ExpressionParser.Root) {
ExpressionParser.Root n = (ExpressionParser.Root) node;
double v = eval(n.cont());
return v;
} else {
throw new IllegalArgumentException("" + node);
}
return 0;
}代入式の処理．mapで実装されたenv に対してputするだけ．
public void assign(ExpressionParser.Node node, double val) {
if (node instanceof ExpressionParser.Token) {
ExpressionParser.Token token = (ExpressionParser.Token) node;
if (token.getSymbolID() == ExpressionParser.TOKEN_IDENTIFIER) {
String image = token.getImage();
env.put(image, val);
return;
}
}
System.err.println("left side of assignment have to be a variable.");
}これで一応完成．
実行してみる．
> $ java Driver > a = 10 10.0 > b = 20 20.0 > a + b - 0.2 / 3 29.933333333333334
どうやら動いているようだ．
