支持并、交、差的正则表达式引擎

作者: rockeet 发表日期: 2014年09月08日分类: 自动机评论: 0 条阅读次数: 15,870 次

先强调一点，在我的引擎中，所有正则表达式的语法结构，包括并、交、差、补都是在编译时完成的，对匹配性能无任何影响，切记！…… 现在可以开始了：

正则表达式，描述的是正则语言，学过形式语言与自动机理论的人应该都知道，正则语言在并、交、差、补运算下都是封闭的；但是，根据 Wikipedia 的描述，到目前为止，还没有任何一个已知的正则流派(Flavor)将交和差纳入正则语法。理论与实践之间竟然隔着这么巨大的鸿沟！

并：	A \|\| B	能匹配 A 或者能匹配 B	这三种操作都可以编译为 DFA，从而非常高效地执行匹配
交：	A && B	能匹配 A 并且能匹配 B
差：	A &! B	能匹配 A 但不能匹配 B，即从 A 中排除 B

虽然 Perl 正则中支持的环视(Look Around)在某种意义上可以认为是交和差的受限子集（之所以说是受限，因为你无法自由组合并交差操作）。另一方面，环视在这些引擎中都是以回溯的方式实现的，效率十分低下。

Java 正则引擎支持字符类的并交差(类似[\w&&[^a-f]])，这的确在某些情况下带来了一些便利，但是和本文描述的并交差完全没有可比性(完全不是一个概念)！

Lucene 中有个支持并交差的正则引擎，看它的代码，是借鉴了 brics.dk/automaton 的，效率很差，并且不支持多正则匹配。

其实，不光正则语言在并、交、差、补运算下都是封闭的，而且，用来表达正则语言的 DFA 可以比较高效地实现这些操作，补运算的复杂度是O(n) ，并交差的复杂度是O(n*m)；这比 NFA 转 DFA 的 O(2ⁿ) 要乐观地多，而且，这只是最坏情况下的复杂度，现实中很多时候都是 O((m+n)^1+ε)，这其中的 ε 往往接近于0。虽然 NFA 转 DFA 的 O(2ⁿ) 在现实中也往往是 O(n^1+ε)，不过指数爆炸也时有发生，发生的概率比并交差要大不少。

经过一番努力，我填补了交、差这个鸿沟，为了语言的完备性和易用性，同时也实现了传统正则的并、连接、重复，为了区别于传统的 RegEx，暂且把它叫做 RegEx++。

在语言设计上，一方面为了避免处理无比复杂的转义、字符类、unicode之类的泥潭，另一方面也为了兼容传统的正则，我设计的 RegEx++ 语言分为两部分，一部分是去除了环视和反向引用的Perl正则(re2语法)，一部分是 RegEx++ 特有的并、交、差、连接、重复。

以 BNF 范式表达

Union  := Inter { '||' Union }
Inter  := ConCat { '&&' ConCat | '&!' ConCat }
ConCat := Repeat { Repeat }
Repeat := Atom [ ( '?' | '*' | '+' | Range ) [ ':' Atom ] ]
Atom   := '{{' PlainOldRegex '}}' | '(' Union ')'
Range  := '{' Min [ ',' Max ] | ',' Max '}'

Union := Inter { '||' Union }

Inter := ConCat { '&&' ConCat | '&!' ConCat }

ConCat := Repeat { Repeat }

Repeat := Atom [ ( '?' | '*' | '+' | Range ) [ ':' Atom ] ]

Atom := '{{' PlainOldRegex '}}' | '(' Union ')'

Range := '{' Min [ ',' Max ] | ',' Max '}'

用更通俗的方式表达

优先级	操作符	说明
最高	{{Plain Old Regex}}	{{}}括起来的部分是传统的正则表达式，使用 re2 的 Parser 解析
较高	( )	调整优先级
高	?	重复:0次或1次	语法和意义与传统正则相同
	*	重复:0次或多次
	+	重复:1次或多次
	{min,max}	重复:最少min次，最多max次
中	无操作符	连接，连着写就行
低	&&	交，x && y 表示既能匹配 x 又能匹配 y
	&!	差，x &! y 表示能匹配 x 但不能匹配 y
最低	\|\|	并，x \|\| y 表达能匹配 x 或者能匹配 y

优先级一列中，处于同一组的操作符优先级相同，其中优先级最低的四个操作：连接、交、差、并都是左结合的，其中连接、交、并遵守结合律，交、并还遵守交换律。

这里面唯一比较别扭的是{{ }}括起来的 Plain Old Regex，一个语法正确并且规范的正则表达式中不会出现 {{ 和 }}，只有一个例外：\{{，这个例外很容易处理。其实严格讲，语法正确的正则表达式中可以出现 {{ 和 }}，但这样正则表达式往往是有问题的，{ 和 } 用作非元字符时，需要转义（\{和\}），而 { 和 } 不转义时是元字符，不会出现 {{ 和 }}， Plain Old Regex 允许未转义的 { 和 } 是为了最大限度地“容忍错误”，传统正则语法甚至容忍这样的正则: [[[[]*，还有 ]{{1-2}，你知道这都是什么意思吗？

还有一点，这里的重复 {min,max} 语法比 Plain Old Regex 中的 {min,max} 要严格，不光要语法正确，而且要规范，不“容忍”任何错误，下面是几种特殊情况：

{min,}	表示最大次数不限	语法正确且规范时语义和 Plain Old Regex 相同中间不能有空格
{,max}	等价于 {0,max}
{,} 或 {0,}	等价于 *
{1,}	等价于 +
{0,1}	等价于 ?
{num}	等价于 {num,num}

补运算我没有单独实现，因为可以用一个非常简单的语法来表达：X 的补就是 {{.*}} &! X

非贪心匹配(Lazy Match / NonGreedy Match)

与传统正则引擎不同，这里的非贪心匹配也是用 DFA 实现的。通用的非贪心匹配在大多数 “资深” 的正则引擎专家眼里，只能用回溯法实现，我也在很长时间内被这种论调蒙蔽了心智，很可悲！

最近(2014-09-23)我忽然意识到，非贪心匹配也许可以用 DFA 实现，经过仔细思考，从理论上证明了这一点。

于是我新增加了非贪心连接操作符(:)，A# : B，其中 # 是任意最少重复 0 次的 repeat 操作符，表示非贪心匹配 A#，后面跟个 B。A# : B 在功能上等价于 ( A# &! (A* B A*)+ ) B，在 regex_build 内部，A# : B 就是 ( A# &! (A* B A*)+ ) B 的语法糖。

当非贪心连接前面的 repeat 操作符的最小重复次数大于0时，最小重复次数不能被“非贪心”掉，在 regex_build 中，针对这种情况进行了自动重写(rewrite)，重写规则举例如下：

重写前	重写后	说明
A+ : B	*A (A : B)**
A{3,3} : B	A{3} B	此时就是普通连接(concat)
A{3,5} : B	A{3}(A{0,2} : B)
A{3,} : B	*A{3}(A : B)**

最后

下面这个测试页面可以看到一些例子和相应的 DFA/NFA 状态转移图，我做这个页面的初衷是为了辅助调试。在新窗口中打开该页面