regex - 有一种方法可以按特异性对正则表达式列表进行排序吗？

Question

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

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

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

但是怎么样

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

哪个不如另一个具体？

提前谢谢你

Answer 1

可以将正则表达式等同于它匹配的字符串集(称为“正则语言”)。如果我们的正则表达式名为 E，我们称其匹配字符串为 L( E)。

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

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

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

首先是利用 pumping lemma .事实证明，对于任何 RE，如果它匹配一个足够长的字符串，那么它还必须匹配一个更长的字符串，该字符串可以通过重复某些小节从第一个开始构造。您可以询问没有任何此类重复段的最长匹配字符串的长度，并将其作为您的指标。也许尊重(嵌入)偏序，也许不尊重。

另一个是考虑在 RE 的状态机上进行图形转换。我怀疑(但我没有任何引用)如果 RE A 比 RE B 更严格，那么 B 的自动机将可以通过折叠状态或一些类似的简化操作从 A 中计算出来。您可以将度量定义为 RE 最小自动机中的状态数。