Re: How are regexen implemented in Emacs?

[Stefan Monnier via Users list for the GNU Emacs text editor <help-gnu-emacs@gnu.org>]

>>> https://www.gnu.org/software/emacs/manual/html_node/elisp/Regexp-Problems.html
>>> and started to wonder if the hints there mean that Emacs has a "naive",
>>> backtracking regex engine or a FA-based one?
>> Naive!
> And what are the reasons?

Largely historical, but changing it is a lot of work with uncertain
outcome:
- Reproducing the exact behavior of the naive match with a non-naive
  match can be tricky.
- The naive approach sucks when the match fails in many
  different ways, but it's quite efficient when the match succeeds
  without any backtracking.
Ideally, we'd like to replace the regexp engine with a "standard one",
but it's not easy to find one that satisfies all the requirements
(e.g. ability to add Emacs-specific elements like \_<, \s, and \c,
ability to operate on "two-part strings" (i.e. with a gap in the
middle), ...).


        Stefan