小议正则表达式效率 贪婪、非贪婪与回溯

先扫盲一下什么是正则表达式的贪婪,什么是非贪婪?或者说什么是匹配优先量词,什么是忽略优先量词?

好吧,我也不知道概念是什么,来举个例子吧。


某同学想过滤之间的内容,那是这么写正则以及程序的。


复制代码 代码如下:

$str = preg_replace('%%i','',$str);//非贪婪


看起来,好像没什么问题,其实则不然。


复制代码 代码如下:

$str = 'alert(document.cookie)>alert(document.cookie)';


那么经过上面的程序处理,其结果为

复制代码 代码如下:

$str = 'alert(document.cookie)>alert(document.cookie)';

$str = preg_replace('%%i','',$str);//非贪婪

print_r($str);

//$str 输出为


仍然达不到他想要的效果。

上面的就是非贪婪,也有的叫惰性。

其标志非贪婪的标识为量数元字符后面加? ,比如 +?、*?、??(比较特殊,以后的BLOG中,我会写到)等。

即标识非贪婪,如果不写?就是贪婪。

比如

复制代码 代码如下:

$str = 'alert(document.cookie)>alert(document.cookie)';

$str = preg_replace('%%i','',$str);//非贪婪

print_r($str);

//$str 输出为 /is";

$str = ""; //长度大于100014

$ret = preg_repalce($reg, "", $str); //返回NULL


其原因就是回溯太多了,直到造成耗尽栈空间爆栈。



再来看个例子。


字符串

复制代码 代码如下:

$str = '';


正则表达式为

复制代码 代码如下:

$strRegex1 = '%%';

$strRegex2 = '%%';

$strRegex3 = '%).)+%';


这三个正则,分别会造成几次回溯呢??


答案见下篇 PHP正则表达式的效率:回溯与固化分组

0.225243s