はじめに

以前の記事でインタプリタにprintlnを追加しました。
それを少し拡張して関数定義と呼び出しをできるようにしてみます。

関数定義と呼び出しでやりたいこと、やらないこと

実装にあたり、具体的にやりたいこととやらないことを確認します。
例えば下のようなプログラムがあったら、addV()関数が定義され、標準出力に3と出力されることを目指します。

v = 0
function addV(num) {
  v = v + num
}
addV(3)
println(v)

そして簡単のためにやらないことも決めます。
関数の引数は1つしか対応しません。引数なしや2つ以上の引数には対応しません。
関数の戻り値に対応しません。
変数のスコープに対応しません。仮引数の変数名もグローバルに定義されます。

実装の仕方

実装の仕方について、字句解析(Lexer)、構文解析(Parser)、インタプリタ(Interpreter)と順に考えていきます。

字句解析(Lexer)への実装の仕方

実装した字句解析には波括弧、{と}を解析する機能がありませんので、それを実装します。

構文解析(Parser)の実装の仕方

まずは関数定義文を構文解析する実装を考えます。
実装の仕方を考えるために、関数定義function addV(num) {}のトークンの並びをよく観察します。
観察するとキーワードfunctionがいつもトークンの並びの始めにくることがわかります。
トークンの並びに決まったトークンが始めにくる、同じような並びの他のパターンがないかを考え、
それに近いかたちで実装できないかを考えます。
そう考えると単項演算子の-1や+1が近いかたちになっています。
始めにくるトークンの-や+が決まれば、単項演算子と決まるからです。
関数定義の構文解析もそれに近いかたちで実装できそうです。

次に関数呼び出しの文の構文解析の実装を考えます。
呼び出しの方は、先に実装しているprintln(v)と同じ構文構造になっています。
従ってすでに実装ができている状態になっています。

インタプリタ(Interpreter)の実装の仕方

まず関数の定義の実装の仕方です。
println()を実装したときに関数を表すクラスを導入しました。
println()関数の実装はFuncクラスを継承しています。
関数定義のインタプリタへの実装も、同じようにFuncクラスを継承すればよさそうです。
そしてインタプリタの実行中で関数定義の部分に出会ったら、
継承したクラスを動的にインスタンス化してあげます。

次に関数呼び出しの実装の仕方です。
呼び出しの方は構文解析のときと同じように、println()の実装がそのまま使えるので
実装できた状態になっています。

Javaで実装してみる

実装にうつります。
字句解析(Lexer)、構文解析(Parser)、インタプリタ(Interpreter)について、
変更と追加をしたところを順にみていきます。

Lexer.java

Lexer.javaの実装です。
まずは括弧、{と}を解析する機能の追加です。
波括弧の終わりのほう}は、ブロックの終わりとして特別扱いしたいため、
意味をeob(End of Block)にしています。

Lexer.java

    
   private boolean isCurlyStart(char c) {
        return c == '{' || c == '}';
    }

    private Token curly() throws Exception {
        Token t = new Token();
        if (c() == '{') {
            t.kind = "curly";
        } else {
            t.kind = "eob";
        }
        t.value = Character.toString(next());
        return t;
    }

波括弧解析の呼び出し部分を追加してあげます。
Lexer.javaの実装は終了です。

Lexer.java

    public Token nextToken() throws Exception {
        skipSpace();
        if (isEOT()) {
            return null;
        } else if (isSignStart(c())) {
            return sign();
        } else if (isDigitStart(c())) {
            return digit();
        } else if (isIdentStart(c())) {
            return ident();
        } else if (isParenStart(c())) {
            return paren();
        } else if (isCurlyStart(c())) {
            return curly();
        } else {
            throw new Exception("Not a character for tokens");
        }
    }

Parser.java

Parser.javaの実装です。
まずトークンの意味に対して、どう動作するかの定義を追加します。
<-- Addの箇所で予約語を定義するreservedを追加し、そちらへfunctionを追加します。

Parser.java

private Map<String, Integer> degrees;
    private List<String> factorKinds;
    private List<String> binaryKinds;
    private List<String> rightAssocs;
    private List<String> unaryOperators;
    private List<String> reserved;  // <-- Add

    public Parser() {
        degrees = new HashMap<>();
        degrees.put("(", 80);
        degrees.put("*", 60);
        degrees.put("/", 60);
        degrees.put("+", 50);
        degrees.put("-", 50);
        degrees.put("=", 10);
        factorKinds = Arrays.asList(new String[] { "digit", "ident" });
        binaryKinds = Arrays.asList(new String[] { "sign" });
        rightAssocs = Arrays.asList(new String[] { "=" });
        unaryOperators = Arrays.asList(new String[] { "+", "-" });
        reserved = Arrays.asList(new String[] { "function" });  // <-- Add
    }

解析を行う部分の変更です。
関数定義の解析を行うメソッドfunc()の呼び出しを<-- Addがあるif文の箇所へ加えました。
単項演算子(unary)の処理と同じように、1つめのトークンの種類によって構文解析方法を決定します。

Parser.java


    private Token lead(Token token) throws Exception {
        if (token.kind.equals("ident") && token.value.equals("function")) {  // <-- Add
            return func(token);
        } else if (factorKinds.contains(token.kind)) {
            return token;
        } else if (unaryOperators.contains(token.value)) {
            token.kind = "unary";
            token.left = expression(70);
            return token;
        } else if (token.kind.equals("paren") && token.value.equals("(")) {
            Token expr = expression(0);
            consume(")");
            return expr;
        } else {
            throw new Exception("The token cannot place there.");
        }
    }

関数定義の解析を行うメソッドfunc()を追加しました。
関数定義の解析結果は引数のtokenにまとめられます。
まとめるにあたり、Tokenクラスへフィールド変数を追加しています。
追加したフィールド変数はident、param、blockです。
identは関数名をあらわすトークンを保持します。
paramは仮引数をあらわすトークンを保持します。
blockは関数の処理ブロックを保持し、その型はList<Token>になっています。

func()メソッドでの処理は、関数定義のトークンを順になぞるようになっています。
最初にトークンの意味をfuncで決定します。
次に関数名をident()メソッド呼び出しで取得します。
ident()メソッドはトークンの意味がidentであることを確認して、そのトークンを返します。
次に引数の始まりの(を消費します。
仮引数を再びident()メソッド呼び出しで取得します。
次に引数の終わりの)を消費し、ブロックの始まりの{を消費します。
ブロックの中身はすでにあるblock()の戻り値をそのまま割り付けます。
最後にブロックの終わりの}を消費すれば、関数定義の構文解析は完了です。
Parser.javaの実装も終了です。

Parser.java

  private Token func(Token token) throws Exception {
        token.kind = "func";
        token.ident = ident();
        consume("(");
        token.param = ident();
        consume(")");
        consume("{");
        token.block = block();
        consume("}");
        return token;
    }

    private Token ident() throws Exception {
        Token id = next();
        if (!id.kind.equals("ident")) {
            throw new Exception("Not an identical token.");
        }
        if (reserved.contains(id.value)) {
            throw new Exception("The token was reserved.");
        }
        return id;
    }

Interpreter.java

Interpreter.javaの実装です。

関数を表すクラスDynamicFuncを導入します。
Funcクラスを継承しています。

フィールド変数には、

インタプリタを駆動するためのcontext
仮引数をあらわすparam
ブロックを保持するblock

があります。

invoke()メソッドの実装は、引数を値として解決し、それを仮引数の値へ保持させます。
その状態でインタプリタであるcontextへ、blockを実行させます。

Interpreter.java

    public static class DynamicFunc extends Func {

        public Interpreter context;
        public Token param;
        public List<Token> block;

        @Override
        public Object invoke(Object arg) throws Exception {
            Variable v = context.variable(context.ident(param));
            v.value = context.value(arg);
            context.body(block);
            return null;
        }
    }

トークンの意味によって、それぞれを処理するメソッドを呼び分ける部分の変更です。
関数定義を<-- Addがある箇所へ加えました。

Interpreter.java

    public Object expression(Token expr) throws Exception {
        if (expr.kind.equals("digit")) {
            return digit(expr);
        } else if (expr.kind.equals("ident")) {
            return ident(expr);
        } else if (expr.kind.equals("func")) { // <-- Add
            return func(expr);
        } else if (expr.kind.equals("paren")) {
            return invoke(expr);
        } else if (expr.kind.equals("sign") && expr.value.equals("=")) {
            return assign(expr);
        } else if (expr.kind.equals("unary")) {
            return unaryCalc(expr);
        } else if (expr.kind.equals("sign")) {
            return calc(expr);
        } else {
            throw new Exception("Expression error");
        }
    }

関数定義部分の実装です。
まず関数名と仮引数名がすでに使われていないかを確認します。
関数を表すクラスDynamicFuncを生成し、フィールド変数へ値を割り付けます。
仮引数paramはあらかじめ変数として定義してしまい、
変数をあらわすインスタンスをフィールド変数へ割り付けます。
最後に関数名とその値を保持するMapへ追加してあげ、関数定義が完了します。

Interpreter.java

    public Object func(Token token) throws Exception {
        String name = token.ident.value;
        if (functions.containsKey(name)) {
            throw new Exception("Name was used");
        }
        if (variables.containsKey(name)) {
            throw new Exception("Name was used");
        }
        DynamicFunc func = new DynamicFunc();
        func.context = this;
        func.name = name;
        func.param = token.param;
        func.block = token.block;
        functions.put(name, func);
        return null;
    }

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

v = 0
function addV(num) {
  v = v + num
}
addV(3)
println(v)

を実行し、変数vへ代入される値3を標準出力へプリントします。

Interpreter.java

public static void main(String[] args) throws Exception {
        String text = "";
        text += "v = 0";
        text += "function addV(num) {";
        text += "  v = v + num";
        text += "}";
        text += "addV(3)";
        text += "println(v)";
        List<Token> tokens = new Lexer().init(text).tokenize();
        List<Token> blk = new Parser().init(tokens).block();
        new Interpreter().init(blk).run();
        // --> 3
    }
}

実装は以上です。
ありがとうございました。

おわりに

ソースの全文はこちらで公開しています。

Calc
https://github.com/quwahara/Calc/tree/article-7-function-r2/Calc/src/main/java

続きの記事があります。

複数の引数に対応する
http://qiita.com/quwahara/items/0bea3bad4eedd2d803cf