正则表达式算法

Question

给定一个子字符串,是否有一种方法可以生成所有可能的正则表达式(限制性最强,限制性最小),以匹配给定字符串的子字符串？

例如,假设你有一个子串"orange"和一个字符串"apple banana orange grape".我如何得到一个匹配"橙色"的正则表达式列表(我知道会有很多;希望有一些库已经为我做了这个).

Answer 1

这基本上与询问"给定一些运行时要求,有没有办法生成所有可能的程序(效率最高,效率最低),以满足给定输入的要求？" 答案是肯定的,有一种方法可以做到,但结果的数量是无限的,仅受合理内存和语言实现约束的限制,所以你需要对什么构成有效的"程序"施加限制"为了你的目的,为了将其削减到一个有限的集合.

例如,您可以将自己限制为特定的语法,表示相关正则表达式语言的子集,并且仅生成与该语法匹配的正则表达式:

Regex       ::= StartAnchor? Anything? (Substring | Anything) Anything? EndAnchor?

StartAnchor ::= "^"

Anything    ::= ".*"
              | "(.*)"

Substring   ::= "orange"
              | "(orange)"

EndAnchor   ::= "$"

递归地获取此语法的所有路径(即,由?and 表示的每个分支|)以生成所有目标正则表达式.当然,这个答案故意没有说明这是一个好主意,还是根本不需要......