私が取り組んでいるプロジェクトでテストする目的で、正規表現が与えられた場合、一致するのに失敗する文字列をランダムに生成する必要があります。たとえば、この正規表現が与えられた場合:
^[abcd]d+
次に、次のような文字列を生成できるはずです。
hnbbad
uduebbaef
9f8;djfew
skjcc98332f
...それぞれが正規表現と一致しませんが、生成しません:
addr32
bdfd09usdj
cdddddd-9fdssee
...それぞれが行います。つまり、対Xegerみたいなものが欲しい。
そのようなライブラリは、できればPythonで存在しますか（理論を理解できれば、必要に応じてPythonに変換できます）？これをどのように書けばよいか少し考えてみましたが、正規表現の範囲を考えると、Xeger のようなものが取り組むよりもはるかに難しい問題のように思えました。これを行うために事前に作成されたライブラリも探しましたが、検索に適切なキーワードを使用していないか、以前にこの問題が発生したことはありません。
私の最初の本能は、いいえ、そのようなライブラリは存在しないということです。妥当な時間内に、任意の正規表現の有効な入力を見つけることができるかどうかを確認することはできません。
たとえば、ある数が素数かどうかを証明することは、解くのが難しい数学的問題であると考えられています。次の正規表現は、少なくとも 10000 文字の長さで、合計の長さが素数である任意の文字列に一致します。
(?!(..+)\1+$).{10000}
この正規表現への有効な入力を合理的な時間内に見つけることができるライブラリが存在するとは思えません。そして、これは単純なソリューションを使用した非常に簡単な例です。たとえば、機能し'x' * 10007ます。有効な入力を見つけるのがはるかに難しい他の正規表現を考え出すことは可能です。
これを解決する唯一の方法は、考えられるすべての正規表現のサブセットに限定することだと思います。
ただし、任意の正規表現に一致するテキストを生成する魔法のライブラリがある場合は、元の表現に一致しないすべての文字列に一致する正規表現を生成するだけです。
幸いなことに、これは否定的な先読みを使用して可能です。
^(?![\s\S]*(?:^[abcd]d+))
正規表現の限られたサブセットのみを許可するように要件を変更する場合は、ブール論理を使用して正規表現を無効にすることができます。たとえば、^[abcd]d+になる場合^[^abcd]|^[abcd][^d]。その後、妥当な時間内にこの正規表現の有効な入力を見つけることができます。
ループを実行して、ランダムな長さのランダムな組み合わせを生成し、正規表現と一致するかどうかをテストします。一致しない状況になるまでループを繰り返します。
明らかに、これは非効率的です。正規表現を逆にして、逆の正規表現で一致を生成できないと確信していますか?
いいえ、これは不可能です。既知の宇宙のすべての文字列に一致する正規表現は無数にあります。例えば：
/^/
/.*/
/[^"\\]*(\\.[^"\\]*)*$/
等
これは、これらすべての正規表現がまったく一致しないためです（これはすべての文字列が持っているものです！）