7

为了对我正在处理的项目进行测试，如果给定正则表达式，我需要随机生成一个无法与之匹配的字符串。例如，如果给我这个正则表达式：

^[abcd]d+

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

hnbbad
uduebbaef
9f8;djfew
skjcc98332f

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

addr32
bdfd09usdj
cdddddd-9fdssee

...每个都可以。换句话说，我想要一个像反 Xeger 这样的东西。

是否存在这样的库，最好是在 Python 中（如果我能理解理论，如果需要，我很可能将其转换为 Python）？我考虑了如何编写这个，但考虑到正则表达式的范围，这似乎比 Xeger 可以解决的问题要困难得多。我还四处寻找一个预制库来执行此操作，但要么我没有使用正确的关键字进行搜索，要么以前没有人遇到过这个问题。

4

4 回答 4

6

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

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

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

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

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

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

幸运的是，这可以使用负前瞻：

^(?![\s\S]*(?:^[abcd]d+))

如果您愿意将要求更改为仅允许有限的正则表达式子集，那么您可以使用布尔逻辑来否定正则表达式。例如，如果^[abcd]d+变成^[^abcd]|^[abcd][^d]. 然后可以在合理的时间内为这个正则表达式找到一个有效的输入。

于 2012-11-09T22:04:13.753 回答
3

我会做一个循环，生成随机长度的随机组合，并测试是否匹配正则表达式。重复循环，直到达到不匹配的情况。

显然，这将是低效的。你确定你不能反转正则表达式并在反转的正则表达式上生成匹配吗？

于 2012-11-09T22:06:47.573 回答
1

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

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

等等

这是因为所有这些正则表达式都不能匹配任何内容（这是所有字符串都有的！）

于 2012-11-10T06:28:31.033 回答
0

我们可以通过限制从给定字符集生成字符串来减少无限的可能性吗？

比如我可以定义字符集，[QWERTYUIOP!@#$%^%^&*))_]我随机生成的所有字符串都应该是从这个集合中诞生的。这样我们可以减少这个问题的无限性吗？

事实上，即使我也在寻找这样的实用程序，最好是在 Python 中。

于 2013-04-06T14:27:13.920 回答