正则表达式算法
问题描述:
给定一个子字符串,是否有一种方法可以生成所有可能的正则表达式(对于最小限制性的限制最多),以匹配给定字符串的子字符串?正则表达式算法
例如,假设您有一个子字符串“orange”和一个字符串“apple banana orange grape”。我如何得到一个匹配“橙色”的正则表达式列表(我知道会有很多,希望有一个库可以为我做这个)。
答
这与询问“给定一些运行时要求,是否有一种方法可以生成所有可能的程序(效率最低至效率最低)匹配给定输入的要求相同?”答案是是的,有一个的方式这样做,但结果的数量是无限的,只受限于合理的内存和语言实现的限制,所以你需要对什么构成一个有效的“程序”用于你的目的,以便将其缩减为一个有限集合。
例如,你可以限制自己特定的语法,排序,代表有问题的正则表达式语言的一个子集,并仅生成正则表达式匹配的语法:
Regex ::= StartAnchor? Anything? (Substring | Anything) Anything? EndAnchor? StartAnchor ::= "^" Anything ::= ".*" | "(.*)" Substring ::= "orange" | "(orange)" EndAnchor ::= "$"
递归采取的所有路径这个语法(即每个分支由?
和|
表示)生成所有目标正则表达式。当然,这个答案故意没有说这样做是否是一个好主意,或者根本不需要...
+0
'这基本上与询问“.....”'相同吗?这不是一回事,也不可行。如果我误解了你,请解释你的意思。 – 2014-01-12 10:29:47
有很多“很多”,有任何目标字符串的正则表达式无限数量。一个简单的例子是:“橙色”,“。*橙色”,“。*橙色。*”,“。*。*橙色。*。*”等等。你应该澄清你的问题,请解释你的最终目标是什么。 – 2010-09-18 12:39:41
即使'(任何可能的正则表达式)?橙色(任何possibe正则表达式)?' – 2010-09-18 12:45:51