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

[Stefan Monnier]

>> - 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).


        Stefan