Existe uma biblioteca que fornece uma análise estática de expressões regulares?

Question

Especificamente, existe uma biblioteca que, quando dado 2 (ou mais) expressões regulares, pode dizer se existe uma entrada que tanto iria corresponder? Os pontos de bónus se ele é facilmente acessível através de Java ou .NET, mas de linha de comando seria ótimo também.

log de Asker, suplementar:

As expressões regulares que seriam alimentadas para esse algoritmo são bastante simples. Enquanto eu acredito que há um casal com lookaheads, eles são todas as combinações bastante simples de literais ou classes de personagens com comprimentos mínima e máxima fixa.

Answer 1

Eu encontrei uma biblioteca python que me permite fazer o que eu preciso fazer.

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

A biblioteca é chamado pyFSA . I terá que implementar alguns preparsing para transformar declarações como \ d {2,4} em \ d \ d \ d? \ D ?, mas diferente do que ele deve atender minhas necessidades muito bem. Obrigado pela contribuição, e se as pessoas a encontrar bibliotecas que implementam este em outros idiomas, por todos os meios incluí-los.

Answer 2

Se houvesse, não seria executado em uma quantidade útil de tempo. Comparando regex é um problema PSPACE

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

Você pode ter um pouco de sorte se você pode permitir que as restrições extra em seu regex

Answer 3

Se eu entendi corretamente, você gostaria de saber se a interseção de 2 expressões regulares é o conjunto vazio ou não? Eu acredito que é difícil, mas eu não ficaria surpreso se a complexidade foi exponencial do comprimento do regex (embora algumas expressões regulares seria obivously ser mais fácil do que outros)

De qualquer maneira, aqui está uma implementação de Haskell: http://sulzmann.blogspot.com/2008/11/ jogar-com-regulares-expressions.html

E uma implementação prólogo http://www.let.rug.nl/vannoord/Fsa/

Answer 4

Este pode ser um lugar para começar.

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