生成正则表达式的所有可能匹配项

Question

给定正则表达式,我想生成正则表达式匹配的字符串集.重要的是要注意,这个集合不会是无限的,因为每个字符串都有最大长度.是否有任何众所周知的算法来执行此操作？我是否有任何研究论文可以阅读以深入了解这个问题？

谢谢.

ps在理论cs堆栈交换中,这类问题会更​​合适吗？

Answer 1

是否有任何众所周知的算法可以做到这一点？

在 Perl 生态系统中，Regexp::Genex CPAN 模块执行此操作。

在 Python 中，sre_yield生成匹配的单词。正则表达式逆变器也可以做到这一点。

这里描述了一种递归算法， 并且这里提到了几个在 Java 中执行此操作的库。

生成与给定正则表达式匹配的随机单词/字符串：xeger (Python)

我可以阅读任何研究论文来深入了解这个问题吗？

是的，以下论文可用于计算与正则表达式匹配的字符串（或获取它们的生成函数）：

1. 计算有限单词集的出现次数：F. Bassino、J. Clement2、J. Fayolle 和 P. Nicodeme (2007)纸质 幻灯片的包含排除方法
2. Regexpcount，一个用于计算正则表达式和单词问题的符号包，作者：Pierre Nicodeme (2003) 论文链接 链接 代码