From: Urabe Shyouhei <shyouhei@...>
Date: 2016-02-29T09:58:51+09:00
Subject: [ruby-core:74039] Re: [Ruby trunk Bug#12103][Rejected] ruby process hangs while executing regular expression.

On 02/28/2016 12:22 PM, Eric Wong wrote:
> Keep in mind the equivalent Perl terminates just fine:

Yes. But,

> So I prefer we acknowledge cases like these as bugs to at least
> encourage someone to fix them.

Ruby's (and Perl's) RE grammar is known to be NP complete.  Fixing this ``issue'' ultimately requires a proof of P=NP.  I don't think it'll happen in a near future.

I guess Perl's RE engine can happen to handle this specific /\(a+( ?a*)*\)/ case, maybe due to their optimization.

Unsubscribe: <mailto:ruby-core-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>