The effect of eager matching on regular expression alternation

This regular expression engine behavior may return unexpected matches in alternation if alternations are not ordered carefully in the regex pattern.

Take an example of this regex pattern, which matches the strings white or whitewash:

white|whitewash

While applying this regex against an input of whitewash, the regex engine finds that the first alternative white matches the white substring of the input string whitewash, hence, the regex engine stops proceeding further and returns the match as white.

Note that our regex pattern has a better second alternative as whitewash, but due to the regex engine's eagerness to complete and return the match, the first alternative is returned as a match and the second alternative is ignored.

However, consider swapping the positions of the third and fourth alternatives in our regex pattern to make it as follows:

whitewash|white

If we apply this against the same input, whitewash, then the regex engine correctly returns the match as whitewash.

We can also use anchors or boundary matchers in our regular expressions to make it match a complete word. Any of the following two patterns will match and return whitewash as a match:

^(white|whitewash)$

(white|whitewash)

Let's take a look at a more interesting example, which attempts to match a known literal string "cat & rat" or a complete word in the input, using the following pattern:

(w+|cat & rat)

If the input string is story of cat & rat, and we apply our regex pattern repeatedly, then the following four matched substrings will be returned:

1. story
2. of
3. cat
4. rat

It is because the regex engine is eagerly using the first alternative pattern w+ to match a complete word and is returning all the matched words. The engine never attempts a second alternative of the literal string, cat & rat, because a successful match is always found using the first alternative. However, let's change the regex pattern to the following:

(cat & rat|w+)

If we apply this regex on the same sting, story of cat & rat, and we apply our regex pattern repeatedly, then the following three matched substrings will be returned:

1. story
2. of
3. cat & rat

This is because now cat & rat is the first alternative and when the regex engine moves to a position before the letter c in the input, it is able to match and return a successful match using the first alternative.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.149.29.145