Regex greedy parse direction

3
votes

I found there're two different opinions about how greedy regex is executed:

  • one is, read all the input string and match the pattern from the back, first match entire input,the first attempt is entire string. Some articles support this opinion are Oracle offical Java tutorial:

Greedy quantifiers are considered "greedy" because they force the matcher to read in, or eat, the entire input string prior to attempting the first match. If the first match attempt (the entire input string) fails, the matcher backs off the input string by one character and tries again, repeating the process until a match is found or there are no more characters left to back off from.

also see this article: Performance of Greedy vs. Lazy Regex Quantifiers

  • the other is matching from the front, the first match attempt is from the 0 index in the left. when a match is found, the engine doesn't stop, keep matching the rest until it fails then it'll backtrack. Articles supports this opinion I found is:

Repetition with Star and Plus the Looking Inside The Regex Engine section talk about <.+>:

The first token in the regex is <. This is a literal. As we already know, the first place where it will match is the first < in the string.

I want to know which one is correct? This matters because it will affect the efficiency of regex. I added various language tags, because I want to know if it's implemented differently in each language.

4
javajavascriptpythonregexperl
Both articles tell the same thing. i mean, your first bullet point. Read Repetition ... link again. - Prince John Wesley
do you have a regexp you'd like us to examine? would you like to profile various regexps? - shinronin
@Prince John Wesley yes, both articles in the first bullet point, have the same opinion, the question is someone have different opinions like in the second bullet point and I don't know which one should follow. - Sawyer
Which link says the second bullet point, the last link Repetition with Star and Plus says the first bullet point. - Prince John Wesley
keep matching the rest until it fails then it'll backtrack - how will the parser know the match failure until it eat everything? - Prince John Wesley

4 Answers

3
votes

Assuming they're functionally equivalent (and based on my Java regex use, they are), it's just a difference in engine implementation. Regular Expressions are not implemented exactly the same way in all languages, and can be more or less powerful based on which language you use.

The second link describes Perl, so I'd trust Oracle on the Java side of things.

Both attempt to get the largest match possible.

Making a quantifier lazy by adding the ? key will attempt the smallest match possible.

0
votes

"The matcher backs off the input string by one character and tries again" is just describing backtracking, so "then it'll backtrack" is therefore saying the same thing. Since both of your quotes regarding greediness say the same thing, both are correct. (Your third quote has nothing to do with greediness.)

Let's provide an example.

'xxabbbbbxxabbbbbbbbb' =~ /([ab]*)bb/;
  1. Try at pos 0.
    1. [ab]* matches 0 chars "".
      1. At pos 0, bb fails to match ⇒ Backtrack.
    2. [ab]* can't match any less ⇒ Backtrack.
  2. Try at pos 1.
    1. [ab]* matches 0 chars "".
      1. At pos 1, bb fails to match ⇒ Backtrack.
    2. [ab]* can't match any less ⇒ Backtrack.
  3. Try at pos 2.
    1. [ab]* matches 6 chars "abbbbb".
      1. At pos 8, bb fails to match ⇒ Backtrack.
    2. [ab]* matches 5 chars "abbbb". (Back off one)
      1. At pos 7, bb fails to match ⇒ Backtrack.
    3. [ab]* matches 4 chars "abbb". (Back off one)
      1. At pos 6, bb matches.
        1. Success.

So $1 is "abbb". (Not abbbbbbb. "Greedy" doesn't mean "longest match possible".)

Now, let's see what happens if we make the "*" non-greedy.

'xxabbbbbxxabbbbbbbbb' =~ /([ab]*?)bb/;
  1. Try at pos 0.
    1. [ab]*? matches 0 chars "".
      1. At pos 0, bb fails to match ⇒ Backtrack.
    2. [ab]* can't match any more ⇒ Backtrack.
  2. Try at pos 1.
    1. [ab]*? matches 0 chars "".
      1. At pos 1, bb fails to match ⇒ Backtrack.
    2. [ab]* can't match any more ⇒ Backtrack.
  3. Try at pos 2.
    1. [ab]*? matches 0 chars "".
      1. At pos 2, bb fails to match ⇒ Backtrack.
    2. [ab]*? matches 1 char "a". (Add one)
      1. At pos 3, bb matches.
        1. Success.

So $1 is "a".

Specific implementation might do things differently as an optimisation, as long as it gives the same result as presented here. You can see Perl at work using

perl -Mre=debug -E'say "xxabbbbbxxabbbbbbbbb" =~ /([ab]*)bb/;'
perl -Mre=debug -E'say "xxabbbbbxxabbbbbbbbb" =~ /([ab]*?)bb/;'
0
votes

Implementation of regex in differenet envronments and programming languages does not have to be same, so there is no exact answer to your question.

If you go with Perl, then you should know that regex implementation is very optimized, as this is one of the strongest feature of this programming language. So, don't worry about efficiency :)

0
votes

There's not a difference, and there's no "matching from the back" implied. When the first reference says "the matcher", it means the repeated regex atom, not the entire expression — i.e. when matching /ab+/ against "abbot", we don't know a priori that the b+ won't match the entire rest of the string. I think that the Java tutorial might be discussing the behavior of regex matching against streams, and noting that a greedy repetition will eagerly consume the rest of the stream, while a nongreedy repetition will lazily consume the stream as needed.