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

Question

对于我正在研究的项目的测试目的,如果给出正则表达式,我需要随机生成一个将由FAIL匹配的字符串.例如,如果我给这个正则表达式:

^[abcd]d+

然后我应该能够生成如下字符串:

hnbbad
uduebbaef
9f8;djfew
skjcc98332f

...每个都与正则表达式不匹配,但不生成:

addr32
bdfd09usdj
cdddddd-9fdssee

......每一个DO.换句话说,我想要像反Xeger这样的东西.

这样的库是否存在,最好是用Python(如果我能理解这个理论,我很可能在需要的时候把它转换成Python)？我考虑过如何写这个,但考虑到正则表达式的范围,似乎可能比Xeger可以解决的问题困难得多.我也四处寻找一个预制的库来做这件事,但要么我没有使用正确的关键字进行搜索,要么之前没有人遇到过这个问题.

Answer 1

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

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

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

我怀疑是否存在可以在合理的时间内找到该正则表达式的有效输入的库.这是一个非常简单的例子,只需一个简单的解决方案即可'x' * 10007.有可能提出其他正则表达式,这些表达式很难找到有效的输入.

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

不过话说回来,如果你有一个产生,对于匹配的文本神奇的库的任何武断的正则表达式,那么所有你需要做的是生成所有的字符串相匹配的正则表达式不要你的原始表达式匹配.

幸运的是,这可能是使用否定前瞻:

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

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