Well, you could use Yapp or YALALR to create a LALR parser for you according to a specific (Yacc like) grammar. Since yours is already clearly defined in BNF there shouldn't be much trouble converting it.

Since you didn't specify a particular database, I assume you're free to choose. In that case I would suggest MySQL, since it has this nice RegExp feature, where you can query according to some (simplified) regular expression.
This would allow you to convert your parse tree into a valid (MySQL) regexp. Simply select everything which looks like your regexp and your finished.

Hope it helps (a bit),

-- JaWi

"A chicken is an egg's way of producing more eggs."