云社区 博客 博客详情
云社区 博客 博客详情

C++元编程之Parser Combinator

netcan96 发表于 2020-09-16 20:52:59 09-16 20:52
netcan96 发表于 2020-09-16 20:52:59 2020/09/16
0
0

【摘要】 2020-09-16 18:26:25---## 引子前不久在CppCon上看到一个Talk:[constexpr All the things](https://www.youtube.com/watch?v=PJwd4JLYJJY),这个演讲技术令我非常震惊,在编译期解析json字符串,进而提出了编译期构造正则表达式(编译期构建FSM),现场掌声一片,而背后依靠的是C++强大的const...

2020-09-16 18:26:25

---

## 引子

前不久在CppCon上看到一个Talk:[constexpr All the things](https://www.youtube.com/watch?v=PJwd4JLYJJY),这个演讲技术令我非常震惊,在编译期解析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是一个解析器函数,输入一个字符串,输出解析后的类型值集合,函数签名如下:

```haskell

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

```


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

```haskell

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

```


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


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

```cpp

// 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,例如匹配给定的字符:

```cpp

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。


匹配给定集合中的字符:

```cpp

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:

```cpp

// 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的结果:

```cpp

// 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的结果:

```cpp

// 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直到匹配失败,每次结果传递给一个函数运算:

```cpp

// 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`:


```cpp

// 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);

    };

};

```


```cpp

// 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`操作:

```cpp

// 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的类型,而需要获取其值的时候,就需要解析字符串了,这些工作应该在编译期确定。


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

```cpp

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

```


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

```cpp

constexpr auto number = AtLeast(OneOf("1234567890"), 0l, [](long acc, char c) -> long {

    return acc * 10 + (c - '0');

});

constexpr auto integer = Option(number, 0l);

```


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

```cpp

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`值。

```cpp

// 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`:

```cpp

constexpr auto ParseNum() {

    using R = std::variant<double, long>;

    return [](ParserInput in) -> ParserResult<R> {

        // ...

    };

}

```


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

```cpp

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()`扫描,做一次宽度优先搜索,确定最外层的元素个数,从而依次解析填值。


登录后可下载附件,请登录或者注册

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区),文章链接,文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:huaweicloud.bbs@huawei.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
评论文章 //点赞 收藏 0
点赞
分享文章到微博
分享文章到朋友圈

评论 (0)


该篇博文已经被设置为禁止评论!

温馨提示

您确认删除评论吗?

确定
取消
温馨提示

您确认删除评论吗?

删除操作无法恢复,请谨慎操作。

确定
取消
温馨提示

您确认删除博客吗?

确定
取消

确认删除

您确认删除博客吗?

确认删除

您确认删除评论吗?

温馨提示

登录超时或用户已下线,请重新登录!!!

确定
取消