C'è una libreria che fornisce l'analisi statica delle espressioni regolari?

Question

In particolare, c'è una libreria che, quando somministrato 2 (o più) le espressioni regolari, può dire se esiste un ingresso che entrambi avrebbero abbinare? I punti di bonus se si tratta di facilmente accessibile tramite Java o .NET, ma della riga di comando sarebbe bene pure.

Registro di Asker, supplementari:

Le espressioni regolari che verrebbero alimentati a questo algoritmo sono abbastanza semplici. Mentre credo che ci sono un paio con lookaheads, sono tutti abbastanza semplici combinazioni di letterali o classi di caratteri con lunghezza massima minimo fisso e.

Answer 1

ho trovato una libreria Python che mi permette di fare quello che devo fare.

>>> 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 libreria si chiama pyFSA . Ho bisogno di attuare alcune preparsing di trasformare affermazioni come \ d {2,4} in \ d \ d \ d? \ D ?, ma diverso da quello che dovrebbe soddisfare le mie esigenze ben. Grazie per l'ingresso, e se la gente trova le librerie che implementano questo in altre lingue, con tutti i mezzi li includono.

Answer 2

Se non ci fosse non sarebbe eseguito in una quantità utile di tempo. Confrontando regex è un problema PSPACE

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

Si può avere un pò di fortuna se si può permettere restrizioni extra sul tuo regex

Answer 3

Se, ho capito bene, si vorrebbe sapere se l'intersezione di 2 espressioni regolari è l'insieme vuoto o no? Credo che è difficile, ma non sarei sorpreso se la complessità è stata esponenziale nella lunghezza della regex (anche se alcune espressioni regolari sarebbero obivously essere più facile rispetto ad altri)

Indipendentemente da ciò, ecco un'implementazione Haskell: http://sulzmann.blogspot.com/2008/11/ giocare-con-regular-expressions.html

E un'implementazione prologo http://www.let.rug.nl/vannoord/Fsa/

Answer 4

Questo può essere un punto di partenza.

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