詳解C++元編程之Parser Combinator
引子
前不久在CppCon上看到一個(gè)Talk：[constexpr All the things](https://www.youtube.com/watch?v=PJwd4JLYJJY)，這個(gè)演講技術(shù)令我非常震驚，在編譯期解析json字符串，進(jìn)而提出了編譯期構(gòu)造正則表達(dá)式（編譯期構(gòu)建FSM），現(xiàn)場(chǎng)掌聲一片，而背后依靠的是C++強(qiáng)大的constexpr特性，從而大大提高了編譯期計(jì)算威力。
早在C++11的時(shí)候就有constexpr特性，那時(shí)候約束比較多，只能有一條return語(yǔ)句，能做的事情只有簡(jiǎn)單的遞歸實(shí)現(xiàn)一些數(shù)學(xué)、hash函數(shù)；而到了C++14的時(shí)候這個(gè)約束放開了，允許像普通函數(shù)那樣，進(jìn)而社區(qū)產(chǎn)生了一系列constexpr庫(kù)；而在C++17，更加泛化了constexpr，允許`if constexpr`來代替元編程的SFINAE手法，STL庫(kù)的一些算法支持constexpr，甚至連lambda都默認(rèn)是constexpr的了；到C++20，更加難以想象，居然支持了constexpr new，STL的vector都是constexpr的了，若用constexpr allocator和constexpr destructor，那么就能統(tǒng)一所有constexpr容器了。
借助C++的constexpr能力，可以輕而易舉的構(gòu)造Parser Combinator，實(shí)現(xiàn)一個(gè)Parser也沒那么繁雜了，對(duì)用戶定義的字符串（User defined literal）釋放了巨大的潛力，這也是本文的重點(diǎn)。
什么是Parser
Parser是一個(gè)解析器函數(shù)，輸入一個(gè)字符串，輸出解析后的類型值集合，函數(shù)簽名如下：
Parser a:: String -> [(a, String)]
簡(jiǎn)單起見，這里我們考慮只輸出零或一個(gè)類型值結(jié)果，而不是集合，那么簽名如下：
Parser a:: String -> Maybe (a, String)
舉個(gè)例子，一個(gè)數(shù)字Parser，解析輸入字符串`"123456"`，輸出結(jié)果為`Just (1, "23456")`，即得到了數(shù)字1和剩余字符串`"23456"`，從而可以供下一個(gè)Parser使用；若解析失敗，輸出`None`。
對(duì)應(yīng)C++的函數(shù)簽名，如下：
// 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的定義了。
根據(jù)定義可以實(shí)現(xiàn)幾個(gè)最基本的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`相當(dāng)于一個(gè)工廠，給定字符`c`，創(chuàng)建匹配`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之間可以組合成任意復(fù)雜的Parser，而Parser Combinator就是一個(gè)高階函數(shù)，輸入一系列Parser，輸出復(fù)合后的新Parser。
根據(jù)定義，可以實(shí)現(xiàn)一個(gè)Combinator組合兩個(gè)Parser，同時(shí)根據(jù)兩個(gè)Parser的結(jié)果計(jì)算出新的結(jié)果，從而得到新的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++支持操作符重載，那么可以重載一個(gè)二元操作符來組合兩個(gè)Parser，比如從兩個(gè)Parser里取出其中一個(gè)Parser的結(jié)果產(chǎn)生新的Parser：
取左邊Parser的結(jié)果：
// 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的結(jié)果：
// 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; });
};
有時(shí)候需要對(duì)同一個(gè)Parser進(jìn)行多次匹配，類似正則表達(dá)式的`*`操作，這個(gè)操作可以看做是`fold`，執(zhí)行多次Parser直到匹配失敗，每次結(jié)果傳遞給一個(gè)函數(shù)運(yùn)算：
// 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`函數(shù)，那么可以很容易實(shí)現(xiàn)函數(shù)來匹配任意多次`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);
};
};
還有種操作是匹配零到一次，類似于正則表達(dá)式的`?`操作，這里我定義為`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;
};
};
有了以上基本操作，接下來看看如何運(yùn)用。
實(shí)戰(zhàn)
解析數(shù)值
項(xiàng)目中模板元編程比較多，而C++17之前模板Dependent type（非類型參數(shù)）不支持double，得C++20才支持double，臨時(shí)方案就是用`template<char... C> struct NumWrapper {};`模擬double的類型，而需要獲取其值的時(shí)候，就需要解析字符串了，這些工作應(yīng)該在編譯期確定。
首先是匹配符號(hào)`+/-`，若沒有符號(hào)，則認(rèn)為是`+`：
constexpr auto sign = Option(OneOf("+-"), '+');
其次是整數(shù)部分，也可能沒有，若沒有，則認(rèn)為是0：
constexpr auto number = AtLeast(OneOf("1234567890"), 0l, [](long acc, char c) -> long {
return acc * 10 + (c - '0');
});
constexpr auto integer = Option(number, 0l);
然后是小數(shù)點(diǎn)`.`，若沒有小數(shù)點(diǎn)，為了不丟失精度，則返回一個(gè)`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);
}
若有小數(shù)點(diǎn)，認(rèn)為是浮點(diǎn)數(shù)，返回其`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);
```
由于該P(yáng)arser可能返回`long`或者`double`類型，所以可以統(tǒng)一成和類型`std::variant`：
```cpp
constexpr auto ParseNum() {
using R = std::variant<double, long>;
return [](ParserInput in) -> ParserResult<R> {
// ...
};
}
最后我們的`NumWrapper`實(shí)現(xiàn)如下，從而可以混入模板類型體系：
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
}
如果僅僅是用于解析數(shù)字，那也殺雞用牛刀了，因?yàn)樵赻Parser Combinator`之前的版本，我就是在一個(gè)普通的`constexpr`函數(shù)中完成解析的，代碼很無趣，但現(xiàn)在我可能想回退代碼了。
Json解析導(dǎo)讀
這次的CppCon主題是編譯期解析`json`字符串，當(dāng)然直接用`string_view`承載字符串即可。然后構(gòu)造一些constexpr容器，例如固定長(zhǎng)度的constexpr vector，由于是17年的talk了，在還不支持constexpr new的情況下，只能這么做。有了constexpr vector，進(jìn)而可以構(gòu)造map容器，也是很簡(jiǎn)單的pair vector集合。
進(jìn)而提出Parser Combinator，解析字符串，`fmap`到j(luò)son數(shù)據(jù)結(jié)構(gòu)中。
最初實(shí)現(xiàn)的時(shí)候，json數(shù)據(jù)結(jié)構(gòu)也是一個(gè)大的`template<size_t Depth> struct Json_Value;`模板承載，導(dǎo)致只能指定最大遞歸層數(shù)，那就不夠?qū)嵱昧?。然后talker想了個(gè)很巧妙的辦法去掉層數(shù)約束，就是先遞歸`sizes()`掃描一遍，計(jì)算出所有值個(gè)數(shù)，這樣就能確定需要多少個(gè)`Value`容器來存儲(chǔ)，其次計(jì)算出字符串長(zhǎng)度，由于`UTF8`、轉(zhuǎn)義字符串的影響，最終要解析的長(zhǎng)度其實(shí)是可能小于輸入長(zhǎng)度的。有了確定空間后，進(jìn)行第二遍遞歸`value_recur<NumObjects, StringSize>::value_parser()`掃描，每次解析完整值時(shí)候填一下`Value`數(shù)據(jù)結(jié)構(gòu)。而由于數(shù)組和對(duì)象類似，可能嵌套，這時(shí)候進(jìn)行第三遍遞歸`extent_recur<>::value_parser()`掃描，做一次寬度優(yōu)先搜索，確定最外層的元素個(gè)數(shù)，從而依次解析填值。
以上就是詳解C++元編程之Parser Combinator的詳細(xì)內(nèi)容，更多關(guān)于C++元編程之Parser Combinator的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
Qt學(xué)習(xí)之QListWidget控件的使用教程詳解
這篇文章主要為大家詳細(xì)介紹了Qt中QListWidget控件的使用教程，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)Qt有一定的幫助，需要的可以參考一下2022-12-12
這篇文章主要為大家詳細(xì)介紹了如何基于QT實(shí)現(xiàn)簡(jiǎn)單的本地音樂播放器,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-03-03
這篇文章主要介紹了C語(yǔ)言指針及占據(jù)內(nèi)存空間的相關(guān)知識(shí)，非常不錯(cuò)，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-02-02
在本篇文章中我們給大家總結(jié)了C/C++中*和&的用法以及相關(guān)的代碼分享，有興趣的朋友趕緊學(xué)習(xí)下吧。2018-03-03
本篇文章是基礎(chǔ)篇，適合c語(yǔ)言剛?cè)腴T的朋友，本文對(duì)初識(shí)c語(yǔ)言的指針和指針變量做了簡(jiǎn)單的分析，幫助大家快速入門c語(yǔ)言的世界，更好的理解c語(yǔ)言2021-08-08
C語(yǔ)言中實(shí)現(xiàn)itoa函數(shù)的實(shí)例
這篇文章主要介紹了C語(yǔ)言中實(shí)現(xiàn)itoa函數(shù)的實(shí)例的相關(guān)資料,希望通過本文能幫助到大家，讓大家實(shí)現(xiàn)這樣的功能，需要的朋友可以參考下2017-10-10
C語(yǔ)言課程設(shè)計(jì)之抽獎(jiǎng)系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言課程設(shè)計(jì)之抽獎(jiǎng)系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-12-12
二叉搜索樹又稱二叉排序樹,二叉搜索樹是一種二叉樹,其中每個(gè)節(jié)點(diǎn)的值大于其左子樹中的任何節(jié)點(diǎn),并且小于其右子樹中的任何節(jié)點(diǎn),本文小編就給大家講講C++二叉搜索樹的操作及實(shí)現(xiàn),感興趣的同學(xué)跟著小編一起來看看吧2023-08-08
C++中實(shí)現(xiàn)線程安全和延遲執(zhí)行詳解
這篇文章主要為大家詳細(xì)介紹了C++中實(shí)現(xiàn)線程安全和延遲執(zhí)行的相關(guān)知識(shí)，文中的示例代碼講解詳細(xì)，具有一定的借鑒價(jià)值，需要的小伙伴可以了解下2024-01-01
使用map實(shí)現(xiàn)單詞轉(zhuǎn)換的實(shí)例分析
本篇文章是對(duì)使用map實(shí)現(xiàn)單詞轉(zhuǎn)換的代碼實(shí)例進(jìn)行了纖細(xì)的分析介紹，需要的朋友參考下2013-05-05