詳解C++元編程之Parser Combinator
引子
前不久在CppCon上看到一個Talk：[constexpr All the things](https://www.youtube.com/watch?v=PJwd4JLYJJY)，這個演講技術(shù)令我非常震驚，在編譯期解析json字符串，進而提出了編譯期構(gòu)造正則表達式（編譯期構(gòu)建FSM），現(xiàn)場掌聲一片，而背后依靠的是C++強大的constexpr特性，從而大大提高了編譯期計算威力。
早在C++11的時候就有constexpr特性，那時候約束比較多，只能有一條return語句，能做的事情只有簡單的遞歸實現(xiàn)一些數(shù)學(xué)、hash函數(shù)；而到了C++14的時候這個約束放開了，允許像普通函數(shù)那樣，進而社區(qū)產(chǎn)生了一系列constexpr庫；而在C++17，更加泛化了constexpr，允許`if constexpr`來代替元編程的SFINAE手法，STL庫的一些算法支持constexpr，甚至連lambda都默認是constexpr的了；到C++20，更加難以想象，居然支持了constexpr new，STL的vector都是constexpr的了，若用constexpr allocator和constexpr destructor，那么就能統(tǒng)一所有constexpr容器了。
借助C++的constexpr能力，可以輕而易舉的構(gòu)造Parser Combinator，實現(xiàn)一個Parser也沒那么繁雜了，對用戶定義的字符串（User defined literal）釋放了巨大的潛力，這也是本文的重點。
什么是Parser
Parser是一個解析器函數(shù)，輸入一個字符串，輸出解析后的類型值集合，函數(shù)簽名如下：
Parser a:: String -> [(a, String)]
簡單起見，這里我們考慮只輸出零或一個類型值結(jié)果，而不是集合，那么簽名如下：
Parser a:: String -> Maybe (a, String)
舉個例子，一個數(shù)字Parser，解析輸入字符串`"123456"`，輸出結(jié)果為`Just (1, "23456")`，即得到了數(shù)字1和剩余字符串`"23456"`，從而可以供下一個Parser使用；若解析失敗，輸出`None`。
對應(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ù)定義可以實現(xiàn)幾個最基本的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`，創(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就是一個高階函數(shù)，輸入一系列Parser，輸出復(fù)合后的新Parser。
根據(jù)定義，可以實現(xiàn)一個Combinator組合兩個Parser，同時根據(jù)兩個Parser的結(jié)果計算出新的結(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++支持操作符重載，那么可以重載一個二元操作符來組合兩個Parser，比如從兩個Parser里取出其中一個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; });
};
有時候需要對同一個Parser進行多次匹配，類似正則表達式的`*`操作，這個操作可以看做是`fold`，執(zhí)行多次Parser直到匹配失敗，每次結(jié)果傳遞給一個函數(shù)運算：
// 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ù)，那么可以很容易實現(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);
};
};
還有種操作是匹配零到一次，類似于正則表達式的`?`操作，這里我定義為`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;
};
};
有了以上基本操作，接下來看看如何運用。
實戰(zhàn)
解析數(shù)值
項目中模板元編程比較多，而C++17之前模板Dependent type（非類型參數(shù)）不支持double，得C++20才支持double，臨時方案就是用`template<char... C> struct NumWrapper {};`模擬double的類型，而需要獲取其值的時候，就需要解析字符串了，這些工作應(yīng)該在編譯期確定。
首先是匹配符號`+/-`，若沒有符號，則認為是`+`：
constexpr auto sign = Option(OneOf("+-"), '+');
其次是整數(shù)部分，也可能沒有，若沒有，則認為是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ù)點`.`，若沒有小數(shù)點，為了不丟失精度，則返回一個`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ù)點，認為是浮點數(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);
```
由于該Parser可能返回`long`或者`double`類型，所以可以統(tǒng)一成和類型`std::variant`：
```cpp
constexpr auto ParseNum() {
using R = std::variant<double, long>;
return [](ParserInput in) -> ParserResult<R> {
// ...
};
}
最后我們的`NumWrapper`實現(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ù)字，那也殺雞用牛刀了，因為在`Parser Combinator`之前的版本，我就是在一個普通的`constexpr`函數(shù)中完成解析的，代碼很無趣，但現(xiàn)在我可能想回退代碼了。
Json解析導(dǎo)讀
這次的CppCon主題是編譯期解析`json`字符串，當然直接用`string_view`承載字符串即可。然后構(gòu)造一些constexpr容器，例如固定長度的constexpr vector，由于是17年的talk了，在還不支持constexpr new的情況下，只能這么做。有了constexpr vector，進而可以構(gòu)造map容器，也是很簡單的pair vector集合。
進而提出Parser Combinator，解析字符串，`fmap`到j(luò)son數(shù)據(jù)結(jié)構(gòu)中。
最初實現(xiàn)的時候，json數(shù)據(jù)結(jié)構(gòu)也是一個大的`template<size_t Depth> struct Json_Value;`模板承載，導(dǎo)致只能指定最大遞歸層數(shù)，那就不夠?qū)嵱昧?。然后talker想了個很巧妙的辦法去掉層數(shù)約束，就是先遞歸`sizes()`掃描一遍，計算出所有值個數(shù)，這樣就能確定需要多少個`Value`容器來存儲，其次計算出字符串長度，由于`UTF8`、轉(zhuǎn)義字符串的影響，最終要解析的長度其實是可能小于輸入長度的。有了確定空間后，進行第二遍遞歸`value_recur<NumObjects, StringSize>::value_parser()`掃描，每次解析完整值時候填一下`Value`數(shù)據(jù)結(jié)構(gòu)。而由于數(shù)組和對象類似，可能嵌套，這時候進行第三遍遞歸`extent_recur<>::value_parser()`掃描，做一次寬度優(yōu)先搜索，確定最外層的元素個數(shù)，從而依次解析填值。
以上就是詳解C++元編程之Parser Combinator的詳細內(nèi)容，更多關(guān)于C++元編程之Parser Combinator的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
怎么實現(xiàn)類的成員函數(shù)作為回調(diào)函數(shù)
不使用成員函數(shù)，為了訪問類的成員變量，可以使用友元操作符(friend)，在C++中將該函數(shù)說明為類的友元即可2013-10-10
所謂的青蛙跳臺階問題，就是指一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。本文將用C語言解決這一問題，需要的可以參考一下2022-01-01
C++開發(fā)在IOS環(huán)境下運行的LRUCache緩存功能
本文著重介紹如何在XCODE中，通過C++開發(fā)在IOS環(huán)境下運行的緩存功能。算法基于LRU,最近最少使用,需要的朋友可以參考下2012-11-11
詳細對比C語言中的chmod()函數(shù)和fchmod()函數(shù)
這篇文章主要介紹了C語言中的chmod()函數(shù)和fchmod()函數(shù)的詳細對比,兩個都是用于修改文件權(quán)限但是請注意實際使用上的差異,需要的朋友可以參考下2015-09-09
C++實現(xiàn)線性表有序表的合并方式(順序表實現(xiàn)and鏈表實現(xiàn))
這篇文章主要介紹了C++實現(xiàn)線性表有序表的合并方式(順序表實現(xiàn)and鏈表實現(xiàn)),具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-04-04
這篇文章主要為大家詳細介紹了如何利用QPainter實現(xiàn)三維餅狀圖的繪制，由于Qt中沒有三維餅狀圖的繪制組件，因此只能自行繪制，感興趣的可以動手嘗試一下2022-06-06
這篇文章主要介紹了C語言之如何求三次方根問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-12-12
下面小編就為大家?guī)硪黄钊肜斫釩++運算符重載。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2021-08-08
C預(yù)處理器不是編譯器的組成部分，但是它是編譯過程中一個單獨的步驟。簡言之，C預(yù)處理器只不過是一個文本替換工具而已，它們會指示編譯器在實際編譯之前完成所需的預(yù)處理。我們將把C預(yù)處理器（C Preprocessor）簡寫為CPP2022-12-12
這篇文章主要介紹了C++運算符重載規(guī)則詳解,是C++入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09