Non-Greedy Regular Expression Misunderstanding

I learned very early on to avoid the dot regex operator as much as possible. I started learning about regexes when I printed out all of the Perl man pages to take with me on my vacation to Iceland 10 years ago (geek!). I had no computer, but was determined to be able to use Perl by the time I got back. The perlre man page was ginormous, and I still to this day remember reading about the various meanings of the dot operator depending on the switches. It meant one thing if the single-line switch was set, another for multi-line, another thing for greedy, and another for non-greedy, and I think yet another for look-ahead and look-back assertions. There were copious warning about not changing your regex switches once you had it working, and several of them mentioned the dot operator.

In short, I learned to avoid it like the plague.

For your specific example, why not use a whitespace class, like "\s" or "[[:space:]]"?

FYI, the term for "non-greedy" is lazy. There are three types of regex quantifiers: greedy, lazy, and possessive. Unfortunately, both ColdFusion and JavaScript only support the first two.

I've heard from an Adobe rep that CF8 will be beefing up CF's regex support. I have no idea what they'll add, though. Hopefully lookbehinds (and variable-length lookbehinds, at that) will be the first thing on the list.

One software recommendation if you haven't already seen it: RegexBuddy (http://regexbuddy.com/). Trust me, it's well worth the measly $30.

Possessive quantifiers are most frequently used to improve performance for certain types of patterns. BTW, possessive quantifiers are simply a limited form of atomic grouping with a shorter notation. Atomic groups are more powerful because you can wrap them around any portion of your pattern, not just the portions you're repeating. With atomic groups/possessive quantifiers, the grouping is treated as one token, and once the regex engine leaves the group it can't backtrack into it (though it can backtrack to tokens before it and try again from there).

This will probably be easier to understand if we break down how regex engines actually work internally. First, let's take a look at the simple (but useless) example from Sun.

Pattern: .*+foo
Input: xfooxxxxxxfoo

Before I get to that, let's take a look at what the more widely used greedy and lazy quantifiers would do.

Using greedy repetition (.*foo), the regex engine would go through the following steps when trying to match the input:

xfooxxxxxxfoo
xfooxxxxxxfoo[backtrack]
xfooxxxxxxfo
xfooxxxxxxfo[backtrack]
xfooxxxxxxf
xfooxxxxxxf[backtrack]
xfooxxxxxx
xfooxxxxxxf
xfooxxxxxxfo
xfooxxxxxxfoo
[Match found]

Note that since the regex started with ".*", the very first step was matching the entire line. That step is done very fast. However, since the regex pattern ends with the literal string "foo", the regex engine then backtracks one character at a time, trying to find the minimum number of characters it needs to give up to match "foo" (that's why they're called greedy quantifiers).

If the string we were testing against was "xfooxxxxxxfoofo", the pattern would require several more steps to test, as I'll show below:

xfooxxxxxxfoofo
xfooxxxxxxfoofo[backtrack]
xfooxxxxxxfoof
xfooxxxxxxfoof[backtrack]
xfooxxxxxxfoo
xfooxxxxxxfoof - Matched the first character in our literal string "foo"
xfooxxxxxxfoofo - Matched the second character in our literal string "foo"
xfooxxxxxxfoofo[backtrack] - Oops, not enough o's at the end, so backtrack one character further than we've backtracked before
xfooxxxxxxfo
xfooxxxxxxfo[backtrack]
xfooxxxxxxf
xfooxxxxxxf[backtrack]
xfooxxxxxx
xfooxxxxxxf
xfooxxxxxxfo
xfooxxxxxxfoo
[Match found]

Note that backtracking can easily get out of hand with certain types of patterns, especially when they're poorly written. In this case, the issue is that the "f"s and "o"s in "foo" are matched by the "." operator, which greedily repeats right past them (then backtracking occurs). However, note that sometimes this is still preferable and faster than other solutions like lazy repetition. It depends entirely on your pattern and the strings you're testing it against.

If we'd used lazy repetition (.*?foo), regex engines would only take five steps to find the first match in both "xfooxxxxxxfoo" and "xfooxxxxxxfoofo":

[backtrack]
x
xf
xfo
xfoo
[Match found]

Note that it steps through the string one character at a time until it can match the literal text "foo". In this case, lazy repetition would be faster.

Now that that's out of the way, here's how a possessive quantifier (.*+foo) would change the game when testing against "xfooxxxxxxfoo":

xfooxxxxxxfoo
xfooxxxxxxfoo[backtrack] - Since we're already at the end of the string, it tries to backtrack to find the literal text "foo", but the possessive quantifier won't give back any of its match
[Match attempt failed]

Note that while it failed a match, it did so extremely quickly. In fact, it took less steps to fail that (2) than trying to match the literal string "xfx" would have (3).

Note that there are certainly many practical uses for atomic groups beyond simply improving performance. For good examples of cases where you're fcuked if you don't have the performance-enhancing power of atomic grouping/possessive quantifiers available to you, I defer to the following excellent page which also explains all of this stuff in more depth: http://regular-expressions.info/atomic.html

Oops. Sorry about accidently not closing one of my strong tags in the previous comment. BTW, regarding your original post, it might not be obvious to some readers where the problem was coming from in your regex. First of all, there is nothing inherently wrong with the regex (<a.+?href="?) (aside from the fact that there should be a space character after "a" to prevent the pattern from dealing with, e.g., "<acronym"). The problem arises when an "a" tag does not have it's own href attribute, and "href=" appears later in the string. Replacing the dot with [^>] simply ensures that the match attempt stays within one "a" tag.

LOL! :) And thanks, Ben.

I, in turn, feel the same way about your ColdFusion / Java skillz. I've got a ways to go, but I'm working on it.

And I've got a ways to go till mastering regular expressions, myself. In particular, now that you've shown me how to use the more powerful, underlying Java regex library in ColdFusion, I'm interested in looking at creative ways to exploit the myriad unicode character properties ( http://regular-expressions.info/unicode.html#prop ) that can be used as regex tokens.

[I never really thought about optimizing regular expressions. I guess, I never really thought that much could be done about it.]

The types of performance differences I've demonstrated on this page are trivial, and not worth fretting over. After a while, though, writing optomized regexes just comes naturally and doesn't take any extra time.

However, the implications of this stuff have the potential to be massive. I could easily write a reasonably short regex / test string pair which would trigger catastrophic backtracking, increasing the number of steps taken by the regex engine exponentially with every couple charaters added to the test string. Such a regex would take a hell of a long time to run (think hours, days, or more), and could potentially even crash the server as the regex engine runs out of memory trying to remember all backtracking positions.

Hey guys, despite all of the comments in this thread, the original question has not been answered: how come non-greedy repetition quantifiers sometimes match too much? I have encountered the same issue as the original poster, although with a different regex. Does this really come down to "you can never use the dot regex operator" inside a repeated non-greedy sub-pattern? That seems kind of weird.

you would not match this because of the end tag in the string

[a name="an>hor" href="TheLink"]

You need a more complex regular expression to filter the attributes and the attribute values before matching the first href attribute.

[a\s+((\w+="[^"]*|\w+=\w?)\s+)??href="]

It matches the right thing. You are mistaken in your regexp. You simply don't understand non-greediness.

You write:
({a.+?href="?)
href=" is optional, so you get:
{a.+?
And it matches everything right from {a

Specify the limiter, so that + can be non-greedy:
{a.+?}
Now it will match everything between {a and }
And it will match the shortest matching text (one tag).

When greedy, it would match } from the last tag in the text. Here:
AAA{a href=""}{/a}{b}BBB{/b}CCC
greedy expresion will match
{a href=""}{/a}{b}BBB{/b}
Non greedy - only {a href=""}

PS. Repair the comment system, as it does not allow to insert greater-then and lesser-then signs - that's why I use { and }. Or change the blogging system.