20

复制：

匹配正则表达式的随机字符串

不，不是。我正在寻找一种简单通用的方法，一种我可以实际实施的方法。这比随机生成密码要困难得多。

我想创建一个采用正则表达式的应用程序，并显示与该表达式匹配的 10 个随机生成的字符串。它应该帮助人们更好地理解他们的正则表达式，并决定他们是否足够安全以用于验证目的。有谁知道一个简单的方法来做到这一点？

一个明显的解决方案是编写（或窃取）一个正则表达式解析器，但这似乎真的超出了我的想象。

我再说一遍，我正在寻找一种简单而通用的方法来做到这一点。

编辑：蛮力方法是不可能的。[a-z0-9]{10}假设随机字符串每秒只有100 万次迭代，那么迭代所有 10 字符字符串的空间需要65 年。

4

5 回答 5

24

将您的正则表达式解析为DFA，然后随机遍历您的 DFA 直到您最终处于接受状态，为每个转换输出一个字符。每次遍历都会产生一个与表达式匹配的新字符串。

但是，这不适用于不是真正正则的“正则”表达式，例如带有反向引用的表达式。这取决于你追求什么样的表达方式。

于 2009-04-14T16:00:51.427 回答
6

看看 Perl 的String::Random。

于 2009-04-14T16:04:11.373 回答
0

一种可能实用也可能不实用的相当丑陋的解决方案是利用现有的正则表达式诊断选项。一些正则表达式库能够找出正则表达式未能匹配的位置。在这种情况下，您可以使用实际上是一种蛮力形式，但一次使用一个字符并尝试获得更长（和更匹配）的字符串，直到获得完全匹配。这是一个非常丑陋的解决方案。但是，与标准的蛮力解决方案不同，它在 ab 之类的字符串上失败还会告诉您是否存在匹配的字符串 ab.*（如果不存在，请停止并尝试 ac。如果是，请尝试更长的字符串）。这可能不适用于所有正则表达式库。

从好的方面来说，从教学的角度来看，这种解决方案可能非常酷。在实践中，它可能在效果上类似于 dfa 解决方案，但不需要考虑 dfa。

请注意，您不希望在此技术中使用随机字符串。但是，如果您跟踪您在树中测试过的内容，则可以使用随机字符开始，因此效果是相同的。

于 2009-04-14T18:53:53.647 回答
-1

如果您的唯一标准是您的方法简单且通用，那么没有什么比蛮力更容易或更通用的了。:)

for (i = 0; i < 10; ++i) {
    do {
        var str = generateRandomString();
    } while (!myRegex.match(str));
    myListOfGoodStrings.push(str);
}

当然，这是一种非常愚蠢的做事方式，主要是为了开玩笑。

我认为你最好的选择是尝试编写你自己的非常基本的解析器，只教它你期望遇到的东西（例如：字母和数字范围，重复/可选字符......不要担心看起来 -背后等）

于 2009-04-14T16:03:31.967 回答
-2

普遍性标准是不可能的。给定正则表达式"^To be, or not to be -- 这就是问题：$"，不会有十个唯一的随机字符串匹配。

对于非退化情况：

moonshadow 与 Perl 的 String::Random 的链接就是答案。从标准输入读取 RegEx 并将十次 String::Random 调用的输出写入标准输出的 Perl 程序是微不足道的。使用Perl2exe将其编译为 Windows 或 Unix exe，并从 PHP、Python 或其他任何地方调用它。

另请参阅基于正则表达式的随机文本生成器

于 2009-04-14T16:10:43.183 回答