From: Yuri Leikind <YuriLeikind@...>
Date: 2002-03-01T22:12:58+09:00
Subject: Re: Ruby Regular Expression problem

Stephan K�mper wrote:
> 
> 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.

Let's then convert (.)*  to .* , and use (?:)  to turn off
backreferences in the remaining bracket pair:

echo "=XX=================================" | ruby -e 'a=$stdin.gets; if
a  =~ X(?:.*..?.)+X/ then puts $& end'

We still have the same problem.

BTW, perl handles it very fast: 

echo "=XX=================================" | perl -e '$a=<>; print
"$&\n" if a  =~ /X(?:.*..?.)+X/ '



Yuri Leikind