小池有话说

正则表达式的懒惰模式、贪婪模式及回溯

2013-05-18

用正则表达式 /ab+/ 去匹配字符串 "abbb" 会匹配到什么?

也许有人会觉得应该匹配到 ab ,实际上,匹配的是整个字符串 abbb 。正则表达式的默认行为模式是匹配 尽可能多 的字符,这种模式称之为 贪婪 。如果你想匹配 尽可能少 的字符,应该用这个正则 /ab+?/ 。这里的 ?懒惰修饰符 。懒惰修饰符不仅可以修饰 + * ,还可以修饰数量描述。比如 /a{3,8}?/ 会匹配大于3个的尽可能少的 a

我们知道,如果拿正则 /ab+c/ 去匹配字符串 abbbc ,会匹配整个字符串,那么中间到底发生了什么?这个正则表达式是如何匹配的呢?

我们把这个正则分成三个部分 a b+ c 。首先,匹配 a ,匹配成功。接着匹配 b+ ,也匹配成功。 b+ 的含义是匹配一个或多个 p ,它实际上匹配了三个字符 bbb 。在 b+ 匹配失败之前,正则表达式是不会去用 c 匹配的。现在到了字符串中的最后一个字符 c ,正则解析器会继续用 b 匹配(贪婪模式),结果匹配失败。这个时候,正则解析器并不会结束匹配。解析器会 退回 一个字符,然后用 c 去匹配。结果匹配成功。字符串和正则表达式都匹配结束了,再无可匹配的动作,于是匹配结束。

在上述匹配过程中,退回字符的过程就称之为 回溯

如果用 /ab+?c/ 去匹配字符串 abbbc 会发生什么?

和上一个正则不同,这一次的正则的中间部分是 b+? ,是是懒惰模式。a 的匹配和前面一个正则是一样的。 b+? 的含义是匹配一个或多个 b ,但是要尽可能少的匹配。当解析器匹配成功第一个 b 之后, b+? 已经匹配成功了。接着会用正则中的 c 匹配下一个字符(也就是第二个 b )。匹配失败。这个时候,匹配并未结束。解析器会用 b 重新匹配那第二个 b ,匹配成功,然后,解析器前进一个字符,又一次试图匹配 c ,结果失败,那就继续重新匹配 b 。如是者三,最后匹配成功整个字符串。

虽然这两次匹配结果都是成功匹配整个字符串,但是匹配的过程不同。懒惰模式虽然名称叫做懒惰模式,可是不一定减少比较次数,仅仅是将数量选择符的作用数量减少到最少。

回溯有时候会产生巨大的性能的差异。

假设我们需要匹配 html 代码。于是有人写出了这个正则:

<html>\s*<head>([\s\S]*)</head>\s*<body>([\s\S]*)</body>\s*</html>

这个正则是可以工作的。但它做了很多回溯。

当正则匹配到第一个分组 ([\s\S]*) 那里的时候,这个分组里的表达式将会匹配所有的字符,因此,会一直匹配到文件末尾。但整个正则还没有匹配完,因此开始回溯,直到回溯到 </head> 才会停止。 <body> 后的分组 ([\s\S]*) 也存在同样的情况。

对这个正则可以做改进,比如改成懒惰模式。

<html>\s*<head>([\s\S]*?)</head>\s*<body>([\s\S]*?)</body>\s*</html>