[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Regexp backtracking issues in 1.8

Vasile Gaburici

3/7/2007 10:57:00 AM

Basically Ruby 1.8 fails to backtrack correctly a number of regular
expressions. The simplest one is probably:

irb(main):036:0> /a(ba|.)*?a/.match('axba')
=> nil

There is more to it, and since I had to write it down for my students,
I'm just going to link to the gory details:
http://www.cs.umd.edu/~gaburici/r...

--
Posted via http://www.ruby-....
3 Answers

Robert Dober

3/7/2007 12:13:00 PM

0

On 3/7/07, Vasile Gaburici <gaburici@cs.umd.edu> wrote:
> Basically Ruby 1.8 fails to backtrack correctly a number of regular
> expressions. The simplest one is probably:
>
> irb(main):036:0> /a(ba|.)*?a/.match('axba')
> => nil
>
> There is more to it, and since I had to write it down for my students,
> I'm just going to link to the gory details:
> http://www.cs.umd.edu/~gaburici/r...
>
> --
> Posted via http://www.ruby-....
>
>
I just followed the link to find this jewel:

Ruby 1.8 has a rather buggy regexp engine. Some constructs using
alternation followed by a Kleene star operator will not behave as
expected, or as they do in Python or Perl.

very funny I think

Cheers
Robert

--
We have not succeeded in answering all of our questions.
In fact, in some ways, we are more confused than ever.
But we feel we are confused on a higher level and about more important things.
-Anonymous

WoNáDo

3/7/2007 12:25:00 PM

0

Vasile Gaburici schrieb:
> Basically Ruby 1.8 fails to backtrack correctly a number of regular
> expressions. The simplest one is probably:
>
> irb(main):036:0> /a(ba|.)*?a/.match('axba')
> => nil
>
> There is more to it, and since I had to write it down for my students,
> I'm just going to link to the gory details:
> http://www.cs.umd.edu/~gaburici/r...
>

It is an Error in Ruby 1.8. In Ruby 1.9 (with Oniguruma) it works correct
("ruby-445" is a special naming of myself for some experiments):

>>>>> Example >>>>>

C:\Dokumente und Einstellungen\wolfgang\Desktop>type regexerr.rb
p "axba".match(/a(ba|.)*?a/)
C:\Dokumente und Einstellungen\wolfgang\Desktop>ruby -v
ruby 1.8.5 (2006-08-25) [i386-mswin32]

C:\Dokumente und Einstellungen\wolfgang\Desktop>ruby regexerr.rb
nil

C:\Dokumente und Einstellungen\wolfgang\Desktop>ruby-445 regexerr.rb
#<MatchData:0x2ac7ab8>

C:\Dokumente und Einstellungen\wolfgang\Desktop>ruby-445 -v
ruby 1.9.0 (2006-10-28) [i386-mingw32]

>>>>> EoE >>>>>

Wolfgang Nádasi-Donner

Nikolas Coukouma

3/8/2007 12:43:00 AM

0

Vasile Gaburici wrote:
> Basically Ruby 1.8 fails to backtrack correctly a number of regular
> expressions. The simplest one is probably:
>
> irb(main):036:0> /a(ba|.)*?a/.match('axba')
> => nil
>
> There is more to it, and since I had to write it down for my students,
> I'm just going to link to the gory details:
> http://www.cs.umd.edu/~gaburici/r...

I've posted a lot of very short test cases with varying quantifiers. The
results are interesting:
http://nikolasco.livejournal.com/3...

Regards,
-Nikolas

--
Posted via http://www.ruby-....