正则表达式:语言生成器
给定C#中的正则表达式,是否有一种方法可以生成被此正则表达式接受的单词?正则表达式:语言生成器
例如,让我们考虑:
[ab]c*b*
是否有可以自动生成像枚举函数:
a
b
ac
ab
bc
bb
acb
bcb
acc
bcc
...
显然,这个名单是无限的潜在的,长期的AS-的你想要的话,发电机必须是聪明的,以便从最简单的到最复杂的输出,而不会陷入无限循环。
我认为这将是一个有用的工具,以验证正则表达式。一般而言,很容易看到正则表达式接受您计划接受的单词。通常要看到它会接受的其他词汇更加困难。
编辑:这个问题不是关于如何做到这一点,而是:有没有什么可以用来在C#中使用它?
这甚至不是C#特有的问题;我认为你可以用任何真正的正则表达式来做到这一点。
在我看来,你应该能够告诉任何正则表达式匹配的世代故事,这只是一个重写列表。在你的例子中[ab]c*b*
可以生成acccbbb
;那就是[ab]c*b*
- >ac*b*
- >acccb*
- >acccbbb
。对于每个运营商,我们可以想象它列举了它重写的所有方式;那么这只是一个枚举重写的所有组合的问题,归结为列举所有N元组的自然数。
编辑:自然的N元组是glib比较。但是你可以想象,基本上在重写状态上执行广度优先遍历,输出每个字符串,所有操作符都被重写。
您可以将您的正则表达式转换为有限状态自动机,然后用某种启发式方法来探索图。但是,真的,我没有时间自己做;) – 2012-03-02 15:59:23
我不知道如何在C#中做到这一点,但理论上是的,它可以做到。
您需要将您的正则表达式转换为NFA或DFA图形,横向使用BFS跟踪当前路径,为每条边添加一个新字符,并在完成节点时打印当前路径被击中。根据手头的正则表达式,您的内存使用情况可以轻松呈指数增长。
例如,给定的正则表达式(a|b)*abb
我们可以创建一个NFA图表如下所示:
这NFA图形既可以采用识别一个单词,枚举所有可能的单词。我们通过非确定性遍历图来做到这一点。意思是,我们需要跟踪图表中所有可能的路径。
从零开始,我们做一个BFS,并且对于每个有两个或更多输出边的节点,我们创建一个新的非确定性路径。所述BFS访问该节点按照下面的顺序,每次打印:
0, 1, 7, 2, 4, 8, 3, 5, 9, 6, 6, 10, 1, 1, 7, ...
对于每个节点访问我们有中间临时路径为:
- 0 “”
- 1中,“E “
- 7, ”E“
- 2, ”EE“
- 4, ”EE“
- 8,” E一个”
- 3, “EEA”
- 5中, “EEB”
- 9中, “EAB”
- 6中, “eeae”
- 6中, “eebe”
- 10 “eabb”
- 1 “eeaee”
- 1 “eebee”
在 “E” 符号是表示空字符串0123的ε-信,应在打印每个单词时将其过滤掉。
通过在图上做一个BFS,我们将每个单词按照需要用NFA识别单词的边的数量进行排序。由于图形包含一个循环,因此该过程永远不会结束。
每一次每一个不确定的路径到达我们打印生成的字符串结束节点10:
- “ABB”
- “AABB”
- “BABB”
寻找解决[停止问题](http://en.wikipedia.org/wiki/Halting_problem)? – Oded 2012-03-02 15:09:11
正则表达式不完整。编辑:一般的正则表达式并不完整。如果C#允许你编写完整的图灵,那么是的,这是一个问题,这些功能将不得不被禁止。 – zmccord 2012-03-02 15:16:00
哦,我看到这也是一个部分愚弄http://*.com/questions/4208733/generative-regular-expressionions – zmccord 2012-03-02 15:19:52