Perl's regex engine causes me distress

[japhy]

Here is my string: "A1234567890A". Here is my regex:

m{
  A         # A
  (?:
    [^AB]*  # 0 or more non-A and non-B characters
    . B     # any character, then a B
  )*        # this combo, 0 or more times
  [^AB]*    # 0 or more non-A and non-B characters
  A         # an A
}x

Now, before you ask, this is related to a) unrolling the loop, and b) reversing a regex. But it's also a very isolated case of the regex engine being a ninny.

This what I personally think the regex engine should do:

BEFORE & AFTER       REGEX
<>  <A01234567890A>  A
<A>  <01234567890A>  [^AB]*
<A01234567890>  <A>  .
<A01234567890A>  <>  B       FAILED
<A0123456789>  <0A>  .
<A01234567890>  <A>  B       FAILED

At this point, Perl should NOT try to do:

<A012345678>  <90A>  .
<A0123456789>  <0A>  B       FAILED

since Perl should KNOW that '0' was matched by [^AB]*, so it can't POSSIBLY match B. Instead, Perl should realize it should give up, and continue:

<A01234567890>  <A>  [^AB]*
<A01234567890>  <A>  A
<A01234567890A>  <>          FINISHED

This is NOT the case. Perl zips ALL the way back to the first 0 in the string, trying to match .B until it is exhausted, and goes back to the '...890' having been matched by [^AB]*, and it goes to the [^AB]* outside the (?:...)*. This matches nothing, and then the 'A' matches.

My gripe is that Perl should know that if something COULD be matched by [^AB]*, then it CAN'T match 'B'.

$_="goto+F.print+chop;\n=yhpaj";F1:eval

[japhy]

As for how I got around Perl's unhappiness here, I rolled my own solution:

m{
  A
  (?:
    (?>[^AB]*)  # match non-A's and non-B's WITHOUT BACKTRACKING
    (?:
      [AB]      # match A or B next...
      |         # ...or...
      (?<=.)    # ...if there was a character before
    )
    B           # match B
  )*            # 0 or more times
  [^AB]*        # you know the rest
  A
}x

Ick. Why should I have to do that work?

$_="goto+F.print+chop;\n=yhpaj";F1:eval

[tilly]

I know of no RE engine that does it, but the idea I outlined in this conversation would enable the above optimization, obviate most needs for loop unrolling, get rid of most possible performance hangs, but wouldn't actually save the whales. Gosh, darn.

OTOH doing it would take some work and thought, and I am definitely not going to undertake the project any time soon.

[japhy]

Another possible optimization:

m{
  A
  (?: [^AB]+ | .B )*
  [^AB]*
  A
}x;



$_="goto+F.print+chop;\n=yhpaj";F1:eval

[demerphq]

This is sometimes called auto-possesification in regex literature. Ive been looking into implementing it, but its not straightforward to do. Unfortunately. PCRE does it to some extent, but not Perl.

[sgt]

by the way the possessive notation +<quantifier> (saw it first in the second edition of the owl's book) is cute actually: "E++" reads well, take all you can (of these E) don't backtrack.

cheers --stephan