CODEWITHSUNDEEP
rubyregex
Eric Walker
Eric Walker

Reputation: 7571

meaning of a `+` following a `*`, when the latter is used as a quantifier in a regular expression

Today I came across the following regular expression and wanted to know what Ruby would do with it:

> "#a" =~ /^[\W].*+$/
=> 0
> "1a" =~ /^[\W].*+$/
=> nil

In this instance, Ruby seems to be ignoring the + character. If that is incorrect, I'm not sure what it is doing with it. I'm guessing it's not being interpreted as a quantifier, since the * is not escaped and is being used as a quantifier. In Perl/Ruby regexes, sometimes when a character (e.g., -) is used in a context in which it cannot be interpreted as a special character, it is treated as a literal. But if that was happening in this case, I would expect the first match to fail, since there is no + in the lvalue string.

Is this a subtly correct use of the + character? Is the above behavior a bug? Am I missing something obvious?

Upvotes: 6

Views: 604

Answers (1)

Jerry
Jerry

Reputation: 71538

Well, you can certainly use a + after a *. You can read a bit about it on this site. The + after the * is called a possessive quantifier.

What it does? It prevents * from backtracking.

Ordinarily, when you have something like .*c and using this to match abcde, the .* will first match the whole string (abcde) and since the regex cannot match c after the .*, the engine will go back one character at a time to check if there is a match (this is backtracking).

Once it has backtracked to c, you will get the match abc from abcde.

Now, imagine that the engine has to backtrack a few hundred characters, and if you have nested groups and multiple * (or + or the {m,n} form), you can quickly end up with thousands, millions of characters to backtrack, called catastrophic backtracking.

This is where possessive quantifiers come in handy. They actually prevent any form of backtracking. In the above regex I mentioned, abcde will not be matched by .*+c. Once .*+ has consumed the whole string, it cannot backtrack and since there's no c at the end of the string, the match fails.

So, another possible use of possessive quantifiers is that they can improve the performance of some regexes, provided the engine can support it.

For your regex /^[\W].*+$/, I don't think that there's any improvement (maybe a tiny little improvement) that the possessive quantifier provides though. And last, it might easily be rewritten as /^\W.*+$/.

Upvotes: 5

Related Questions