正则表达式算法

Question

给定一个子字符串，是否有一种方法可以生成所有可能的正则表达式（对于最小限制性的限制最多），以匹配给定字符串的子字符串？

例如，假设您有一个子字符串“orange”和一个字符串“apple banana orange grape”。我如何得到一个匹配“橙色”的正则表达式列表（我知道会有很多，希望有一个库可以为我做这个）。

Answer 1

这与询问“给定一些运行时要求，是否有一种方法可以生成所有可能的程序（效率最低至效率最低）匹配给定输入的要求相同？”答案是是的，有一个的方式这样做，但结果的数量是无限的，只受限于合理的内存和语言实现的限制，所以你需要对什么构成一个有效的“程序”用于你的目的，以便将其缩减为一个有限集合。

例如，你可以限制自己特定的语法，排序，代表有问题的正则表达式语言的一个子集，并仅生成正则表达式匹配的语法：

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

StartAnchor ::= "^" 

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

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

EndAnchor ::= "$" 

递归采取的所有路径这个语法（即每个分支由?和|表示）生成所有目标正则表达式。当然，这个答案故意没有说这样做是否是一个好主意，或者根本不需要...