C++ 自制 Parser Combinator

Posted on Edited on In Disqus:

写在最前

自制一个 C++ 的 Parser Combinator，并用它写一个 json 的 parser，目标是代码尽可能简洁且便于理解（换句话说，就是一个玩具）。文章分为几个阶段，每一阶段后都有相应的代码，方便渐进式学习。

前置知识：基本的模板元编程，基本的 STL 用法，对 C++17 和 C++20 的特性有一些了解。但是如果你愿意查阅 cppreference，那么不需要任何前置知识了。

简单的字符组合

接收字符串的基本 Parser

首先定义 Parser 类型和 ParseResult 的类型。

Parser 的结果可能成功可能失败，如果成功的话会得到一个值，所以就借用 std::optional，如果空就代表失败。

Parser 干的事情就是接受一个字符串并消耗掉它的若干字符，然后给出一个输出。它本质上是一个函数，输入是一个可能被修改的字符串，这里就用 std::string_view& 了，所以它的类型就是 std::function<ParseResult<T>(std::string_view&)>。

1
2
3
4
5
template<typename T>
using ParseResult = std::optional<T>;

template<typename T>
using Parser = std::function<ParseResult<T>(std::string_view&)>;

最简单的就是接收一个字符串：

1
2
3
4
5
6
7
8
9
10
Parser<std::string> literal(const std::string& s) {
  return [=](std::string_view& in)->ParseResult<std::string> {
    if (in.starts_with(s)) {
      in.remove_prefix(s.length());
      return s;
    } else {
      return {};
    }
  };
}

不用测试就能看出如此简陋的功能应该没什么问题。

组合子 - seq

光有这个还没什么用，接下来就来添加一个最简单的 Combinator，也就是连接函数 seq。目标是 literal("a") & literal("b") 能接受 "ab" 同时返回一个 ("a", "b") 的 tuple。之所以是 tuple，因为参与连接的 Parser 类型不一定相同，对于 Parser<T1>, Parser<T2>, ... 连接的结果是 Parser<std::tuple<T1, T2, ...>>。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Parser<std::tuple<>> seq() {
  return [](std::string_view&)->ParseResult<std::tuple<>> {
    return std::make_tuple();
  };
}

template<typename T, typename... Ts, typename R = std::tuple<T, Ts...>>
Parser<R> seq(const Parser<T>& p, const Parser<Ts>& ...ps) {
  return [=](std::string_view& in)->ParseResult<R> {
    auto v = p(in);
    if (!v) return {};
    auto vs = seq(ps...)(in);
    if (!vs) return {};
    return std::tuple_cat(std::make_tuple(v.value()), vs.value());
  };
}

测试代码

1
2
3
4
5
6
auto a = literal("a"), b = literal("b");
auto ab = seq(a, b);
std::string_view in{"ab"};
auto [x, y] = ab(in).value();
std::cout << x << ' ' << y << std::endl;
// output: a b

注：为什么不弄成二元组合子，重载 &，就能搞出更加自然的 Parser<T1> & Parser<T2> & ... 呢？因为有点麻烦。考虑一下类型，最左边的 & 的签名类似于 (Parser<T1>, Parser<T2>) ⇒ Parser<(T1, T2)>，其他的 & 的签名类似于 (Parser<(Ts...)>, Parser<T>) ⇒ Parser<(Ts..., T)>，有一些需要特殊处理的东西。

CHECKPOINT 1

扩展 optional 并改写

众所周知，optional 是一个 monad，但是 STL 里提供的方法有点少，所以我对其做了一些扩展（见附录），然后后一个 seq 函数可以写成这样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// change ParseResult from std::optional to optional (see appendix for definition)
template<typename T>
using ParseResult = optional<T>; 

template<typename T, typename... Ts, typename R = std::tuple<T, Ts...>>
Parser<R> seq(const Parser<T>& p, const Parser<Ts>& ...ps) {
  return [=](std::string_view& in)->ParseResult<R> {
    return p(in).flat_map([&](auto v) {
      return seq(ps...)(in).map([&](auto vs) { 
        return std::tuple_cat(std::make_tuple(v), vs); 
      });
    });
  };
}

由于 C++ lambda 语法限制，所以似乎更难看了，如果有很甜的语法糖就好了（做梦中）。

CHECKPOINT 2

组合子 - alt

alt 是蛋疼的开始，由于 alt 的结果是若干类型之一，所以用 std::variant<T1, T2, ...> 作为结果。但是把一个 std::variant 和一个类型不一定在内的元素组合起来并没有那么容易。具体见附录中 std::variant 的讨论。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
template<typename T>
Parser<T> attempt(const Parser<T>& p) {
  return [=](std::string_view& in)->ParseResult<T> {
    auto in_bak = in;
    auto v = p(in);
    if (!v) in = in_bak;
    return v;
  };
}

namespace detail {
  template<typename R>
  Parser<R> alt() {
    return [](std::string_view&)->ParseResult<R> {
      return {};
    };
  }

  template<typename R, typename T, typename... Ts>
  Parser<R> alt(const Parser<T>& p, const Parser<Ts>& ...ps) {
    return [=](std::string_view& in)->ParseResult<R> {
      return attempt(p)(in).map([](auto v){ return R{v}; })
          .or_else(alt<R>(ps...)(in));
    };
  }
}

template<typename... Ts>
auto alt(const Parser<Ts>& ...ps) {
  return detail::alt<unique_variant_t<Ts...>>(ps...);
}

int main() {
  auto a = literal("a"), b = literal("b");
  auto ab_ba = alt(seq(a, b), seq(a, a));
  std::string_view in{"aab"};
  auto [x, y] = std::get<std::tuple<std::string, std::string>>(ab_ba(in).value());
  std::cout << x << ' ' << y << std::endl; // a a
}

注意 attempt 的存在，因为对于 alt，单个 Parser 失败时需要回溯。如果没有的话，对于代码中的例子，第一个可选项 ab 会把 aab 中的第一个 a 吃掉，然后再匹配 aa 时就会失败。

测试代码中的 get 非常恶心，所以最好处理一下，如果 variant 中只有一种类型，那么直接返回这个类型，而不是 variant。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
namespace detail {
	template<typename... Ts>
  auto flat(const std::variant<Ts...>& v) {
    if constexpr (sizeof...(Ts) == 1) {
      return std::get<0>(v);
    } else {
      return v;
    }
  }
}

template<typename F, typename T, typename R = std::invoke_result_t<F, T>>
Parser<R> operator % (const Parser<T>& p, F&& f) {
  return [=](std::string_view& in)->ParseResult<R> {
    return p(in).map([&](T v) { return f(v); });
  };
}

#define RESOLVE_OVERLOAD(...) \\
	[](auto&&...args)->decltype(auto){return __VA_ARGS__(std::forward<decltype(args)>(args)...);}

template<typename... Ts>
auto alt(const Parser<Ts>& ...ps) {
  return detail::alt<unique_variant_t<Ts...>>(ps...) % RESOLVE_OVERLOAD(detail::flat);
}

int main() {
  auto a = literal("a"), b = literal("b");
  auto ab_ba = alt(seq(a, b), seq(a, a));
  std::string_view in{"aab"};
  auto [x, y] = ab_ba(in).value();
  std::cout << x << ' ' << y << std::endl;
}

引入了一个很重要的东西，就是运算符 %（只是为了写起来方便），其实就是 map，但是这次是对于 Parser 的 map 而不是 optional 的 map。另外为什么要有这个恶心的 RESOLVE_OVERLOAD，在我的另一篇博客中有讲，这里就省略了。可以看到，对于相同类型的 alt，用户就不会拿到繁琐的 std::variant 作为结果了，std::variant 只会在必要的时候出现。

CHECKPOINT 3

四则运算

首先是 number 的 parser，为此加了 many 和 ch，many 就是尽可能多的应用 parser，ch 就是接受一个符合特定条件的字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
template<typename T, typename R = std::vector<T>>
Parser<R> many(const Parser<T>& p) {
  return [=](std::string_view& in)->ParseResult<R> {
    R r;
    ParseResult<T> v;
    while ((v = attempt(p)(in))) {
      r.emplace_back(v.value());
    }
    return r;
  };
}

template<typename R = char>
Parser<R> ch(const std::function<bool(char)>& f) {
  return [=](std::string_view& in)->ParseResult<R> {
    if (in.empty() || !f(in[0])) return {};
    char c = in[0];
    in.remove_prefix(1);
    return c;
  };
}

int main() {
  auto number = many(ch(isdigit)) % [](std::vector<char> v) {
    int r = 0;
    for (char c: v) r = r * 10 + c - '0';
    return r;
  };
  std::string_view in = "123";
  std::cout << number(in).value() << std::endl;
}

然后就能搞表达式了（得先消除左递归）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
template<typename T>
Parser<T> lazy(const Parser<T>& p) {
  return [p_addr = &p](std::string_view& in)->ParseResult<T> {
    return (*p_addr)(in);
  };
}

template<typename F, typename... Ts, typename R = std::invoke_result_t<F, Ts...>>
Parser<R> operator % (const Parser<std::tuple<Ts...>>& p, F&& f) {
  return [=](std::string_view& in)->ParseResult<R> {
    return p(in).map([&](auto v) { return std::apply(f, v); });
  };
}

int main() {
  auto eval = [](int x, const std::vector<std::tuple<std::string, int>>& v) {
    for (auto [op, y]: v) {
      if (op == "*") x *= y;
      if (op == "/") x /= y;
      if (op == "+") x += y;
      if (op == "-") x -= y;
    }
    return x;
  };

  Parser<int> exp;
  Parser<int> number = many(ch(isdigit)) % [](std::vector<char> v) {
    int r = 0;
    for (char c: v) r = r * 10 + c - '0';
    return r;
  };

  Parser<int> factor = alt(
      seq(literal("("), lazy(exp), literal(")")) % [](auto x){ return std::get<1>(x); },
      number
  );

  Parser<int> term = seq(
    factor,
    many(seq(
      alt(literal("*"), literal("/")),
      factor))) % eval;
  
  exp = seq(
      term,
      many(seq(
          alt(literal("+"), literal("-")),
          term))) % eval;

  std::string_view in = "4+(1+2)*3+100+100";
  std::cout << exp(in).value() << std::endl;
  std::cout << "Remain: " << in << std::endl;
}

又引入了一个新的函数 lazy，因为 expression 是递归定义的，而且为了方便，所有 parser 都是按值捕获的，然后运行到 factor 时发现 exp 没定义就炸了。因此就提前声明 exp，并用 lazy 使它捕获一个 exp 的地址用于运行时计算。

顺便重载了运算符 %，方便应用于 Parser<std::tuple<...>> 也就是 seq 的返回值，这样就不用一个一个 std::get 了。

那这样计算器就完成了，但还有一个让人有些不爽的问题，表达式里不允许有空格。

CHECKPOINT 4

Json 解析器

为了证明这些东西是能用的，所以就写一个 Json Parser 吧。最后搞出来的 Json 可能在 parse 浮点数时漏了一点情况（主要是网上找了几个 json 浮点数 EBNF，感觉都不大对），但是目的是展示自制的 parser combinator 库是可以用的，所以正确性也无伤大雅。另外为了简化，整数和浮点数是存成了字符串。

首先把拆分了一下文件，全写在一个文件里显得有些杂乱了。

Json 这个东西在语法上是递归的，而 std:variant 本身是不能递归自己的（因为它不是在堆上分配内存的），但是可以套一层 smart pointer（因为支持用 incomplete type 定义），所以弄出来这样一个类型。

1
2
3
4
5
6
7
struct Json;
using JsonPtr = std::shared_ptr<Json>;
using JsonV = std::variant<std::string, std::vector<JsonPtr>, std::vector<std::tuple<std::string, JsonPtr>>>;
struct Json {
  Json(JsonV v): v(v) {}
  JsonV v;
};

另外增加了一个叫 printer 的头文件，用于输出 tuple, variant, optional, vector 等类型，方便调试使用。在 helper 中，增加了 sep_by（相当于用分隔符 parser 分隔的 many），raw（不管原先 parser 的类型，输出吃掉的那部分输入字符串），eof（当 parser 运行结束后恰好输入也结束才算成功）。

最后的 json parser 长这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include "zpc/helper.hpp"
#include "zpc/printer.hpp"
#include <iostream>

struct Json;
using JsonPtr = std::shared_ptr<Json>;
using JsonV = std::variant<std::string, std::vector<JsonPtr>, std::vector<std::tuple<std::string, JsonPtr>>>;
struct Json {
  Json(JsonV v): v(v) {}
  JsonV v;
};

std::ostream& operator << (std::ostream& os, const Json& json) {
  return os << json.v;
}

int main() {
  auto ws = many(ch([](char c) { return isspace(c); }));
  auto tok = [&](auto&& p) { return seq(p, ws) % RESOLVE_OVERLOAD(std::get<0>); };

  auto sign = alt(lit("+"), lit("-"));
  auto digit = ch_range('0', '9');

  auto json_int = alt(
      lit("0"),
      seq(ch_range('1', '9'), many(digit))
  );
  auto json_exp = seq(
      alt(lit("E"), lit("e")),
      opt(sign),
      json_int
  );
  auto float_part = seq(lit("."), many1(digit));
  Parser<std::string> json_number = tok(raw(seq(
      opt(sign),
      alt(
          seq(json_int, opt(float_part)),
          float_part
      ),
      opt(json_exp)
  )));

  Parser<std::string> json_string = tok(alt(
  seq(lit("\\""), raw(many(ch([](char c) { return c != '"'; }))), lit("\\"")),
  seq(lit("'"), raw(many(ch([](char c) { return c != '"'; }))), lit("'"))
  )) % RESOLVE_OVERLOAD(std::get<1>);

  Parser<JsonPtr> json_val;

  auto lazy_json_val = lazy(json_val);

  Parser<std::vector<JsonPtr>> json_arr = tok(seq(
      tok(lit("[")),
      sep_by(lazy_json_val, tok(lit(","))),
      tok(lit("]"))
  )) % RESOLVE_OVERLOAD(std::get<1>);

  Parser<std::vector<std::tuple<std::string, JsonPtr>>> json_obj =
      tok(seq(
          tok(lit("{")),
          sep_by(
              seq(
                  json_string, tok(lit(":")), lazy_json_val
              ) %= [](const std::string &k, const std::string &, const JsonPtr &v) { return std::make_tuple(k, v); },
              tok(lit(","))
          ),
          tok(lit("}"))
      )) % RESOLVE_OVERLOAD(std::get<1>);

  Parser<JsonV> _json_val = tok(alt(
      json_number,
      json_string,
      tok(lit("true")),
      tok(lit("false")),
      tok(lit("null")),
      json_arr,
      json_obj
  ));
  json_val = _json_val % [](const JsonV &v) { return std::make_shared<Json>(v); };

  auto json = eof(json_obj);

  std::string_view in = R"|({
    "a": [1, 2, 3],
    "b": 1,
    "c": {
      "x": 1.1,
      "y":.1e2,
      "z": -2.e+2
    }
  })|";
  auto res = json(in);
  std::cout << res << std::endl;
  // ?:[("a", V{[V{"1"}, V{"2"}, V{"3"}]}), ("b", V{"1"}), ("c", V{[("x", V{"1.1"}), ("y", V{".1e2"}), ("z", V{"-2.e+2"})]})]
  std::cout << "Remain: " << in << std::endl;
}

CHECKPOINT 5

更进一步

  • 引入 Scanner 和 Token 优雅解决空格（CHECKPOINT 6）
  • 使用 packrat，解决左递归问题
  • 错误信息

附录

扩展 optional

函数名参考了 Scala 的 Option[T]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
template<typename T>
class optional : std::optional<T> {
public:
  optional() : std::optional<T>() {}
  template<typename Q>
  optional(Q&& v) : std::optional<T>(std::forward<Q>(v)) {}

  using std::optional<T>::has_value;
  using std::optional<T>::value;
  using std::optional<T>::value_or;
  using std::optional<T>::operator bool;

  template<typename F, typename Q = std::invoke_result_t<F, T>>
  auto map(F&& f) { // f: T => ?
    if (!has_value()) return optional<Q>();
    return optional<Q>(f(value()));
  }

  template<typename F, typename Q = std::invoke_result_t<F, T>>
  auto flat_map(F&& f) { // f : T => optional<?>
    if (!has_value()) return Q();
    return f(value());
  }

  auto or_else(const optional<T>& alternative) {
    if (!has_value()) return alternative;
    return *this;
  }
};

std::variant 的连接

std::variant 中包含的元素类型是可以重复的，但是对于重复的元素类型进行操作会有一些限制。

1
2
3
4
5
6
7
std::variant<int, int, double> v;
v = 1.0;
v = 1; // compile error
v.emplace<0>(1);
auto x = std::get<double>(v);
auto x = std::get<int>(v); // compile error
std::get<0>(v);

看上去似乎也只是麻烦了一些。但是考虑这样一个情景，我要写一个对于 variant 的函数 map，接受一个函数和 variant，返回一个新的 variant。如果类型都不相同，那么可以这么写：

1
2
3
4
using V = std::variant<int, double>;
auto f = [](auto&& x)->std::variant<int, double> { return x * 2; };
auto v_int = std::visit(f, V{1});
auto v_double = std::visit(f, V{1.0});

但是有相同类型的话，根据输入的 index 来决定输出的 index 也行，但是 STL 把 index 设计成模板参数，想要 runtime 有点麻烦。

因此对于合并一个 std::variant 和一个可能已经存在也可能不存在的 type，有两种方法，一种就是保证 unique，如果已经存在就类型不变，另一种就是始终把这个类型加进去。我实现了一下后者（之所以不是 append 而是 prepend 因为 alt 是 foldr 的）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
template<size_t I, typename... Ts, typename T>
void emplace_by_index(std::variant<Ts...>& variant, size_t idx, T&& x) {
  if constexpr (I == 1) {
    assert(0);
  } else if (idx + 1 == I) {
    variant.template emplace<I - 1>(x);
  } else {
    emplace_by_index<I - 1>(variant, idx, x);
  }
}

template<typename T, typename... Ts, typename R = std::variant<T, Ts...>>
R prepend_variant_type(const std::variant<Ts...>& variant) {
  R r;
  std::cout << variant.index() << std::endl;
  emplace_by_index<std::variant_size_v<R>>(r, variant.index() + 1, std::visit([](auto&& x){ return x; }, variant));
  return r;
}

int main() {
  std::variant<int, double> v;
  v.emplace<0>(1);
  auto vv = prepend_variant_type<std::string>(v);
  static_assert(std::is_same_v<decltype(vv), std::variant<std::string, int, double>>);
  assert(vv.index() == 1);
}

但是考虑到用户代码，写 visitor 的时候并不能拿到 index 来区分，不写 visitor 而是判断 index 就很蠢，所以这种方法不仅麻烦，也不能方便用户，所以就放弃了。

此时需要一个 unique_variant，之后就再也不碰 std::variant 的 index 了，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
template<typename T, typename... List>
constexpr bool is_in_list = (std::is_same_v<T, List> || ...);

template<typename...>
struct variant_concat;

template<typename T, typename... Ts>
struct variant_concat<T, std::variant<Ts...>> {
  using type = std::variant<T, Ts...>;
};

template<typename T, typename... Ts>
struct unique_variant {
  using type = std::conditional_t<
      is_in_list<T, Ts...>,
      typename unique_variant<Ts...>::type,
      typename variant_concat<T, typename unique_variant<Ts...>::type>::type
  >;
};

template<typename T>
struct unique_variant<T> {
  using type = std::variant<T>;
};

template<typename... Ts>
using unique_variant_t = typename unique_variant<Ts...>::type;

int main() {
  static_assert(std::is_same_v<unique_variant_t<int, int, double>, std::variant<int, double>>);
  static_assert(std::is_same_v<unique_variant_t<int, double, double>, std::variant<int, double>>);
}

写在最后

我为什么需要一个 C++ 的 Parser Combinator？

每年的九月份，对于大四的计科学生，就到了编译原理实践的季节。相比起去年（也就是我亲身经历那个季节），愚蠢的老师因为自己的无知限定了编程语言（C, C++, Java, C#）。（题外话：这绝对是扼杀创新力的，虽然只会影响到一小部分人，我和 K 分别把它当成了熟悉 Scala 和 Rust 的机会。）再让我选择的话，肯定得用一个 Parser Combinator（由此否决了 Antlr，lex & yacc 一众代码生成的库），由于我讨厌 Java，以及考虑到 C# 的学习成本（其实只是觉得学了没啥用），就只有 C++ 这一个选项了。

我为什么要造轮子？

其实 CppCmb 相当符合我的需求，但是我就是要造轮子。

Boost Spirit X3 功能挺全的，但是有很多 boilerplate code，写起来浑身难受。

PEGTL 算是 star 最多 C++ parser combinator 项目了，很牛逼，利用元编程的编译器 parser combinator，写代码时 CLion 非常非常卡，占用非常非常多内存，就算开省电模式也没用。一度决定使用这个库，但是调试起来实在是太折磨了，还有就是文档和它 release 的代码不匹配，API 还要靠猜，这个实在是没办法。

然后还有不少 star 数比较少的项目，可能之后也会成为它们的一员。我觉得我的 Parser Combinator Library 的好处就是代码少，适合这篇博客的产出，以及给别人一些启发（如果真的有人看的话）。

参考

  • https://github.com/beark/ftl/blob/master/docs/Parsec-I.md 非常函数式的 C++ Parser Combinator
  • https://stackoverflow.com/questions/28997271/c11-way-to-index-tuple-at-runtime-without-using-switch 如何对于 tuple 使用 runtime 的 index，对于 variant 也是同理
  • https://llh911001.gitbooks.io/mostly-adequate-guide-chinese 不错的函数式入门教程，帮我复习了一下（中文版少了一章）
  • https://www.slideshare.net/alexandrgranin/monadic-parsers-in-c 一个 PPT，有很多函数签名可供参考（但并没有实现）
  • 《Haskell函数式编程入门（第2版）》 10.7 和 14.1 章，可以看到 Haskell 中赋予 Parser 以 Functor Monad Applicative Alternative 非常方便以及 parsec 库的使用
  • https://netcan.github.io/2020/09/16/C-元编程之Parser-Combinator/ 利用 constexpr 编译期 parser

CHECKPOINTS