2

具体的には、2 つ (またはそれ以上) の正規表現が与えられたときに、両方が一致する入力が存在するかどうかを判断できるライブラリはありますか? Java または .NET 経由で簡単にアクセスできる場合はボーナス ポイントですが、コマンドラインでも問題ありません。

アスカーのログ、補足:

このアルゴリズムに供給される正規表現はかなり単純です。先読みのあるものもいくつかあると思いますが、それらはすべて、最小長と最大長が固定されたリテラルまたは文字クラスの非常に単純な組み合わせです。

4

4 に答える 4

4

必要なことを実行できる 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? に変換するには、いくつかの事前解析を実装する必要がありますが、それ以外は私のニーズにうまく適合するはずです。ご意見をお寄せいただきありがとうございます。他の言語でこれを実装しているライブラリを見つけた場合は、必ずそれらを含めてください。

于 2009-10-06T20:23:12.373 に答える
3

正しく理解できた場合、2つの正規表現の共通部分が空集合であるかどうかを知りたいですか？それは難しいと思いますが、複雑さが正規表現の長さで指数関数的であったとしても驚かないでしょう（ただし、一部の正規表現は明らかに他の正規表現よりも簡単です）

とにかく、Haskellの実装は次のとおりです： http ：//sulzmann.blogspot.com/2008/11/playing-with-regular-expressions.html

そしてプロローグの実装 http://www.let.rug.nl/vannoord/Fsa/

于 2009-10-05T23:41:37.720 に答える
3

もしあれば、それは有用な時間で実行されません。正規表現の比較は PSPACE 問題です

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

正規表現に追加の制限を許可できれば、運が良いかもしれません

于 2009-10-05T23:12:18.573 に答える