Understanding Quantifiers

 

I was going through the Java Tutorial on Quantifiers.

There is a difference mentioned among Differences Among Greedy, Reluctant, and Possessive Quantifiers.

I am not able to understand what's the difference exactly.

Explanation provided as follows: 

Enter your regex: .*foo  // greedy quantifier
Enter input string to search: xfooxxxxxxfoo
I found the text "xfooxxxxxxfoo" starting at index 0 and ending at index 13.

Enter your regex: .*?foo  // reluctant quantifier
Enter input string to search: xfooxxxxxxfoo
I found the text "xfoo" starting at index 0 and ending at index 4.
I found the text "xxxxxxfoo" starting at index 4 and ending at index 13.

Enter your regex: .*+foo // possessive quantifier
Enter input string to search: xfooxxxxxxfoo
No match found.

The first example uses the greedy quantifier .* to find "anything", zero or more times, followed by the letters "f" "o" "o". Because the quantifier is greedy, the .* portion of the expression first eats the entire input string. At this point, the overall expression cannot succeed, because the last three letters ("f" "o" "o") have already been consumed. So the matcher slowly backs off one letter at a time until the rightmost occurrence of "foo" has been regurgitated, at which point the match succeeds and the search ends.

The second example, however, is reluctant, so it starts by first consuming "nothing". Because "foo" doesn't appear at the beginning of the string, it's forced to swallow the first letter (an "x"), which triggers the first match at 0 and 4. Our test harness continues the process until the input string is exhausted. It finds another match at 4 and 13.

The third example fails to find a match because the quantifier is possessive. In this case, the entire input string is consumed by .*+, leaving nothing left over to satisfy the "foo" at the end of the expression. Use a possessive quantifier for situations where you want to seize all of something without ever backing off; it will outperform the equivalent greedy quantifier in cases where the match is not immediately found.

General rules

A basic knowledge of the quantifiers ? , * , and + (respectively, "zero or one", "zero or more", "one or more") is understood.

  • We say that a quantifier is greedy if it tries to elaborate as many characters as possible.
  • We say that a quantifier is reluctant ( lazy ) if it tries to elaborate less characters as possible.
  • We say that a quantifier is possessive if it is greedy and it do not allow to backtrace.

    • You can understand what "backtrace" means only if you know how regex parsers work (see "Dynamic example" below).

    Single-case explanations

  • ? : first test 1 occurrence, then 0; if you have found 1 occurrence and then you need to discard it, you can do it
  • ?? : first test 0 occurrences, then 1
  • ?+ : first test 1 occurrence, then 0; if you have found 1 occurrence and then you need to discard it, you can't do it
  • * : try to get as many occurrences as possible (even 0); if you have found N occurrences and then you need to discard (some of) them, you can do it, starting from the last
  • *? : try to get less occurrences as possible (even 0)
  • *+ : try to get as many occurrences as possible (even 0); if you have found N occurrences and then you need to discard (some of) them, you can't do it
  • + : try to get as many occurrences as possible (at least 1); if you have found N occurrences and then you need to discard (some of) them, you can do it, starting from the last
  • +? : try to get less occurrences as possible (at least 1)
  • ++ : try to get as many occurrences as possible (at least 1); if you have found N occurrences and then you need to discard (some of) them, you can't do it

    • Dynamic example

    In this section I'll try to show you what is the logic behind a regex parser:

    1) Case /.*foo/ :

    First it's the turn of subpattern /.*/ . It starts elaborating the first character: 

    xfooxxxxxxfoo
^

    Then it tries to elaborate as many characters as possible: 

    xfooxxxxxxfoo
^^
xfooxxxxxxfoo
^^^
[...]
xfooxxxxxxfoo
^^^^^^^^^^^
xfooxxxxxxfoo
^^^^^^^^^^^^
xfooxxxxxxfoo
^^^^^^^^^^^^^

    The cursor reached the end, but the subpattern /foo/ hasn't played its role yet. So the cursor "goes back" for allowing the subpattern /foo/ to get a match: 

    xfooxxxxxxfoo
^^^^^^^^^^^^

    /foo/ still cannot get a match, so we need to go back again: 

    xfooxxxxxxfoo
^^^^^^^^^^^
xfooxxxxxxfoo
^^^^^^^^^^

    Now the subpattern /foo/ can get a match: 

    xfooxxxxxxfoo
^^^^^^^^^^^^^

    So the match is the whole string xfooxxxxxxfoo .

    2) Case /.*?foo/ :

    First it's the turn of subpattern /.*?/ . It is lazy, so we'd like it maches 0 characters. But if it did, the subpattern /foo/ couldn't get a match, so it has to elaborate one character: 

    xfooxxxxxxfoo
^

    Now it's foo 's turn: 

    xfooxxxxxxfoo
^^^^

    So the match is xfoo .

    (if you set the type global for the regex, then the parser would restart from the first character after the match, giving a second match xxxxxxfoo )

    3) Case /.*+foo/ :

    First it's the turn of subpattern /.*+/ . It tries to elaborate as many characters as possible: 

    xfooxxxxxxfoo
^
[...]
xfooxxxxxxfoo
^^^^^^^^^^^^^

    The cursor reached the end, but the subpattern /foo/ hasn't played its role yet. So the cursor "goes back"... oh no, what a pity, it can't (because it is possessive)!

    So we have no matches.

    The main difference between lazy (reluctant) & greedy case is that the behaviour of the backtracking structure, and the possessive is just way too aggressive !

  • Lazy case will always, after a single match, will relinquish the focus of the matching engine to the next operator in the regex. If next operator fails, the backtrack structure will force lazy case to be repeated, and this continues until either operators or target text ends; for example in your example passing to the matching of char f after every successful match, so whenever you had a foo phrase, you'd get a match, that is why we get multiple matches from its usage.

    • .*?foo

    x fooxxxxxxfoo
    At the beginning, lazy case will have a successful match with the x (after successful empty match) and pass the focus to the next operator; foo part of the regex, and since that is present after x , we get a match for this fragment, same idea for the secondary part of the string.

  • Greedy case is the opposite, will continue its matching until it fails, never passes the focus to the next operator, only when the matching fails the backtracking goes into effect, and the next operators will be matched from reverse;

    • .*foo

    xfooxxxxxxfo o
    When the greedy case is at this point (last char) the matching will fail since we couldn't match the foo part of the regex. Than the backtracking will force the greedy case to backtrace its steps and enforce the next operator foo , similar of lazy case;

    xfooxxxxxx f oo
    At this point, the foo part will get a successful match, and thus ending with a successful match of the whole string.

  • Possessive Case is very similar to greedy case, except the last part where the failure of match causing a backtracking , this is not the case for possessive. If it can be matched, it will posses and will sacrifice the success of the match in the process. If it would've failed in matching a character, only then the focus would pass to the next operator of the regex.

    • .*+foo

    xfooxxxxxxfo o
    Similar of greedy case, we have reached to the end of the string, but possessive case can still match it, thus will not pass the torch to the backtrack structure, and will cause a matching failure.

    链接地址: http://www.djcxy.com/p/13434.html

    上一篇: jQuery选择正则表达式

    下一篇: 理解量词