From: "Stephan Kämper" <Stephan.Kaemper@...>
Date: 2002-03-01T20:32:53+09:00
Subject: Re: Ruby Regular Expression problem

Olonichev Sergei wrote:
> 
> Hello,
> 
> I faced the problem of Regular Expression (RE) matching speed in real
> application, a model of it is shown below.
> What RE mechanisms are deployed in Ruby? Are there any Ruby libraries of
> DFA-based RE?
> 

Hi highly doubt that Ruby's RegExes are DFA-based from what I learned from
Friedl's "Mastering Regular Expressions". The reason is that you don't have,
among other features IIRC, grouping with DFA RegExes.


> 1.
> echo "=XX=================================" | grep '/X((.)*..?.)+X/'
> 
> Ok.
> 
> 2.
> echo "=XX=================================" | gawk '/X((.)*..?.)+X/'
> 
> Ok.
> 
> 3.
> echo "=XX=================================" | ruby -e 'a=$stdin.gets; if a
> =~ "X((.)*..?.)+X" then puts $& end'
> 
> Hangs up !!!
> 
> ruby -v
> 
> ruby 1.6.2 (2000-12-18) [i386-cygwin]

Anyway, lets have a look at the RegEx

    /X((.)*..?.)+X/

You're looking for 

   X

followed by at least one occurrence {the '(____)+' part} of 

    (.)*..?.

That is

    Any number of chars including none -> (.)*

followed by

    Exactly one char            -> .

followed by

    Zero ore one char           -> .?

followed by

    Exactly one char            -> .

Now, the (___)+ group is mandatory because of the '+' _and_ this group must
contain at least two chars (the single '.'s in side the group).

The 'problem here is the (.)* part inside the group, which leads to an
incredible amount of backtracking during the matching process: The asterisk
is greedy and will consume everything possible until the end of your string
at first.
Then it's subsequently forced to give up one char at a time to allow the
following part of the RegEx to be matched too.

In the end you're out of luck anyway, because the whole RegEx can't possibly
match, as there's nothing in between the two Xes (but the RegEx would need
them as shown above...)

It's well possible the grep and gawk optimize the problem before starting
the match process and thus don't run into the problem you face with Ruby.
But that's just a (more or less wild) guess.

HTH

Stephan