Re: Psql regex is NFA or DFA?

On Tue, 10 Sep 2002, Bruce Momjian wrote:

> Tom Lane wrote:
> > Josh Jore <josh@greentechnologist.org> writes:
> > > So I've finished reading Jeffery Friedl's _Mastering Regular Expressions_
> > > and while I don't need regex in PostgreSQL I know I'll do it for something
> > > - eventually. The book makes a distinction between DFA, POSIX NFA and
> > > Traditional NFA and then ascribes some properties and behaviours to each.
> > > So what sort does PostgreSQL have?
> >
> > Well, you could read the code (src/backend/regex), or you could apply
> > the tests that Friedl suggests to distinguish the type of an unknown
> > engine ...
> >
> > My guess is that it's an NFA, but I dunno if Spencer did the POSIX
> > semantics or not.
>
> I am continuing to talk to Henry about getting a newer version of his
> regex library. He is working on it but is not yet finished.

Do you have some details about the implementation itself?  I would like
to work on implementing a regex engine using the Shift-And algorithm
families, and that can probably give a performance improvement over the
current engine.

--
Alvaro Herrera (<alvherre[@]dcc.uchile.cl>)