浅谈正则表达式解析过程 / 效率优化

前言

编写高性能的正则表达式，有如下几条规则，这几条规则是本人总结出来的：

1、使用正确的边界匹配器（^、$、b、B等）

2、使用具体的元字符、字符类（d、w、s等）

3、使用正确的量词（+、*、?、{n,m}）

4、使用非捕获组、原子组

5、注意量词的嵌套

其实正则表达式的很多优化技巧都是围绕着“减少回溯”这样一个原则进行优化的。

至于什么是“回溯”，笔者就不在这里重复了，以下通过具体的例子理解这样的过程。

示例

一、以下是一则匹配电子邮件地址的正则表达式：

先一步步的解析：

1、^w+：表示必须以字符开始， 且是一个或者多个；

2、([.-]?w+)*中的“[.-]?”表示匹配“.”或者“-”，零次或者一次；

3、([.-]?w+)*中的“w+”则表示匹配一个或者多个的字符；

4、([.-]?w+)*整个则表示匹配.xxx、-xxx或者xxx这样的字符，且零次或者多次；

5、第1-4步，则匹配sunny或者sunny.yang这样的字符；

6、“@”则是具体元，匹配具体的@；

7、 w+：则表示匹配的一个或者多个的字符，因为email不可能这样嘛：sunny@.gmail.com；

8、([.-]?w+)*：则跟第2-4步一样，匹配.163、-lib、.gd这样的字符，且零次或者多次；

9、(.w{2,3})+$：则匹配.com、.cc这样结尾的域名，且因为w{2,3}限定了长度必须为2-3位，所以不能匹配.c、.n这样的字符。

乍看这样一个解析过程没问题，逻辑正确，但其实暗藏很多问题，看看以下的一个匹配图，backtrack则表示回溯（使用RegexBuddy可以很清晰的看到这过程）

整个成功的匹配过程经历了55步，我们先分析下整个匹配过程：

4、图中第5步，因为上一步产生了回溯，所以“[.-]?w+”匹配了零次，由于([.-]?w+)*中限定零次或者多次，因此也匹配成功，也没匹配上具体的字符；

以下步骤，匹配该过程：

5、图中第6步，匹配了“@” ，第7步匹配了“w+”，即匹配了“open”；

6、图中第8-13步，匹配“([.-]?w+)*” ，匹配了“-lib”、“.com”，匹配“.com”可能与我们期望不相符，我们期望这子表达式匹配的是www.xx.gd.cn中的“.gd”；

7、图中第7-10步，匹配了open-lib，第7-13步则匹配了open-lib.com；

8、因为“([.-]?w+)*”中的量词是“*”，则继续重复这个过程；

9、 图中第14步，匹配“([.-]?w+)*”中的“[.-]?”，因为此时指针已经位于@open-lib.com之后了，但由于量词“?”，因此也匹配成功，但没匹配上字符，也没字符可匹配；

10、 图中第15步，匹配“([.-]?w+)*”中的“w+”，此时指针仍位于字符串末尾，没任何字符能匹配，所以匹配失败，产生回溯，回到上次成功的位置，即图中的第13步，继续下个表达式的匹配；

11、 图中第16步，匹配(.w{2,3})+中的“.”，由于没有任何字符能匹配，匹配失败，进行回溯；

12、图中第17步 ，(.w{2,3})+中量词“+”，表示该表达式必须匹配一次或者多次，由于上一步匹配失败了，所以匹配零次，但不符合一次或者多次的限定，因此继续回溯；

13、由于上一步匹配失败，需要进行回溯，因此表达式没有更多的分支了，只能将指针回退一个字符，回溯上次成功的位置，即([.-]?w+)*中w+的位置（这是上次产生分支的位置）；

14、图中剩下的步骤，就重复着匹配([.-]?w+)*，回退字符，匹配(.w{2,3})+这样的过程，直到匹配成功。

二、以下看看另外一则同样匹配邮件地址的正则表达式：

这个正则跟上面的看起来貌似差不多，不过细看还是有区别的，也先一步步来解析：

1、^w+：表示必须以字符开始， 且是一个或者多个（这一步与上面的一样）；

2、([-.]w+)*中的“[-.]”表示匹配“-”或者“.”；

3、([-.]w+)*中的“w+”则表示匹配一个或者多个的字符；

5、第1-4步，则匹配sunny或者sunny.yang这样的字符；

8、([-.]w+)*：则跟第2-4步一样，匹配.163、-lib、.gd这样的字符，且零次或者多次；

9、“.”则是具体元，匹配“.”；

10、w+：则匹配一个或者多个字符；

11、([-.]w+)*：则匹配“.com”、“-lib”、“.c”这样的字符，且可以零次或者多次；

12、$：则表示结尾

乍看这个正则的步骤过程貌似比上一则长，其实不然，同时这个正则也存在着问题，先看看匹配图，同样backtrack表示回溯：

对的，你没看错，整个正确的匹配过程用了19步，对比前面的55步，简直天与地的差别。，我们继续分析下匹配过程：

3、图中第4步，因为上一步产生了回溯，所以“[-.]w+”匹配了零次，由于([-.]w+)*中限定零次或者多次，因此也匹配成功，也没匹配上具体的字符；

^w+([-.]w+)* @ w+([-.]w+)*.w+([-.]w+)*$

4、图中第6步w+，匹配了open；

5、图中第7-12步匹配([-.]w+)*，匹配了“-lib”和“.com”；

6、因为“([-.]w+)*”中的量词是“*”，则继续重复这个过程；

7、图第13步，匹配([-.]w+)*，因为此时指针已经位于@open-lib.com之后了，也没具体的量词允许匹配零次，因此匹配失败，回溯到上次成功的位置；

8、图第14步，匹配([-.]w+)*$中的“[-.]”，此时指针仍位于字符串末尾，没任何字符能匹配，所以匹配失败，产生回溯，回到上次成功且还没尝试过的位置，即图中的第9步；

9、经过上面的回溯，指针已经位于@open-lib之后的位置了；

10、图第15步匹配了“.”，第16步w+则匹配了“com” ；

11、图第17步匹配([-.]w+)*，由于此时指针又位于字符串末尾，因此[-.]部分没匹配上任何字符，因此产生回溯；

12、图第18步，由于([-.]w+)*的量词是“*”，表示匹配零次或多次，虽然子表达式[-.]匹配失败，所以整个表达式匹配了零次，也是匹配成功；

13、最后一步第19步，“$”表示末尾匹配，因为此时指针位于字符串末尾，故符合，因此也匹配成功。

分析

整个匹配过程关键优化地方，还是回溯，两个示例表达式看起来相近，匹配过程也部分类似，但两个例子的效率却如此大的分别，现在来分析一下造成回溯的原因。

对比下两个表达式不同的部分：

^w+([.-]w+)*@w+([.-]w+)*.w+([-.]w+)*$

（编辑：李大同）

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