On Tue, Jul 16, 2013 at 10:00 AM, Rich Felker
<dalias@aerifal.cx> wrote:
The whole concept of regular expressions is that they're regular,
meaning they're matchable in O(n) time with O(1) space. PCRE (the
implementation) uses backtracking for everything, giving it
exponentially-bad performance (JIT cannot fix this), and PCRE (the
language) has a lot of features that are fundamentally not regular and
thus can't be implemented efficiently. Also, the behavior of some of
the features (e.g. greedy vs non-greedy matching) were not designed
intentionally but just arose out of the backtracking implementation,
and thus don't make a lot of sense unless you think from the
standpoint of such an implementation.