LoginSignup
6
4

More than 5 years have passed since last update.

@quwahara(光昭 桑原)

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

Last updated at Posted at 2017-02-06

はじめに

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

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

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
6
4