Edited at

17 配列に対応する

More than 1 year has passed since last update.


はじめに

基本的なデータ構造の配列に対応したいと思います。

この記事は「メソッド呼び出しに対応する」の続きの記事です。


配列対応でやりたいこと

配列対応でやりたいことを確認します。

例えば下のようなプログラムがあります。

1行目で配列を作成し、変数arへ代入します。

2行目では配列の長さ3を出力します。

3行目では配列の3番目の要素"c"が出力されることを目指します。

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>を使うことにしました。

前の記事でメソッド呼び出しに対応したのでそれが活かせます。

構文に対する処理は、配列の生成と配列要素へのアクセスを実装します。

配列の生成では、ArrayList<Object>を生成して要素を追加していきます。

配列要素へのアクセスはArrayList<Object>::get()メソッド呼び出しを行います。


Javaで実装してみる

実装にうつります。

字句解析(Lexer)、構文解析(Parser)、インタプリタ(Interpreter)について、

変更と追加をしたところを順にみていきます。


Lexer.java

Lexer.javaの実装です。

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

isBracketStart()メソッドを追加します。

[]を検出します。


Lexer.java

    private boolean isBracketStart(char c) {

return c == '[' || c == ']';
}

bracket()メソッドを追加します。

[]をトークンへ解析します。

[]を表すkindbracketにします。


Lexer.java

    private Token bracket() throws Exception {

Token t = new Token();
t.kind = "bracket";
t.value = Character.toString(next());
return t;
}

nextToken()メソッドを変更します。

// Addのところへ、追加したメソッドの呼び出しを追加します。

これで[]をトークンへ分解できます。


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になっています。


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()メソッドの呼び出しを追加しました。


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へ集めます。

トークンの種類kindnewArrayにしました。

配列が[1,2,]のように最後の要素が空だったら、それは要素として無視するようにしました。

配列が[1,,3]のように、並びの途中で空の要素が指定されたら、

予め用意しておくblankトークンを割り付けるようにしました。


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トークンを、スタティックフィールド変数に加えました。


Parser.java

    public static Token blank;

static {
blank = new Token();
blank.kind = "blank";
blank.value = "";
}

配列アクセス構文を実装します。

関数呼び出し構文などを解析するbind()メソッドの

// Addのところへ配列アクセス構文解析を追加しました。

[トークンにあたるoperatorleftには、配列自身、例ar[2]arにあたるトークンを割り付けます。

operatorrightには、アクセスするインデックス、例ar[2]2にあたるトークンを割り付けます。


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()メソッド呼び出しを追加しました。


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


Interpreter.java

    public Object blank(Token token) {

return null;
}

配列生成のためのnewArray()メソッドを追加しました。

ArrayList<Object>を生成して要素を追加したら、それを返します。


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を値として許容するようにしました。


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()メソッドで要素を取り出して返り値にします。


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()メソッドでアクセスするものが、配列であることを保証してあげます。


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

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

var ar = ["a", "b", "c"]

println(ar.size())
println(ar[2])

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


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