perl语言正则表达式非贪婪的数量词

xiaoliu

下面是一个例子：假设在fred and barney went bowling last night 上使用/fred.+barney/进行匹配。我们知道正则表达式
将匹配上，下面我们具体的讲解这一个过程◆。首先，子模式fred 将匹配其对应的字符串。模式的下一部分是.+，它将匹
配除了换行符之外的任意字符，次数大于等于一。。但，由于加号(+)是贪婪的；它将尽可能的进行匹配。因此，它将匹配
剩余的所有字符串，包括night。这可能让你惊奇，但故事还没结束。）
◆正则表达式引擎作了一些优化，真实情况和我们这里讲述的有些不同，这些优化随Perl 的不同版本而可能不同。但也不能说其操作过程
和我们这里讲述的不同。想了解其具体的操作过程，请阅读最新的源码。注意给你发现的bug 提交补丁。
现在对banrey 进行匹配，但不能成功，因为已经到了字符串的结尾处。由于.+在少一个字符的情况下仍能匹配成功，因此
它退回字符串最后一个字母t。（它虽是贪婪的，但更希望整个模式能匹配成功。）
子模式barney 又尝试匹配，结果仍是不行。因此.+再退回字母h，又进行匹配。一个字符接一个字符，.+退回其匹配的字
符，直到其退回了字符串barney。最后，子模式banrey 被匹配上了，现在整个模式都匹配上了。
正则表达式引擎有大量的像上面那样的回退（backtracking）操作，尝试每一种可能，直到成功或者根本不能匹配为止◆。
如本例所显示的那样，这些操作引起了大量的回退操作，因为这些数量词匹配了太多的字符串，正则表达式引擎强迫它们
返回一些。
◆有些正则表达式引擎所采用的方法不同，一旦匹配上则进行下一项的匹配。但Perl 的正则表达式引擎更关心模式是否匹配，因此找到所
有能匹配模式的字符串，引擎工作才算完成。请参看Jeffy Friedl’s 的书《掌握正则表达式》(Mastering Regular Expressions)(O’Reilly)。
因此对于每一个贪婪的数量词，需要一种非贪婪的方法。不是使用加号(+),而是使用非贪婪的数量词+?，它将匹配一次或
多次（加号的意思），但其匹配尽可能少的次数，而非尽可能多的次数。现在我们来看看模式为/fred.+?barney/时的过程。
首先，fred 将被匹配上。接着，模式的下一部分是.+?，它匹配的字符个数不大于1，因此匹配fred 后面的空格。下一个子
模式是banrey，它在这里不能被匹配（因为现在的位置是and barney… 的开头）。.+?再匹配a，剩下的模式继续进行匹配。
又一次，barney 不能匹配上，因此.+?再匹配n，依次类推。当.+?匹配了这5 个字符后，barney 可以被匹配上了，现在模
式匹配成功。
这里也存在一些回退操作，但由于引擎只需回退，并只尝试几次，其在速度上会有很大提高。但，这种提高依赖于banrey
在fred 的附近能被找到。如果数据中fred 在字符串的开头，而barney 在结尾处，则贪婪数量词方法的速度更快。因此，正
则表达式的速度依赖于具体的数据。
非贪婪数量词不仅和效率相关。即便它和其对应的贪婪数量词表达式均能匹配（或者不能匹配）同一个字符串，它们匹配
的部分也可能是不同的。例如，假设你有一些HTML 类型的◆文本，你想移除标记<BOLD>和</BOLD>，而保留其间的
内容。下面是文本：
◆我们不能使用真实的HTML，因为通过简单的正则表达式不能对其进行解析。如果想对HTML 或者某种简单的标记语言进行解析，使用模
块来处理更加恰当。
I’am talking about the cartoon with Fred and <BOLD>Wilma</BOLD>!
下面是一种移除标记的方法。它有什么错误呢？
s#<BOLD>(.*)</BOLD>#$1#g;
其问题出在星号是贪婪的◆。如果文本变成了下面的样子，会得到什么结果？
◆还有另一个问题：我们不得不使用/s 修饰符，因为结束的标记可能和开始的标记不在同一行。幸好我们这里只是练习；在实际代码中，
最好使用模块。
I thought you said Fred and <BOLD>Velma</BOLD>, not <BOLD>Wilma</BOLD>
此时，模式将匹配从第一个<BOLD>到最后一个</BOLD>之间的内容，中间的部分被保留下来。噢！我们需要非贪婪的数
量词。星号的非贪婪的类型是*?，因此此模式应当是：
$#<BOLD>(.*?)</BOLD>#$1#g;
现在它能正确执行了。
由于加号的非贪婪类型是+?，星号的为*?，你可能已经意识到剩下的两种数量词其对应的类型也是类似的。花括号的非
贪婪类型看起来一样，只是在闭花括号后有一个问号，如{5,10}?或者{8,}?◆。甚至问号数量词也有非贪婪类型：??。它匹
配一次或者0 次，但倾向于匹配0 次。
◆理论上，对于单个的数字，也应有非贪婪类型，如{3}?。由于它是指匹配前面一项3 次，则没有任何意义说其是贪婪或者非贪婪的。