查找所有匹配正则表达式（不含+和*运算符）的字符串

Question

我希望能够列出与正则表达式匹配的所有可能字符串。 我想要匹配的所有正则表达式中都没有“*”或“+”，只有类似于“x*{5}”这样的内容，它等同于“x?x?x?x?x?”。

因此，对于任何像下面这样的正则表达式：

[a-c]?cdr*{0,2}

我希望能够匹配表达式中的所有字符串。因此，该库或程序应该输出类似于以下内容：

cd, acd, bcd, ccd, cdr, acdr, bcdr, ccdr, cdrr, acdrr, bcdrr, ccdrr

只要在Linux上运行，我不关心它实现的编程语言。

精化：如果将正则表达式转换为确定性有限状态自动机，则该自动机必须可表示为有向无环图。这就是为什么可能的输出字符串必须是可枚举的（而不是无限长的字符串）。

- Alexander Oh

---

@Mithun：这个链接的问题与本问题完全无关。 - Jens

这个更接近您想要的 https://dev59.com/aEjSa4cB1Zd3GeqPIc3b - Narendra Yadala

你的问题没有意义。你的“正则表达式”最多只有3个字符，除非我弄错了，但是你的结果却超过了三个字符？ - FailedDev

@FailedDev，*{2} 运算符表示最后一个字符的重复次数为0或2。 - Alexander Oh

@Alex 好的，现在我明白你的意思了。所以你需要的是[abc]?cdr{0,2}，我猜测是这样。 - FailedDev

Answer 1

我认为这个Java库http://code.google.com/p/xeger/会帮助你完成此任务，并且它可以在Linux上运行，祝你好运！

- Narendra Yadala

---

啊，这看起来非常有前途，我会在测试完是否满足我的需求后立即接受。 - Alexander Oh

Answer 2

这是一个关于此问题的Python解决方案：https://github.com/asciimoo/exrex。它也可以处理*和+运算符。

- asciimoo