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

您将如何创建与某个正则表达式匹配的随机字母数字字符串？

这专门用于创建满足常规密码要求的初始密码.

1> Ken..：

---

韦尔普,只是沉思,而是产生一个相匹配的正则表达式随机输入的一般问题听起来是可行的,以我的随机足够放松的定义和正则表达式的足够紧的定义.我想经典的正式定义,即只允许()的|*和字母字符.

正则表达式可以映射到称为有限自动机的正式机器.这样的机器是有向图,其具有称为最终状态的特定节点,称为初始状态的节点,以及每个边缘上的字母表中的字母.正则表达式接受一个单词,如果它可以从初始状态开始并遍历通过图形标记每个字符的一个边缘并结束最终状态.

可以构建图形,然后从最终状态开始并向后遍历随机边缘,跟踪路径.在标准结构中,图中的每个节点都可以从初始状态到达,因此您不必担心会出现无法恢复的错误并需要回溯.如果达到初始状态,请停止并读取前进路径.那是你与正则表达式的匹配.

但是,对于何时或是否达到初始状态,没有特别的保证.人们必须弄清楚生成的字符串在什么意义上是"随机的",并且在什么意义上你希望首先从语言中获得随机元素.

不过,也许这是思考这个问题的起点!

既然我已经写出来了,在我看来,重复解决选择以简化正则表达式模式可能更简单,直到你留下一个简单的字符串.找到模式中的第一个非字母字符.如果是*,则复制前面的项目若干次并删除*.如果是|,则选择要保留的OR项目,然后删除其余项目.对于左边的paren,做同样的事情,但是看看匹配右边的角色后面的角色.如果您首先将正则表达式解析为树表示,这使得paren分组结构更易于使用,这可能更容易.

对于担心决定正则表达式是否真正匹配任何内容的人来说,等同于停止问题:不,常规语言表现得非常好.您可以判断任何两个正则表达式是否描述了相同的接受字符串集.您基本上是在上面制作机器,然后按照算法生成规范的最小等效机器.对两个正则表达式执行此操作,然后检查生成的最小机器是否相同,这很简单.

---

到目前为止,我简化的答案(在http://stackoverflow.com/questions/54991/generating-random-passwords上使用接受的答案,直到它与你的正则表达式相匹配)看起来很有前途:)尽管你选择了彻底性.

2> Chas. Owens..：

---

Perl中的String :: Random将从正则表达式的子集生成随机字符串:

#!/usr/bin/perl

use strict;
use warnings;

use String::Random qw/random_regex/;

print random_regex('[A-Za-z]{3}[0-9][A-Z]{2}[!@#$%^&*]'), "\n";

---

总是更好地使用能够满足您需求的东西.

3> Jon Skeet..：

---

如果您遇到特定问题,可能会考虑特定的正则表达式.我会采用那个正则表达式,用简单的人类术语解决它的含义,并从那里开始工作.

我怀疑可以创建一个通用的正则表达式随机匹配生成器,但它可能比处理特定情况要多得多 - 即使这种情况每年改变几次.

(实际上,可能无法在最一般意义上生成随机匹配 - 我有一个模糊的记忆,"任何字符串匹配此正则表达式"的问题是伪装的停止问题.使用非常简化的正则表达式语言你可能会有更多的运气.)