Re: Regular-Expressions Problem/Bug

On Wed, 19 Jul 2006, Reto Schuettel wrote:

> Hi 
> 
> I've experienced a rather strange problem with regular-expressions
> recently. I used a RE to capture some input from a cisco-device, like:

so you need the brackets....
> 
        [...]
>  4. ...  And a '#' at the end of the prompt #

Is the prompt at the end of what you are looking for, or does text
follow the prompt?
        [...]
> | # "x" * length + "ABC" + "y" * 10 
> | -> takes forever (if LENGHT is big enough), as you can see here the tag
> | 'ABC' occurred, but the ending of the second variable part hasn't.
> 
> After some experiments I could even simplify the problem:
> LENGTH = 20000
> text = "x" * LENGTH + "ABC" + "y" * 10
> re = /(.*)ABC[y]#/
> -> takes forever...

which is similar.
> 
> I'm not sure if this is a problem of the ruby RE-implementation 
> or if this a problem of RE in general (Keyword: back-tracking). Some

Yes, it's backtracking.  Hence my question above.  Try
  re = /(.*)ABC[y]#$/
if the prompt is the last thing you are looking for.  That will
seriously help, because it is saying "If there's no # at the end of
the string. give up now."

that [y]# looks odd to me -- do you mean
  re = /(.*)ABC[y]*#$/
And you might want to try out *? since you have 2 stars in that case.
That would make it non-greedy.  And having a character class [] with 
only one char in it looks odd too.  Maybe you need a non-capturing bracket
instead  
  re = /(.*?)ABC(?:y*?)#$/

> tests with Perl showed to me that Perl usually reacts better to such
> regular-expressions.

Concrete examples and timings might be of use to the regexp developers,
but a statement like the above makes it hard to test improvements.
I don't develop the RE code in Ruby, so you'll need to wait for 
someone who does to show interest in this detail.
> 
> Attached is a short test-program.
> 
> Regards,
> Reto Schtel
>