Javaで始めるパーザコンビネータの作り方(2) ~ Hello + World!

前回の記事 では、 Hello, World!をパーザコンビネータでパーズできるようにするところまで進めたのでした。今回は、二つのパーザを組み合わせて、二つのパーザの連接を構成できるようにします。その前に、前回のコードについて、パッケージがないと不便ですので、所属パッケージを付加しておきます。

package parser;
public interface Parser<T> {
    ParseResult<T> invoke(String input);
        static Parser<String> string(String literal) {
        return new StringParser(literal);
    }
}
package parser;
public class StringParser implements Parser<String> {
    public final String literal;
    public StringParser(String literal) {
        this.literal = literal;
    }

    @Override
    public ParseResult<String> invoke(String input) {
        if(input.startsWith(literal)) {
            return new ParseResult.Success<>(literal, input.substring(literal.length()));
        }else {
            return new ParseResult.Failure<>("expect: " + literal, input);
        }
    }
}
package parser;
import java.util.function.*;
public interface ParseResult<T> {
    public static class Success<T> implements ParseResult<T> {
        public final T value;
        public final String next;
        Success(T value, String next) {
            this.value = value;
            this.next = next;
        }

        @Override
        public <U> ParseResult<U> map(Function<T, U> fn) {
            return new Success<U>(fn.apply(value), next);
        }
    }

    public static class Failure<T> implements ParseResult<T> {      
        public final String message;
        public final String next;
        public Failure(String message, String next) {
            this.message = message;
            this.next = next;
        }
        @Override
        public <U> ParseResult<U> map(Function1<T, U> fn) {
            return (ParseResult<U>)this;
        }       
    }

    <U> ParseResult<U> map(Function<T, U> fn);
}

パッケージ名はなんでもよいので、シンプルに parser としておきます。さて、今回の本題は、二つのパーザを連結するというものです。

具体的なコード片で説明します。いま、

Parser<A> pa = ...;
Parser<B> pb = ...;
String input;

という二つのパーザと入力文字列があったとします。この二つのパーザを使うと、次のようなコードを書くことができます。

ParseResult<A> ra = pa.parse(input);
if(ra instanceof ParseResult.Success<*>) {
    String next = ((ParseResult.Success<A>)ra).next;
    ParseResult<B> rb = pb.parse(next);
    if(rb instanceof ParseResult.Success<*>) {
        return build(
            ((ParseResult.Success<A>)ra),
            ((ParseResult.Success<B>)rb)
        );
    } else {
        return rb;
    }
} else {
    return ra;
}

最初のパーザ pa によって、入力の先頭からパーズを開始し、残りのパーザ pb は、 pa が成功した場合にのみ、残りの文字列を使ってパーズを行い、その結果を合成する、といったところでいたって簡単です。ただし、ここで、任意の型 A の値と 任意の型 B の値を組み合わせた新しい値を作ることができないのが多少困りものです。

こういう場合、次のような Tuple クラスを作るのが定番です。

package parser;
public class Tuple2<A, B> {
    public final A item1;
    public final B item2;

    public Tuple2(A item1, B item2) {
        this.item1 = item1;
        this.item2 = item2;
    }
}

例によって、 Tuple2<A, B> クラスのフィールドは外部にそのまま公開(ただしfinal)します。この Tuple2<A, B> クラスを使うと、先程のコードは次のように書くことができます。

ParseResult<A> ra = pa.parse(input);
if(ra instanceof ParseResult.Success<?>) {
    String next = ((ParseResult.Success<A>)ra).next;
    ParseResult<B> rb = pb.parse(next);
    if(rb instanceof ParseResult.Success<?>) {
        return new ParseResult.Success<>(
            new Tuple2<>(
                ((ParseResult.Success<A>)ra).value,
                ((ParseResult.Success<A>)rb).value
            ),
            ((ParseResult.Success<A>)rb).next
        );
    } else {
        return rb;
} else {
    return ra;
}

あとは、このコードをオブジェクトのメソッドに閉じ込めるだけです。とても簡単です。

package parser;
public class Cat<X, Y> implements Parser<Tuple2<X, Y>> {
    private Parser<X> lhs;
    private Parser<Y> rhs;
    public Cat(Parser<X> lhs, Parser<Y> rhs) {
        this.lhs = lhs;
        this.rhs = rhs;
    }

    @Override
    public ParseResult<Tuple2<X, Y>> invoke(String input) {
        ParseResult<X> lresult = lhs.invoke(input);

        if(lresult instanceof ParseResult.Success<?>) {
            X value1 = ((ParseResult.Success<X>)lresult).value;
            String next = ((ParseResult.Success<X>)lresult).next;
            ParseResult<Y> rresult = rhs.invoke(next);

            if(rresult instanceof ParseResult.Success<?>) {
                Y value2 = ((ParseResult.Success<Y>)rresult).value;
                return new ParseResult.Success<>(
                    new Tuple2<>(value1, value1),
                    ((ParseResult.Success<Y>)rresult).next
                );
            } else {
                return rresult;
            }
        } else {
            return lresult;
        }
    }
}

CatParser を毎回 new するのは面倒なので、 Parser のメソッドとして、付け足してしまいましょう。 二つの Parser から新しい Parser を作るので、Parser のデフォルトメソッドとして定義することにします。

package parser;
public interface Parser<T> {
    ParseResult<T> invoke(String input);

    static Parser<String> string(String literal) {
        return new StringParser(literal);
    }

    default <U> Parser<Tuple2<T, U>> cat(Parser<U> rhs) {
        return new Cat<>(this, rhs);
    }
}

最後に、このコードで、 "Hello, ""World! をパーズする二つのパーザから、 "Hello, World!" をパーズするパーザを合成してみます。

package parser;
public class Main {
  public static void main(String[] args) {
    Parser<String> hello = Parser.string("Hello, ");
    Parser<String> world = Parser.string("World!");
    Parser<Tuple2<String, String>> helloWorld = hello.cat(world);
    ParseResult.Success<Tuple2<String, String>> success = (ParseResult.Success<Tuple2<String, String>>)helloWorld.invoke("Hello, World!");
    assert "Hello, ".equals(success.item1);
    assert "World!".equals(success.item2);
  }
}

簡単ですね!次回は、パーザの繰り返しを表すコンビネータについて解説します。

なお、これらのコードは、私が練習用に作ったJavaのパーザコンビネータのコードから説明用に改変を加えて引っ張ってきているものですが、改変の過程でミスを犯して、コンパイルが通らないコードになっている可能性があります。もしそのようなことがありましたら、遠慮なくご指摘いただければと思います。