Match a pair of <p> and </p> XHTML tags and the text between them. The text between the tags can include other XHTML tags.

<p>.*?</p>

All the quantifiers discussed in Recipe 2.12 are greedy, meaning they try to repeat as many times as possible, giving back only when required to allow the remainder of the regular expression to match.

This can make it hard to pair tags in XHTML (which is a version of XML and therefore requires every opening tag to be matched by a closing tag). Consider the following simple excerpt of XHTML:

<p>
The very <em>first</em> task is to find the beginning of a paragraph.
</p>
<p>
Then you have to find the end of the paragraph
</p>

There are two opening <p> tags and two closing </p> tags in the excerpt. You want to match the first <p> with the first </p>, because they mark a single paragraph. Note that this paragraph contains a nested <em> tag, so the regex can’t simply stop when it encounters a < character.

Take a look at one incorrect solution for the problem in this recipe:

<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 ‹› 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+› and ‹d+?› 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+› on 1234, ‹d+› will match all the digits. ‹› then matches, and an overall match is found. If we use ‹d+?›, ‹d+?› first matches only 1. ‹› fails between 1 and 2. ‹d+?› expands to 12, and ‹› still fails. This continues until ‹d+?› matches 1234, and ‹› succeeds.

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

If we use ‹d+?› on 1234X, ‹d+?› first matches only 1. ‹› fails between 1 and 2. ‹d+?› expands to 12. ‹› still fails. This continues until ‹d+?› matches 1234, and ‹› 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, ‹d+› would be better off without any backtracking at all. The next recipe explains how you can use a possessive quantifier ‹d++› to achieve that, at least with some flavors.

Recipe 2.8 describes how the regex engine attempts different alternatives when you use alternation. That is also a form of backtracking.

Recipe 2.12 shows the different alternation operators supported by regular expressions.

Recipe 2.9 explains how to group part of a regex, so that part can be repeated as a whole.

Recipe 2.14 explains how to make sure the regex engine doesn’t needlessly try different amounts of repetition.

Recipe 2.15 explains how to make sure the regex engine doesn’t needlessly try different ways of matching a group.