はじめに
基本的なデータ構造の配列に対応したいと思います。
この記事は「メソッド呼び出しに対応する」の続きの記事です。
配列対応でやりたいこと
配列対応でやりたいことを確認します。
例えば下のようなプログラムがあります。
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()メソッドを追加します。
[と]を検出します。
private boolean isBracketStart(char c) {
return c == '[' || c == ']';
}
bracket()メソッドを追加します。
[と]をトークンへ解析します。
[や]を表すkindはbracketにします。
private Token bracket() throws Exception {
Token t = new Token();
t.kind = "bracket";
t.value = Character.toString(next());
return t;
}
nextToken()メソッドを変更します。
// Addのところへ、追加したメソッドの呼び出しを追加します。
これで[と]をトークンへ分解できます。
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になっています。
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()メソッドの呼び出しを追加しました。
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トークンを割り付けるようにしました。
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トークンを、スタティックフィールド変数に加えました。
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にあたるトークンを割り付けます。
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()メソッド呼び出しを追加しました。
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を返します。
public Object blank(Token token) {
return null;
}
配列生成のためのnewArray()メソッドを追加しました。
ArrayList<Object>を生成して要素を追加したら、それを返します。
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を値として許容するようにしました。
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()メソッドで要素を取り出して返り値にします。
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()メソッドでアクセスするものが、配列であることを保証してあげます。
@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"を出力します。
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