はじめに
以前の記事で構文解析を実装しました。
ついでにそれを使って、単純なインタプリタを実装してみたいとおもいます。
インタプリタでやりたいこと
実装にあたりやりたいことを確認します。
インタプリタでやりたいことは、プログラムになっている文字列を計算することです。
下の式を例に考えると、最終的にaに23が代入された状態になることを目指します。
a = 3 + 4 * 5
計算の仕方
では計算の仕方を考えます。
前回の記事で式を構文解析しました。
構文解析された式は、演算子トークンのleftとrightに、その演算子で計算される値を持つように解析されました。
例えば式6 - 7なら、演算子トークンが-で、leftに6、rightに7を持つといった具合です。
またleftやrightには値だけでなく、計算順序で先にくる式も持つことがありました。
例えば式3 + 4 * 5なら、演算子トークンが+で、leftに3、rightに4 * 5を持ちます。
このようなデータ構造になっているので計算をするには、演算子トークンのleftやrightを順に下っていき、
末端の演算子にたどりついたらそれを計算します。
その計算結果をもって、1つ上の演算子の計算をします。
この動作を1番上まで繰り返すことで、計算ができます。
先の例の式3 + 4 * 5ならば、末端の演算子は4 * 5の*なのでそれを計算し20になります。
その計算結果を持って1つ上の演算子+を計算します。
leftが3、rightが計算結果の20なので、足して23になり、計算ができました。
Javaで実装してみる
実装にうつります。
インタプリタの実装を部分的にみていきます。
まずは初期化の部分です。
構文解析で解析されたトークンリストを受けとります。
このトークンリストを計算します。
またインタプリタは変数に対応するので、変数名とその値を保持するMapを準備します。
public class Interpreter {
public Map<String, Integer> variables;
List<Token> body;
public Interpreter init(List<Token> body) {
variables = new HashMap<>();
this.body = body;
return this;
}
計算を起動する部分の説明です。
run()は、先に渡されたトークンリストbodyの計算をし、計算結果を保持した変数Mapを返します。
public Map<String, Integer> run() throws Exception {
body(body);
return variables;
}
計算する部分の説明です。
body()は、先に渡されたトークンリストbodyから式1つ分のトークンをとりだし、式を処理するexpression()へ渡します。
public void body(List<Token> body) throws Exception {
for (Token exprs : body) {
expression(exprs);
}
}
expression()はトークンの意味によって、それぞれを処理するメソッドを呼び出し、その結果をそのまま返します。
public Object expression(Token expr) throws Exception {
if (expr.kind.equals("digit")) {
return digit(expr);
} else if (expr.kind.equals("variable")) {
return var(expr);
} else if (expr.kind.equals("sign") && expr.value.equals("=")) {
return assign(expr);
} else if (expr.kind.equals("sign")) {
return calc(expr);
} else {
throw new Exception("Expression error");
}
}
digit()は数値のトークンを受けとり、それをIntegerにします。
public Integer digit(Token token) {
return Integer.decode(token.value);
}
var()は変数のトークンを受けとり変数名にします。
変数名が変数Mapに未登録なら、値を0で登録します。
public Object var(Token token) {
String name = token.value;
if (!variables.containsKey(name)) {
variables.put(name, 0);
}
return name;
}
assign()は変数へ値を代入します。
public String assign(Token expr) throws Exception {
String name = variable(expression(expr.left));
Integer value = value(expression(expr.right));
variables.put(name, value);
return name;
}
variable()はassign()の処理で、expr.leftの結果が変数名であることを確かめます。
public String variable(Object value) throws Exception {
if (value instanceof String) {
return (String) value;
} else {
throw new Exception("left value error");
}
}
value()はassign()の処理のexpr.rightや、あとの説明ででてくる四則演算の処理で、計算できる数値に仕立てます。
引数valueがIntegerなら、そのまま返します。Stringなら変数Mapから値を取り出して返します。
public Integer value(Object value) throws Exception {
if (value instanceof Integer) {
return (Integer) value;
} else if (value instanceof String) {
return variables.get((String) value);
} else {
throw new Exception("right value error");
}
}
calc()は四則演算をします。
public Object calc(Token expr) throws Exception {
Integer left = value(expression(expr.left));
Integer right = value(expression(expr.right));
if (expr.value.equals("+")) {
return left + right;
} else if (expr.value.equals("-")) {
return left - right;
} else if (expr.value.equals("*")) {
return left * right;
} else if (expr.value.equals("/")) {
return left / right;
} else {
throw new Exception("Unknown sign for Calc");
}
}
以上の実装を使って、例のプログラムになっている文字列
a = 3 + 4 * 5
を計算し、変数とその値を標準出力へプリントします。
public static void main(String[] args) throws Exception {
String text = "a = 3 + 4 * 5";
List<Token> tokens = new Lexer().init(text).tokenize();
List<Token> blk = new Parser().init(tokens).block();
Map<String, Integer> variables = new Interpreter().init(blk).run();
for (Map.Entry<String, Integer> variable : variables.entrySet()) {
System.out.println(variable.getKey() + " " + variable.getValue());
}
// --> a 23
}
}
実装は以上です。
ありがとうございました。
おわりに
ソースはこちらで公開しています。
Calc
https://github.com/quwahara/Calc/tree/article-3-interpreter/Calc/src/main/java
続きの記事があります。
インタプリタにprintlnを追加する
http://qiita.com/quwahara/items/82067b00cbe1cb974e4a
最後に、Interpreterクラスをまとめたものもあげておきます。
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Interpreter {
public Map<String, Integer> variables;
List<Token> body;
public Interpreter init(List<Token> body) {
variables = new HashMap<>();
this.body = body;
return this;
}
public Map<String, Integer> run() throws Exception {
body(body);
return variables;
}
public void body(List<Token> body) throws Exception {
for (Token exprs : body) {
expression(exprs);
}
}
public Object expression(Token expr) throws Exception {
if (expr.kind.equals("digit")) {
return digit(expr);
} else if (expr.kind.equals("variable")) {
return var(expr);
} else if (expr.kind.equals("sign") && expr.value.equals("=")) {
return assign(expr);
} else if (expr.kind.equals("sign")) {
return calc(expr);
} else {
throw new Exception("Expression error");
}
}
public Integer digit(Token token) {
return Integer.decode(token.value);
}
public Object var(Token token) {
String name = token.value;
if (!variables.containsKey(name)) {
variables.put(name, 0);
}
return name;
}
public String assign(Token expr) throws Exception {
String name = variable(expression(expr.left));
Integer value = value(expression(expr.right));
variables.put(name, value);
return name;
}
public String variable(Object value) throws Exception {
if (value instanceof String) {
return (String) value;
} else {
throw new Exception("left value error");
}
}
public Integer value(Object value) throws Exception {
if (value instanceof Integer) {
return (Integer) value;
} else if (value instanceof String) {
return variables.get((String) value);
} else {
throw new Exception("right value error");
}
}
public Object calc(Token expr) throws Exception {
Integer left = value(expression(expr.left));
Integer right = value(expression(expr.right));
if (expr.value.equals("+")) {
return left + right;
} else if (expr.value.equals("-")) {
return left - right;
} else if (expr.value.equals("*")) {
return left * right;
} else if (expr.value.equals("/")) {
return left / right;
} else {
throw new Exception("Unknown sign for Calc");
}
}
public static void main(String[] args) throws Exception {
String text = "a = 3 + 4 * 5";
List<Token> tokens = new Lexer().init(text).tokenize();
List<Token> blk = new Parser().init(tokens).block();
Map<String, Integer> variables = new Interpreter().init(blk).run();
for (Map.Entry<String, Integer> variable : variables.entrySet()) {
System.out.println(variable.getKey() + " " + variable.getValue());
}
// --> a 23
}
}