17 配列に対応する

# はじめに

基本的なデータ構造の配列に対応したいと思います。
この記事は「[メソッド呼び出しに対応する](http://qiita.com/quwahara/items/f1bddefe984c8d233e02)」の続きの記事です。

# 配列対応でやりたいこと

配列対応でやりたいことを確認します。
例えば下のようなプログラムがあります。
1行目で配列を作成し、変数`ar`へ代入します。
2行目では配列の長さ`3`を出力します。
3行目では配列の3番目の要素`"c"`が出力されることを目指します。

```JS
var ar = ["a", "b", "c"]
println(ar.size())
println(ar[2])
```

# 実装の仕方

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

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

`[`と`]`を解析する機能がないので追加します。

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

構文解析への実装は配列を生成する構文と、配列の要素へアクセスする構文の2つに対応します。

配列を生成する構文は、`[`トークンで始まります。
他の1つ目のトークンで構文決まるものと同じように、`lead()`メソッドへ実装します。

配列の要素へアクセスする構文は、引数を1つとる関数呼び出しの構文と同等です。
プログラムの例にある`ar[2]`の`[]`を`()`へ置き換えると`ar(2)`となり、
関数呼び出しの見た目になるので同等だと分かります。
関数呼び出し構文解析と同等に`bind()`メソッドへ実装します。

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

配列の実体は、要素の追加や長さの取得がインスタンスメソッド行えるので、
`ArrayList<Object>`を使うことにしました。
前の記事で[メソッド呼び出しに対応](http://qiita.com/quwahara/items/f1bddefe984c8d233e02)したのでそれが活かせます。

構文に対する処理は、配列の生成と配列要素へのアクセスを実装します。
配列の生成では、`ArrayList<Object>`を生成して要素を追加していきます。
配列要素へのアクセスは`ArrayList<Object>::get()`メソッド呼び出しを行います。

# Javaで実装してみる

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

## Lexer.java

Lexer.javaの実装です。

`[`と`]`の字句解析機能を追加します。

`isBracketStart()`メソッドを追加します。
`[`と`]`を検出します。

```Java:Lexer.java
    private boolean isBracketStart(char c) {
        return c == '[' || c == ']';
    }
```

`bracket()`メソッドを追加します。
`[`と`]`をトークンへ解析します。
`[`や`]`を表す`kind`は`bracket`にします。

```Java:Lexer.java
    private Token bracket() throws Exception {
        Token t = new Token();
        t.kind = "bracket";
        t.value = Character.toString(next());
        return t;
    }
```

`nextToken()`メソッドを変更します。
`// Add`のところへ、追加したメソッドの呼び出しを追加します。
これで`[`と`]`をトークンへ分解できます。

```Java:Lexer.java
    public Token nextToken() throws Exception {
        skipSpace();
        if (isEOT()) {
            return null;
        } else if (isSignStart(c())) {
            return sign();
        } else if (isDotStart(c())) {
            return dot();
        } else if (isDigitStart(c())) {
            return digit();
        } else if (isStringStart(c())) {
            return string();
        } else if (isIdentStart(c())) {
            return ident();
        } else if (isParenStart(c())) {
            return paren();
        } else if (isCurlyStart(c())) {
            return curly();
            // Add
        } else if (isBracketStart(c())) {
            return bracket();
        } else if (isSymbolStart(c())) {
            return symbol();
        } else {
            throw new Exception("Not a character for tokens");
        }
    }
```

Lexer.javaの変更は以上です。

## Parser.java

Parser.javaの実装です。

トークンの意味に対して、どう動作するかの定義を追加します。
`// Add`のところへ`[`の順序付けの度合いを追加しました。
`[`は`+`や`*`のような算術的な演算子よりも、
強く左右のトークンを結びつけるので、
`+`や`*`の度合いよりも大きい80になっています。

```Java:Parser.java
    public Parser() {
        degrees = new HashMap<>();
        degrees.put(".", 80);
        degrees.put("(", 80);
        degrees.put("[", 80);   // Add
        degrees.put("*", 60);
        degrees.put("/", 60);
        degrees.put("+", 50);
        degrees.put("-", 50);
        degrees.put("==", 40);
        degrees.put("!=", 40);
        degrees.put("<", 40);
        degrees.put("<=", 40);
        degrees.put(">", 40);
        degrees.put(">=", 40);
        degrees.put("&&", 30);
        degrees.put("||", 30);
        degrees.put("=", 10);
        factorKinds = Arrays.asList(new String[] { "digit", "ident", "string" });
        binaryKinds = Arrays.asList(new String[] { "sign", "dot" });
        rightAssocs = Arrays.asList(new String[] { "=" });
        unaryOperators = Arrays.asList(new String[] { "+", "-", "!" });
        reserved = Arrays.asList(new String[] { "function", "return", "if", "else", "while", "break", "var" });
    }
```

配列生成構文の解析を実装します。
1つ目のトークンで構文が決まるものを実装する`lead()`メソッドの
`// Add`のところへ配列生成構文解析を行う`newArray()`メソッドの呼び出しを追加しました。

```Java:Parser.java
    private Token lead(Token token) throws Exception {
        if (token.kind.equals("ident") && token.value.equals("function")) {
            return func(token);
        } else if (token.kind.equals("ident") && token.value.equals("return")) {
            token.kind = "ret";
            if (!token().kind.equals("eob")) {
                token.left = expression(0);
            }
            return token;
        } else if (token.kind.equals("ident") && token.value.equals("if")) {
            return if_(token);
        } else if (token.kind.equals("ident") && token.value.equals("while")) {
            return while_(token);
        } else if (token.kind.equals("ident") && token.value.equals("break")) {
            token.kind = "brk";
            return token;
        } else if (token.kind.equals("ident") && token.value.equals("var")) {
            return var(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;
            // Add
        } else if (token.kind.equals("bracket") && token.value.equals("[")) {
            return newArray(token);
        } else {
            throw new Exception("The token cannot place there.");
        }
    }
```

配列生成構文解析を行う`newArray()`メソッドを追加しました。
`,`で区切られた要素を`]`トークンに達するまで、`[`トークンの`params`へ集めます。
トークンの種類`kind`は`newArray`にしました。
配列が`[1,2,]`のように最後の要素が空だったら、それは要素として無視するようにしました。
配列が`[1,,3]`のように、並びの途中で空の要素が指定されたら、
予め用意しておく`blank`トークンを割り付けるようにしました。

```Java:Parser.java
    private Token newArray(Token token) throws Exception {
        token.kind = "newArray";
        token.params = new ArrayList<Token>();
        while(true) {
            if (token().value.equals("]")) {
                consume("]");
                break;
            }
            if (token().value.equals(",")) {
                token.params.add(blank);
                consume(",");
                continue;
            }
            token.params.add(expression(0));
            if (token().value.equals(",")) {
                consume(",");
                continue;
            } else {
                consume("]");
                break;
            }
        }
        return token;
    }
```

先に出てきた空の要素を表す`blank`トークンを、スタティックフィールド変数に加えました。

```Java:Parser.java
    public static Token blank;
    static {
        blank = new Token();
        blank.kind = "blank";
        blank.value = "";
    }
```

配列アクセス構文を実装します。
関数呼び出し構文などを解析する`bind()`メソッドの
`// Add`のところへ配列アクセス構文解析を追加しました。
`[`トークンにあたる`operator`の`left`には、配列自身、例`ar[2]`の`ar`にあたるトークンを割り付けます。
`operator`の`right`には、アクセスするインデックス、例`ar[2]`の`2`にあたるトークンを割り付けます。

```Java:Parser.java
    private Token bind(Token left, Token operator) throws Exception {
        if (binaryKinds.contains(operator.kind)) {
            operator.left = left;
            int leftDegree = degree(operator);
            if (rightAssocs.contains(operator.value)) {
                leftDegree -= 1;
            }
            operator.right = expression(leftDegree);
            return operator;
        } else if (operator.kind.equals("paren") && operator.value.equals("(")) {
            operator.left = left;
            operator.params = new ArrayList<Token>();
            if (!token().value.equals(")")) {
                operator.params.add(expression(0));
                while (!token().value.equals(")")) {
                    consume(",");
                    operator.params.add(expression(0));
                }
            }
            consume(")");
            return operator;
            // Add
        } else if (operator.kind.equals("bracket") && operator.value.equals("[")) {
            operator.left = left;
            operator.right = expression(0);
            consume("]");
            return operator;
        } else {
            throw new Exception("The token cannot place there.");
        }
    }

```

Parser.javaの変更は以上です。

## Interpreter.java

Interpreter.javaの実装です。

`expression()`メソッドの変更です。
式を表すトークンの意味(kind)によって分岐する処理です。
`// Add`の下へ、
空要素のための`blank()`メソッド呼び出し、
配列生成のための`newArray()`メソッド呼び出し、
配列アクセスのための`accessArray()`メソッド呼び出しを追加しました。

```Java:Interpreter.java
    public Object expression(Token expr) throws Exception {
        if (expr.kind.equals("digit")) {
            return digit(expr);
        } else if (expr.kind.equals("string")) {
            return string(expr);
        } else if (expr.kind.equals("ident")) {
            return ident(expr);
            // Add
        } else if (expr.kind.equals("blank")) {
            return blank(expr);
            // Add
        } else if (expr.kind.equals("newArray")) {
            return newArray(expr);
            // Add
        } else if (expr.kind.equals("bracket")) {
            return accessArray(expr);
        } else if (expr.kind.equals("func")) {
            return func(expr);
        } else if (expr.kind.equals("fexpr")) {
            return fexpr(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 if (expr.kind.equals("dot")) {
            return dot(expr);
        } else {
            throw new Exception("Expression error");
        }
    }
```

空要素のための`blank()`メソッドを追加しました。
単純に`null`を返します。

```Java:Interpreter.java
    public Object blank(Token token) {
        return null;
    }
```

配列生成のための`newArray()`メソッドを追加しました。
`ArrayList<Object>`を生成して要素を追加したら、それを返します。

```Java:Interpreter.java
    public Object newArray(Token expr) throws Exception {
        List<Object> a = new ArrayList<>();
        for (Token item : expr.params) {
            a.add(value(expression(item)));
        }
        return a;
    }
```

引数が値であることを保証するメソッドの、`value()`メソッドを変更しました。
最初の`// Add`のところは`ArrayList<Object>`を値として許容するようにしました。
次の`// Add`のところは`null`を値として許容するようにしました。

```Java:Interpreter.java
    public Object value(Object value) throws Exception {
        if (value instanceof Integer) {
            return value;
        } else if (value instanceof String) {
            return value;
            // Add
        } else if (value instanceof List<?>) {
            return value;
            // Add
        } else if (value == null) {
            return value;
        } else if (value instanceof Func) {
            return value;
        } else if (value instanceof Variable) {
            Variable v = (Variable) value;
            return value(v.value);
        }
        throw new Exception("right value error");
    }
```

配列アクセスのための`accessArray()`メソッドを追加しました。
引数の`expr`は`[`トークンが渡されます。
`[`トークンの`left`は配列自身に解決します。
`[`トークンの`right`はアクセスするインデックスに解決します。
それらを使い`ArrayList<Object>::get()`メソッドで要素を取り出して返り値にします。

```Java:Interpreter.java
    public Object accessArray(Token expr) throws Exception {
        List<Object> ar = array(expression(expr.left));
        Integer index = integer(expression(expr.right));
        return ar.get(index);
    }
```

引数が配列(`List<Object>`)であることを保証するメソッドの、`array()`メソッドを追加しました。
先の`accessArray()`メソッドでアクセスするものが、配列であることを保証してあげます。

```Java:Interpreter.java
    @SuppressWarnings("unchecked")
    public List<Object> array(Object value) throws Exception {
        if (value instanceof List<?>) {
            return (List<Object>) value;
        } else if (value instanceof Variable) {
            Variable v = (Variable) value;
            return array(v.value);
        }
        throw new Exception("right value error");
    }
```

以上の実装を使って下のプログラム

```JS
var ar = ["a", "b", "c"]
println(ar.size())
println(ar[2])
```

を実行し、配列の長さ`3`と配列の3番目の要素`"c"`を出力します。

```Java:Interpreter.java
    public static void main(String[] args) throws Exception {
        String text = "";
        text += "var ar = [\"a\", \"b\", \"c\"]";
        text += "println(ar.size())";
        text += "println(ar[2])";
        List<Token> tokens = new Lexer().init(text).tokenize();
        List<Token> blk = new Parser().init(tokens).block();
        new Interpreter().init(blk).run();
        // --> 3
        // --> c
    }
```

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

# おわりに

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

**Calc**
https://github.com/quwahara/Calc/tree/article-17-array/Calc/src/main/java

続きの記事があります。

**JSON風のオブジェクト定義に対応する**
http://qiita.com/quwahara/items/5e6cee17b7b03bd994ee