Is there a library that provides static analysis of regular expressions?
In particular, is there a library that, when provided 2 (or more) regular expressions, can determine if an input exists that will match? Bonus points if readily available via Java or .NET, but command line would be fine too.
Asker, additional:
The regular expressions that will be fed to this algorithm are pretty simple. While I believe there are a couple with looks, they are all pretty simple combinations of literals or character classes with a fixed minimum and maximum length.
source to share
I found a python library that allows me to do what I need.
>>> import reCompiler
>>> fsa1 = reCompiler.compileRE('\d\d\d?\d?a')
>>> fsa2 = reCompiler.compileRE('123a')
>>> fsa3 = reCompiler.compileRE('a23a')
>>> print len(FSA.intersection(fsa1, fsa2).finalStates)
1
>>> print len(FSA.intersection(fsa1, fsa3).finalStates)
0
The library is called pyFSA . I will have to make some preparations to turn expressions like \ d {2,4} into \ d \ d \ d? \ D?, But other than that it should suit my needs. Thanks for the input, and if people find libraries that implement this in other languages, be sure to include them.
source to share
If it did, it wouldn't work for a good time. Regular expression comparison - PSPACE problem
http://en.wikipedia.org/wiki/PSPACE-complete
You might be in luck if you can allow additional constraints on your regex
source to share
If, I understand you correctly, you would like to know if the intersection of two regexes is empty or not? I find it difficult, but I wouldn't be surprised if the complexity was exponential in the length of the regex (although some regex would be easier than others)
Regardless, here's the Haskell implementation: http://sulzmann.blogspot.com/2008/11/playing-with-regular-expressions.html
And prologue implementation http://www.let.rug.nl/vannoord/Fsa/
source to share