2

正则表达式很快变得太复杂（对我来说）无法理解。即使像[ab][cd], 这样简单的东西也有几个逻辑分支。我的目标是提高代码库的可维护性，因此这些问题的答案可以帮助我们检测和修复复杂代码：

  1. 是否存在包含正则表达式固有的复杂性的计算复杂度度量（类似于圈复杂度）？
  2. 是否有任何工具可以为正则表达式生成复杂度数？
  3. 是否有可以建议简化正则表达式的工具？
4

2 回答 2

2

您可以尝试使用正则表达式的编译形式，并尝试将一些代码复杂度指标映射到该形式，例如代码行数或圈复杂度。要了解我的意思，请查看以下 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)

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

于 2019-02-14T20:35:33.083 回答
1

如果您正在处理与正式正则表达式等效的正则表达式系统（描述正则语言；不计数，不向后查找，不匹配括号对等），或者如果您只处理使用这些的正则表达式功能（尽管您的正则表达式系统能够描述非常规语言），那么就有一个精确的复杂性概念（或者至少您可以推导出一个），并且在某种意义上可以“最小化”正则表达式。

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

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

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

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

于 2019-02-18T13:41:49.290 回答