Y at-il une bibliothèque qui fournit une analyse statique des expressions régulières?

Question

Plus précisément, il est une bibliothèque qui, lorsqu'il est administré 2 (ou plus) des expressions régulières, peut dire s'il existe une entrée que les deux correspondrait? Les points de bonus si elle est facilement accessible via Java ou .NET, mais la ligne de commande serait bien aussi.

journal de Asker, complémentaires:

Les expressions régulières qui seraient envoyées à cet algorithme sont assez simples. Même si je crois qu'il ya un couple avec lookaheads, ils sont toutes les combinaisons assez simples de littéraux ou des classes de caractères avec des longueurs minimum et maximum fixe.

Answer 1

J'ai trouvé une bibliothèque python qui me permet de faire ce que je dois faire.

>>> 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

La bibliothèque est appelée pyFSA . Je vais devoir mettre en œuvre certaines déclarations pour transformer d'aiguillage comme \ d {2,4} dans \ d \ d \ d? \ D ?, mais à part qu'il devrait convenir à bien mes besoins. Merci pour l'entrée, et si les gens trouvent les bibliothèques qui mettent en œuvre cette dans d'autres langues, par tous les moyens de les inclure.

Answer 2

S'il y avait, il ne se présenterait pas une quantité de temps utile. La comparaison regex est un problème PSPACE

http://en.wikipedia.org/wiki/PSPACE-complete

Vous pouvez avoir un peu de chance si vous pouvez autoriser des restrictions supplémentaires sur votre regex

Answer 3

Si, je vous comprends bien, vous voulez savoir si l'intersection de 2 expressions régulières est l'ensemble vide ou non? Je crois que est difficile, mais je ne serais pas surpris si la complexité est exponentielle de la longueur de la regex (bien que certaines expressions rationnelles seraient obivously plus facile que d'autres)

Peu importe, voici une mise en œuvre Haskell: http://sulzmann.blogspot.com/2008/11/ jouer-avec-régulier expressions.html

Et une mise en œuvre Prolog http://www.let.rug.nl/vannoord/Fsa/

Answer 4

Cela peut être un endroit pour commencer.

http://kedrigern.dcs.fmph.uniba.sk /~riso/papers/KraPhD.pdf