<p>.*</p>

The only difference is that this incorrect solution lacks the extra question mark after the asterisk. The incorrect solution uses the same greedy asterisk explained in Recipe 2.12.

After matching the first <p> tag in the subject, the engine reaches ‹.*›. The dot matches any character, including line breaks. The asterisk repeats it zero or more times. The asterisk is greedy, and so ‹.*› matches everything all the way to the end of the subject text. Let me say that again: ‹.*› eats up your whole XHTML file, starting with the first paragraph.

When the ‹.*› has its belly full, the engine attempts to match the ‹<› at the end of the subject text. That fails. But it’s not the end of the story: the regex engine backtracks.

The asterisk prefers to grab as much text as possible, but it’s also perfectly satisfied to match nothing at all (zero repetitions). With each repetition of a quantifier beyond the quantifier’s minimum, the regular expression stores a backtracking position. Those are positions the engine can go back to, in case the part of the regex following the quantifier fails.

When ‹<› fails, the engine backtracks by making the ‹.*› give up one character of its match. Then ‹<› is attempted again, at the last character in the file. If it fails again, the engine backtracks once more, attempting ‹<› at the second-to-last character in the file. This process continues until ‹<› succeeds. If ‹<› never succeeds, the ‹.*› eventually runs out of backtracking positions and the overall match attempt fails.

If ‹<› does match at some point during all that backtracking, ‹/› is attempted. If ‹/› fails, the engine backtracks again. This repeats until ‹</p>› can be matched entirely.

So what’s the problem? Because the asterisk is greedy, the incorrect regular expression matches everything from the first <p> in the XHTML file to the last </p>. But to correctly match an XHTML paragraph, we need to match the first <p> with the first </p> that follows it.

That’s where lazy quantifiers come in. You can make any quantifier lazy by placing a question mark after it: ‹*?›, ‹+?›, ‹??›, and ‹{7,42}?› are all lazy quantifiers.

Lazy quantifiers backtrack too, but the other way around. A lazy quantifier repeats as few times as it has to, stores one backtracking position, and allows the regex to continue. If the remainder of the regex fails and the engine backtracks, the lazy quantifier repeats once more. If the regex keeps backtracking, the quantifier will expand until its maximum number of repetitions, or until the regex token it repeats fails to match.

‹<p>.*?</p>› uses a lazy quantifier to correctly match an XHTML paragraph. When ‹<p>› matches, the ‹.*?›, lazy as it is, initially does nothing but procrastinate. If ‹</p>› immediately occurs after <p>, an empty paragraph is matched. If not, the engine backtracks to ‹.*?›, which matches one character. If ‹</p>› still fails, ‹.*?› matches the next character. This continues until either ‹</p>› succeeds or ‹.*?› fails to expand. Since the dot matches everything, failure won’t occur until the ‹.*?› has matched everything up to the end of the XHTML file.

The quantifiers ‹*› and ‹*?› allow all the same regular expression matches. The only difference is the order in which the possible matches are tried. The greedy quantifier will find the longest possible match. The lazy quantifier will find the shortest possible match.

If possible, the best solution is to make sure there is only one possible match. The regular expressions for matching numbers in Recipe 2.12 will still match the same numbers if you make all their quantifiers lazy. The reason is that the parts of those regular expressions that have quantifiers and the parts that follow them are mutually exclusive. ‹\d› matches a digit, and ‹\b› matches after ‹\d› only if the next character is not a digit (or letter).

It may help to understand the operation of greedy and lazy repetition by comparing how ‹\d+\b› and ‹\d+?\b› act on a couple of different subject texts. The greedy and lazy versions produce the same results, but test the subject text in a different order.

If we use ‹\d+\b› on 1234, ‹\d+› will match all the digits. ‹\b› then matches, and an overall match is found. If we use ‹\d+?\b›, ‹\d+?› first matches only 1. ‹\b› fails between 1 and 2. ‹\d+?› expands to 12, and ‹\b› still fails. This continues until ‹\d+?› matches 1234, and ‹\b› succeeds.

If our subject text is 1234X, the first regex, ‹\d+\b›, still has ‹\d+› match 1234. But then ‹\b› fails. ‹\d+› backtracks to 123. ‹\b› still fails. This continues until ‹\d+› has backtracked to its minimum 1, and ‹\b› still fails. Then the whole match attempt fails.

If we use ‹\d+?\b› on 1234X, ‹\d+?› first matches only 1. ‹\b› fails between 1 and 2. ‹\d+?› expands to 12. ‹\b› still fails. This continues until ‹\d+?› matches 1234, and ‹\b› still fails. The regex engine attempts to expand ‹\d+?› once more, but ‹\d› does not match X. The overall match attempt fails.

If we put ‹\d+› between word boundaries, it must match all the digits in the subject text, or it fails. Making the quantifier lazy won’t affect the final regex match or its eventual failure. In fact, ‹\b\d+\b› would be better off without any backtracking at all. The next recipe explains how you can use a possessive quantifier ‹\b\d++\b› to achieve that, at least with some flavors.