13.2.13 Backtracking

We’ve already seen that greedy quantifiers match the maximal number of times, but the overriding priority is that the overall match succeed. Consider

(pregexp-match "a*a" "aaaa")

The regexp consists of two subregexps, a* followed by a. The subregexp a* cannot be allowed to match all four a’s in the text string "aaaa", even though * is a greedy quantifier. It may match only the first three, leaving the last one for the second subregexp. This ensures that the full regexp matches successfully.

The regexp matcher accomplishes this via a process called backtracking. The matcher tentatively allows the greedy quantifier to match all four a’s, but then when it becomes clear that the overall match is in jeopardy, it backtracks to a less greedy match of three a’s. If even this fails, as in the call

(pregexp-match "a*aa" "aaaa")

the matcher backtracks even further. Overall failure is conceded only when all possible backtracking has been tried with no success.

Backtracking is not restricted to greedy quantifiers. Nongreedy quantifiers match as few instances as possible, and progressively backtrack to more and more instances in order to attain an overall match. There is backtracking in alternation too, as the more rightward alternates are tried when locally successful leftward ones fail to yield an overall match.

This document was generated on March 31, 2014 using texi2html 5.0.