From: Bill Kelly <billk@...>
Date: 2006-07-28T14:01:27+09:00
Subject: Re: Slow regular expressions :(

From: "Just Another Victim of the Ambient Morality" <ihatespam@rogers.com>
> "William James" <w_a_x_man@yahoo.com> wrote in message 
> news:1154045557.877418.140290@p79g2000cwp.googlegroups.com...
>> Roman Hausner wrote:
>>> However, regular expression can get generated automatically
>>
>> Stop generating crappy regular expressions.
> 
>    This is easier said than done.  It can be very hard to write code that 
> can specifically avoid generating pathological regexes, especially if you 
> don't understand how regexes work.  Indeed, it would be nice if the regexp 
> engine can do this for you.  After all, it is the job of the programming 
> language to make programming easier for us, is it not?

Is it worth noting that the article at
http://perlmonks.org/index.pl?node_id=502408
indicates:

  - a performance penalty is incurred for keeping track of the
    "have we been here before" state;

  - the solution doesn't cover all regexps, so some regexps
    can still produce exponential backtracking.

?


The Perl guys seem to feel the trade-off was worth it.  Maybe
so.  But it doesn't seem 100% clear cut to me.


Regards,

Bill