Perl Cd Bookshelf [Electronic resources] نسخه متنی

6.15. Greedy and Non-Greedy Matches

6.15.1. Problem

You have a pattern with a greedy
quantifier like *, +,
?, or { }, and you want to stop
it from being greedy.

A classic example is the naïve substitution to remove tags
from HTML. Although it looks appealing,
s#<TT>.*</TT>##gsi deletes everything
from the first open TT tag through the last
closing one. This would turn "Even
<TT>vi</TT> can
edit <TT>troff</TT>
effectively." into "Even
effectively", completely changing the meaning of
the sentence!

6.15.2. Solution

Replace the offending greedy quantifier with the corresponding
non-greedy version. That is, change *,
+, ?, and {
} into *?, +?,
??, and { }?, respectively.

6.15.3. Discussion

Perl
has two sets of quantifiers: the maximal
ones—*, +,
?, and { }—and the
minimal ones—*?,
+?, ??, and
{ }?. Less formally, these two sorts of
quantifiers are often referred to as greedy and
non-greedy (or sometimes
lazy), respectively. For instance, given the
string "Perl is
a Swiss Army
Chainsaw!", the pattern
/(r.*s)/ matches "rl
is a Swiss
Army Chains", whereas
/(r.*?s)/ matches "rl
is".

With maximal quantifiers, when you ask to match a variable number of
times, such as zero or more times for * or one or
more times for +, the matching engine prefers the
"or more" portion of that description. Thus
/foo.*bar/ matches the first
"foo" through the last "bar" in
the string, rather than only through the next
"bar" as some might expect. That's because the
greedy .* first expands to the rest of the string,
but since that wouldn't leave any characters for
"bar" to match, the engine backs up one character
at a time until it finds "bar".

To make any repetition operator match minimally instead of maximally,
add an extra ?. So *? still
matches zero or more times, but rather than match as much as it can,
the way * would, it matches as little as it can.

# greedy pattern
s/<.*>//gs; # try to remove tags, very badly
# nongreedy pattern
s/<.*?>//gs; # try to remove tags, better (but still rather badly)

This approach doesn't remove tags from all possible HTML correctly,
because a single regular expression is seldom an acceptable
replacement for a real parser. See Recipe 20.6 for the right way.

Minimal matching isn't all it's cracked up to be. Don't fall into the
trap of thinking that including the partial pattern
BEGIN.*?END in a pattern amidst other elements
will always match the shortest amount of text between occurrences of
BEGIN and END. Consider the
pattern /BEGIN(.*?)END/. If matched against the
string "BEGIN and
BEGIN and
END", $1 would contain
"and BEGIN
and". This is probably not what you want.

Imagine trying to pull out everything between bold-italic pairs:

<b><i>this</i> and <i>that</i> are important</b>
 Oh, <b><i>me too!</i></b>

A pattern to find only text between bold-italic
HTML pairs, that is, text that doesn't include them, might appear to
be:

m{ <b><i>(.*?)</i></b> }sx

You might be surprised to learn that the pattern doesn't find such
pairs. Many people incorrectly understand this as matching a
"<b><i>" sequence, then anything up to
a "</i></b>" sequence, leaving the
intervening text in $1. While it often works out
that way due to the input data, that's not what
it says. There's nothing in that pattern that says
.*? can't match
"<b><i>" again (and again and again)
before it comes to "</i></b>". If the
intention were to extract only stuff between
"<b><i>" and its
corresponding
"</i></b>", with no other bold-italic
tags in between, that pattern would be incorrect.

If the string in question is just one character, and if what follows
the minimal match is not a literal character, a negated class is
remarkably more efficient than a minimal match, as in
/X([^X]*)X/. But the general way to say "match
BEGIN, then not BEGIN, then END" for any arbitrary values of BEGIN
and END would be as follows (this also stores the intervening part in
$1):

/BEGIN((?:(?!BEGIN).)*)END/s

or, more legibly:

{
BEGIN               # locate initial portion
(                   # save this group into $1
(?:             # non-capturing group
(?! BEGIN)  # assert: can't be at another BEGIN
.           # now match any one character
) *             # entire group 0 or more 
)                   # end $1 group
END                 # locate final portion
}sx

However, this might not be what you're after, either. The greedy star
quantifier means that the non-BEGIN portion in $1
will be maximized, giving fence posts of the last BEGIN through not
the first END, but the last one. So if your string were:

$_ = "BEGIN1 BEGIN2 BEGIN3 3END 2END 1END";

$1 would contain "3 3END 2END
1". Making the quantifier a minimal matching one:

/BEGIN((?:(?!BEGIN).)*?)END/s

puts "3 3" in $1 for you. Now
add another lookahead negation, (?!END), next to
the existing one. Written out with plenty of whitespace, we now have:

m{
BEGIN           # locate initial portion
(               # save this group into $1
(?:         # non-capturing group
(?! BEGIN   )   # can't be at a BEGIN 
(?! END     )   # also can't be at an END
.               # finally, match any one char
) *         # repeat entire group ad libitum
)               # end $1 capture
END
}sx

Instead of adding another lookahead, another possibility is to use
alternation within the existing one:
(?!BEGIN|END). Applying this approach to the
HTML-matching code, we end up with something like:

m{ <b><i>(  (?: (?!</b>|</i>). )*  ) </i></b> }sx

or perhaps:

m{ <b><i>(  (?: (?!</[ib]>). )*  ) </i></b> }sx

Jeffrey Friedl points out that this quick-and-dirty method isn't
particularly efficient. He suggests crafting a more elaborate pattern
when speed matters, such as:

m{
<b><i>
[^<]*  # stuff not possibly bad, and not possibly the end.
(?:
# at this point, we can have '<' if not part of something bad
(?! </?[ib]>  )    # what we can't have
<                  # okay, so match the '<'
[^<]*              # and continue with more safe stuff
) *
</i> </b>
}sx

This is a variation on Jeffrey's unrolling-the-loop technique,
described in Chapter 6 of Mastering Regular
Expressions, Second Edition.

6.15.4. See Also

The
non-greedy quantifiers in the "Regular Expressions" section of
perlre(1) and in Chapter 5 of
Programming Perl