Gibt es eine Bibliothek, die statische Analyse von regulären Ausdrücken liefert?

Question

Im Einzelnen gibt es eine Bibliothek, dass, wenn 2 angegeben (oder mehr) von regulären Ausdrücken können sagen, ob eine Eingabe vorhanden ist, dass beide passen würden? Bonuspunkte, wenn es über Java oder .NET leicht zugänglich ist, aber Befehlszeile wäre schön auch.

Asker Logbuch, Nachtrag:

Die regulären Ausdrücke, die zu diesem Algorithmus zugeführt werden würden, sind ziemlich einfach. Während ich glaube, dass es ein Paar mit Lookaheads ist, sind sie alle ziemlich einfachen Kombinationen von Literalen oder Zeichenklassen mit festen minimalen und maximalen Längen.

Answer 1

fand ich eine Python-Bibliothek, die ich können tun, was ich tun muß.

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

Die Bibliothek heißt pyFSA . Ich muss einige preparsing implementieren Aussagen machen wie \ d {2,4} in \ d \ d \ d? \ D ?, aber außer, dass es sollte meine Bedürfnisse gut passen. Vielen Dank für die Eingabe, und wenn die Leute finden Bibliotheken, die diese in anderen Sprachen implementieren, mit allen Mitteln, sie umfassen.

Answer 2

Wenn es nicht in einer nützlichen Menge an Zeit laufen würde. Vergleicht man regex ist ein PSPACE Problem

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

Sie können etwas Glück haben, wenn Sie auf Ihrem regex zusätzliche Einschränkungen zulassen

Answer 3

Wenn ich Dich richtig verstehen, würden Sie wissen, ob der Schnittpunkt von zwei regulären Ausdrücken ist die leere Menge oder nicht? Ich glaube, das ist hart, aber ich wäre nicht überrascht, wenn die Komplexität in der Länge der regex exponentielle ist (obwohl einige regulären Ausdrücke obivously wären einfacher als andere)

Egal, hier ist eine Haskell Umsetzung: http://sulzmann.blogspot.com/2008/11/ spielen-mit-regular-expressions.html

Und eine Prolog Implementierung http://www.let.rug.nl/vannoord/Fsa/

Answer 4

Dies kann ein Ort sein, zu starten.

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