Re: Re: Re: Ovid, Long Live .*? (dot star question-mark)

Wow. That sucks about capturing. I guess the engine is really specific about that optimization. There's got to be a reason that capturing is so bad like that.

_____________________________________________________
Jeff[japhy]Pinyan: Perl, regex, and perl hacker.
s++=END;++y(;-P)}y js++=;shajsj<++y(p-q)}?print:??;

Comment on Re: Re: Re: Ovid, Long Live .*? (dot star question-mark)

Replies are listed 'Best First'.
Re (tilly) 4: Ovid, Long Live .*? (dot star question-mark) by tilly (Archbishop) on Sep 06, 2001 at 18:10 UTC
Well if you want to make that capture fast, you need to guarantee that at no point in the RE will you use a backreference back to that captured pattern. While danger's pattern could be safely optimized, the following one cannot be: `/foo(.?)bar and stuff then \1 here/` [download] Remember that matching arbitrary REs with internal backreferences is an NP complete problem. Matching REs without is not, and an efficient solution is a DFA. As I explained to you, it would* be possible to make NFAs efficient on patterns that are solvable by a DFA. But as soon as you start in on capturing and backreferences, you have to throw out pretty much all hope for non-trivial optimizations.	[reply] [d/l]

Replies are listed 'Best First'.

Re (tilly) 4: Ovid, Long Live .*? (dot star question-mark)
by tilly (Archbishop) on Sep 06, 2001 at 18:10 UTC

While danger's pattern could be safely optimized, the following one cannot be:

/foo(.*?)bar and stuff then \1 here/
[download]

would

[reply]
[d/l]