[Top][All Lists]

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

Re: regexp does not work as documented

From: Stefan Monnier
Subject: Re: regexp does not work as documented
Date: Mon, 12 May 2008 09:43:49 -0400
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/23.0.60 (gnu/linux)

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


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

reply via email to

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