Re^2: This regex seems to have splattered non-greedy everywhere

b) trying real hard to remove exponential behaviour from regexps when you can.

Yes, well, there's the problem of recognizing this before it bites me in the ass in production. I mean, I guess this particular exponential behavior might be something I'll recognize in the future, but is there some automated tool that can recognize when regular expressions have the potential for exponential behavior? (Or is this one of those problems that get as hard as the decideability problem?)

--
@/=map{[/./g]}qw/.h_nJ Xapou cets krht ele_ r_ra/;
map{y/X_/\n /;print}map{pop@$_}@/for@/
[download]

Comment on Re^2: This regex seems to have splattered non-greedy everywhere Download Code

Replies are listed 'Best First'.

Re^3: This regex seems to have splattered non-greedy everywhere
by hv (Prior) on Aug 11, 2005 at 14:52 UTC

The general question is: given a regexp fragment like

  ( prefix (meat)* suffix )*
[download]

/(meat){n}/

I'm sure that at the least a subset of exponential regexps should be discernible. I imagine the first stage of such an approach would be to iteratively strip out anything that can be zero-width, in which case it would be rather harder to detect that eg:

  /( (foo)* (?=b) (bar)? )* baz )/x
[download]

Note that one generic approach to fixing such regexps is to use the 'cut' operator (?> ...), but as far as I am aware that operator is available only in perl itself and the ever-faithful PCRE. For example:

  /( (?> [^']* ) ('[^']*')? )* /x
[download]

[^']*

Hugo

[reply]
[d/l]
[select]


Problems? Is your data what you think it is?
	PerlMonks