12 while文に対応する

# はじめに

以前の記事で[比較演算子と論理演算子](http://qiita.com/quwahara/items/162d01c5af7c69cfa0ed)や、[if文に対応](http://qiita.com/quwahara/items/96a68cdee4f2a0452836)しました。
その延長でwhile文に対応したいと思います。

# while文対応でやりたいこと

簡単にやりたいことを確認します。
例えば下のようなプログラムがあったら、
while文で繰り返し、`v`が`２`になったところで繰り返しをぬけて、`println()`で`２`が出力されことを目指します。

```JS
v = 0
while (v < 4) {
  v = v + 1
  if (v == 2) {
    break
  }
}
println(v)
```

# 実装の仕方

実装の仕方ですが、
while文の実装は[if文の対応](http://qiita.com/quwahara/items/96a68cdee4f2a0452836)とほとんど同じで、
break文の実装は[関数の戻り値対応](http://qiita.com/quwahara/items/1db9a5b880fd36dcfd3c)とほとんど同じとなっています。
なので詳しい説明はそちらを参照して頂いて、早速実装してみましょう。

# Javaで実装してみる

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

## Parser.java

Parser.javaの実装です。
トークンの意味に対して、どう動作するかの定義を追加します。
`while`と`break`が予約語となるので、`<-- Update`のところへ加えました。

```Java:Parser.java
    public Parser() {
        degrees = new HashMap<>();
        degrees.put("(", 80);
        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" });
        binaryKinds = Arrays.asList(new String[] { "sign" });
        rightAssocs = Arrays.asList(new String[] { "=" });
        unaryOperators = Arrays.asList(new String[] { "+", "-", "!" });
        reserved = Arrays.asList(new String[] { "function", "return", "if", "else", "while", "break"});  // <-- Update
    }
```

解析を行う部分の変更です。
`while`の解析を行う関数の呼び出しをはじめの`<-- Add`のところへ加えました。
`break`の解析を2つめの`<-- Add`のところへ加えました。
`break`の解析は`token.kind`への代入で、トークンの意味を`brk`に決定して終わりです。

```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")) { // <-- Add
            return while_(token);
        } else if (token.kind.equals("ident") && token.value.equals("break")) { // <-- Add
            token.kind = "brk";
            return 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.");
        }
    }
```

解析を行う部分の変更です。
while文の解析を行うメソッド`while_()`を追加しました。
前述したようにif文の解析を、単純にした説明になります。

while文の解析結果は引数のtokenにまとめられます。

`while_()`メソッドでの処理は、while文定義のトークンを順になぞるようになっています。
最初に`token.kind`への代入で、トークンの意味を`while`に決定します。
次に条件文の始まりの`(`を消費します。
`expression()`メソッドはwhile文の条件文を解析して、`token.left`へ保持します。
次いで条件文の終わり`)`を消費します。

処理ブロックの解析です。
ブロックの始まりの`{`があれば、`{`トークンと`}`トークンで囲まれた
処理ブロックを解析する`body()`メソッドを呼び出して、`token.block`へ保持します。
ブロックの始まりの`{`がなければ、処理ブロックは1文だけだとみなして、`token.block`へ保持します。

```Java:Parser.java
    private Token while_(Token token) throws Exception {
        token.kind = "while";
        consume("(");
        token.left = expression(0);
        consume(")");
        if (token().value.equals("{")) {
            token.block = body();
        } else {
            token.block = new ArrayList<Token>();
            token.block.add(expression(0));
        }
        return token;
    }
```

## Interpreter.java

Interpreter.javaの実装です。

式を逐次実行するメソッド`body()`への変更です。

`body()`のシグニチャーに`boolean[] brk`を加えました。
`brk`の役割りは2つです。
１つめは`brk`が`null`でないなら、`break`が可能な状況であることを表します。
２つめは`break`にであったら、呼び出し元にも`break`にであったことを伝播します。
`brk`を`boolean`の配列型にしたのは、呼び出し元に値を返すためです。

`// <-- Add 2`のところで逐次実行するトークンが`break`かを判定します。
トークンが`break`なら`break`可能な状況か判定します。
`brk`へ`break`にであったことを呼び出し元に伝えるために`true`を代入します。

`// <-- Add 1`のところへwhile文を処理するメソッドの呼び出しを追加しました。
while文の処理ブロックの中で`return`が呼ばれた場合に上位へ戻れるように、
`ret[0]`が`true`かを判定して、`body()`メソッドを中断します。

```Java:Interpreter.java
    public Object body(List<Token> body, boolean[] ret, boolean[] brk) throws Exception {
        for (Token exprs : body) {
            if (exprs.kind.equals("if")) {
                Object val = if_(exprs, ret, brk);
                if (ret != null && ret[0]) {
                    return val;
                }
            } else if (exprs.kind.equals("ret")) {
                if (ret == null) {
                    throw new Exception("Can not return");
                }
                ret[0] = true;
                if (exprs.left == null) {
                    return null;
                } else {
                    return expression(exprs.left);
                }
            } else if (exprs.kind.equals("while")) { // <-- Add 1
                Object val = while_(exprs, ret);
                if (ret != null && ret[0]) {
                    return val;
                }
            } else if (exprs.kind.equals("brk")) { // <-- Add 2
                if (brk == null) {
                    throw new Exception("Can not break");
                }
                brk[0] = true;
                return null;
            } else {
                expression(exprs);
            }
        }
        return null;
    }
```

while文を実行する`while_()`メソッドです。
`token.left`が条件式を保持しています。
`isTrue()`メソッドで、条件式が真かを判定します。
条件式が真のあいだは`token.block`を繰り返します。
ただし条件式が真であっても、`body()`メソッド呼び出し内で、
`return`か`break`トークンにであったら繰り返しは中断します。

```Java:Interpreter.java
    public Object while_(Token token, boolean[] ret) throws Exception {
        boolean[] brk = new boolean[1];
        Object val;
        while (isTrue(token.left)) {
            val = body(token.block, ret, brk);
            if (ret != null && ret[0]) {
                return val;
            }
            if (brk[0]) {
                return null;
            }
        }
        return null;
    }
```

続いて`body()`メソッドのシグニチャーを変更したことへの対応です。

if文内でも`break`が呼ばれることがあります。
そのため`if_()`メソッドのシグニチャーにも`brk`仮引数を追加して、
`body()`メソッドの呼び出しではそれを渡します。

```Java:Interpreter.java
    public Object if_(Token token, boolean[] ret, boolean[] brk) throws Exception {
        List<Token> block;
        if (isTrue(token.left)) {
            block = token.block;
        } else {
            block = token.blockOfElse;
        }
        if (block != null) {
            return body(block, ret, brk);
        } else {
            return null;
        }
    }
```

引き続き`body()`メソッドのシグニチャーを変更したことへの対応です。

`<-- Update`にある`body()`メソッドの呼び出しでは、
`break`呼び出しが行えない文脈での処理なので
`body()`メソッドの引数`brk`は`null`で呼び出します。

```Java:Interpreter.java
    public Map<String, Variable> run() throws Exception {
        body(body, null, null); // <-- Update
        return variables;
    }

    public static class DynamicFunc extends Func {

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

        @Override
        public Object invoke(List<Object> args) throws Exception {
            for (int i = 0; i < params.size(); ++i) {
                Token param = params.get(i);
                Variable v = context.variable(context.ident(param));
                if (i < args.size()) {
                    v.value = context.value(args.get(i));
                } else {
                    v.value = null;
                }
            }
            boolean[] ret = new boolean[1];
            return context.body(block, ret, null); // <-- Update
        }
    }
```

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

```JS
v = 0
while (v < 4) {
  v = v + 1
  if (v == 2) {
    break
  }
}
println(v)
```

を実行し、標準出力へ`2`を順にプリントします。

```Java:Interpreter.java
    public static void main(String[] args) throws Exception {
        String text = "";
        text += "v = 0";
        text += "while (v < 4) {";
        text += "  v = v + 1";
        text += "  if (v == 2) {";
        text += "    break";
        text += "  }";
        text += "}";
        text += "println(v)";
        List<Token> tokens = new Lexer().init(text).tokenize();
        List<Token> blk = new Parser().init(tokens).block();
        new Interpreter().init(blk).run();
        // --> 2
    }
```

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

# おわりに

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

**Calc**
https://github.com/quwahara/Calc/tree/article-12-while-r2/Calc/src/main/java

続きの記事があります。

**Scopeに対応する**
http://qiita.com/quwahara/items/d9f932195da1b655b617