Re: How are regexen implemented in Emacs?

[Stefan Monnier]

> Very interesting.  Re: back references, are even "regexen" with back
> references still real regular expressions?

No, back references aren't part of the "regular language" family.
They can't easily be accommodated by the usual DFA/NFA
non-backtracking matchers (and IIRC they are fundamentally
exponential-complexity in the worst case), tho some do handle them
(by falling back to a backtracking algorithm, AFAIK).


        Stefan