Re: Compiling Elisp to a native code with a GCC plugin

[Helmut Eller]

* Stefan Monnier [2010-09-15 14:59] writes:

>>> - The main problem with Emacs regexps right now is that they have
>>> pathological cases where the match-time is enormous (potentially
>>> exponential explosion in the size of the input string).  To be
>>> worthwhile a replacement should address this problem, which basically
>>> needs it should not be based on backtracking.
>> Is it possible (theoretically) to implement all of Emacs regexps without
>> backtracking?  In particular those with back-references (\N) seem
>> problematic.  Or is it necessary to recognize "optimizable" regexps
>> before using a different regexp engine?
>
> IIRC regexps without back-refs can be matched (and searched) in O(N)
> where N is the length of the input.  With back-refs, I think (not sure)
> the theoretical bound is O(N^2), which requires
> a non-backtracking algorithm.
>
> So yes, we'd need to handle back-refs specially.  Several regexp engines
> do that already (they have a few different inner engines and choose
> which one to use based on the particular regexp at hand).

After googleing a bit I found this page 
http://swtch.com/~rsc/regexp/regexp1.html
which again links to this
http://perl.plover.com/NPC/NPC-3SAT.html
which says that regexp matching with backreferences is NP-complete.

Cox (the first page) seems to say that backtracking-with-memoization is
linear time at the expense of O(N) space.

Helmut