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

Question

这个问题在这里已经有了答案:





Using Regex to generate Strings rather than match them

(12 个回答)


3个月前关闭。




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

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

Answer 1

好吧，只是沉思，但是生成与正则表达式匹配的随机输入的一般问题对我来说是可行的，因为随机定义足够宽松，正则表达式定义足够严格。我在考虑经典的正式定义，它只允许 ()|* 和字母字符。

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

可以构建图，然后从最终状态开始，向后遍历随机边，跟踪路径。在标准构造中，图中的每个节点都可以从初始状态到达，因此您无需担心犯不可恢复的错误和需要回溯。如果您达到初始状态，请停下来并阅读前进的路径。那是正则表达式的匹配项。

但是，没有特别保证何时或是否会达到初始状态。人们必须弄清楚生成的字符串在什么意义上是“随机”的，以及在什么意义上您首先希望从语言中获得随机元素。

不过，也许这是考虑问题的起点!

既然我已经把它写出来了，在我看来，重复解析选项以简化正则表达式模式可能更简单，直到剩下一个简单的字符串。找到模式中的第一个非字母字符。如果是 *，则复制前面的项目若干次并删除 *。如果是 |，请选择要保留的 OR 项并删除其余项。对于左括号，执行相同的操作，但查看匹配的右括号后面的字符。如果您首先将正则表达式解析为树表示，这可能会更容易，这使得 paren 分组结构更易于使用。

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