2 単純な構文解析をJavaで実装する

# はじめに

コンパイラ実装の処理過程に構文解析があります。
[単純な字句解析をJavaで実装する](http://qiita.com/quwahara/items/d7ea5d0e0dbc0409a01f)の続きで、
構文解析のごくごく原始的なものをJavaで実装してみたいとおもいます。

# 構文解析でやりたいこと

実装にあたりやりたいことを確認します。
プログラムになっている文字列が四則演算だったとします。
構文解析ではその四則演算をどういう順序で計算するかを解析します。
下の式を例に考えます。

```JS
a = 3 + 4 * 5
```

一目瞭然ですが、下の順序で括弧を付けた部分から計算します。

1. `(4 * 5)`
1. `(3 + (4 * 5))`
1. `(a = (3 + (4 * 5)))`

構文解析ではこの順序付けを行います。
実際のプログラムでは関数の定義や呼び出しなどがあります。
簡単のためにまずは四則演算と、変数への代入が解析できることをめざします。

# 順序付けの表現方法

順序付けをしたいことは分かりました。
順序付けした状態を実装でどう表現するか考えます。
例の式の一部、`4 * 5`からみていきましょう。
[前回の記事](http://qiita.com/quwahara/items/d7ea5d0e0dbc0409a01f)で式をトークンへ分解しました。
`4 * 5`はトークンに分解すると、`4`、`*`、`5`の３つになります。
ここで`4 * 5`の状態を表現するために、`*`トークンに対して、左に`4`トークン、右に`5`トークンを持っているとわかるように、フィールド変数を追加してあげます。
具体的には前回の記事のTokenクラスの実装に、`left`と`right`を追加してあげます。

```Java:Token.java

public class Token {

    public String kind;
    public String value;
    public Token left;
    public Token right;

    @Override
    public String toString() {
        return kind + " \"" + value + "\"";
    }

    public String paren() {
        if (left == null && right == null) {
            return value;
        } else {
            StringBuilder b = new StringBuilder();
            b.append("(");
            if (left != null) {
                b.append(left.paren()).append(" ");
            }
            b.append(value);
            if (right != null) {
                b.append(" ").append(right.paren());
            }
            b.append(")");
            return b.toString();
        }
    }

}
```

これで`*`トークンの`left`に`4`トークンを持たせ、`right`に`5`トークンを持たせれば、`4 * 5`の状態を表現できます。
次に`3 + (4 * 5)`の状態を表現します。
同じ考え方で、`+`トークンの`left`に`3`トークンを持たせ、`right`に`*`トークンを持たせます。
ここで`*`トークンは先の説明で`left`と`right`に`4`と`5`のトークンを持っています。
つまり`4 * 5`となっています。
まとめると、`+`トークンがあって、`left`に`3`トークン、`right`が`4 * 5`トークンとなり、`3 + (4 * 5)`の状態が表現できました。
話がそれますが、内容の確認用に括弧付きの状態を表すparen()もTokenクラスへ追加しました。

# 順序付けの仕方

次はこの順序付けの仕方を考えます。
例の式では、3つの演算子が登場します。`=`、`+`、`*`の3つです。
順序の基準になっているのはそれらの演算子です。
構文解析でやりたいことで確認した順序では、`*`が1番、`+`が2番、`=`が3番でした。
ここでこの順序に対して先にくる方の演算子へ、先にくる度合いの数値を割り当てます。
具体的には`*`に`60`を、`+`に`50`を、`=`に`10`を割り当てます。
この度合いを基準に、数値が大きい方から先に括弧付をしていきます。
`*`が`60`で度合いが1番大きいので、最初に括弧付され、
`=`は`10`で度合いが1番小さいので、最後に括弧付されることになります。

# Javaで実装してみる

実装にうつります。
構文解析を行うクラスを部分的にみていきます。

はじめはトークンの意味に対して、どう動作するかを定義します。
`degrees`は演算子順序の度合いを定義します。
`factorKinds`は`a`トークンや`3`トークンなど、式の左右の端にくるトークンの`kind`を定義します。
`binaryKinds`は`=`トークンや`+`トークンなど、式の真ん中にくるトークンの`kind`を定義します。
`rightAssocs`は`=`トークンへの順序付けで、特別扱いをする必要があり、そのための定義です。

```Java:Parser.java
public class Parser {

    private Map<String, Integer> degrees;
    private List<String> factorKinds;
    private List<String> binaryKinds;
    private List<String> rightAssocs;

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

続いて構文解析を行う前の初期化の部分です。
字句解析で分解されたトークンのリストを受けとります。
このトークンリストへ構文解析をかけます。
解析で終端を処理するのに都合がいいので、トークンリストの末尾へ終端をあらわす`eob`トークンを追加します。
またトークンリストを先頭から終端へ順に参照するためのインデックス`i`も0にします。

```Java:Parser.java
    private List<Token> tokens;
    private int i;
    
    public Parser init(List<Token> tokens) {
        i = 0;
        this.tokens = new ArrayList<Token>(tokens);
        Token eob = new Token();
        eob.kind = "eob";
        eob.value = "(eob)";
        this.tokens.add(eob);
        return this;
    }
```

トークンリストを順に参照する機能です。
`token()`はトークンリスト中の現在注目しているトークンです。
`next()`は注目していたトークンを返し、注目する位置を次へ進めます。

```Java:Parser.java
    private Token token() throws Exception {
        if (tokens.size() <= i) {
            throw new Exception("No more token");
        }
        return tokens.get(i);
    }

    private Token next() throws Exception {
        Token t = token();
        ++i;
        return t;
    }
```

解析をする部分の説明へ入っていきます。
`lead()`は`a`や`3`など、式の左右の端にこられるトークンであることを解析して、そのトークンを返します。

```Java:Parser.java
    private Token lead(Token token) throws Exception {
        if (factorKinds.contains(token.kind)) {
            return token;
        } else {
            throw new Exception("The token cannot place there.");
        }
    }
```

`degree()`はトークンの優先順位度合いを返します。
`bind()`は演算子トークンへ左右にくるトークンを割り付け、割り付けの済んだ演算子トークンを返します。

```Java:Parser.java
    private int degree(Token t) {
        if (degrees.containsKey(t.value)) {
            return degrees.get(t.value);
        } else {
            return 0;
        }
    }

    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 {
            throw new Exception("The token cannot place there.");
        }
    }

```

`bind()`について詳しくみていきます。
`bind()`は引数に式の左にくるトークンと、式の演算子トークンをとります。
`bind()`ではまず、その左にくるトークンを演算子トークンの`operator.left`へ割り付けます。
`operator.right`へ割り付けるトークンは、`expression()`を呼んだ戻り値を割り付けます。
`expression()`がどのようなトークンを返すかを説明しましょう。
`expression()`を呼び出すとき引数に、演算子トークンの優先順位度合いを渡します。
渡された度合いは`expression()`の中で、トークンリストで後に続く演算子の度合いと比較されます。
渡された度合が大きいか同じときは、後に続く演算子トークンの前のトークンを、`expression()`は返します。
例えば下の式で、`bind()`を引数に`left`が`6`で`operator`が`+`で呼び出したときを考えます。

```JS
6 + 7 - 8
```

`expression()`は`+`の度合い`50`で呼び出され、後にくる`-`の度合い`50`と比較します。
度合いは同じなので、`-`の前にくるトークン`7`を返します。
そして`bind()`に戻り`7`は`operator.right`へ割り付けられます。
これで`6 + 7`に関連付けた`+`を`bind()`は返します。
度合い比較で`leftDegree`が小さい場合は、あとで説明します。

`expression()`は演算子の優先順位度合いをつかって、トークンの関連付けを制御します。
先に説明した、`lead()`と`bind()`を`expression()`が呼び出します。

```Java:Parser.java
    public Token expression(int leftDegree) throws Exception {
        Token left = lead(next());
        int rightDegree = degree(token());
        while (leftDegree < rightDegree) {
            Token operator = next();
            left = bind(left, operator);
            rightDegree = degree(token());
        }
        return left;
    }

```

`expression()`の動きを幾つかのトークンリストを例にとってみてみましょう。

## トークンリストが`a`だけの場合

まず初めの`expression()`の呼び出しでは`leftDegree`は`0`で呼び出します。
`a`だけの場合、`lead()`の呼び出しで、`a`が返され、`left`が`a`で決まりす。
次の`degree()`では終端しやすいように追加した`(eob)`の度合いが返され`rightDegree`は`0`です。
`leftDegree`が`0`、`rightDegree`が`0`で`while`が成立せず、`left`の`a`がそのまま返されます。
つまり`a`だけのトークンリストが解析できました。

## トークンリストが`a = 3`の場合

`a = 3`の場合も、`lead()`の呼び出しで、`a`が返され、`left`が`a`で決まります。
次の`degree()`では`=`の度合いが返され`rightDegree`は`10`です。
先の場合と同じで`expression()`は、`leftDegree`が`0`で呼び出されていて`while`が成立します。
すると`bind()`を`a`と`=`を引数に呼び出します。
`bind()`で説明したように、`bind()`では式の右側のトークンを解析するために、`expression()`を呼び出します。
`bind()`で`expression()`を呼び出すときは、`a =`まで解析できているので、トークンリストに残るトークンは、`3`のみです。
これは先に説明した、「トークンリストが`a`だけの場合」と同じ状況です。
つまり`bind()`で呼び出した`expression()`は`3`を返し、`operator.right`は`3`で決まります。
`bind()`は呼び出し元の`expression()`へ`=`を返し、
呼び出し元の`expression()`の`left`は`=`で決まります。
`bind()`呼び出しの次の行の`degree()`は`(eob)`の度合い`0`を返すので、`while`を抜けます。
これで`=`に決まった`left`を`expression()`が返し、解析ができました。
またこの説明は、あとで説明するとしていた度合い比較で`leftDegree`が小さい場合の説明にもなっています。

解析をする部分の最後の説明です。
`block()`はトークンリストが`(eob)`になるまで、`expression()`を呼び出し、その解析結果をリストへ追加します。
トークンリストにある式の数だけ、`blk`に解析結果が追加されます。

```Java:Parser.java
    public List<Token> block() throws Exception {
        List<Token> blk = new ArrayList<Token>();
        while (!token().kind.equals("eob")) {
            blk.add(expression(0));
        }
        return blk;
    }
```

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

```JS
a = 3 + 4 * 5
```

を構文解析し、標準出力へプリントします。

```Java:Parser.java
    public static void main(String[] args) throws Exception {
        String text = "a = 3 + 4 * 5";
        List<Token> tokens = new Lexer().init(text).tokenize();
        List<Token> blk = new Parser().init(tokens).block();
        for (Token ast : blk) {
            System.out.println(ast.paren());
        }
        // --> (a = (3 + (4 * 5)))
    }
}
```

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


# おわりに

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

**Calc**
https://github.com/quwahara/Calc/tree/article-2-parser/Calc/src/main/java

続きの記事があります。

**単純なインタプリタをJavaで実装する**
http://qiita.com/quwahara/items/30e93dfd2690913d66c0





最後に、Parserクラスをまとめたものもあげておきます。

```Java:Parser.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Parser {

    private Map<String, Integer> degrees;
    private List<String> factorKinds;
    private List<String> binaryKinds;
    private List<String> rightAssocs;

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

    private List<Token> tokens;
    private int i;
    
    public Parser init(List<Token> tokens) {
        i = 0;
        this.tokens = new ArrayList<Token>(tokens);
        Token eob = new Token();
        eob.kind = "eob";
        eob.value = "(eob)";
        this.tokens.add(eob);
        return this;
    }

    private Token token() throws Exception {
        if (tokens.size() <= i) {
            throw new Exception("No more token");
        }
        return tokens.get(i);
    }

    private Token next() throws Exception {
        Token t = token();
        ++i;
        return t;
    }

    private Token lead(Token token) throws Exception {
        if (factorKinds.contains(token.kind)) {
            return token;
        } else {
            throw new Exception("The token cannot place there.");
        }
    }

    private int degree(Token t) {
        if (degrees.containsKey(t.value)) {
            return degrees.get(t.value);
        } else {
            return 0;
        }
    }

    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 {
            throw new Exception("The token cannot place there.");
        }
    }

    public Token expression(int leftDegree) throws Exception {
        Token left = lead(next());
        int rightDegree = degree(token());
        while (leftDegree < rightDegree) {
            Token operator = next();
            left = bind(left, operator);
            rightDegree = degree(token());
        }
        return left;
    }

    public List<Token> block() throws Exception {
        List<Token> blk = new ArrayList<Token>();
        while (!token().kind.equals("eob")) {
            blk.add(expression(0));
        }
        return blk;
    }

    public static void main(String[] args) throws Exception {
        String text = "a = 3 + 4 * 5";
        List<Token> tokens = new Lexer().init(text).tokenize();
        List<Token> blk = new Parser().init(tokens).block();
        for (Token ast : blk) {
            System.out.println(ast.paren());
        }
        // --> (a = (3 + (4 * 5)))
    }
}
```