What does .*? regular expression actually means?

Question

I've been using perl for a decade. But lately I've got confused with using .*? regex.

It does not seem to match the minimum number of characters. Sometimes it gives different results.

For example for this string:aaaaaaaaaaaaaaaaaaaaaaammmmmmmmmmmbaaaaaaaaaaaaaaaaaaaaaab and pattern: a.*?b it matches complete input string in two groups. As per the definition it should have matched the last "ab".

Answer 1

It doesn't cause a.*?b to match the fewest characters possible; it causes .* to match the fewest characters possible. Since it only affects .*, it has no effect on what's already been matched (i.e. by a).

Example shortened to:

#01234
'aaab' =~ /a.*?b/

What happens:

1. At pos 0, a matches 1 character (a).
2. At pos 1, .*? matches 0 characters (empty string).
3. At pos 1, b fails to match. ⇒ backtrack
4. At pos 1, .*? matches 1 character (a).
5. At pos 2, b fails to match. ⇒ backtrack
6. At pos 1, .*? matches 2 characters (aa).
7. At pos 3, b matches 1 character (b)
8. Pattern match successful.

As you can see, it tried to match zero characters, which is obviously the smallest possible match. But the overall pattern failed to match when it did so, so larger and larger matches were tried until the overall pattern matched.

---

I try to avoid the non-greedy modifier.

'aaab' =~ /a[^a]*b/

If a is really something more complex, then one can use a negative lookahead.

'aaab' =~ /a(?:(?!a).)*b/

Answer 2

It means

.   # match any character except newlines
*   # zero or more times
?   # matching as few characters as possible

So in

<tag> text </tag> more text <tag> even more text </tag>

the regex <tag>(.*)</tag> will match the entire string at once, capturing

 text </tag> more text <tag> even more text 

in backreference number 1.

If you match that with <tag>(.*?)</tag> instead, you'll get two matches:

1. <tag> text </tag>
2. <tag> even more text </tag>

with only text and even more text being captured in backreference number 1, respectively.

And if (thanks Kobi!) your source text is

<tag> text <tag> nested text </tag> back to first level </tag>

then you'll find out that <tag>(.*)</tag> matches the whole string again, but <tag>(.*?)</tag> will match

<tag> text <tag> nested text </tag>

because the regex engine works from left to right. This is one of the reasons regular expressions are "not the best tool" for matching context-free grammars.