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

发布时间：2020-12-14 06:04:01 所属栏目：百科来源：网络整理

导读：我正在寻找允许我对正则表达式列表进行排序的东西, 或一些文件和研究, 根据他们的特殊性/严谨性 /[a-z]+/ // most strict/[a-z0-9]+//[a-z0-9èòà]+/ // less strict/.*/ 但怎么样 /[a-z]+ABC//[a-z0-9]+/ 哪一个比另一个更不具体？先感谢您解决方法可

我正在寻找允许我对正则表达式列表进行排序的东西,
或一些文件和研究,

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

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

但怎么样

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

哪一个比另一个更不具体？

先感谢您

解决方法

可以将正则表达式等同于它匹配的字符串集(称为“常规语言”.)如果我们的正则表达式名为E,那么让我们调用它的匹配字符串L(E).

在上面提到的意义上的严格性然后成为子集关系：如果L(A)是L(B)的适当子集,则定义RE A比RE B更严格.这使得“同一”RE的同义词变得模糊不清：它们是相同的,因为它们具有相同的常规语言.

正如@yi_H指出的那样,RE语言的子集关系(通过一些常见的字母表)形成了部分排序.你听起来像是想要总订购.如果是这样,您可以规定可接受的总排序应嵌入由子集关系表示的部分排序.

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

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

另一种是考虑RE状态机上的图形转换.我怀疑(但我没有任何参考)如果RE A比RE B更严格,那么B的自动机将通过折叠状态或类似的简化动作从A计算.您可以将度量标准定义为RE最小自动机中的状态数.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!