Re: How are regexen implemented in Emacs?

[tomas]

On Thu, Dec 15, 2022 at 06:18:36AM +0100, Emanuel Berg wrote:

[...]

> A set of rules crunches the input and determines transitions
> from one state to another, I can imagine deterministic such
> rules - but nondeterministic, what does that mean?
> 
> Maybe that from one state S and input I there are not one but
> several ways to go, one can go to S' but also S'' and both
> "moves" are legal?

Exactly. The naive implementation of which involves keeping
a queue of possible states (breadth-first search).

Thompson's trick is converting the NFA into a DFA by considering
"sets of (possible) states" as your new states. But now you've
got 2^n states; the clever part is how to reduce that to some
manageable state space.

I think the Wikipedia has good articles on that.

Cheers
-- 
t

signature.asc
Description: PGP signature