The PCRE (www.pcre.org) is a C library which allows Perl-compatible regular expressions in C, using a fairly straightforward API. Antony Sidwell and I wrote bindings for the PCRE so you can access it from Lua, using an even more straightforward interface. However, this library is probably superceded by other libraries and depends on a rather odd piece of software named Aranha.
For archival purposes, then: libpcre 1.0.2.