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

はじめに

コンパイラ実装の処理過程に構文解析があります。
単純な字句解析をJavaで実装するの続きで、
構文解析のごくごく原始的なものをJavaで実装してみたいとおもいます。

構文解析でやりたいこと

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

a = 3 + 4 * 5

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

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

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

順序付けの表現方法

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

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は=トークンへの順序付けで、特別扱いをする必要があり、そのための定義です。

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

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()は注目していたトークンを返し、注目する位置を次へ進めます。

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など、式の左右の端にこられるトークンであることを解析して、そのトークンを返します。

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()は演算子トークンへ左右にくるトークンを割り付け、割り付けの済んだ演算子トークンを返します。

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が+で呼び出したときを考えます。

6 + 7 - 8

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

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

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に解析結果が追加されます。

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

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

a = 3 + 4 * 5

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

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クラスをまとめたものもあげておきます。

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