Regular Expressions for Parsing Structured Text
Greedy matching is the default: a regular expression repetition looks for the longest match, which the source calls the Max Munch rule.
Predicting How Far a Pattern Reaches
A regular expression repetition looks simple on the page. A pattern that repeats a small unit seems to stop after one copy, and any extra copies seem to need extra instruction. Before reading on, it is worth testing that belief. Consider the pattern (ab)* and the text ababab. How much of the text do you expect the pattern to match, and why?
What do you think happens?
For the pattern (ab)* applied to ababab, how much of the text does the match cover?
Reveal answer
All three copies of ab, the whole string ababab.
A repetition in a regular expression is greedy by default. The matcher looks for the longest match it can produce from where it started. It does not stop after the first copy of ab, because it can still extend the match, so it keeps going while the pattern keeps succeeding. Nothing in the pattern asked for three copies; the greedy default simply kept extending the match.
If your prediction was the first ab, your intuition is the common one, and the rest of this article explains why the matcher does not behave that way by default. If your prediction was the whole string, you have already seen the greedy default at work. Either way, the goal is to be able to predict the extent of a match from the rule, and then check the prediction against what the matcher actually does.
Tracing the Match Step by Step
Hold the pattern fixed and trace what the matcher does with the text ababab. The matcher starts at the first character. It matches the first ab. Because it is still able to extend the match, it tries another copy, and it finds the second ab. It then tries again, finds the third ab, and finally reaches the end of the text, where no further copy is possible. At that point it stops, and the match is the entire string.
Tracing (ab)* on ababab
Pattern: (ab)* . Text: ababab. Which characters does the greedy repetition claim?
- 1Start at position 0
The repetition begins at the first character, which is a. The unit ab matches characters 0 and 1.
- 2Extend to a second copy
The match can still be extended, so the matcher tries another ab. It matches characters 2 and 3.
- 3Extend to a third copy
The matcher tries once more and matches characters 4 and 5, the final ab of the text.
- 4Stop at the end
No characters remain, so no further copy can be matched. The longest possible match has been found.
The match covers all six characters, ababab, which is the whole string. The greedy repetition did not need an instruction to take three copies; it kept extending because each extension succeeded.
The Max Munch Rule
The Max Munch rule is the behavior that a regular expression repetition looks for the longest match it can produce from where it started. Because this is the default, greedy matching is what you get unless you ask for something else.
The rule explains the prediction from the opening section. The matcher does not stop at the first copy of ab because it is still able to extend the match. A repetition does not wait for permission to continue. It keeps going for as long as the pattern keeps succeeding, and it stops only when it cannot go further. This is why the greedy default feels surprising: the pattern's visible shape suggests a short unit, but the matching rule chooses the longest acceptable extent.
Greedy is not a special mode that you turn on. It is the default behavior of a repetition. The matcher's question is how long a match it can build, and the answer is the longest one.
Switching to Lazy Matching
A trailing question mark placed after a repetition changes how the matcher chooses its length. The ? does not add new text to match. It changes which of the possible lengths the matcher prefers. A lazy repetition accepts the shortest acceptable length first. Writing (ab)*? instead of (ab)* is the way to ask for the shorter choice.
The clearest way to see the difference is to hold the text fixed and vary only the modifier. On the text ababab, the greedy pattern (ab)* ends at the end of the string, while the lazy pattern (ab)*? ends after the first ab. Both patterns are valid, and both do exactly what their modifiers specify. Neither is a bug. The question is which match you want, and the surrounding pattern and text determine whether the matcher's choice is the one you need.
Greedy Overreach on Tagged Text
The problem becomes serious when the text contains delimiters that appear many times, as XML and HTML do. Suppose you want the text between a tag and its end tag. The pattern has two subpatterns: one for the opening tag and one for the closing tag, with a middle subpattern in between. If the middle subpattern is greedy, it grabs as much as it can. The greedy match on the first subpattern can run from the first < to the last >, and a greedy match on the closing subpattern can run from the first <b> to the last </b>. Both results follow the matching rules correctly, but they are unlikely to be what the programmer wanted.
The diagram shows the mechanism. The greedy middle part does not stop at the first closing tag, because the match can still be extended. It keeps consuming characters until it has reached the last available delimiter, so the single match swallows the first end tag and everything after it.
The source's repair is to make the middle subpattern lazy. Writing .*? instead of .* for the text between the tag and the end tag tells the matcher to stop at the nearest end tag. This is why lazy matching is the usual tool for parsing XML tags, where the delimiters repeat in the text.
Mistakes Beginners Make
Common mistake Assuming a repetition stops after the first copy of the unit
What it looks likeExpecting (ab)* on ababab to match only the first ab
Why it failsThe default repetition is greedy, so the matcher keeps extending the match for as long as the pattern keeps succeeding, following the Max Munch rule.
Do this insteadPredict the extent from the rule: a greedy repetition runs to the longest acceptable length, then check the result.
Common mistake Thinking the ? adds text to the match
What it looks likeBelieving (ab)*? must match more characters than (ab)*
Why it failsThe ? does not add new text. It changes how the matcher chooses among the possible lengths, preferring the shortest acceptable one.
Do this insteadHold the text fixed and vary only the modifier, then compare the end positions of the two matches.
Common mistake Using a greedy middle subpattern to extract text between XML tags
What it looks likeA greedy .* between an opening and closing tag that runs past the first closing tag
Why it failsWith repeated delimiters, the greedy subpattern grabs as much as it can and crosses the nearest end tag.
Do this insteadUse .*? for the text between the tag and its end tag so the matcher stops at the nearest end tag.
Common mistake Treating a valid match as a bug when the result looks too long
Practicing Match Predictions
Use the rules from this article to predict a result before running any pattern. The aim is to explain the prediction, whether it turns out right or wrong.
The text is <b>one</b> and <b>two</b>. Predict what the greedy pattern <b>.*</b> matches, then predict what <b>.*?</b> matches. Explain each prediction using the Max Munch rule and the effect of the trailing ?.
Hints
- Start at the first <b> and ask how far a greedy repetition can extend before it runs out of valid continuations.
- For the lazy version, ask which end tag the matcher accepts first.
- Compare the two end positions on the same text, holding the text fixed.
Key Takeaways
- A regular expression repetition is greedy by default, and the matcher looks for the longest match it can produce from where it started, which the source calls the Max Munch rule.
- A trailing ? after a repetition such as the star switches the matcher to lazy behavior, where it prefers the shortest acceptable match. The ? changes the choice of length, not the text being matched.
- On the text ababab, (ab)* matches the whole string while (ab)*? ends after the first ab in the source's example, so the same text can produce different matches from different modifiers.
- When delimiters repeat in text such as XML, a greedy subpattern can run past the intended end tag, and the lazy form .*? is the usual repair for text between tags.