小议正则表达式效率 贪婪、非贪婪与回溯
网络编程 2021-07-05 10:07www.168986.cn编程入门
前几天看了鸟哥的BLOG上写的关于正则表达式的回溯与递归的限制时，对贪婪、非贪婪产生的回溯有疑问，遂近段时间，仔细的学习研究了一下，现在把经验心得与大家分享一下。
先扫盲一下什么是正则表达式的贪婪，什么是非贪婪？或者说什么是匹配优先量词，什么是忽略优先量词？
好吧，我也不知道概念是什么，来举个例子吧。
某同学想过滤之间的内容，那是这么写正则以及程序的。
$str = preg_replace('%<script>.+?</script>%i','',$str);//非贪婪
看起来，好像没什么问题，其实则不然。若
$str = '<script<script>alert(document.cookie)</script>>alert(document.cookie)</script>';
那么经过上面的程序处理，其结果为
$str = '<script<script>alert(document.cookie)</script>>alert(document.cookie)</script>';
$str = preg_replace('%<script>.+?</script>%i','',$str);//非贪婪
print_r($str);
//$str 输出为 <script>alert(document.cookie)</script>
仍然达不到他想要的效果。上面的就是非贪婪，也有的叫惰性。其标志非贪婪的标识为量数元字符后面加? ，比如 +?、?、??(比较特殊，以后的BLOG中，我会写到)等。即标识非贪婪，如果不写?就是贪婪。比如
$str = '<script<script>alert(document.cookie)</script>>alert(document.cookie)</script>';
$str = preg_replace('%<script>.+</script>%i','',$str);//非贪婪
print_r($str);
//$str 输出为 <script 只有这些了，好像还是不太合适，哈，您知道如何重写那个正则吗？
以上为贪婪，非贪婪的区别介绍。狼蚁网站SEO优化，聊下贪婪、非贪婪引起的回溯问题。先看个小例子。
正则表达式为\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>.?<\/script>/is";
$str = "<script></script>"; //长度大于100014
$ret = preg_repalce($reg, "", $str); //返回NULL
其原因就是回溯太多了，直到造成耗尽栈空间爆栈。
再来看个例子。
字符串
$str = '<script>123456</script>';
正则表达式为
$strRegex1 = '%<script>.+<\/script>%';
$strRegex2 = '%<script>.+?<\/script>%';
$strRegex3 = '%<script>(?:(?!<\/script>).)+<\/script>%';
这三个正则，分别会造成几次回溯呢？？
答案见下篇 PHP正则表达式的效率回溯与固化分组
好吧，我也不知道概念是什么，来举个例子吧。
某同学想过滤之间的内容，那是这么写正则以及程序的。
代码如下:
$str = preg_replace('%<script>.+?</script>%i','',$str);//非贪婪
看起来，好像没什么问题，其实则不然。若
代码如下:
$str = '<script<script>alert(document.cookie)</script>>alert(document.cookie)</script>';
那么经过上面的程序处理，其结果为
代码如下:
$str = '<script<script>alert(document.cookie)</script>>alert(document.cookie)</script>';
$str = preg_replace('%<script>.+?</script>%i','',$str);//非贪婪
print_r($str);
//$str 输出为 <script>alert(document.cookie)</script>
仍然达不到他想要的效果。上面的就是非贪婪，也有的叫惰性。其标志非贪婪的标识为量数元字符后面加? ，比如 +?、?、??(比较特殊，以后的BLOG中，我会写到)等。即标识非贪婪，如果不写?就是贪婪。比如
代码如下:
$str = '<script<script>alert(document.cookie)</script>>alert(document.cookie)</script>';
$str = preg_replace('%<script>.+</script>%i','',$str);//非贪婪
print_r($str);
//$str 输出为 <script 只有这些了，好像还是不太合适，哈，您知道如何重写那个正则吗？
以上为贪婪，非贪婪的区别介绍。狼蚁网站SEO优化，聊下贪婪、非贪婪引起的回溯问题。先看个小例子。
正则表达式为\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>.?<\/script>/is";
$str = "<script></script>"; //长度大于100014
$ret = preg_repalce($reg, "", $str); //返回NULL
其原因就是回溯太多了，直到造成耗尽栈空间爆栈。
再来看个例子。
字符串
代码如下:
$str = '<script>123456</script>';
正则表达式为
代码如下:
$strRegex1 = '%<script>.+<\/script>%';
$strRegex2 = '%<script>.+?<\/script>%';
$strRegex3 = '%<script>(?:(?!<\/script>).)+<\/script>%';
这三个正则，分别会造成几次回溯呢？？
答案见下篇 PHP正则表达式的效率回溯与固化分组
编程语言
- 如何快速学会编程 如何快速学会ug编程
- 免费学编程的app 推荐12个免费学编程的好网站
- 电脑怎么编程：电脑怎么编程网咯游戏菜单图标
- 如何写代码新手教学 如何写代码新手教学手机
- 基础编程入门教程视频 基础编程入门教程视频华
- 编程演示：编程演示浦丰投针过程
- 乐高编程加盟 乐高积木编程加盟
- 跟我学plc编程 plc编程自学入门视频教程
- ug编程成航林总 ug编程实战视频
- 孩子学编程的好处和坏处
- 初学者学编程该从哪里开始 新手学编程从哪里入
- 慢走丝编程 慢走丝编程难学吗
- 国内十强少儿编程机构 中国少儿编程机构十强有
- 成人计算机速成培训班 成人计算机速成培训班办
- 孩子学编程网上课程哪家好 儿童学编程比较好的
- 代码编程教学入门软件 代码编程教程