正規表現の静的解析を提供するライブラリはありますか?
-
19-09-2019 - |
質問
具体的には、2(またはそれ以上)与えられた、ライブラリがある正規表現は、両者が一致していることの入力が存在する場合は、伝えることができますか?ボーナスポイントは、Javaや.NETを経由して簡単にアクセスできるのですが、コマンドラインにもいいと思います。
場合アスカーのログ、補足:
このアルゴリズムに供給されるだろう正規表現は非常に単純です。私は先読みを持つ夫婦があると考えているが、それらはすべて固定された最小値と最大長のリテラルや文字クラスのかなり単純な組み合わせです。
解決
私は私が私が何をする必要があるか行うことができますPythonライブラリを見つけます。
>>> 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
ライブラリーは、 pyFSA に呼ばれています。私はに\ dの{2,4}のようなステートメントを回すために、いくつかの事前解析を実装する必要があります\ D \ D \ dは?\ dは?それはうまく自分のニーズに合わせなければならないこと以外。入力のおかげで、人々は他の言語でこれを実装したライブラリを見つけた場合、すべての手段によってそれらを含めます。
他のヒント
があった場合、それは時間の有用な量で実行されません。正規表現を比較するとPSPACE問題です。
http://en.wikipedia.org/wiki/PSPACE-completeする
あなたが正規表現に余分な制限を許可することができます場合は、あなたは、いくつかの運を持っていることがあります。
、私が正しくあなたを理解していれば、あなたは2つの正規表現の交点が空集合であるかどうか知りたいのですが?私はそれは難しいと考えていますが、複雑さは、正規表現の長さが指数関数的だった場合、私は驚かないだろう(一部の正規表現がobivously他よりも容易になるだろうが)。
にかかわらず、ここではHaskellの実装があります: http://sulzmann.blogspot.com/2008/11/演奏-で正規-expressions.htmlする
そしてプロローグ実装 http://www.let.rug.nl/vannoord/Fsa/する
このを開始するための場所かもしれません。
http://kedrigern.dcs.fmph.uniba.sk /~riso/papers/KraPhD.pdfする