boost pcre Greta RE2 正则表达式性能测试

本站寻求有缘人接手，详细了解请联系站长QQ1493399855

算法：

a depth-first search of the pattern tree： pcre 称其为 NFA ，一条路径，需回溯，反复遍历输入输入字符串。

a breadth-first search of the tree： pcre 称其为 DFA ，Google RE2 称其为 Thompson NFA ，所有路径，不需回溯，输入字符串只需遍历一次。类似 NFA 转 DFA 算法 Powerset construction 的过程。

 

DFA 不需要回溯，理论性能比 NFA 要强，但缺点是不能实现 back references，这点确实得到了 Google RE2 的印证。但奇怪的是 pcre 文档说自己的 DFA 实现比 NFA 实现要慢。同时 pcre 的 DFA 不支持 capturing parentheses （小括号捕获），导致大多数测试无法进行，故没有做 pcre DFA 测试。