詳解C++元編程之Parser Combinator

Posted on 2021-05-21 by WalkonNet

引子

前不久在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是一個解析器函數，輸入一個字符串，輸出解析後的類型值集合，函數簽名如下：

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`：
```cpp
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的詳細內容，更多關於C++元編程之Parser Combinator的資料請關註WalkonNet其它相關文章！

詳解C++元編程之Parser Combinator

引子

什麼是Parser

什麼是Parser Combinator

實戰

Json解析導讀

推薦閱讀：

發佈留言取消回覆

近期文章

引子

什麼是Parser

什麼是Parser Combinator

實戰

Json解析導讀

推薦閱讀：

發佈留言 取消回覆

近期文章

標籤

發佈留言取消回覆