Two Engines for Expression Processing - A match without backtracking
(Page 3 of 4 )
Let’s look at a simple example, matching ab?c against abc. Once the a has matched, the current state of the match is reflected by:
However, now that b? is up to match, the regex engine has a decision to make: should it attempt the b,or skip it?. Well, since ? is greedy, it attempts the match. But, so that it can recover if that attempt fails or eventually leads to failure, it adds
to its otherwise empty list of saved states. This indicates that the engine can later pick up the match in the regex just after the b?, picking up in the text from just before the b (that is, where it is now). Thus, in effect, skipping the b as the question mark allows.
Once the engine carefully places that pile of crumbs, it goes ahead and checks the b. With the example text, it matches, so the new current state becomes:
The final c matches as well, so we have an overall match. The one saved state is no longer needed, so it is simply forgotten.
A match after backtracking
Now, if 'ac' had been the text to match, everything would have been the same until the b attempt was made. Of course, this time it wouldn’t match. This means that the path that resulted from actually attempting the ...? failed. Since there is a saved state available to return to, this “local failure” does not mean overall failure. The engine backtracks, meaning that it takes the most recently saved state as its new current state. In this case, that would be the
state that had been saved as the untried option before the b had been attempted. This time, the c and c match up, so the overall match is achieved.
A non-match
Now let’s look at the same expression, but against ‘abX'. Before the b is attempted, the question mark causes this state to be saved:
The b matches, but that avenue later turns out to be a dead end because the c fails to match X. The failure results in a backtrack to the saved state. The engine next tests c against the b that the backtrack effectively “unmatched.” Obviously, this test fails, too. If there were other saved states, another backtrack would occur, but since there aren’t any, the overall match at the current starting position is deemed a failure.
Are we done? Nope. The engine’s transmission still does its “bump along the string and retry the regex,” which might be thought of as a pseudo-backtrack. The match restarts at:
The whole match is attempted again from the new spot, and like before, all paths lead to failure. After the next two attempts (from abX and abX) similarly fail, overall failure is finally reported.
A lazy match
Let’s look at the original example, but with a lazy quantifier, matching ab??c against ‘abc’. Once the a has matched, the state of the match is reflected by:
Now that b?? is next to be applied, the regex engine has a decision to make: attempt the b or skip it? Well, since ?? is lazy, it specifically chooses to first skip the attempt, but, so that it can recover if that attempt fails or eventually leads to failure, it adds
to its otherwise empty list of saved states. This indicates that the engine can later pick up the match by making the attempt of b, in the text from just before the b. (We know it will match, but the regex engine doesn’t yet know that, or even know if it will ever need to get as far as making the attempt.) Once the state has been saved, it goes ahead and continues from after its skip-the-attempt decision:
The c fails to match ‘b’, so indeed the engine must backtrack to its one saved state:
Of course, it matches this time, and the subsequent c matches ‘c’. The same final match we got with the greedy ab?c is achieved, although via a different path.
Next: Backtracking and Greediness >>
More Java Articles
More By O'Reilly Media
|
 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.
|
|
