Re: Which regular experssion matching method does Glibc implement, NFA or DFA?

[gliao at cs dot ucr dot edu]

Hey Jakub,

Thanks for your quick reply. so does that mean the internal data structure
regex_t from regcomp of current mainstream glibc contains DFA relevant
info(states, transition table etc)instead of NFA?

Thanks in advance

Guangdeng


> 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
>