随机生成与给定正则表达式不匹配的字符串

Question

为了测试我正在工作的项目，如果给定了正则表达式，我需要随机生成一个字符串，该字符串将失败与之匹配。例如，如果给我这个正则表达式：

^[abcd]d+

然后我应该能够生成字符串，例如：

^{pr2}$

…每个都不匹配正则表达式，但不会生成：

addr32
bdfd09usdj
cdddddd-9fdssee

…每一个都要做。换言之，我想要一个反谢格的东西。在

这样的库是否存在，最好是在Python中（如果我能理解这个理论，如果需要，我很可能将其转换为Python）？我考虑过如何编写这篇文章，但是考虑到正则表达式的范围，这似乎是一个比Xeger之类的东西更难解决的问题。我也找了一个预先制作好的库来做这个，但是要么我没有使用正确的关键字来搜索，要么以前没有人遇到过这个问题。在

Answer 1

我最初的直觉是，不，这样的库不存在，因为它是不可能的。您不能确定在合理的时间内可以为任意正则表达式找到有效的输入。在

例如，证明一个数是否素数被认为是一个很难解决的数学问题。以下正则表达式匹配长度至少为10000个字符且总长度为质数的任何字符串：

(?!(..+)\1+$).{10000}

我怀疑是否有任何库能够在合理的时间内找到这个正则表达式的有效输入。这是一个非常简单的例子，有一个简单的解决方案，例如'x' * 10007就可以了。我们可以想出其他更难找到有效输入的正则表达式。在

我认为解决这个问题的唯一方法是将自己限制在所有可能的正则表达式的子集上。在

---

但是，如果您有一个神奇的库，它可以生成与任意正则表达式匹配的文本，那么您需要做的就是生成一个正则表达式来匹配所有与原始表达式不匹配的字符串。在

幸运的是，这是可能的使用消极展望：

^{pr2}$

---

如果您愿意将需求更改为只允许有限的正则表达式子集，那么可以使用布尔逻辑对正则表达式求反。例如，^[abcd]d+变成{}。然后就可以在合理的时间内找到这个正则表达式的有效输入。在

Answer 2

不，这是不可能的。有无限多的正则表达式与已知宇宙中的每个字符串匹配。例如：

/^/
/.*/
/[^"\\]*(\\.[^"\\]*)*$/

等等

这是因为所有这些regex都可以匹配根本不匹配（这是所有字符串都有的！）在

Answer 3

我会做一个循环，生成随机长度的随机组合，并测试是否匹配regexp。重复循环，直到出现不匹配的情况。在

显然，这将是低效的。您确定不能反转regexp并在反转的regexp上生成匹配项吗？在