关于c++:技术解析丨C元编程之Parser-Combinator

1次阅读

共计 6273 个字符，预计需要花费 16 分钟才能阅读完成。

摘要：借助 C ++ 的 constexpr 能力，能够轻而易举的结构 Parser Combinator，对用户定义的字符串（User defined literal）开释了微小的后劲。

引子

前不久在 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 能力，能够轻而易举的结构 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 {}; 模仿 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++
发表至： c#
2020-09-19
 0
关于c:FreeBSD12-安装dwm-st
关于c++:c中lambda表达式用法
关于c++:c类访问权限及友元
关于c#:C-官方文档导读及推荐书单

站内搜索

-「」