How to implement Regex

Question

I'm working on a database server software product (see my profile) and we see the need to implement free- text searching in our software. The query language standard we are using only supports free-text search using a BT type Regex. The only way we can use our free-text database indexes together with Regex seems to be to implement our own. My questions to SO is:

• Where can I find papers/examples/patterns on how to implement a BT style Regex?

• Is it worth looking into taking one of the open source C/C++ Regex libraries and altering the code to fit our needs?

Answer 1

If I'm not wrong SPARQL uses the XPath/XQuery regular expression syntax which is based on PERL regular expressions (At least that is what the W3C docs say)

If this is indeed the case then you can use PCRE from http://www.pcre.org/

It is licensed as BSD so you will be able to use it in a commercial product

If your syntax is slightly modified you can probably write a small routine to normalize it to the PERL syntax used by PCRE

Answer 2

There are two papers I have found on the subject on REGEX indexing online; one from Bell Labs and one from UCLA/IBM. I'm still not sure if to use an existing Regex library and modify it or write one from scratch.