Subject: Re: regexp does not work as documented

From: Stefan Monnier <[email-masked]>
Date: Mon, 12 May 2008 09:43:49 -0400

> years ago, is to consider *offline* DFA conversion (a la 'lex(1)').

That's what I do in lex.el.

> The advantage of offline (batch) conversion is that you can burn a lot
> of cycles on DFA minimization and, if your offline converter
> terminates, you've got a reliably linear matcher.  The disadvantages
> for *many* uses of regular expressions in Emacs should be pretty
> obvious.  For something like font-lock, where the regular expressions
> don't change that often, that might be a good approach -- precompile
> a minimal DFA and then add support for "regular expression
> continuations" when using those tables.

I do not intend to replace src/regexp.c with a matcher based on offline
DFA conversion.  Actually, the need to support backrefs makes it pretty
much impossible (tho I'm sure there's a way to adapt an offline DFA so
it can be used with backrefs), and most importantly it has too different
performance characteristics.  More specifically, the compilation step
should be made explicit.

In any case I think you did answer my question: an offline DFA matcher
is fine, the worst case is not that common and can be worked around.
This is not that different from the current backtracking matcher.

        Stefan

PS: The original motivation for a DFA-matcher is to extend syntax-tables
so they can match match multi-char elements.