正则表达式的计算复杂度

您可以尝试使用正则表达式的编译形式，并尝试将一些代码复杂性指标映射到该指标，例如代码行或圈复杂度。要了解我的意思，请查看以下 stackoverflow 答案：https://stackoverflow.com/a/2348725/5747415，它显示了如何使用 perl 访问正则表达式的编译形式。另一个示例如下所示： http://perldoc.perl.org/perldebguts.html#Debugging-Regular-Expressions，引用该页面的工具输出：

Compiling REx '[bc]d(ef*g)+h[ij]k$'
1: ANYOF[bc](12)
12: EXACT <d>(14)
14: CURLYX[0] {1,32767}(28)
16:   OPEN1(18)
18:     EXACT <e>(20)
20:     STAR(23)
21:       EXACT <f>(0)
23:     EXACT <g>(25)
25:   CLOSE1(27)
27:   WHILEM[1/1](0)
28: NOTHING(29)
29: EXACT <h>(31)
31: ANYOF[ij](42)
42: EXACT <k>(44)
44: EOL(45)
45: END(0)

顺便说一句，我祝贺你决定提高代码的可维护性。也就是说，我只需要表达我的怀疑，任何正式的指标都比有经验的开发人员的判断提供了更好的指导（甚至可以接近）......

如果你正在处理一个等同于形式正则表达式的正则表达式系统（它描述正则语言;没有计数，没有后视，没有匹配的括号对等），或者如果你只处理使用这些特性的正则表达式（尽管你的正则表达式系统能够描述非常规语言），那么就有一个精确的复杂性概念（或者至少你可以推导出一个），并且有一定的意义哪些正则表达式可以“最小化”。

根据 Myhill-Nerode 定理，在字符串的不可区分关系下，所有常规语言都具有有限数量的等价类。这些等价类直接对应于常规语言的最小确定性有限自动机中的状态。你可以把语言的最小确定性有限自动机的状态数作为语言本身的“基本”复杂性。

有一些算法可以将您从（形式）正则表达式带到最小确定性有限自动机，然后再回到正则表达式。这样做应该会为每种常规语言提供一个规范的正则表达式。我想象 - 但还没有找到证明 - 从最小确定性有限自动机生成正则表达式的过程可以被修改，以便它产生短路（就运算次数而言）正则表达式可能。

语言的复杂性可能是这种规范正则表达式中的运算数量。任何给定正则表达式的实际复杂度可能是其中的运算数。该比率可以让您了解正则表达式的“低效”或“不必要的复杂”程度。

如果你真的需要正则表达式的非 reguar 功能，那么你就不走运了;在高阶语言类中没有可计算最小化的概念。你可以整天发明复杂性指标，但你永远不会得到一个通用的算法答案，即“与基线相比，这有多低效率？另一种说法是：做蛋糕可能比做爆米花更难，但如果你需要蛋糕，你必须付出额外的努力才能得到你需要的东西。