¿Hay una librería que proporciona el análisis estático de las expresiones regulares?

Question

En concreto, hay una biblioteca que, cuando se administra 2 (o más) las expresiones regulares, puede decir si existe una entrada que ambos coincidirían? Los puntos de bonificación si es fácilmente accesible a través de Java o .NET, pero la línea de comandos estaría bien también.

registro de Asker, complementarios:

Las expresiones regulares que se alimentaban de este algoritmo son bastante simples. Aunque creo que hay un par de símbolos de anticipación, que son todas las combinaciones bastante simples de literales o clases de caracteres con las longitudes mínima y máxima fija.

Answer 1

He encontrado una biblioteca de Python que me permite hacer lo que tengo que hacer.

>>> 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 biblioteca se llama pyFSA . Voy a necesitar para implementar algunas preparsing convertir declaraciones como \ d {2,4} a \ d \ d \ d? \ D ?, pero aparte de que debe satisfacer mis necesidades muy bien. Gracias por la entrada, y si la gente encuentra bibliotecas que implementan este en otros idiomas, por todos los medios los incluyen.

Answer 2

Si hubiera que no se presentaría en una cantidad de tiempo útil. La comparación de expresión regular es un problema PSPACE

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

Es posible que tenga un poco de suerte si se puede permitir restricciones adicionales en su expresión regular

Answer 3

Si, he entendido bien, que le gustaría saber si la intersección de 2 expresiones regulares es el conjunto vacío o no? Creo que es difícil, pero no me sorprendería si la complejidad fue exponencial en la longitud de la expresión regular (aunque algunas expresiones regulares serían obivously ser más fácil que otros)

En cualquier caso, he aquí una aplicación Haskell: http://sulzmann.blogspot.com/2008/11/ jugar-con-regular expressions.html

Y una aplicación prólogo http://www.let.rug.nl/vannoord/Fsa/

Answer 4

Esto puede ser un punto de partida.

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