The combinator of combinator

來自專欄霧雨魔法店45 人贊了文章

組合子的組合子

大霧~

最近把之前寫的Parser combinator拿了出來, 因為剛好想到一些有趣的東西. 之前的組合子是不能回溯的, 因為所有的組合子的構建是自下而上的, 當前組合子的語法分析只能看到其子組合子的綜合屬性, 返回一條分支的值之後便不再嘗試其他分支. 這會對其表達能力造成一些限制.

一個解決辦法是像一般的Parser combinator一樣, 傳入一個所有的當前分析位置的list, 對每一個位置進行分析, 保存所有分支的結果傳出一個新的list.

我使用的是另一種思路, 對組合子的組合函數進行CPS變換, 這樣每一個組合子除了能看見子組合子的綜合屬性還能看見後續的分析結果, 於是分支選擇變成了可能, 即是對應與Direct style的回溯.

詳細的構造請看文章Parser combinator 在C++里的DSL更新的第4節, 是我新加入噠.

為什麼需要回溯呢? 那當然是我想到了一些好玩的東西啦, 在之前的文章里通過Parser combinator構造了一個小的四則運算計算器, 組合子是:

ParserCombinator<int> Additive

返回的是表達式的語義值, 一個 類型的數值表示算式的值.

於是問題來了, 很自然地會想到一個生成Parser combinator的Parser combinator是什麼呢?

一個典型的最簡單的例子, 正則表達式!

對! 又是正則表達式~

理由很簡單, 在Chomsky hierarchy里, 正則表達式是Type-3 grammars, 弱於Parser combinator描述的Type-2 grammars上下文無關文法. 顯然地, 我們可以使用組合子來構造一個正則表達式的匹配器.

正則表達式的匹配器是一個返回 型的Parser combinator, 返回 表示匹配成功.

對於正則表達式的字元匹配:

ParserCombinator<bool> match;match = (Token(ch) >> Return(true));

是需要匹配的 .

對於正則表達式的連接:

//ParserCombinator<bool> part_1, part_2;ParserCombinator<bool> match;match = part_1 + part_2 >> Return(true);

和 是子表達式.

對於正則表達式的分支 :

ParserCombinator<bool> match;match = part_1 | part_2;

和 是子表達式.

對於正則表達式的閉包:

ParserCombinator<bool> match;match = match + unit >> Return(true) | Epsilon(true);

是子表達式.

有了以上的構造之後可以輕鬆地寫出生成正則表達式組合子:

ParserCombinator<ParserCombinator<bool>> unit, repeat, connection, branch, regex;unit = Token([](char ch) { return ch != ( && ch != ) && ch != | && ch != +; }) >> [](char ch){ ParserCombinator<bool> match; match = (Token(ch) >> Return(true)); return match;} | \_T + Token(AnyChar{}) >> [](Placeholder, char ch){ ParserCombinator<bool> match; match = (Token(ch) >> Return(true)); return match;} | (_T + regex + )_T >> [](Placeholder, const ParserCombinator<bool>& unit, Placeholder){ return unit;};repeat = unit + *_T >> [](const ParserCombinator<bool>& unit, Placeholder){ ParserCombinator<bool> match; match = match + unit >> Return(true) | Epsilon(true); return match;} | unit;connection = connection + repeat >> [](const ParserCombinator<bool>& part_1, const ParserCombinator<bool>& part_2){ ParserCombinator<bool> match; match = part_1 + part_2 >> Return(true); return match;} | repeat;branch = branch + |_T + connection >> [](const ParserCombinator<bool>& part_1, Placeholder, const ParserCombinator<bool>& part_2){ ParserCombinator<bool> match; match = part_1 | part_2; return match;} | connection;regex = branch >> [](const ParserCombinator<bool>& match){ ParserCombinator<bool> regex(match); regex.ReturnDefaultWhenFail(true); //return false return regex;};std::string pattern = "(a|b)*abb";std::string match = "babaababb";std::cout << regex(pattern)(match) << std::endl;//print: 1

看到 了嘛, 於是我們在50行內寫出了一個正則表達式引擎(特大霧).

完整的代碼在這裡下載: Parser Combinator [.zip]

除了簡單的正則表達式, 更加實用的是使用這種方式將一段BNF文法文本自動生成一個Parser.

我感覺我都快成正則表達式專業戶了(笑~). 其實我是用CPS改寫了我的Parser combinator, 更新文章了不過感覺沒什麼人會看到, 於是來水了一篇文章.

(Parser combinator是用C++以一種極其扭曲的FP風格寫出來的, 極其難以調試和測試, 所以保不準會出一些奇怪的bug啊哈)

繼續拓展, 一個能生成生成Parser combinator的Parser combinator的Parser combinator會是什麼呢? 這個嘛...嗯...我不知道. 更加地, 一個能生成自身Parser combinator的Parser combinator又會是什麼呢? (無限嵌套的遞歸類型, C++也里實現不出來呀哈)

知道的小夥伴請告訴我>.<