深度分析正则(pcre)最大回溯/递归限制

 更新时间:2011年04月12日 21:44:51   作者:   我要评论
深度分析正则(pcre)最大回溯/递归限制,需要的朋友可以参考下。
今天,Tank问了一个问题, 对于如下的正则:
复制代码 代码如下:

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

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

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

难道正则对匹配的串有长度限制?
不是, 当然不是, 原因是这样的, 在PHP的pcre扩展中, 提供了俩个设置项.
复制代码 代码如下:

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

默认的backtarck_limit是100000(10万).
这个问题, 就和设置项backtrack_limit有关系. 现在要弄清这个问题的原因, 关键就是什么是”回溯”.
这个正则, 使用非贪婪模式, 非贪婪模式匹配原理简单来说是, 在可配也可不配的情况下, 优先不匹配. 记录备选状态, 并将匹配控制交给正则表达式的下一个匹配字符, 当之后的匹配失败的时候, 再溯, 进行匹配.
举个例子:
复制代码 代码如下:

源字符串: aaab
正则: .*?

匹配过程开始的时候, “.*?”首先取得匹配控制权, 因为是非贪婪模式, 所以优先不匹配, 将匹配控制交给下一个匹配字符”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以后, 提供了:
复制代码 代码如下:

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

我们应该经常检查这个函数的返回值, 当不为零的时候说明上一个正则函数出错, 特别的对于文章的例子, 出错返回(PREG_BACKTRACK_LIMIT_ERROR)
最后, 在顺便说一句, 非贪婪模式导致太多回溯, 必然会有一些性能问题, 适当的该写下正则, 是可以避免这个问题的. 比如将文章开头例子中的正则修改为:
复制代码 代码如下:

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

就不会导致这么多的回溯了~
而recursion_limit限制了最大的正则嵌套层数, 如果这个值, 设置的太大, 可能会造成耗尽栈空间爆栈. 默认的100000似乎有点太大了…
就比如对于一个长度为10000的字符串, 如下这个看似”简”的单正则:
复制代码 代码如下:

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

会导致core, 这是因为嵌套太多, 导致爆栈.
当然, 你可以通过修改栈的大小来暂时的解决这个问题, 比如修改栈空间为20M以后, 上面的代码就能正常运行, 但这肯定不是最完美的解法. 根本之道, 还是优化正则.
最后: 正则虽易, 用好却难.. 尤其在做大数据量的文本处理的时候, 如果正则设计不慎, 很容易导致深度嵌套, 另外考虑到性能, 还是建议能用字符串处理尽量使用字符串处理代替.

相关文章

  • JScript中正则表达函数的说明与应用

    JScript中正则表达函数的说明与应用

    JScript中正则表达函数的说明与应用...
    2006-06-06
  • RegExp 随笔 JavaScript RegExp 对象

    RegExp 随笔 JavaScript RegExp 对象

    这篇文章主要介绍了RegExp 随笔 JavaScript RegExp 对象,需要的朋友可以参考下
    2016-10-10
  • JS和C#实现的两个正则替换功能示例分析

    JS和C#实现的两个正则替换功能示例分析

    这篇文章主要介绍了JS和C#实现的两个正则替换功能,结合具体实例形式分析了js与C#进行字符串正则替换的相关实现方法与注意事项,需要的朋友可以参考下
    2017-06-06
  • linux grep正则表达式与grep用法详解

    linux grep正则表达式与grep用法详解

    在此首先大家要牢记:正则表达式与通配符不一样,它们表示的含义并不相同。正则表达式应用非常广泛,但是大家很少有过整理吧,下面澳门金沙网上娱乐的小编整理了关于正则表达式的描述,还比较详细,在此分享给大家,感兴趣的朋友可以参考下。
    2015-09-09
  • asp.net 正则表达式[经常用的到]

    asp.net 正则表达式[经常用的到]

    经常用的到的一些正则表达式,正则规则是这样写的,大家可以根据自己的需要,用各种语言调用即可
    2008-11-11
  • 获取网址路径的正则

    获取网址路径的正则

    获取网址路径的正则,大家可以自己测试下。
    2009-08-08
  • 正则表达式教程之子表达式用法分析

    正则表达式教程之子表达式用法分析

    这篇文章主要介绍了正则表达式教程之子表达式用法,分析了正则表达式中子表达式的概念、功能与使用方法,需要的朋友可以参考下
    2017-01-01
  • PHP 正则的使用基础入门

    PHP 正则的使用基础入门

    正则表达式,作为一种快速、便捷的处理字符串的工具,在各种编程语言中都有着广泛的用途,通过在PHP中的一些使用,下面记录一下关于PHP中正则使用的一些技巧。
    2009-10-10
  • js中string之正则表达式replace方法详解

    js中string之正则表达式replace方法详解

    本篇文章主要介绍了js中string之正则表达式replace方法详解,replace方法是javascript涉及到正则表达式中较为复杂的一个方法,严格上说应该是string对象的方法。
    2017-03-03
  • 当ES6遇上字符串和正则表达式

    当ES6遇上字符串和正则表达式

    这篇文章主要介绍了当ES6遇上字符串和正则表达式的相关知识,本文通过实例代码给大家介绍的非常详细,具有一定的参考借鉴价值,需要的朋友可以参考下
    2019-08-08

最新评论