给定一个正则表达式，我想生成该正则表达式匹配的字符串集。重要的是要注意这个集合不会是无限的，因为每个字符串都有最大长度。是否有任何众所周知的算法可以做到这一点？有没有我可以阅读的研究论文来深入了解这个问题？
谢谢。
附注这种问题在理论cs堆栈交换中是否更合适？
最佳答案
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?
是的，以下论文可用于计算与正则表达式匹配的字符串(或获取它们的生成函数):
- 计算有限词集的出现次数:F 的包含排除方法。 Bassino、J. Clement2、J. Fayolle 和 P. Nicodeme (2007) paper slides
- Regexpcount，用于计算正则表达式和单词问题的符号包 作者:Pierre Nicodeme (2003) paper link link code
关于regex - 生成正则表达式的所有可能匹配项，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6643730/