Two Engines for Expression Processing - Backtracking and Greediness
(Page 4 of 4 )
For tools that use this NFA regex-directed backtracking engine, understanding how backtracking works with your regular expression is the key to writing expressions that accomplish what you want, and accomplish it quickly. We’ve seen how ? greediness and ?? laziness works, so now let’s look at star and plus.
Star, plus, and their backtracking
If you consider x* to be more or less the same as
x?x?x?x?x?x?... (or, more appropriately, (x(x(x(x...?)?)?)?)?),† it’s not too different from what we have already seen. Before checking the item quantified by the star, the engine saves a state indicating that if the check fails (or leads to failure), the match can pick up after the star. This is done repeatedly, until an attempt via the star actually does fail.
Thus, when matching [0-9] + against 'a 1234 num’, once [0-9] fails to match the space after the 4, there are four saved states corresponding to locations to which the plus can backtrack:
a 1234 num
a 1234 num
a 1234 num
a 1234 num
These represent the fact that the attempt of [0-9] had been optional at each of these positions. When [0-9] fails to match the space, the engine backtracks to the most recently saved state (the last one listed), picking up at 'a 1234 num' in the text and at [0-9] + in the regex. Well, that’s at the end of the regex. Now that we’re actually there and notice it, we realize that we have an overall match.
Note that ‘a 1234 num’ is not in the list of positions, because the first match using the plus quantifier is required, not optional. Would it have been in the list had the regex been [0-9]*? (hint: it’s a trick question) Turn the page to check your answer.
Revisiting a fuller example
With our more detailed understanding, let’s revisit the ˆ.* ([0-9] [0-9]) example from page 152. This time, instead of just pointing to “greediness” to explain why the match turns out as it does, we can use our knowledge of NFA mechanics to explain why in precise terms.
I’ll use ‘CA 95472, USA’ as an example. Once the .* has successfully matched to the end of the string, there are a baker’s dozen saved states accumulated from the star-governed dot matching 13 things that are (if need be) optional. These states note that the match can pick up in the regex at ^.* ([0-9] [0-9]), and in the string at each point where a state was created.
has successfully matched to the end of the string, there are a baker’s dozen saved states accumulated from the star-governed dot matching 13 things that are (if need be) optional. These states note that the match can pick up in the regex at ([] []), and in the string at each point where a state was created.
Now that we’ve reached the end of the string and pass control to the first [0-9], the match obviously fails. No problem: we have a saved state to try (a baker’s dozen of them, actually). We backtrack, resetting the current state to the one most recently saved, to just before where .* matched the final A. Skipping that match (or “unmatching” it, if you like) gives us the opportunity to try that A against the first [0-9]. But, it fails.
This backtrack-and-test cycle continues until the engine effectively unmatches the 2, at which point the first [0-9] can match. The second can’t, however, so we must continue to backtrack. It’s now irrelevant that the first [0-9] matched during the previous attempt; the backtrack resets the current state to before the first [0-9] . As it turns out, the same backtrack resets the string position to just before the 7, so the first [0-9] can match again. This time, so can the second (matching the 2). Thus, we have a match: ‘CA 95472, USA’, with $1 getting ‘72’.
A few observations: first, backtracking entails not only recalculating our position within the regex and the text, but also maintaining the status of the text being matched by the subexpression within parentheses. Each backtrack caused the match to be picked up before the parentheses, at ^.* ([0-9] [0-9]).As far as the simple match attempt is concerned, this is the same as ^.* [0-9] [0-9], so I used phrases such as “picks up before the first [0-9].” However, moving in and out of the parentheses involves updating the status of what $1 should be, which also has an impact on efficiency.
One final observation that may already be clear to you: something governed by star (or any of the greedy quantifiers) first matches as much as it can without regard to what might follow in the regex. In our example, the .* does not magically know to stop at the first digit, or the second to the last digit, or any other place until what’s governed by the greedy quantifier—the dot—finally fails. We saw this earlier when looking at how ˆ.* ([0-9] +) would never have more than a single digit matched by the [0-9] + part ( 153).
Please check back next week for the continuation of this article.
| DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware. |
|
 This article is excerpted from chapter four of the book Mastering Regular Expressions, Third Edition, written by Jeffrey E.F. Friedl (O'Reilly, 2006; ISBN: 0596528124). Check it out today at your favorite bookstore. Buy this book now.
|
|
