PEGParserCombinators
2016/04/30 ARRAYとOBJECTで要素０のとき未対応だったので修正しました。
kmizuさんがJava版のパーサコンビネータを作っていたのでそれを使ってみた。
サンプルとして、JSONのパーサを作ってみた。
以下は、kmizuさんのパーサコンビネータを改造したもの。
package jp.gr.java_conf.mizu; import java.util.*; import java.util.regex.Matcher; import java.util.regex.Pattern; import static java.lang.String.format; /** * kmizuさんのPEGParserCombinatorsを改造した。 * ・整形し、コメントを入れた。 * ・正規表現を使って解析するパーサregex()を追加した。 * ・repsec(), rep1sep()を追加した。 * ・or()を可変長引数にした。 * @see http://kmizu.hatenablog.com/entry/20090225/1235576560 */ public class PEGParserCombinators2 { /** ペア */ 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> regex(final String regex) { return new Parser<String>() { Pattern p = Pattern.compile(regex); public ParseResult<? extends String> parse(String input) { Matcher m = p.matcher(input); if (m.lookingAt()) { return new ParseResult<String>(m.group(), input.substring(m.end())); } return 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> Parser<A> or(final Parser<? extends A>... ps) { return new Parser<A>() { public ParseResult<? extends A> parse(String input) { for (Parser<? extends A> p: ps) { ParseResult<? extends A> r = p.parse(input); if (r != null) return r; } return null; // いずれも成功しなかった } }; } /** ２つのパーサを結合 */ 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) { // p (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> Parser<List<A>> repsep(final Parser<A> p, final Parser<String> sep) { return new Parser<List<A>>() { public ParseResult<? extends List<A>> parse(String input) { List<A> rs = new ArrayList<A>(); ParseResult<? extends A> r = p.parse(input); if (r != null) { rs.add(r.value); input = r.rest; while (true) { ParseResult<? extends String> s = sep.parse(input); if (s == null) break; input = s.rest; r = p.parse(input); if (r == null) return null;//throw new Exception("セパレータの次の要素が不正"); rs.add(r.value); input = r.rest; } } return new ParseResult<List<A>>(rs, input); } }; } /** セパレータで区切られた要素のリストを解析する。 */ public static <A> Parser<List<A>> rep1sep(final Parser<A> p, final Parser<String> sep) { return new Parser<List<A>>() { public ParseResult<? extends List<A>> parse(String input) { List<A> rs = new ArrayList<A>(); ParseResult<? extends A> r = p.parse(input); if (r == null) return null; rs.add(r.value); input = r.rest; while (true) { ParseResult<? extends String> s = sep.parse(input); if (s == null) break; input = s.rest; r = p.parse(input); if (r == null) return null; // throw new Exception("セパレータの次の要素が不正"); rs.add(r.value); input = r.rest; } return new ParseResult<List<A>>(rs, input); } }; } /** 「解析後の結果を好みの構造に変換する」というパーサを作る */ 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); } }; } }
JSONのパーサ。
正規表現が使えるので、数値などの定義が簡単です。
「空白文字を読み飛ばす」処理をどう実装すべきか悩みました。
とりあえず、プリミティブな要素の前にスキップするようにしました。
ParserProxyとParserの使い分けですが、JSONのVALUEはOBJECTの要素でもあり、
OBJECT自体もVALUEになります。定義がループしています。
そういうときはParserProxyを使う必要があります。
定義済みの構文だけで定義できる場合はParserProxyでなくてもかまいません。
わからなければ、全部ParserProxyにしておけばおｋ。
package jp.gr.java_conf.mizu; import static jp.gr.java_conf.mizu.PEGParserCombinators2.*; import java.util.List; /** * JSONのパーサ * @see http://www.json.org/json-ja.html */ public class TestJson2 { static Parser<String> WHITESPACE = regex("\\s*"); // 空白文字 /** 空白文字を読み飛ばしてから解析する。 */ public static <A> Parser<A> sp(final Parser<A> p) { return new Parser<A>() { public ParseResult<? extends A> parse(String input) { return p.parse(WHITESPACE.parse(input).rest); } }; } /** 両側のカッコを無視する。実はカッコ以外でも使える。 */ public static <A> Parser<A> ignoreBracket(final Parser<String> bra, final Parser<A> p, final Parser<String> ket) { return apply(seqN(bra, p, ket), list -> (A) list.get(1)); } // 構文の定義。プリミティブな要素は先頭の空白文字を読み飛ばすようにする。 static Parser<Double> NUMBER = apply( sp(regex("-?(0|[1-9][0-9]*)(\\.[0-9]+)?([eE][+-]?[0-9]+)?")), // 数値。この正規表現は正しい。 s -> Double.parseDouble(s)); // 文字列。この正規表現はあってないかも？？？ static Parser<String> STRING = sp(regex("\""+"([^\"\\p{Cntrl}\\\\]|\\\\[\\\\/bfnrt]|\\\\u[a-fA-F0-9]{4})*"+"\"")); // 文字列 //static Parser<String> IDENT = regex("[a-zA-Z_]\\w*"); // 識別子 static Parser<Boolean> TRUE = apply(sp(string("true")), s -> Boolean.TRUE); static Parser<Boolean> FALSE = apply(sp(string("false")), s -> Boolean.FALSE); static Parser<Object> NULL = apply(sp(string("null")), s -> null); // 構文の定義。合成した構文は再帰になって定義できないことがあるからProxyで定義。 static ParserProxy<Object> VALUE = proxy(null); static Parser<Pair<String,Object>> MEMBER = apply( seqN(STRING, sp(string(":")), VALUE), list -> { String key = (String) list.get(0); Object value = list.get(2); return new Pair<String, Object>(key, value); }); static Parser<List<Pair<String,Object>>> OBJECT = ignoreBracket( sp(string("{")), repsep(MEMBER, sp(string(","))), sp(string("}"))); static Parser<List<Object>> ARRAY = ignoreBracket( sp(string("[")), repsep(VALUE, sp(string(","))), sp(string("]"))); static { /** value <- string / number / object / array / true / false / null */ VALUE.target = or(STRING, NUMBER, OBJECT, ARRAY, TRUE, FALSE, NULL); } public static void main(String[] args) { System.out.println(NUMBER.parse("1024")); // (value = 1024, rest = ) System.out.println(NUMBER.parse("3.14159")); // (value = 3, rest = .14159) System.out.println(NUMBER.parse("-255")); // (value = -255, rest = ) System.out.println(WHITESPACE.parse(" \t\r\n123")); // (value = " \t\r\n", rest = 123) System.out.println(WHITESPACE.parse("123")); // (value = , rest = 123) System.out.println(TRUE.parse(" true ")); // (value = true, rest = ) System.out.println(TRUE.parse(" truee")); // (value = true, rest = e) うーん System.out.println(FALSE.parse(" false")); // (value = false, rest = ) System.out.println(NULL.parse(" null")); // (value = null, rest = ) System.out.println(MEMBER.parse(" \"Key\" : 999,")); // (value = ("Key", 999), rest = ,) System.out.println(MEMBER.parse("\"Key\":999,")); // (value = ("Key", 999), rest = ,) System.out.println(MEMBER.parse("\"Key\":999,")); // (value = ("Key", 999), rest = ,) System.out.println(ARRAY.parse("[1,1,2,3,5,8,13]")); // (value = [1.0, 1.0, 2.0, 3.0, 5.0, 8.0, 13.0], rest = ) System.out.println(ARRAY.parse("[ ]")); // (value = [], rest = ) System.out.println(OBJECT.parse("{\"apple\":\"りんご\",\"boat\":\"ふね\"}")); // (value = [("apple", "りんご"), ("boat", "ふね")], rest = ) System.out.println(OBJECT.parse("{ }")); // (value = [], rest = ) System.out.println(VALUE.parse("true")); // (value = true, rest = ) System.out.println(VALUE.parse("3.14")); // (value = 3.14, rest = ) System.out.println(VALUE.parse("\"文字列\"")); // (value = "文字列", rest = ) System.out.println(VALUE.parse("[1,1,2,3,5,8,13]")); // (value = [1.0, 1.0, 2.0, 3.0, 5.0, 8.0, 13.0], rest = ) System.out.println(VALUE.parse("{\"apple\":\"りんご\",\"boat\":\"ふね\"}")); // (value = [("apple", "りんご"), ("boat", "ふね")], rest = ) String source = " {\n\t\"address book\": {\n"+ "\t\t\"name\":\"John Smith\",\n"+ "\"address\" : {\n"+ "\t\t\"street\":\"10 Market Street\",\n"+ "\t\t\"city\": \"San Francisco, CA\","+ "\t\t\"zip\" : 94111\n"+ "\t},"+ "\"phone numbers\": [\"408 338-4238\",\"408 111-6832\"]\n"+ "}\n"+ "}"; System.out.println(VALUE.parse(source)); } }
これ、解析中に構文エラーがあったら、例外とかにならずにnullを返すだけです。
どこが間違っているのかわかりません。
機械が吐くデータならこのパーサで問題ありませんが、人間が書くソースを読み込むのであればイマイチ。
