技術解析丨C++元程式設計之Parser Combinator

摘要：借助C++的constexpr能力，可以輕而易舉的構造Parser Combinator，對使用者定義的字元串（User defined literal）釋放了巨大的潛力。

前不久在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，解析輸入字元串`"123456"`，輸出結果為`Just (1, "23456")`，即得到了數字1和剩餘字元串`"23456"`，進而可以供下一個Parser使用；若解析失敗，輸出`None`。

對應C++的函數簽名，如下：

這就是Parser的定義了。

根據定義可以實作幾個最基本的Parser，例如比對給定的字元：

`makeCharParser`相當于一個工廠，給定字元`c`，建立比對`c`的Parser。

比對給定集合中的字元：

Parser是可組合的最小單元，Parser與Parser之間可以組合成任意複雜的Parser，而Parser Combinator就是一個高階函數，輸入一系列Parser，輸出複合後的新Parser。

根據定義，可以實作一個Combinator組合兩個Parser，同時根據兩個Parser的結果計算出新的結果，進而得到新的Parser：

由于C++支援操作符重載，那麼可以重載一個二進制操作符來組合兩個Parser，比如從兩個Parser裡取出其中一個Parser的結果産生新的Parser：

取左邊Parser的結果：

取右邊Parser的結果：

有時候需要對同一個Parser進行多次比對，類似正規表達式的`*`操作，這個操作可以看做是`fold`，執行多次Parser直到比對失敗，每次結果傳遞給一個函數運算：

有了`fold`函數，那麼可以很容易實作函數來比對任意多次`many`，比對至少一次`atLeast`：

還有種操作是比對零到一次，類似于正規表達式的`?`操作，這裡我定義為`option`操作：

有了以上基本操作，接下來看看如何運用。

項目中模闆元程式設計比較多，而C++17之前模闆Dependent type（非類型參數）不支援double，得C++20才支援double，臨時方案就是用`template<char... C> struct NumWrapper {};`模拟double的類型，而需要擷取其值的時候，就需要解析字元串了，這些工作應該在編譯期确定。

首先是比對符号`+/-`，若沒有符号，則認為是`+`：

其次是整數部分，也可能沒有，若沒有，則認為是0：

然後是小數點`.`，若沒有小數點，為了不丢失精度，則傳回一個`long`值。

若有小數點，認為是浮點數，傳回其`double`值。

最後我們的`NumWrapper`實作如下，進而可以混入模闆類型體系：

如果僅僅是用于解析數字，那也殺雞用牛刀了，因為在`Parser Combinator`之前的版本，我就是在一個普通的`constexpr`函數中完成解析的，代碼很無趣，但現在我可能想回退代碼了。

這次的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()`掃描，做一次寬度優先搜尋，确定最外層的元素個數，進而依次解析填值。

點選關注，第一時間了解華為雲新鮮技術~