pcre, bifs, drivers and ports

[Bjorn Gustavsson]

Not all regexps (especially in Perl) can be converted to a FA.
In fact, the second paragraph of the web page gives an example
of such a regexp.

Also, a FA can be difficult/impossible to use if you need to
know exactly what part of the string matched, for instance if
you need to replace the matched string with something else.

Therefore, good regexp libraries use an FA if it's possible,
otherwise they fall back other methods (which for some regular
expressions can be very slow).

So if you could be sure that a given regexp would be converted
to a FA, your heuristic would work.

/Bjorn

Mats Cronqvist <mats.cronqvist@REDACTED> writes:

> Richard A. O'Keefe wrote:
> > Mats Cronqvist <mats.cronqvist@REDACTED> wrote:
> > 	   but as far as i understand (from googling) the time is
> > bounded by k*M*N, 	where M is the length of the string and N is
> > the length of the regexp. so by Is this so?  Matching a string
> > against a finite state automaton
> > is linear, but I thought turning a regular expression into a finite state
> > automaton is exponential.  Certainly the classic RE -> NFA -> FA method
> > is exponential.
> 
>    if it's on the internet, it must be true :>
> 
> http://perl.plover.com/NPC
> 
>    mats
> 

-- 
Björn Gustavsson, Erlang/OTP, Ericsson AB