写在最前
自制一个 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;
注:为什么不弄成二元组合子,重载 &
,就能搞出更加自然的 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 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; }
注意 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) { 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) { 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 ; v.emplace <0 >(1 ); auto x = std::get <double >(v);auto x = std::get <int >(v); 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