贪婪与非贪婪

beyes

正则表达式的量词，如 + 和 * 是具有贪婪性的，也就是说，在保证整体匹配的前提下，它们会尽量匹配长字符串，实在不行才会吐出一点，而吐这个动作可称为“回溯” 。下面分析贪婪与回溯的过程：

假如有一个字符串为：Have you read the article on information revolution 。

假设有一匹配 /article.+information/ ，很容易知道，它匹配 article on information 这一部分内容。但是正则表达式引擎如何找到这个匹配呢？比较自然的是，先会找到 article 这个单词，接着匹配 .+ 这部分内容。由于 + 是具有贪婪性的，所以它不会乖乖的只匹配到 on 后面的空格处就戛然而止，而是会吞噬整个 article 后面的所有内容。然后开始匹配 information 这部分内容了，但是由于之前的 .+ 已经将后面的整个字符串吃掉，所以 information 就无法进行匹配了。这时候就需要 .+ 吐出前面所吞噬的内容了，每次吐出一个，然后再比较一下吐出来的东西是否能够和 information ，不匹配的话则继续吐，直到最终匹配或没有匹配为止。这个不断吐出来的过程称之为 “回溯” 。

然而，对于每一个贪婪的量词来说，都有一个与之对应的非贪婪的量词。以加号(+)来说，它的非贪婪形式是 +? (* 的非贪婪形式为 *?)。对于一些情况来说，非贪婪特性要比贪婪特性效率要来得高一些。比如在上面所举得例子里，使用非贪婪特性后，它每次小心谨慎的吃进一个字符后进行匹配比较，比如先吃掉 article 后的空格，然后比较有没有 information 的匹配，如果没有，那么继续往前吃进一个字符，接着继续比较，如此依次下去，直到模式最终能够匹配成功。

对于上面所举例子，在非贪婪特性的匹配下，可能只需要吞进 4 个字符后 (一个空格+or+一个空格)后便可以得到匹配，这比使用贪婪特性来说提高了效率。但是情况并非如此，因为这是在 article 和 information 之间的距离比较近时才会成立，反之如果距离较大，那么也许使用贪婪特性的效率就更高了。

贪婪特性和非贪婪特性之间的差异并不只是和效率有关，也可跟最终得到的匹配结果有关。下面的例子使用贪婪特性和非贪婪特性去掉 <bold> 和 </bold> 这种 html 标签，最终得出的结果是不相同的，考虑下面的代码：
[code=perl]#!/usr/bin/perl

$_ = "Those people go <bold>around</bold> preaching <bold>revolution</bold>";

s#<bold>(.*)</bold>#$1#g;

print "$_\n";

$_ = "Those people go <bold>around</bold> preaching <bold>revolution</bold>";

s#<bold>(.*?)</bold>#$1#g;

print "$_\n";[/mw_shl_code]
运行输出：

# ./greed.pl
Those people go around</bold> preaching <bold>revolution
Those people go around preaching revolution

由输出可见，使用非贪婪形式可以过滤掉 bold 标签(包括 <bold> 和 </bold>)，这是因为，正是因为非贪婪形式是逐步逼近式，发现一对则消灭一对，而不像贪婪形式那样囫囵吞枣一下子从头吃到尾，又兼之正则表达式的“贪功”性质，一旦发现匹配，马上返回邀功。

deadgirl

好，很好，看了就明白多了