This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: Which regular experssion matching method does Glibc implement, NFA or DFA?
- From: Jakub Jelinek <jakub at redhat dot com>
- To: gliao at cs dot ucr dot edu
- Cc: libc-alpha at sourceware dot org
- Date: Mon, 7 May 2007 02:20:37 -0400
- Subject: Re: Which regular experssion matching method does Glibc implement, NFA or DFA?
- References: <2581.75.40.48.117.1178515212.squirrel@squirrelmail.cs.ucr.edu>
- Reply-to: Jakub Jelinek <jakub at redhat dot com>
On Sun, May 06, 2007 at 10:20:12PM -0700, gliao@cs.ucr.edu wrote:
> I am a newbie for glibc. I am not sure whether I post question in the
> right place. If not, pls forgive me!
>
> I thought that regular expression matching (regexec & regcomp)of the
> mainstream glibc is based on NFA instead of DFA. However, What makes me
> confused is that I found there were many data structures named dfa* when I
> took a look at source code of regcomp.c. could you tell me which one is
> glibc implementing, DFA or NFA?
Before 2002 glibc used a NFA based regex, since it then it uses a DFA based
one (completely rewrite was checked in end of February 2002).
Jakub