emacs-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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


From: Stefan Monnier
Subject: Re: Compiling Elisp to a native code with a GCC plugin
Date: Wed, 15 Sep 2010 16:59:31 +0200
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/24.0.50 (gnu/linux)

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



reply via email to

[Prev in Thread] Current Thread [Next in Thread]