※ [本文转录自 PHP 看板 #1Eb53dRp ] 作者: knuckles (那克斯) 看板: PHP 标题: [分享] Regular expression: 贪婪、非贪婪 时间: Tue Oct 11 22:21:23 2011 自己写的一些笔记，给大家参考一下 我也是初学regex的新手，没看过书只看了一些网页教学而已 有什麽错误或观念不对的地方还请大家多多指教 ^^ 网页上色好读版: http://disp.cc/b/11.cj-2q1S 贪婪与非贪婪 当要抓取一段不固定的字串，例如 <b> 与 </b> 中间的字 最常看到的方法就是使用正规表示式 regular expression (以下简称 regex)： /<b>(.*?)<\/b>/ 其中 . 代表任意字元 * 代表前面的字元会出现0~∞次 ? 代表使用非贪婪(non-greedy)的方法 ( ) 代表将匹配的结果输出到要抓取的第一个字串$1 若使用 /<b>(.*)<\/b>/ 则是代表使用贪婪(greedy)的方法 贪婪代表所有可能的匹配结果中，取字元数最多的 非贪婪就是取字元数最少的 如果整个字串确定就只有一组 <b> </b> 的话那匹配的结果就一样 但若是像这样的字串： $string = "000<b>abc</b>1234<b>xxx</b>5678<b>yyy</b>0000"; 贪婪抓到的 <-----------------------------> 非贪婪抓到的 <-> 可以看出使用非贪婪的方法才会抓到正确的结果 非贪婪的效能问题 其实非贪婪还蛮好用的，符号也很简洁，刚开始学会这个就可以应付大部份的情况了 但使用非贪婪的效能不好，当遇到 $string = "<b>很长很长的文章.....</b>" 时 preg_replace("/<b>(.*?)<\/b>/","$1",$string) 可能会直接传出null 一开始还以为是要抓取的字串有长度限制...其实不是，是使用非贪婪造成回溯 (backtracking)次数过多 只要regex改用 /<b>([^<]*)<\/b>/ 这种排除型字符组(Negated Character Classes/Set)就好了 其中 [^<]* 代表除了 < 以外的所有字元，可能有0~∞个 这样就可以使用贪婪的方法，但又不会抓到超过 </b> 的字元了 为什麽使用非贪婪会造成回溯次数过多呢，这要先知道regex匹配字串的方法 举例来说，当 $string = "<b>1234567890</b>" 使用贪婪法 regex 为 /<b>(.*)<\/b>/ 时 $string = "<b>1234567890</b>" <-> 符合regex一开始的<b>，交给下一个符号 .* <------------> 因为 .* 是贪婪，会抓取所有的可能， 然後交给下一个符号 < ^ 发现下一个字元不是 <，回溯 <----------->^ .* 吐一个字元出来给 <，还是不符合，回溯 <---------->^ .* 吐一个字元出来给 <，还是不符合，回溯 <--------->^ .* 吐一个字元出来给 <，还是不符合，回溯 <-------->^ .* 吐一个字元出来给 <，符合了，交给下个符号 <-> 後面的 \/b> 也符合，结束 使用非贪婪法 regex 为 /<b>(.*?)<\/b>/ 时 $string = "<b>1234567890</b>" <-> . . 符合regex一开始的<b>，交给下一个符号 .*? ^ . . 因为.*?非贪婪，空字元就符合了，交给下个符号 < ^ . . 发现下一个字元不是<，回溯 ^ . . .*?抓了一个字元後，交给下个符号 < . . 但下个字元不是 <，回溯 ^ . . .*?再抓一个字元後，交给下个符号 < . . 但下个字元不是 <，回溯 ....... ^ . .*?再抓一个字元後，交给下个符号 < ^ . 下个字元符合 <，交给下个符号 <-> 後面的\/b>也符合，结束 由以上过程可以知道，使用非贪婪法时，要抓取的字串有多少个，就相当於要回溯多少次 所以要抓取的字串很长很长时，自然就爆表了 就算没爆表但效率不佳所以也不是个好方法 排除型字符组的问题 如果使用 /<b>([^<]*)<\/b>/ 这种抓到<之前为止的贪婪法 好像就没有回溯问题了？ 但这又会产生另一个问题 若 $string = "<b>12345<i>italic</i>67890</b>" 会匹配失败，什麽都抓不到 所以必需要明确的定义我们要的是抓到 </b> 之前的字串，而不是只看到 < 就算了 这时候就要用到 lookahead assertion 了 regex的写法为 /<b>((?:(?!<\/b>).)*)<\/b>/ 其中 . 为任意字元 (?!<\/b>) 代表接下来的字串不可以是 <\b> 接在 . 的左边所以 . 与 . 右边三个字元不可以是 <\b> (?: ) 只是用来把 (?!<\/b>) 与 . 包起来 加上 ?: 是为了避免变成要抓取的字串之一 * 代表 (?:(?!<\/b>).) 这个任意但不会是<後面接\b>的字元， 可能会出现 0~∞ 次 终级解决法: once-only + lookahead assertion 但改成这样效率还是不够好，因为要判断每个字元以及他的下三个字元是否为 </b> 能不能只要先检查字元是否为 < 就好，不是的话就检查下一个字元， 是的话再看後面三个字元是否为 /b> 呢？ 这样就要用到 Once-only subpatterns 或叫固化分组 用法： (?>pattern) 其中的pattern只要成功的匹配到一次，就确定用这个匹配的结果 交给下一个符号後，若下一个符号无法匹配， 也不会再回溯到pattern寻找其它的可能 ps. 类似 (?: ) ，pattern 不会被当作要抓取的字串之一 所以再将以上例子的regex改写为 /<b>((?>[^<]*)(?><(?!\/b>)[^<]*)*)<\/b>/ 用在 $string = "<b>xxxxxx<i>iiiii</i>xxxxxx</b>" 时 <->. . . . 符合一开始的<b> <---->. . . 符合接下来的 (?>[^<]*) . . . 因为有加 ?> 不会再回溯到这里 . ^ . . 符合 <(?!\/b>) 也就是一个 . . . . 後面不是接 /b> 的 < 字元 . <-----> . 符合 [^<]* . <------> . 上两个合起来 (?><(?!\/b>)[^<]*) . . . 有加?>不再回溯 . <--------> 第二个 (?><(?!\/b>)[^<]*) . . 也就是<开头到下个<的前一个字元 . . 但不是</b>开头的字串 . . 因为可能有 0~∞ 个，所以再加个 * . . <----------------------> 最後再用 ( ) 将整块包起来当作 要抓取的第一个字串 ^遇到 < 但後面是接 /b> 不符合 (?!<\/b>)< 所以交给後面的符号 <\/b> 发现符合，结束 参考网页: 深度分析正则(pcre)最大回溯/递归限制 http://www.jb51.net/article/26817.htm 小议正则表达式效率 贪婪、非贪婪与回溯 http://www.jb51.net/article/26816.htm PHP正则表达式的效率 回溯与固化分组 http://www.jb51.net/article/26814.htm Regex: long Pattern vs. Short Pattern http://tinyurl.com/3wtx5f3 Once-only subpatterns http://tinyurl.com/3owctlu --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 111.248.0.200 ※ 编辑: knuckles 来自: 111.248.0.200 (10/11 22:22) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 111.248.0.200 ※ 编辑: knuckles 来自: 111.248.0.200 (10/13 03:33) ※ 编辑: knuckles 来自: 111.248.6.95 (10/13 06:47)