Re: Fixing ill-conditioned regular expressions. Proof of concept.

[Alan Mackenzie <acm@muc.de>]

Hello, Paul.

On Mon, Feb 23, 2015 at 11:55:24AM -0800, Paul Eggert wrote:
> Would it be possible to fix the regular expression engine, so that 
> programs don't have to worry about parsing and reformulating regexps so 
> that they're "nice"?

Anything's possible.

Somebody once explained to me that it was all about NFAs and DFAs (which
I only understand exceptionally vaguely) and that Emacs has the "wrong"
one of these.

I talked briefly with Kaz Kylheku on comp.theory a little while ago, and
he opined:

"I suspect, though, that what you're calling "regexp engine" may
 actually be some Perl-inspired job which requires a stack for
 backtracking, and which basically interprets the regular expression, or
 at least partially."

, which, if you take out the disparagement, is what we have, I think.

About replacing it with "the other sort" of regexp engine - it might
well be that the one we have, complete with backtracking stack and what
have you, is generally faster, and that if we were to convert to a
regexp engine which could handle awkward regexps gracefully, that could
slow Emacs down.

It seems a bit like using RISC chips - they can be faster than CISC, but
you need an intelligent compiler to drive them.  My fix-re.el might be
analogous to that intelligent compiler.

But, basically, I've got little idea about regexp engines.  The one
we've got's earliest copyright date is 1993, which seem very late.  Perl
was first released in 1987.

-- 
Alan Mackenzie (Nuremberg, Germany).