パーサジェネレータを作る簡単さで言うと、 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が返ってくる。