Perl regular expression engine

[Ricardo]

Hi all,

I was wondering if someone could point me some ref on what algorithms
are used by perl to find matches between regular expressions and
text? Is it a dfa?
Thanks!

 

[Ben Morrow]

I was wondering if someone could point me some ref on what algorithms
are used by perl to find matches between regular expressions and
text? Is it a dfa?

No, it's a form of NFA, to allow capturing. The only real reference for
the algorithms used by perl is reg{comp,exec}.c in the perl source, but
I *really* wouldn't recommend starting there . Find a good reference
on POSIX regular expression implementations.

Ben

 

[Uri Guttman]

BM> No, it's a form of NFA, to allow capturing. The only real reference for
BM> the algorithms used by perl is reg{comp,exec}.c in the perl source, but
BM> I *really* wouldn't recommend starting there . Find a good reference
BM> on POSIX regular expression implementations.

and get the book mastering regular expressions. it doesn't show detailed
algorithms but explains them well enough to learn about them. and it
covers almost all major regex versions in many different programs.

uri

 

[Tad J McClellan]

BM> No, it's a form of NFA, to allow capturing. The only real reference for
BM> the algorithms used by perl is reg{comp,exec}.c in the perl source, but
BM> I *really* wouldn't recommend starting there . Find a good reference
BM> on POSIX regular expression implementations.

and get the book mastering regular expressions. it doesn't show detailed
algorithms but explains them well enough to learn about them. and it
covers almost all major regex versions in many different programs.

See also:

How Regexes Work:

http://perl.plover.com/Regex/article.html

 

[Hans Mulder]

No, it's a form of NFA, to allow capturing. The only real reference for
the algorithms used by perl is reg{comp,exec}.c in the perl source, but
I *really* wouldn't recommend starting there . Find a good reference
on POSIX regular expression implementations.

If you really want to know how it's implemented, there's
http://search.cpan.org/~rgarcia/perl-5.10.0/pod/perlreguts.pod

This is easier to understand then the C code. It still assumes you
already know what regular expressions do and want to know more about
how it's done.

Hope this helps,

-- HansM