kmizuの日記

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

Javaで作るPEGパーザコンビネータ

パーサジェネレータを作る簡単さで言うと、 PEG <<<< LL(1) <<<< LALR(1) くらいな感じのイメージです。

http://twitter.com/kmizu/statuses/1183248403

なんて偉そうなこと書いたので、(パーザジェネレータじゃないけど)PEGパーザコンビネータを実際にJavaで書いてみた。文字クラスを除くPEGの機能のほぼフルセットをサポートするのを目標に書いたので、やや煩雑になっている。

package jp.gr.java_conf.mizu;
import java.util.*;
import static java.lang.String.format;
public class PEGParserCombinators {
  public static final class Pair<A, B> {
    public final A _1;
    public final B _2;
    public Pair(A _1, B _2) { this._1 = _1; this._2 = _2; }
    public String toString() { return format("(%s, %s)", _1, _2); }
  }
  public static final class ParseResult<T> {
    public final T value;
    public final String rest;
    public ParseResult(T value, String rest) { 
      this.value = value; this.rest = rest;
    }
    public String toString() { 
      return format("(value = %s, rest = %s)", value, rest); 
    }
  }
  public interface Parser<T> { ParseResult<? extends T> parse(String input); }
  public interface Transformer<A, B> { B apply(A param); }
  public static class ParserProxy<T> implements Parser<T> {
    public Parser<? extends T> target;
    public ParserProxy(Parser<? extends T> target) { this.target = target; }
    public ParseResult<? extends T> parse(String input) {
      return target.parse(input);
    }
  }
  public static <T> ParserProxy<T> proxy(Parser<T> p) {
    return new ParserProxy<T>(p);
  }
  public static Parser<String> string(final String param) {
    return new Parser<String> () {
      public ParseResult<? extends String> parse(String input) {
        return input.startsWith(param) ?
          new ParseResult<String>(param, input.substring(param.length())) : null;
      }
    };
  }
  public static Parser<String> any = new Parser<String> () {
    public ParseResult<? extends String> parse(String input) {
      return input.length() > 0 ?
        new ParseResult<String>(input.substring(0, 1), input.substring(1)) : null;
    }
  };
  public static <A> Parser<A> or(final Parser<? extends A> p1, final Parser<? extends A> p2) {
    return new Parser<A>() {
      public ParseResult<? extends A> parse(String input) {
        ParseResult<? extends A> r1 = p1.parse(input);
        if(r1 != null) return r1; 
        return p2.parse(input);
      }
    };
  }
  public static <A, B> Parser<Pair<A, B>> seq(final Parser<A> p1, final Parser<B> p2) {
    return new Parser<Pair<A, B>>() {
      public ParseResult<? extends Pair<A, B>> parse(String input) {
        ParseResult<? extends A> r1 = p1.parse(input);
        if(r1 == null) return null;
        ParseResult<? extends B> r2 = p2.parse(r1.rest);
        if(r2 == null) return null;
        return new ParseResult<Pair<A, B>>(
          new Pair<A, B>(r1.value, r2.value), r2.rest
        );
      }
    };
  }
  public static <A> Parser<List<A>> seqN(final Parser<? extends A>... ps) {
    return new Parser<List<A>>() {
      public ParseResult<? extends List<A>> parse(String input) {
        List<A> rs = new ArrayList<A>();
        for(Parser<? extends A> p:ps) {
          ParseResult<? extends A> r = p.parse(input);
          if(r == null) return null;
          rs.add(r.value);
          input = r.rest;
        }
        return new ParseResult<List<A>>(rs, input);
      }
    };
  }
  public static <T> Parser<Void> not(final Parser<T> p) {
    return new Parser<Void>() {
      public ParseResult<? extends Void> parse(String input) {
        ParseResult<? extends T> r = p.parse(input);
        return r == null ? new ParseResult<Void>(null, input) : null;
      }
    };
  }
  public static <T> Parser<Void> and(final Parser<T> p) { 
    return not(not(p)); 
  }
  public static <T> Parser<T> opt(final Parser<T> p) {
    return or(
      p, 
      apply(string(""), new Transformer<String, T>() {
        public T apply(String param) { return null; }
      })
    );
  }
  public static <A> Parser<List<A>> rep1(final Parser<A> p) {
    return apply(seq(p, rep(p)), new Transformer<Pair<A, List<A>>, List<A>>() {
      public List<A> apply(Pair<A, List<A>> param) {
        param._2.add(param._1);
        return param._2;
      }
    });
  }
  public static <A> Parser<List<A>> rep(final Parser<A> p) {
    return new Parser<List<A>>() {
      public ParseResult<? extends List<A>> parse(String input) {
        List<A> rs = new ArrayList<A>();
        while(true) {
          ParseResult<? extends A> r = p.parse(input);
          if(r == null) return new ParseResult<List<A>>(rs, input);
          rs.add(r.value);
          input = r.rest;
        }
      }
    };
  }
  public static <A, B> Parser<B> apply(final Parser<A> p, final Transformer<A, B> t) {
    return new Parser<B>() {
      public ParseResult<? extends B> parse(String input) {
        ParseResult<? extends A> r = p.parse(input);
        return r == null ? null : new ParseResult<B>(t.apply(r.value), r.rest);
      }
    };
  }
}

使い方は以下のような感じ。ここでは、文脈自由文法では表現できない、a^n b^n c^nをPEGで表現したものを記述している。

import static jp.gr.java_conf.mizu.PEGParserCombinators.*;
public class User {
  static ParserProxy<Object> S = proxy(null), A = proxy(null), B = proxy(null);
  static {
    S.target = seqN(
                 and(seq(A, not(string("b")))),
                 rep1(string("a")),
                 B,
                 not(string("c"))
               );
    A.target = seqN(string("a"), opt(A), string("b"));
    B.target = seqN(string("b"), opt(B), string("c"));
  }
  public static void main(String[] args) {
    System.out.println(S.parse(args[0]));
  }
}

これらのプログラムをコンパイルして、

> java User aaabbbccc

とすると、パーズに成功して、

(value = [null, [a, a, a], [b, [b, [b, null, c], c], c], null], rest = )

のように結果が返ってくる。一方、

> java User aaabbbcc

のように文法にマッチしない入力を与えると、パーズに失敗して、nullが返ってくる。


しかし、やはりJavaでパーザコンビネータ作るのはめんどい。無名クラス使いまくりだし。