3 単純なインタプリタをJavaで実装する

# はじめに

以前の記事で[構文解析を実装](http://qiita.com/quwahara/items/9bf468ff4286b28d2a24)しました。
ついでにそれを使って、単純なインタプリタを実装してみたいとおもいます。

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

実装にあたりやりたいことを確認します。
インタプリタでやりたいことは、プログラムになっている文字列を計算することです。
下の式を例に考えると、最終的に`a`に`23`が代入された状態になることを目指します。

```JS
a = 3 + 4 * 5
```

# 計算の仕方

では計算の仕方を考えます。
[前回の記事](http://qiita.com/quwahara/items/9bf468ff4286b28d2a24)で式を構文解析しました。
構文解析された式は、演算子トークンの`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を準備します。

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

```Java:Interpreter.java
    public Map<String, Integer> run() throws Exception {
        body(body);
        return variables;
    }
```

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

```Java:Interpreter.java
    public void body(List<Token> body) throws Exception {
        for (Token exprs : body) {
            expression(exprs);
        }
    }
```

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

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

```Java:Interpreter.java
    public Integer digit(Token token) {
        return Integer.decode(token.value);
    }
```

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

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

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

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

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

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

```Java: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");
        }
    }
```

以上の実装を使って、例のプログラムになっている文字列

```JS
a = 3 + 4 * 5
```

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

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


```Java: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
    }
}
```