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

この記事では、パーザコンビネータライブラリを一から作れるようになるための方法について説明します。

パーザコンビネータとは何か

統一された定義があるわけではないですが、パーザコンビネータとは、パーザを部品として、より複雑なパーザを構築するための技法であるというのが一般的な説明になるでしょうか。抽象的な説明だけですとわかりにくいと思うので、具体的な例を出します。コード例はScalaです:

import com.github.kmizu.scomb.SCombinator

object IntegerParser extends SCombinator[Int] {
  override def root: P[Int] = (digit.+).map{ case digits => digits.mkString.toInt }
  lazy val digit: P[String] = set('0'to'9')

  def main(args: Array[String]): Unit = {
    assert(parse("100") == Success(100))
  }
}

これは、私が開発中のパーザコンビネータライブラリSCombのコードです。

P[String] は、構文解析の結果、 String 型の値が得られることを、 P[Int]Int 型の値が得られることを示しています。 set() は、文字の集まりを引数にとって、その文字にマッチするパーザを返します。 set('0'to'9') は、0から9までの文字のいずれかにマッチするパーザで返り値は文字列であるようなパーザを意味します。そして、そのパーザに対して digit という名前を付けています。

root は構文解析を開始するための規則で、一般には必要ありませんが、構文解析をここから開始することを表します。 rootdigit.+ つまり、0から9までの文字の1回以上の繰り返しにマッチします(正規表現と似ていますが、意図的に記号の使い方を似せてあります)。 map メソッドは、マッチした値を加工します。 digits には文字の列が入っているため、それをいったん文字列に変換した後、 Int 型の値としてパーズしています。

パーザコンビネータとパーザジェネレータの違い

パーザコンビネータとパーザジェネレータはしばしば混同されるので、ここで説明しておきます。パーザジェネレータは、ホスト側のプログラミング言語の別の構文で書かれた定義ファイル(BNFに類似したもの)を読み取り、そこからホスト側のプログラミング言語で書かれたパーザを自動生成します。このようなアプローチは、外部DSLを呼ばれます。問題領域に特化した言語を外側に作ることからそう呼ばれるのだと思います。

一方、パーザコンビネータは内部DSLのアプローチです。ホスト側のプログラミング言語(ここではScala)を使って、問題領域に特化した言語を内部に作り上げます。ホスト言語の構文を使ってパーザを組み上げるので、型チェックや補完などの機能をそのまま使えますし、そのプログラミング言語を知っていれば楽に利用することができます。

また、パーザコンビネータでは、パーザの組み合わせ方を定義することで、より高度な部品化を促進することができる柔軟性もあります。パーザジェネレータは、解析速度などの面でメリットがありますが、特に試行錯誤してパーザを組み上げていく段階において、パーザコンビネータのメリットが生きてくると思っています。

というわけで、この連載記事(?)では、いくつかに分けて、 パーザコンビネータを自作 するにはどうすればいいか解説してみたいと思います。正直、あまりパーザコンビネータに向いていないのですが、多くの人に読んでもらうために、言語としてはJavaを採用します。Java 8のラムダ式とインタフェースのデフォルトメソッドを使うので、それが前提になっていることは注意してください。

準備作業( Parser )

まず、 Parser 型を定義してやる必要があります。 Parser は入力文字列を受け取って、解析結果 ParseResult を返すこととします。すると、それぞれの定義は次のようになります。

public interface Parser<T> {
    ParseResult<T> invoke(String input);
}
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<T> の定義は特に問題ないと思います。 invoke メソッドを文字列を引数にとって呼び出し、 ParseResult<T>
型の値を返します。

ParseResult<T> の定義はちょっと長いので、解説します。 ParseResult<T> は構文解析の結果を格納するための型で、サブクラスとして、 ParseResult.Success<T>ParseResult.Failure<T> を持ちます。名前の通り、前者が成功した場合、後者が失敗した場合を表します。 map は解析結果の値を加工するためのもので、それぞれの内部動作は定義をみるとわかると思います。 Success<T>Failure<T> は immutable な値で、また、特に後で内部表現を変える予定もないので、手抜きのために public final にしてあります。

ここまでで準備作業は完了です。

文字列を読み取るパーザ

さて、準備作業はできましたが、まだパーザの実体がないため、何もパーズすることができません。最初に、ある文字列のプレフィクスにマッチするかどうかを判定して、マッチしたらその文字列を値とする Success を、そうでなければ失敗をあらわす Failure を返すものとします。このようなパーザ StringParser の定義は次のようになります:

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

パーザコンビネータライブラリでは、パーザを関数と見立てることが多いのですが、Javaはオブジェクトが第一級の値であっても関数は第一級の値ではないので、オブジェクトをパーザと見立てることにします。文字列を読み取るパーザは、読み取る対象の文字列をコンストラクタ引数で受け取り、フィールドに格納します。

実際にパーズを実行するコードは invoke の中にありますが、入力が対象文字列をプレフィクスとしているかどうかを判定して、そうであれば Success 、そうでなければ Failure を返すだけの簡単なコードです。

さて、これを使うときに毎回 new StringParser("Hello, World!") と書くのは面倒なので、短く書けるようにします。幸い、Java 8からインタフェースがデフォルトメソッドおよびstaticメソッドを持てるようになったので、 Parser インタフェースに加えます。

public interface Parser<T> {
    ParseResult<T> invoke(String input);
        static Parser<String> string(String literal) {
        return new StringParser(literal);
    }
}

使うのは簡単で、

public class Main {
  public static void main(String[] args) {
    ParseResult<String> result = Parser.string("Hello, World!").invoke("Hello, World!");
    System.out.println((ParseResult.Success<String>)result).value);
  }
}

このようにするだけです。ここでは、パーズが成功したものとして決め打ちしていますが、実際には解析が成功したかどうかで分岐が必要ですが、ともあれ、最初のステップはこれでできたわけです。

次回以降は、他の、基本的なメソッドの定義や、 ParseResult<T> に定義するその他のメソッドについて説明します。