kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

Java (8)によるパーザコンビネータライブラリ JCombinator 0.0.1をリリースしました

Javaには既にJParsecというパーザコンビネータライブラリもあり、あえて新しいものを作る必要はないかもしれません。

ただ、JParsecはイマイチ気に入らなかったので、新しいパーザコンビネータライブラリを作ってみることにしました。とりあえず、基本的なコンビネータはそろっているので、デバッグの容易さとか考えなければこれで割と複雑なパーザを組むことも可能だと思います。

github.com

今後は、より色々なパーザを書きやすくするためのコンビネータの充実と、パーズエラー時のメッセージをわかりやすくすることに力を注いでいきたいところです。

例として、四則演算をできる式(括弧を含む)のパーザは次のようにして書くことができます。

import com.github.kmizu.jcombinator.datatype.Function2;

import static com.github.kmizu.jcombinator.Parser.*;
import static com.github.kmizu.jcombinator.Functions.*;

public class ArithmeticExpression {
    private Rule<Integer> expression() {
        return rule(() ->
            additive().cat(eof()).map(t -> t.extract((result, __) -> result))
        );
    }
    private Rule<Integer> additive() {
        return rule(() -> {
            final Parser<Function2<Integer, Integer, Integer>> Q = string("+").map(op -> (Integer lhs, Integer rhs) -> lhs + rhs);
            final Parser<Function2<Integer, Integer, Integer>> R = string("-").map(op -> (Integer lhs, Integer rhs) -> lhs - rhs);
            return multitive().chain(Q.or(R));
        });
    }
    private Rule<Integer> multitive() {
        return rule(() -> {
            final Parser<Function2<Integer, Integer, Integer>> Q = string("*").map(op -> (Integer lhs, Integer rhs) -> lhs * rhs);
            final Parser<Function2<Integer, Integer, Integer>> R = string("/").map(op -> (Integer lhs, Integer rhs) -> lhs / rhs);
            return primary().chain(Q.or(R));
        });
    }
    private final Rule<Integer> primary() {
        return rule(() ->
            number().or((string("(").cat(expression())).cat(string(")")).map(t -> t.item1().item2()))
        );
    }
    private final Rule<Integer> number() {
        return rule(() ->
            digit().many1().map(digits -> Integer.parseInt(join(digits, "")))
        );
    }

    public void testExpression() {
        Parser<Integer> arithmetic = expression();
        arithmetic.invoke("100").onSuccess(s -> {
            assert ((Integer)100) == s.value();
        });
        arithmetic.invoke("100+200").onSuccess(s -> {
            assert ((Integer)300) == s.value();
        });
        arithmetic.invoke("(1+2)*(3+4)").onSuccess(s -> {
            assert ((Integer)21) == s.value();
        });
        arithmetic.invoke("1+2*3+4").onSuccess(s -> {
            assert ((Integer)11) == s.value();
        });
    }
}