视频1 视频21 视频41 视频61 视频文章1 视频文章21 视频文章41 视频文章61 推荐1 推荐3 推荐5 推荐7 推荐9 推荐11 推荐13 推荐15 推荐17 推荐19 推荐21 推荐23 推荐25 推荐27 推荐29 推荐31 推荐33 推荐35 推荐37 推荐39 推荐41 推荐43 推荐45 推荐47 推荐49 关键词1 关键词101 关键词201 关键词301 关键词401 关键词501 关键词601 关键词701 关键词801 关键词901 关键词1001 关键词1101 关键词1201 关键词1301 关键词1401 关键词1501 关键词1601 关键词1701 关键词1801 关键词1901 视频扩展1 视频扩展6 视频扩展11 视频扩展16 文章1 文章201 文章401 文章601 文章801 文章1001 资讯1 资讯501 资讯1001 资讯1501 标签1 标签501 标签1001 关键词1 关键词501 关键词1001 关键词1501 专题2001
php正则表达式效率贪婪、非贪婪与回溯分析
2020-11-27 20:32:28 责编:小采
文档


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

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

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

$str = preg_replace('%

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

$str = '

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

结果为

$str = 'alert(document.cookie)>alert(document.cookie)'; 
$str = preg_replace('%
输出为

仍然达不到他想要的效果。上面的就是非贪婪,也有的叫惰性。其标志非贪婪的标识为量数元字符后面加? ,比如 +?、*?、??(比较特殊,以后的BLOG中,我会写到)等。即标识非贪婪,如果不写?就是贪婪。比如

$str = 'alert(document.cookie)>alert(document.cookie)'; 
$str = preg_replace('%
输出为

以上为贪婪,非贪婪的区别介绍。下面,聊下贪婪、非贪婪引起的回溯问题。先看个小例子。
正则表达式为\w*(\d+),字符串为cfc456n,那么,这个正则匹配的$1是多少??

如果您回答是 456,那么,恭喜你,回答错了,其结果不是456,而是6,您知道为什么吗?

CFC4N来解释一下,当正则引擎用正则\w*(\d+)去匹配字符串cfc456n时,会先用\w*去匹配字符串cfc456n,首先,\w*会匹配字符串cfc456n的所有字符,然后再交给\d+去匹配剩下的字符串,而剩下的没了,这时,\w*规则会不情愿的吐出一个字符,给\d+去匹配,同时,在吐出字符之前,记录一个点,这个点,就是用于回溯的点,然后\d+去匹配n,发现并不能匹配成功,会再次要求\w*再吐出一个字符,\w*会先再次记录一个回溯的点,再吐出一个字符。这时,\w* 匹配的结果只有cfc45了,已经吐出6n了,\d+再去匹配6,发现匹配成功,则会通知引擎,匹配成功了,就直接显示出来了。所以,(\d+)的结果是6,而不是456。

当上面的正则表达式改为 \w*?(\d+)(注意,此处为非贪婪),字符串仍然为cfc456n,那么,这时候,正则匹配的$1是多少??
甲同学回答:结果是 456。
嗯,是的,正确,是456,CFC4N弱弱的问下,为什么是456 呢?
我在来解释一下 为什么是456
正则表达式有条规则,是量词优先匹配,所以\w*?会先去匹配字符串cfc456,由于\w*?是非贪婪,正则引擎会用表达式\w+?每次仅匹配一个字符串,然后再将控制权交给后面的\d+去匹配下一个字符,同时,记录一个点,用于在匹配不成功的时候,返回这里,再次匹配,也就是回溯点。由于\w后面是量词是*,*表示0到无数次,所以,首先是0次,也就是\w*?匹配个空,记录回溯点,将控制权交给\d+,\d+去匹配cfc456n的第一个字符c,然后,匹配失败,于是乎,接着讲控制权交给\w*?去匹配cfc456n的c,\w*?匹配c成功,由于是非贪婪,所以,他每次只匹配一个字符,记录回溯点,然后再将控制权交给\d+匹配f,接着,\d+匹配f再失败,再把控制权给\w*,\w*?再匹配c,记录回溯点(这时\w*?匹配结果是cfc了),再把控制权给\d+,\d+去匹配4,匹配成功,然后,由于量词是+,就是1到无数次,所以,接着往后匹配,再匹配5,成功,再接着,再匹配6,成功,再接着,继续匹配操作,下一个字符是n,匹配失败,这时,\d+会吧控制权交出去。由于\d+后面已经没有正则表达式了,所以,整个正则表达式宣告匹配完成,其结果就是 cfc456, 其中第一组结果是456。亲爱的同学,您明白刚刚的题目的结果,为什么是456了吗?

好了,您是否从上面的例子了解了贪婪,非贪婪的匹配原理了?那您是否明白您在什么时候需要使用贪婪,非贪婪去处理您的字符串了?
鸟哥的文章里讲到针对表达式、程序为

$reg = "/.*?<\/script>/is"; 
$str = "

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

再来看个例子。

字符串

$str = '

正则表达式为

$strRegex1 = '%.+<\/script>%'; 
$strRegex2 = '%.+?<\/script>%'; 
$strRegex3 = '%

下载本文
显示全文
专题