regex - 有没有办法按特异性对正则表达式列表进行排序？

Question

我正在寻找可以让我对正则表达式列表或一些文档和研究进行排序的东西，

根据他们的特殊性/严格性

/[a-z]+/           // most strict
/[a-z0-9]+/
/[a-z0-9èòà]+/     // less strict
/.*/

但是怎么样

/[a-z]+ABC/
/[a-z0-9]+/

哪一个比另一个不那么具体？

先感谢您

Answer 1

可以将正则表达式等同于它匹配的一组字符串（称为“正则语言”）。如果我们的正则表达式是 named E，我们就称它为匹配字符串L(E)。

您在上面提到的意义上的严格性然后成为子集关系：如果是 的适当子集，则将 RE 定义A为比 RE 更严格。这消除了歧义，例如“相同” RE 的同义词：它们完全相同，因为它们具有相同的常规语言。BL(A)L(B)

正如@yi_H 指出的那样，RE 语言（在某些常见字母表上）的子集关系形成了部分排序。你听起来像你想要一个总订购。如果是这样，您可以规定可接受的总排序应该嵌入由子集关系表示的部分排序。

对于如何构建总排序，我没有明确的答案，但我想到了两种方法。

首先是利用抽水引理。事实证明，对于任何 RE，如果它匹配一个足够长的字符串，那么它还必须匹配一个更长的字符串，该字符串可以通过重复某些小节从第一个构造出来。您可以询问没有任何此类重复段的最长匹配字符串的长度是多少，并将其作为您的指标。也许这尊重（嵌入）部分排序，也许它没有。

另一种是考虑 RE 的状态机上的图变换。我怀疑（但我没有任何参考）如果 REA比 RE 更严格B，那么B's 自动机将可以A通过折叠状态或一些类似的简化操作从 's 计算。您可以将度量定义为 RE 最小自动机中的状态数。

Answer 2

正如您的第二个示例所示，您不能对正则表达式进行全排序，只有部分排序是可能的。

更糟糕的是，有几十种方法可以编写相同的正则表达式： [ab]bvs (ab|bb)，aa*vs a+。因此，即使确定两个正则表达式是否等价也不是一项简单的任务。

Answer 3

假设您谈论的是纯正则表达式，而不是疯狂的 perl 东西，您可以根据它们接受的字符串集定义与您的问题匹配的正则表达式的偏序（即，将正则表达式视为正则语言）。

鉴于正则语言的差异、交集和空性是可判定的问题，这意味着有一些算法会告诉你一个表达式是否接受另一个表达式接受的所有字符串。