Re: How are regexen implemented in Emacs?

[Marcin Borkowski]

On 2022-12-12, at 20:17, Stefan Monnier via Users list for the GNU Emacs text 
editor <help-gnu-emacs@gnu.org> wrote:

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

Thanks, that's pretty interesting.

The linked article sounded a bit like "only idiots implement regexen
in the naive way", and I was pretty sure Emacs devs are not idiots - but
now I understand the reasons better.

Best,

-- 
Marcin Borkowski
http://mbork.pl