msgbartop
PHP语言, PHP扩展, Zend引擎相关的研究,技术,新闻分享 – 左手代码 右手诗
msgbarbottom

08 Jun 10 深悉正则(pcre)最大回溯/递归限制

今天,Tank问了一个问题, 对于如下的正则:

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

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

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

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

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

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

默认的backtarck_limit是100000(10万).

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

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

举个例子:

源字符串: aaab
正则:     .*?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以后, 提供了:

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

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

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

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

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

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

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

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

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

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

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


分享到:



Random Posts:

Tags: , , ,

28 Responses to “深悉正则(pcre)最大回溯/递归限制”

  1. PHP教程:基于正则表达式替换的模板引擎 – 优读网 |

    [...] 1、2010, Laruence 《深悉正则(pcre)最大回溯/递归限制》 [...]

  2. xiaoq |

    更正一下:
    最后一段代码
    $ret = preg_repalce($reg, “”, $str);
    应该是replace而不是repalce.

  3. 立Q |

    最近确实遇到了正则匹配html标签对得问题,之前是通过“非贪婪”的方式来获取如/.*?/is,但也“如愿以偿”地得到了超过回溯限制的错误提示,也正因此搜索到了这篇文章,因此我就尝试探索一种不受回溯限制的写法,最后我得到了如下写法/(?<!script).*?/is,即采用否定逆序/顺序环视的写法,但是我不确定这种写法带来的性能上的问题是怎样的?有没有高手指点?!

  4. 模板引擎正则表达式调试小技巧 | 聚沙笔记 |

    [...] 1、2010, Laruence 《深悉正则(pcre)最大回溯/递归限制》 [...]

  5. coldstar |

    /[^<]*/is
    这个例子也有是错误的,如果要匹配的内容中,含有 < 这个符号,将不会匹配到任何内容。
    如:

    function test(){
    if ( 1 < 2){
    alert '1';
    }else{
    alert '2';
    }
    return true;
    }

  6. 如何调试PHP的Core之获取基本信息 | 风雪之隅 |

    [...] 比如我之前文章中介绍深悉正则(pcre)最大回溯/递归限制). [...]

  7. 深悉正则(pcre)最大回溯/递归限制 | 万维网黑客联盟 |

    [...] 本文地址: http://www.laruence.com/2010/06/08/1579.html [...]

  8. 李惟 |

    还是正则回溯默认值的问题,麻烦帮忙看看,谢谢。

    http://bbs.phpchina.com/thread-208687-1-1.html

  9. Rains |

    php运行时配置:
    PCRE Configuration Options Name Default Changeable Changelog
    pcre.backtrack_limit “100000″ PHP_INI_ALL Available since PHP 5.2.0.
    pcre.recursion_limit “100000″ PHP_INI_ALL Available since PHP 5.2.0.

  10. 半瓶子醋 » [PHP]正则(pcre)最大回溯/递归限制 |

    [...] 转自[风雪之隅] [...]

  11. Anders |

    这么简单的事情,这么大的数据量 为什么要用正则来解决呢?

  12. CFC4N |

    鸟哥,函数写错了
    $ret = preg_repalce($reg, “”, $str);
    应该是preg_repLAce..手误哈,。

  13. 小议正则表达式效率:贪婪、非贪婪与回溯 | CNXCT小组的博客 |

    [...] 前几天看了鸟哥的BLOG上写的关于正则表达式的回溯与递归的限制时,对贪婪、非贪婪产生的回溯有疑问,遂近段时间,仔细的学习研究了一下,现在把经验心得与大家分享一下。 (我日,这里好像被左侧的图挡着了,换行换行凑字数,换行换行凑字数,换行换行凑字数,换行换行凑字数,换行换行凑字数,换行换行凑字数,换行换行凑字数,换行换行凑字数,换行换行凑字数,换行换行凑字数,换行换行凑字数,换行换行凑字数,换行换行凑字数,换行换行凑字数,换行换行凑字数) 先扫盲一下什么是正则表达式的贪婪,什么是非贪婪?或者说什么是匹配优先量词,什么是忽略优先量词? 好吧,我也不知道概念是什么,来举个例子吧。 某同学想过滤….之间的内容,那是这么写正则以及程序的。 [...]

  14. Brhum |

    你这个wp主题在IE6下乱的不成样子~~~~

  15. shzhrui |

    $reg 也存在长度过大会出错
    每当国家各种会议期间,都会有大量的关键词要屏蔽。
    目前只能分批进行匹配,这样做在性能方法定有所下降。,不知高人有何其它解决方法。或者从原理上给分析下。。

  16. 神仙 |

    我最开始用正则表达式来搞关键词匹配,词少的时候没事,词一多就撞上那个限制了……
    然后php的pcre包里没那个dfa, nfa的转换

  17. 饼饼 |

    匹配过程开始的时候, “.*?”首先取得匹配控制权, 因为是非贪婪模式
    .*? 这个不算贪婪么?

  18. 雪候鸟 |

    @N 谢谢指正,是写错了, 手误. 至于第二个问题, 你是哪里没看明白呢?

  19. N |

    1.开头的正则是不小心写错的吗?

    2.用非贪婪匹配的话,回溯数就是最小匹配的字符数,文章中说到因为match自身的逻辑,回溯数会加3,那么“********”中的”*****”长度超过99997(100000-3)就会匹配失败,我是这么理解的。但是“因为默认的backtrack_limit是100000, 源字符串的开头是9 个字符, 一共是99997个字符.”这句话我没看明白。

  20. 雪候鸟 |

    @胖子 你们的队形很整齐.

  21. 胖子 |

    学习了,回忆正则

  22. 创意网 |

    学习……同时回忆正则。…..

  23. 雪候鸟 |

    @神仙 恩,是有这个限制, 不过一般来说, 这个限制咱们倒不会触及, :)

  24. 〤依然特雷西 |

    谢谢鸟哥..解释出了我 在PPC上的困惑的问题..http://bbs.phpchina.com/thread-184862-1-1.html

  25. 神仙 |

    记得还有正则表达式的最大长度限制,默认貌似是64k

  26. yufeng |

    学习……同时回忆正则。

  27. 小熊 |

    还有这等事,学习了。
    劳伦斯威武

  28. Skiyo |

    明白了哈 多谢鸟哥

Leave a Reply

*