c++で関数型のパーサー作成
実用性は置いといてc++でmap, flatMapを利用したパーサーコンビネーターを作成していこうと思います。c++ではLL1パーサーを実装するのが相性が良さそうだと思うのですが、今回はパーサーコンビネータを使うのでPEGパーサーのようになるので書きやすいかどうか確認していきたいです。
実装は以下になります。
以下のscalaで実装されたパーサコンビネータを参考にしています。
概要
まずパーサークラスについて、以下のようにindexを受け取ったらパース結果を返す型として定義しておきます。
template <typename T> class ParseSuccess { public: int index_; T value_; ParseSuccess(int index, T value) : index_(index), value_(value) {} }; class ParseFailure { public: int index_; std::string message_; ParseFailure(int index, std::string message) : index_(index), message_(message) {} }; template <typename T> using ParseResult = std::variant<ParseSuccess<T>, ParseFailure>; template <typename F> using Parser = std::function<ParseResult<F>(int index)>
それからパーサーを利用し、パース結果を返すクラスとして以下のように定義しておきます。文字列はinput_でクラス内で保持し、parseの関数を呼び出すと言う流れです。
template <typename T> class CCombinator { public: Parser<T> root_parser_; std::string input_; CCombinator(Parser<T> root_parser) : root_parser_(root_parser), input_("") {} Result<T> parse(std::string input) { input_ = input; auto parse_result = root_parser_(0); if (std::holds_alternative<ParseSuccess<T>>(parse_result)) { auto p_success = std::get<ParseSuccess<T>>(parse_result); return Success(p_success.value_); } else { auto p_failure = std::get<ParseFailure>(parse_result); return Failure(Location{0, p_failure.index_}, p_failure.message_); } } ~省略~
実際に利用する際は以下のようにCCombinatorを拡張して利用しています。
class ParseAAAorBBB : public CCombinator<std::string> { public: explicit ParseAAAorBBB() : CCombinator<std::string>(gen_parser()) {} Parser<std::string> gen_parser(void) { auto p1 = pstr("aaa"); auto p2 = pstr("bbb"); return orp(p1, p2); } }; TEST(ccombinator, orp) { auto scombinator = ParseAAAorBBB(); auto result = scombinator.parse("bbb"); ASSERT_TRUE(std::holds_alternative<Success<std::string>>(result)); auto result_success = std::get<Success<std::string>>(result); std::cout << result_success.value_ << std::endl; }
基本的なパーサー
文字列パーサー
基本的なパーサーはCCombinatorに追加していきます。文字列のパーサーについては以下のように文字列を受け取ったらパース結果を吐き出す関数を返します。
Parser<std::string> pstr(std::string literal) { return [this, literal](int index) { std::string input = input_.substr(index); int len = literal.size(); if (input.size() >= len && input.substr(0, len) == literal) { return static_cast<ParseResult<std::string>>( ParseSuccess(index + len, literal)); } else { return static_cast<ParseResult<std::string>>( ParseFailure(index, "expect " + literal)); } }; }
ORパーサー
ORパーサーについてはパーサーを2つ受け取ってパースに成功した方を有効にするパーサーを返します。
template <typename V> Parser<V> orp(Parser<V> parser1, Parser<V> parser2) { return [this, parser1, parser2](int index) { auto parse_result1 = parser1(index); if (std::holds_alternative<ParseSuccess<V>>(parse_result1)) { return static_cast<ParseResult<V>>( std::get<ParseSuccess<V>>(parse_result1)); } else { auto parse_result2 = parser2(index); if (std::holds_alternative<ParseSuccess<V>>(parse_result2)) { return static_cast<ParseResult<V>>( std::get<ParseSuccess<V>>(parse_result2)); } else { auto p_failure = std::get<ParseFailure>(parse_result2); return static_cast<ParseResult<V>>( ParseFailure(p_failure.index_, p_failure.message_)); } } }; }
ANDパーサー
ANDパーサーではパーサーを2つ受け取って順番に2つのパーサーを実行するパーサーを返します。
template <typename V, typename U> Parser<std::tuple<V, U>> andp(Parser<V> parser1, Parser<U> parser2) { return [this, parser1, parser2](int index) { auto parse_result1 = parser1(index); if (std::holds_alternative<ParseSuccess<V>>(parse_result1)) { auto parse_success1 = std::get<ParseSuccess<V>>(parse_result1); auto parse_result2 = parser2(parse_success1.index_); if (std::holds_alternative<ParseSuccess<V>>(parse_result2)) { auto parse_success2 = std::get<ParseSuccess<U>>(parse_result2); return static_cast<ParseResult<std::tuple<V, U>>>(ParseSuccess( parse_success2.index_, std::tuple<V, U>(parse_success1.value_, parse_success2.value_))); } else { auto p_failure2 = std::get<ParseFailure>(parse_result2); return static_cast<ParseResult<std::tuple<V, U>>>( ParseFailure(p_failure2.index_, p_failure2.message_)); } } else { auto p_failure1 = std::get<ParseFailure>(parse_result1); return static_cast<ParseResult<std::tuple<V, U>>>( ParseFailure(p_failure1.index_, p_failure1.message_)); } }; }
繰り返しパーサー
パーサーを受け取って繰り返しパースを実行する(0回以上パース成功で成功とする)パーサーとして以下のように定義しています。
template <typename V> Parser<std::vector<V>> repeat0(Parser<V> parser) { return [this, parser](int index) { std::vector<V> value; while (true) { auto parse_result = parser(index); if (std::holds_alternative<ParseSuccess<V>>(parse_result)) { auto parse_success = std::get<ParseSuccess<V>>(parse_result); value.push_back(parse_success.value_); if (index == parse_success.index_) { break; } else { index = parse_success.index_; } } else { break; } } return static_cast<ParseResult<std::vector<V>>>( ParseSuccess(index, value)); }; }
関数型パーサー
map
パース結果の値を変換するmap処理は以下のようにtemplateを使って実装します。
template <typename S, typename V> Parser<V> map(Parser<S> parser, std::function<V(S)> f) { return [this, parser, f](int index) { auto parse_result = parser(index); if (std::holds_alternative<ParseSuccess<S>>(parse_result)) { auto p_success = std::get<ParseSuccess<S>>(parse_result); return static_cast<ParseResult<V>>( ParseSuccess(p_success.index_, f(p_success.value_))); } else { auto p_failure = std::get<ParseFailure>(parse_result); return static_cast<ParseResult<V>>( ParseFailure(p_failure.index_, p_failure.message_)); } }; }
flatMap
それからflatMapを以下のように実装します。
template <typename S, typename V> Parser<V> flatMap(Parser<S> parser, std::function<Parser<V>(S)> f) { return [this, parser, f](int index) { auto parse_result = parser(index); if (std::holds_alternative<ParseSuccess<S>>(parse_result)) { auto p_success = std::get<ParseSuccess<S>>(parse_result); return static_cast<ParseResult<V>>( f(p_success.value_)(p_success.index_)); } else { auto p_failure = std::get<ParseFailure>(parse_result); return static_cast<ParseResult<V>>( ParseFailure(p_failure.index_, p_failure.message_)); } }; }
使用感
jsonの文字列をパースする場合、参考元のscalaの実装の場合は以下のように簡単にかけています。
lazy val string: Parser[String] = rule{for { _ <- $("\"") contents <- ($("\\") ~ any ^^ { case _ ~ ch => escape(ch).toString} | except('"')).* _ <- $("\"").l("double quote") _ <- DefaultSpace.* } yield contents.mkString} lazy val jstring: Parser[JValue] = rule(string ^^ {v => JString(v)})
エスケープ処理が含まれていて複雑かもしれないので、除外すると以下のようになります。
lazy val string: Parser[String] = rule{for { _ <- $("\"") contents <- except('"').* _ <- $("\"").l("double quote") _ <- DefaultSpace.* } yield contents.mkString} lazy val jstring: Parser[JValue] = rule(string ^^ {v => JString(v)})
今回のc++の実装では以下のようになりましたが、for式のようなシンタックスシュガーがないので直接map, flatMapを呼び出すしかないので以下のようになりました。flatMapを呼び出すための関数を定義しておくしかないので、大分わかりづらくなることが分かります。
Parser<JString*> JsonCombinator::gen_jstring_prser(void) { auto p1 = pstr("\""); auto p2 = repeat0(except('"')); std::function<Parser<std::string>(std::string)> f1 = [&, p2](std::string a) { std::function<std::string(std::vector<std::string>)> f = [](std::vector<std::string> list) { std::string ret = ""; for (std::string b : list) { ret += b; } return ret; }; return map(p2, f); }; std::function<Parser<std::string>(std::string)> f2 = [&, p1](std::string a) { std::function<std::string(std::string)> f = [a](std::string b) { return a; }; return map(p1, f); }; std::function<JString*(std::string)> f3 = [](std::string a) { return new JString(std::move(a)); }; return map(flatMap(flatMap(p1, f1), f2), f3); }