c++で関数型のパーサー作成

実用性は置いといてc++でmap, flatMapを利用したパーサーコンビネーターを作成していこうと思います。c++ではLL1パーサーを実装するのが相性が良さそうだと思うのですが、今回はパーサーコンビネータを使うのでPEGパーサーのようになるので書きやすいかどうか確認していきたいです。
実装は以下になります。

github.com

以下のscalaで実装されたパーサコンビネータを参考にしています。

github.com

概要

まずパーサークラスについて、以下のように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);
}