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

Question

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

谢谢。

附注这种问题在理论cs堆栈交换中是否更合适？

Answer 1

Are there any well known algorithms in place to do this?

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

在 Python 中 sre_yield生成匹配的词。 Regex inverter也是这样做的。

这里描述了一个递归算法 link1 link2在 Java 中执行此操作的几个库是 mentioned here .

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

Are there any research papers I could read to gain insight into this problem?

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

1. 计算有限词集的出现次数:F 的包含排除方法。 Bassino、J. Clement2、J. Fayolle 和 P. Nicodeme (2007) paper slides
2. Regexpcount，用于计算正则表达式和单词问题的符号包 作者:Pierre Nicodeme (2003) paper link link code