C++ 元编程之 Parser Combinator

微信扫一扫,分享到朋友圈

C++ 元编程之 Parser Combinator

引子

前不久在 CppCon 上看到一个 Talk: constexpr All the things
,这个演讲主题令我非常震撼,在编译期解析 json 字符串,进而提出了编译期构造正则表达式(编译期构建 FSM),现场掌声一片,而背后依靠的是 C++ 强大的 constexpr 特性,从而大大提高了编译期计算威力。

早在 C++11 的时候就有 constexpr 特性,那时候约束比较多,只能有一条 return 语句,能做的事情只有简单的递归实现一些数学、hash 函数;而到了 C++14 的时候这个约束放开了,允许像普通函数那样,进而社区产生了一系列 constexpr 库;而在 C++17,更加泛化了 constexpr,允许 if constexpr
来代替元编程的 SFINAE 手法,STL 库的一些算法支持 constexpr,甚至连 lambda 都默认是 constexpr 的了;到 C++20,更加难以想象,居然支持了 constexpr new,STL 的 vector 都是 constexpr 的了,若用 constexpr allocator 和 constexpr destructor,那么就能统一所有 constexpr 容器了。

借助 C++ 的 constexpr + lambda 能力,可以轻而易举的构造 Parser Combinator,实现一个 Parser 也没那么繁杂了,对用户定义的字符串(User defined literal)释放了巨大的潜力,这也是本文的重点。

什么是 Parser

Parser 是一个解析器函数,输入一个字符串,输出解析后的类型值集合,函数签名如下:

Parser a :: String -> [(a, String)]

简单起见,这里我们考虑只输出零或一个类型值结果,而不是集合,那么签名如下:

Parser a :: String -> Maybe (a, String)

举个例子,一个数字 Parser,解析输入字符串 "123456"
,输出结果为 Just (1, "23456")
,即得到了数字 1 和剩余字符串 "23456"
,从而可以供下一个 Parser 使用;若解析失败,输出 None

对应 C++ 的函数签名,如下:

// Parser a :: String -> Maybe (a, String)
using ParserInput = std::string_view;
template <typename T>
using ParserResult = std::optional<std::pair<T, ParserInput>>;
template <typename T>
using Parser = auto(*)(ParserInput) -> ParserResult<T>;

这就是 Parser 的定义了。

根据定义可以实现几个最基本的 Parser,例如匹配给定的字符:

constexpr auto makeCharParser(char c) {
// CharParser :: Parser Char
return [=](ParserInput s) -> ParserResult<char> {
if (s.empty() || c != s[0]) return std::nullopt;
return std::make_pair(s[0], ParserInput(s.begin() + 1, s.size() - 1));
};
};

makeCharParser
相当于一个工厂,给定字符 c
,创建匹配 c
的 Parser。

匹配给定集合中的字符:

constexpr auto oneOf(std::string_view chars) {
// OneOf :: Parser Char
return [=](ParserInput s) -> ParserResult<char> {
if (s.empty() || chars.find(s[0]) == std::string::npos) return std::nullopt;
return std::make_pair(s[0], ParserInput(s.begin() + 1, s.size() - 1));
};
}

什么是 Parser Combinator

Parser 是可组合的最小单元,Parser 与 Parser 之间可以组合成任意复杂的 Parser,而 Parser Combinator 就是一个高阶函数,输入一系列 Parser,输出复合后的新 Parser。

根据定义,可以实现一个 Combinator 组合两个 Parser,同时根据两个 Parser 的结果计算出新的结果,从而得到新的 Parser:

// combine :: Parser a -> Parser b -> (a -> b -> c) -> Parser c
template<typename P1, typename P2, typename F,
typename R = std::invoke_result_t<F, Parser_t<P1>, Parser_t<P2>>>
constexpr auto combine(P1&& p1, P2&& p2, F&& f) {
return [=](ParserInput s) -> ParserResult<R> {
auto r1 = p1(s);
if (!r1) return std::nullopt;
auto r2 = p2(r1->second);
if (!r2) return std::nullopt;
return std::make_pair(f(r1->first, r2->first), r2->second);
};
};

由于 C++ 支持操作符重载,那么可以重载一个二元操作符来组合两个 Parser,比如从两个 Parser 里取出其中一个 Parser 的结果产生新的 Parser:

取左边 Parser 的结果:

// operator> :: Parser a -> Parser b -> Parser a
template<typename P1, typename P2>
constexpr auto operator>(P1&& p1, P2&& p2) {
return combine(std::forward<P1>(p1),
std::forward<P2>(p2),
[](auto&& l, auto) { return l; });
};

取右边 Parser 的结果:

// operator< :: Parser a -> Parser b -> Parser b
template<typename P1, typename P2>
constexpr auto operator<(P1&& p1, P2&& p2) {
return combine(std::forward<P1>(p1),
std::forward<P2>(p2),
[](auto, auto&& r) { return r; });
};

有时候需要对同一个 Parser 进行多次匹配,类似正则表达式的 */+
操作,这个操作可以看做是 fold
,执行多次 Parser 直到匹配失败,每次结果传递给一个函数运算:

// foldL :: Parser a -> b -> (b -> a -> b) -> ParserInput -> ParserResult b
template<typename P, typename R, typename F>
constexpr auto foldL(P&& p, R acc, F&& f, ParserInput in)
-> ParserResult<R> {
while (true) {
auto r = p(in);
if (!r) return std::make_pair(acc, in);
acc = f(acc, r->first);
in = r->second;
}
};

有了 fold
函数,那么可以很容易实现函数来匹配任意多次 many
,匹配至少一次 atLeast

// many :: Parser a -> Parser monostate
template<typename P>
constexpr auto many(P&& p) {
return [p=std::forward<P>(p)](ParserInput s)
-> ParserResult<std::monostate> {
return detail::FoldL(p, std::monostate{},
[](auto acc, auto) { return acc; }, s);
};
};
// atLeast :: Parser a -> b -> (b -> a -> b) -> Parser b
template<typename P, typename R, typename F>
constexpr auto atLeast(P&& p, R&& init, F&& f) {
static_assert(std::is_same_v<std::invoke_result_t<F, R, Parser_t<P>>, R>,
"type mismatch!");
return [p=std::forward<P>(p),
f=std::forward<F>(f),
init=std::forward<R>(init)](ParserInput s) -> ParserResult<R> {
auto r = p(s);
if (!r) return std::nullopt;
return detail::foldL(p, f(init, r->first), f, r->second);
};
};

还有种操作是匹配零到一次,类似于正则表达式的 ?
操作,这里我定义为 option
操作:

// option :: Parser a -> a -> Parser a
template<typename P, typename R = Parser_t<P>>
constexpr auto option(P&& p, R&& defaultV) {
return [=](ParserInput s) -> ParserResult<R> {
auto r = p(s);
if (! r) return make_pair(defaultV, s);
return r;
};
};

有了以上基本操作,接下来看看如何运用。

实战

解析数值

项目中模板元编程比较多,而 C++17 之前模板 Dependent type(非类型参数)不支持 double,得 C++20 才支持 double,临时方案就是用 template<char... C> struct NumWrapper {};
和 User defined literal 来模拟 double 的类型,而需要获取其值的时候,就需要解析字符串了,这些工作应该在编译期确定。

首先是匹配符号 +/-
,若没有符号,则认为是 +

constexpr auto sign = Option(OneOf("+-"), '+');

其次是整数部分,也可能没有,若没有,则认为是 0:

constexpr auto number = AtLeast(OneOf("1234567890"), 0l, [](long acc, char c) -> long {
return acc * 10 + (c - '0');
});
constexpr auto integer = Option(number, 0l);

然后是小数点 .
,若没有小数点,为了不丢失精度,则返回一个 long
值。

constexpr auto point = MakeCharParser('.');
// integer
if (! (sign < integer < point)(in)) {
return Combine(sign, integer, [](char sign, long number) -> R {
return sign == '+' ? number : -number;
})(in);
}

若有小数点,认为是浮点数,返回其 double
值。

// floating
constexpr auto decimal = point < Option(number, 0l);
constexpr auto value = Combine(integer, decimal,
[](long integer, long decimal) -> double {
double d = 0.0;
while (decimal) {
d = (d + (decimal % 10)) * 0.1;
decimal /= 10;
}
return integer + d;
});
return Combine(sign, value,
[](char sign, double d) -> R { return sign == '+' ? d : -d; })(in);

由于该 Parser 可能返回 long
或者 double
类型,所以可以统一成和类型 std::variant

constexpr auto ParseNum() {
using R = std::variant<double, long>;
return [](ParserInput in) -> ParserResult<R> {
// ...
};
}

最后我们的 NumWrapper
实现如下,从而可以混入模板类型体系:

template<char... Cs>
constexpr std::array<char, sizeof...(Cs)> ToArr = {Cs...};
template<char ...Cs>
class NumberWrapper {
public:
constexpr static auto numStr = ToArr<Cs...>;
constexpr static auto res =
ParseNum()(std::string_view(numStr.begin(), numStr.size()));
static_assert(res.has_value() && res->second.empty(), "parse failed!");
public:
constexpr static auto value =
std::get<res->first.index()>(res->first); // long or double
}

如果仅仅是用于解析数字,那也杀鸡用牛刀了,因为在 Parser Combinator
之前的版本,我就是在一个普通的 constexpr
函数中完成解析的,代码很无趣,但现在我可能想回退代码了。

Json 解析导读

这次的 CppCon 主题是编译期解析 json
字符串,当然直接用 string_view
承载字符串即可。然后构造一些 constexpr 容器,例如固定长度的 constexpr vector,由于是 17 年的 talk 了,在还不支持 constexpr new 的情况下,只能这么做。有了 constexpr vector,进而可以构造 map 容器,也是很简单的 pair vector 集合。

进而提出 Parser Combinator,解析字符串, fmap
到 json 数据结构中。

最初实现的时候,json 数据结构也是一个大的 template<size_t Depth> struct Json_Value;
模板承载,导致只能指定最大递归层数,那就不够实用了。然后 talker 想了个很巧妙的办法去掉层数约束,就是先递归 sizes()
扫描一遍,计算出所有值个数,这样就能确定需要多少个 Value
容器来存储,其次计算出字符串长度,由于 UTF8
、转义字符串的影响,最终要解析的长度其实是可能小于输入长度的。有了确定空间后,进行第二遍递归 value_recur<NumObjects, StringSize>::value_parser()
扫描,每次解析完整值时候填一下 Value
数据结构。而由于数组和对象类似,可能嵌套,这时候进行第三遍递归 extent_recur<>::value_parser()
扫描,相当于做一次宽度优先搜索,确定最外层的元素个数,从而依次解析填值。

微信扫一扫,分享到朋友圈

C++ 元编程之 Parser Combinator

必应API接口nodejs版

上一篇

Uber同意将其欧洲货运部门出售给森德公司

下一篇

你也可能喜欢

C++ 元编程之 Parser Combinator

长按储存图像,分享给朋友