From: MenTaLguY <mental@...>
Date: 2007-04-14T22:23:00+09:00
Subject: Re: Slow ruby regexes

--=-ibs43dWNRBfuPlWuP071
Content-Type: text/plain
Content-Transfer-Encoding: quoted-printable

To be fair, I oversimplified a bit because I couldn't think of a better
example until just now.  Though you can prune the DFA with priorities in
the NFA, an expression like /^(?:(abc)|(a)).*$/ still requires more
sophisticated handling, explicitly tracking alternative matches.

Here's an implementation of a Thompson NFA which does Perl-style
capture:

 http://swtch.com/~rsc/regexp/nfa-perl.y.txt

The same approach works if you construct the DFA in advance or via
memoization of the Thompson NFA evaluation (which is probably the better
of the two for reasons already discussed).

-mental

--=-ibs43dWNRBfuPlWuP071
Content-Type: application/pgp-signature; name=signature.asc
Content-Description: This is a digitally signed message part

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.3 (GNU/Linux)

iD8DBQBGINWxSuZBmZzm14ERArnWAJwJPaT22kAGq5/AlFDUMYR7vv8gUACfYUBS
p1eMFB5yypVM0tCyQENNq7A=
=WhvQ
-----END PGP SIGNATURE-----

--=-ibs43dWNRBfuPlWuP071--