Re^2: Perl regexp matching is slow??

I've been thinking of the "atomic subpatterns" and possessive quantifiers as pruning operations. The entire search space may be exponential but entire branches can be eliminated if you just code your pruning operations into your expressions.

⠤⠤ ⠙⠊⠕⠞⠁⠇⠑⠧⠊

Comment on Re^2: Perl regexp matching is slow??

Replies are listed 'Best First'.
Re^3: Perl regexp matching is slow?? by demerphq (Chancellor) on Jan 30, 2007 at 16:51 UTC
Exactly, they are hints to tell the matching engine not to bother backtracking. Hypothetically the optimiser should be able to determine them all automatically and you shouldnt need them, but its a lot easier to let people do it themselves in terms of implementation. Auto-possessiveification is something that sure does need doing. If you consider the general case XqY, where X and Y are literals and q is a quantifer, you should be able to do Xq+Y whenever X cannot overlap Y. Ive not got round to it yet tho. --- $world=~s/war/peace/g	[reply]

Replies are listed 'Best First'.

Re^3: Perl regexp matching is slow??
by demerphq (Chancellor) on Jan 30, 2007 at 16:51 UTC

Exactly, they are hints to tell the matching engine not to bother backtracking. Hypothetically the optimiser should be able to determine them all automatically and you shouldnt need them, but its a lot easier to let people do it themselves in terms of implementation.

Auto-possessiveification is something that sure does need doing. If you consider the general case XqY, where X and Y are literals and q is a quantifer, you should be able to do Xq+Y whenever X cannot overlap Y. Ive not got round to it yet tho.

---
$world=~s/war/peace/g

[reply]