regex - 正则表达式算法

Question

给定一个子字符串，是否有一种方法可以生成所有可能的正则表达式(从最严格到最不严格)来匹配给定字符串的子字符串？

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

Answer 1

这基本上等同于询问“给定一些运行时要求，是否有一种方法可以生成所有可能的程序(从效率最高到效率最低)来满足给定输入的这些要求？”答案是是的，有一种方法可以做到，但是结果的数量是无限的，仅受合理内存和语言实现约束的限制，所以您需要针对您的目的对构成有效“程序”的内容施加限制，以便将其缩减为有限集。

例如，您可以限制自己使用某种特定的语法，表示所讨论的正则表达式语言的一个子集，并且只生成与该语法匹配的正则表达式:

Regex       ::= StartAnchor? Anything? (Substring | Anything) Anything? EndAnchor?StartAnchor ::= "^"Anything    ::= ".*"              | "(.*)"Substring   ::= "orange"              | "(orange)"EndAnchor   ::= "$"

递归地采用此语法的所有路径(即，由 ? 和 | 指示的每个分支)以生成所有目标正则表达式。当然，这个答案故意不说这样做是个好主意，还是有必要...