Re: RFC 72 (v3) Variable-length lookbehind: the regexp engine should also go backward.

From: Peter Heslin <[email protected]>
Sent: Thursday, August 31, 2000 10:49 PM

> Simply put, I want variable-length lookbehind.

The RFC seems to say you want this so that you can optimize the operation of
the regex execution.  I've been looking at the existing fixed-length
look-behind and see that it does not seem to operate the way you may have
assumed.

In particular, it is greedy in the sense of the forward matching "*" or "+"
constructs.

Here is a demonstation with the regex-debugging switch enabled.  Note that
the look-behind test fails 7 times, before succeeding on the 8th try.  If
the "*" was greedier than the look-behind, you would expect 2 look-behind
failures, and success on the 3rd.

This doesn't argue against a variable-length lookbehind as a useful feature,
but it may not be what you were looking for.

  - mike mulligan

$ perl "-Dr" -e "print qq($&\n) if qq(mxnxxxxoxxx) =~ /(?<=[aeiou])x*/"

Compiling REx `(?<=[aeiou])x*'
size 17 first at 1
   1: IFMATCH[-1](14)
   3:   ANYOF[aeiou](12)
  12:   SUCCEED(0)
  13:   TAIL(14)
  14: STAR(17)
  15:   EXACT <x>(0)
  17: END(0)
minlen 0
Enabling $` $& $' support.

EXECUTING...

Matching REx `(?<=[aeiou])x*' against `mxnxxxxoxxx'
  Setting an EVAL scope, savestack=3
   0 <> <mxnxxxxoxxx>     |  1:  IFMATCH[-1]
                            failed...
  Setting an EVAL scope, savestack=3
   1 <m> <xnxxxxoxxx>     |  1:  IFMATCH[-1]
   0 <> <mxnxxxxoxxx>     |  3:    ANYOF[aeiou]
                              failed...
                            failed...
  Setting an EVAL scope, savestack=3
   2 <mx> <nxxxxoxxx>     |  1:  IFMATCH[-1]
   1 <m> <xnxxxxoxxx>     |  3:    ANYOF[aeiou]
                              failed...
                            failed...
  Setting an EVAL scope, savestack=3
   3 <mxn> <xxxxoxxx>     |  1:  IFMATCH[-1]
   2 <mx> <nxxxxoxxx>     |  3:    ANYOF[aeiou]
                              failed...
                            failed...
  Setting an EVAL scope, savestack=3
   4 <mxnx> <xxxoxxx>     |  1:  IFMATCH[-1]
   3 <mxn> <xxxxoxxx>     |  3:    ANYOF[aeiou]
                              failed...
                            failed...
  Setting an EVAL scope, savestack=3
   5 <mxnxx> <xxoxxx>     |  1:  IFMATCH[-1]
   4 <mxnx> <xxxoxxx>     |  3:    ANYOF[aeiou]
                              failed...
                            failed...
  Setting an EVAL scope, savestack=3
   6 <mxnxxx> <xoxxx>     |  1:  IFMATCH[-1]
   5 <mxnxx> <xxoxxx>     |  3:    ANYOF[aeiou]
                              failed...
                            failed...
  Setting an EVAL scope, savestack=3
   7 <mxnxxxx> <oxxx>     |  1:  IFMATCH[-1]
   6 <mxnxxx> <xoxxx>     |  3:    ANYOF[aeiou]
                              failed...
                            failed...
  Setting an EVAL scope, savestack=3
   8 <mxnxxxxo> <xxx>     |  1:  IFMATCH[-1]
   7 <mxnxxxx> <oxxx>     |  3:    ANYOF[aeiou]
   8 <mxnxxxxo> <xxx>     | 12:    SUCCEED
                              could match...
   8 <mxnxxxxo> <xxx>     | 14:  STAR
                           EXACT <x> can match 3 times out of 32767...
  Setting an EVAL scope, savestack=3
  11 <mxnxxxxoxxx> <>     | 17:    END
Match successful!
xxx
Freeing REx: `(?<=[aeiou])x*'