はじめに

以前の記事で構文解析を実装しました。
ついでにそれを使って、単純なインタプリタを実装してみたいとおもいます。

インタプリタでやりたいこと

実装にあたりやりたいことを確認します。
インタプリタでやりたいことは、プログラムになっている文字列を計算することです。
下の式を例に考えると、最終的に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を準備します。

Interpreter.java

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を返します。

Interpreter.java

    public Map<String, Integer> run() throws Exception {
        body(body);
        return variables;
    }

計算する部分の説明です。
body()は、先に渡されたトークンリストbodyから式1つ分のトークンをとりだし、式を処理するexpression()へ渡します。

Interpreter.java

    public void body(List<Token> body) throws Exception {
        for (Token exprs : body) {
            expression(exprs);
        }
    }

expression()はトークンの意味によって、それぞれを処理するメソッドを呼び出し、その結果をそのまま返します。

Interpreter.java

    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にします。

Interpreter.java

    public Integer digit(Token token) {
        return Integer.decode(token.value);
    }

var()は変数のトークンを受けとり変数名にします。
変数名が変数Mapに未登録なら、値を0で登録します。

Interpreter.java

    public Object var(Token token) {
        String name = token.value;
        if (!variables.containsKey(name)) {
            variables.put(name, 0);
        }
        return name;
    }

assign()は変数へ値を代入します。

Interpreter.java

    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の結果が変数名であることを確かめます。

Interpreter.java

    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から値を取り出して返します。

Interpreter.java

    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()は四則演算をします。

Interpreter.java

    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

を計算し、変数とその値を標準出力へプリントします。

Interpreter.java

    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クラスをまとめたものもあげておきます。

Interpreter.java

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
    }
}