关于正则的优化分析

Question

前些天看编译原理，看到了把正则语句的状态机分析，把NFA转换为DFA再进行优化，所以想着能不能反过来用这套分析法去优化正则语句。我试了下【匹配数字】和【/(a*b+)*/正则语句的优化】。
匹配数字：

结论：加上起止符号，数字匹配的最优写法是/^\d*(.\d+)?$/
/(a*b+)*/正则语句的优化：

结论是NFA语法的/(a*b+)*/可以转换成DFA的/((a|b)*b)?/

但是，/(a*b+)*/正则语句的优化感觉得到/((a|b)*b)?/的过程很生硬，不知道应该怎么去解释，正则优化这块有比较好的理论分析方法吗？

Answer 1

我觉得可以这么看，b+ 可以看成 b*b，这样的话 a*b*b 就缩成 (a|b)*b。
然后 ((a|b)*b)*，外面的贪婪不会比里面的贪婪范围更大，因此保留 0 次和 1 次，就变成了 ?

大概可以这么去理解吧

===== 补充

说实话写的时候可能根本不会想到这么多，大多是按照直觉和顺序去写。不过也有很多文章说，为了正则的性能，少用或、少用限定、少用组、之类之类的，什么优化最根本是减少回溯，所以少贪婪，就有点儿玄学。

Answer 2

看了些评论，你的优化目标好像是想让 RE 匹配得更快。

但这有一个问题，就是程序设计中得正则表达式匹配，基本就没有用 NFA/DFA 来实现的。于是 NFA/DFA 来指导这个优化，可能意义不大。

并且，RE -> NFA , DFA -> RE ，算法貌似都不是只有一个，结果是没有办法保证的。

如果一个算法用 DFA 来匹配的话，那么他可以将 RE 转化为最小的 DFA （这个是唯一的）来进行匹配。RE 的写法仅影响转化的时间，不影响匹配的时间。这时 RE 的写法其实不太重要，容易理解优先。

不过，现实的正则表达式匹配通常都是用类似于上下文无关文法匹配的方式写的（为了实现提取匹配到串等功能）。这个算法本质上是指数级的复杂度，正则写得不好真得非常慢，但这与正则会转化成什么样的 NFA/DFA 无关。

---

另外，NFA 也是不用回溯的。DFA 匹配的时候是从一个状态走到下一个状态，最后到达结束状态就成功。对应到 NFA ，就是从一个状态集走到下一个状态集，最后到达的状态集里只要有一个是结束状态就算成功，不需要回溯。状态集的规模不会超过 NFA 的总状态数，匹配复杂性依然是很低。

Answer 3

不知道你疑惑的是NFA转DFA的逻辑，还是不理解图，还是说不理解图对应的正则表达式。一一解释一下吧。
图有很多种画法，这里我偷个懒，就借用你的图去说了。

1. 先画出(a*b+)*

a*b+可拆分为a+b+和b+（分支），而a+b+可进一步拆分为a+和b+（顺序）。

a+

a+b+

a+b+画完了，p0是起始点，p3是这个分支的终点。

b+

b+画完了，p0是起始点，p2是这个分支的终点。

然后，是画(a*b+)*。我们可以将其拆分为(a*b+)?(a*b+)?(a*b+)?...。
我们先只看前2个部分(a*b+)?(a*b+)?，这里可以类似地拆分为(a*b+)?(a+b+)?和(a*b+)?(b+)?。

其中，(a*b+)?(a+b+)?可拆分为(a+b+)?(a+b+)?，即重复p1到p3的流程；

(a+b+)*

(a*b+)?(a+b+)?还可拆分为(b+)?(a+b+)?，即p2到p1，再到p3的流程。

(b+)?(a+b+)

再来看最后的一部分(a*b+)?(b+)?，同样可拆分为(a+b+)?(b+)?和(b+)?(b+)?。
其中，(a+b+)?(b+)?可合并为(a+b+)?，即原先的p0到p1再到p3的流程；
而(b+)?(b+)?可合并为(b+)?，即原先的p0到p2的流程。

所以，得到NFA图：

2. NFA转DFA的逻辑

我们发现p2和p3都是终点，且它们都可以表述b*，而从p2和p3都有一条相同的a路径指向p1，所以我们可以将p2和p3合并成同一个点。即得到下图：

3. DFA的正则表达式

先看p0出发有2个分支，分别到p1和p2两点，即a|b。
p1和p2分别有指向自己的边，即相当于(a|b)+。
另外，p1和p2有分别指向对方的边，即(a|b)*。
由于，结束点是p2，所以，最后必定会经过b路径，即(a|b)*b。
又由于(a|b)*b中变成了要求最后至少经过一次b，但实际情况是，我们这个整体可以重复0次，所以要加上?，即((a|b)*b)?。

---

抛开这个示例说，这里的图其实不是很清晰，除非非常熟悉的情况，否则不可能一下子画出这样的图。
通常情况下，可以参考此文章画一下状态机的图。https://houbb.github.io/2020/...
然后再根据此文章中NFA转DFA的算法进行转换。https://houbb.github.io/2020/...

最后提一句，如果正则表达式中还有捕获组，会更难优化。优化后确实可以避免回溯，从而提升性能，但相对于其他可提升性能的点微乎其微，可以作为优化的最后手段，对于复杂的表达式，虽然优化后可以提升很多性能，但也许使用词法分析或其他手段也许能更高效。