C++ 自制 Parser Combinator

写在最前

自制一个 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 而不是 optionalmap。另外为什么要有这个恶心的 RESOLVE_OVERLOAD,在我的另一篇博客中有讲,这里就省略了。可以看到,对于相同类型的 alt,用户就不会拿到繁琐的 std::variant 作为结果了,std::variant 只会在必要的时候出现。

CHECKPOINT 3

四则运算

首先是 number 的 parser,为此加了 manychmany 就是尽可能多的应用 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 的好处就是代码少,适合这篇博客的产出,以及给别人一些启发(如果真的有人看的话)。

参考

CHECKPOINTS