支持 并、交、差 的正则表达式引擎
先强调一点,在我的引擎中,所有正则表达式的语法结构,包括 并、交、差、补 都是在编译时完成的,对匹配性能无任何影响,切记!…… 现在可以开始了:
正则表达式,描述的是正则语言, 学过形式语言与自动机理论的人应该都知道,正则语言在并、交、差、补运算下都是封闭的;但是,根据 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(2n) 要乐观地多,而且,这只是最坏情况下的复杂度,现实中很多时候都是 O((m+n)1+ε),这其中的 ε 往往接近于0。虽然 NFA 转 DFA 的 O(2n) 在现实中也往往是 O(n1+ε),不过指数爆炸也时有发生,发生的概率比并交差要大不少。
经过一番努力,我填补了交、差这个鸿沟,为了语言的完备性和易用性,同时也实现了传统正则的并、连接、重复,为了区别于传统的 RegEx,暂且把它叫做 RegEx++。
在语言设计上,一方面为了避免处理无比复杂的转义、字符类、unicode之类的泥潭,另一方面也为了兼容传统的正则,我设计的 RegEx++ 语言分为两部分,一部分是去除了环视和反向引用的Perl正则(re2语法),一部分是 RegEx++ 特有的 并、交、差、 连接、重复。
以 BNF 范式表达
1 2 3 4 5 6 |
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 状态转移图,我做这个页面的初衷是为了辅助调试。在新窗口中打开该页面