注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

@fc_lamp

关注Web应用解决方案MySql/PHP/Python一盏名为"飞川"的灯~

 
 
 

日志

 
 

什么是正则 最大回溯/递归限制  

2012-08-17 17:05:05|  分类: Web技术-正则表达 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
对于如下的正则:


/<script>.*?<\/script>/is

当要匹配的字符串长度大于100014的时候, 就不会得出正确结果:


  1. $reg = "/<script>.*?<\/script>/is";
  2. $str = "<script>********</script>"; //长度大于100014
  3. $ret = preg_replace($reg, "", $str); //返回NULL


难道正则对匹配的串有长度限制?

不是, 当然不是, 原因是这样的, 在PHP的pcre扩展中, 提供了俩个设置项.


  1. 1. pcre.backtrack_limit //最大回溯数
  2. 2. pcre.recursion_limit //最大嵌套数


默认的backtarck_limit是100000(10万).

这个问题, 就和设置项backtrack_limit有关系. 现在要弄清这个问题的原因, 关键就是什么是”回溯”.

这个正则, 使用非贪婪模式, 非贪婪模式匹配原理简单来说是, 在可配也可不配的情况下, 优先不匹配. 记录备选状态, 并将匹配控制交给正则表达式的下一个匹配字符, 当之后的匹配失败的时候, 再溯, 进行匹配.

举个例子:


  1. 源字符串: aaab
  2. 正则: .*?b


匹配过程开始的时候, “.*?”首先取得匹配控制权, 因为是非贪婪模式, 所以优先不匹配, 将匹配控制交给下一个匹配字符”b”, “b”在源字符串位置1匹配失败(“a”), 于是回溯, 将匹配控制交回给”.*?”, 这个时候, “.*?”匹配一个字符”a”, 并再次将控制权交给”b”, 如此反复, 最终得到匹配结果, 这个过程中一共发生了3次回溯.(请仔细读此段)

现在我们来看看文章开头的例子, 默认的backtrack_limit是100000, 而源字符串的开头是9个字符, 一共是99997个字符.

另外, 因为match函数自身的逻辑, 在文章开头的例子下, 会导致回溯计数增3(有兴趣的可以参看pcrelib/pcre_exec.c中match函数逻辑部分), 所以在匹配到"“之前, pcre中的回溯计数刚好是100000,于是就正常匹配, 退出.

而, 只要在增加一个字符, 就会导致回溯计数大于100000, 从而导致匹配失败退出.

在PHP 5.2以后, 提供了:


  1. int preg_last_error ( void )
  2. Returns the error code of the last PCRE regex execution.


我们应该经常检查这个函数的返回值, 当不为零的时候说明上一个正则函数出错, 特别的对于文章的例子, 出错返回(PREG_BACKTRACK_LIMIT_ERROR)

最后, 在顺便说一句, 非贪婪模式导致太多回溯, 必然会有一些性能问题, 适当的该写下正则, 是可以避免这个问题的. 比如将文章开头例子中的正则修改为:


/<script>[^<]*<\/script>/is


就不会导致这么多的回溯了~

而recursion_limit限制了最大的正则嵌套层数, 如果这个值, 设置的太大, 可能会造成耗尽栈空间爆栈. 默认的100000似乎有点太大了…

就比如对于一个长度为10000的字符串, 如下这个看似”简”的单正则:


  1. //默认recursion_limit为100000
  2. $reg = /(.+?)+/is;
  3. $str = str_pad("laruence", 10000, "a"); //长度为1万
  4. $ret = preg_repalce($reg, "", $str);

会导致core, 这是因为嵌套太多, 导致爆栈.

当然, 你可以通过修改栈的大小来暂时的解决这个问题, 比如修改栈空间为20M以后, 上面的代码就能正常运行, 但这肯定不是最完美的解法. 根本之道, 还是优化正则.

最后: 正则虽易, 用好却难.. 尤其在做大数据量的文本处理的时候, 如果正则设计不慎, 很容易导致深度嵌套, 另外考虑到性能, 还是建议能用字符串处理尽量使用字符串处理代替.

本文来源:http://www.laruence.com/2010/06/08/1579.html?cp=3#comments


什么是正则 最大回溯/递归限制 - fc_lamp - @fc_lamp
 
  评论这张
 
阅读(471)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017