GNU bug report logs - #192
regexp does not work as documented

Previous Next

Full log

View this message in rfc822 format

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Thomas Lord <lord <at> emf.net>
Cc: Chong Yidong <cyd <at> stupidchicken.com>, martin rudalics <rudalics <at> gmx.at>,
        David Koppelman <koppel <at> ece.lsu.edu>, 192 <at> debbugs.gnu.org,
        Bruno Haible <bruno <at> clisp.org>, emacs-devel <at> gnu.org
Subject: bug#192: regexp does not work as documented
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.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.