JavaScript正则表达式,你真的知道?

ymsz7788 5年前
   <h2><strong>前言</strong></h2>    <p>粗浅的编写正则表达式,是造成性能瓶颈的主要原因。如下:</p>    <pre>  <code class="language-javascript">var reg1 = /(A+A+)+B/;    var reg2 = /AA+B/;  </code></pre>    <p>上述两个正则表达式,匹配效果是一样的,但是,效率就相差太远了,甚至在与少量字符串匹配时,reg1就会造成你浏览器卡死。</p>    <p>不信?我们可以测试下。</p>    <p>首先,我们声明一个字符串变量str,同时赋予一个包含20个A的字符串给str,采用match方法与上述reg1、reg2进行匹配测试,如下:</p>    <pre>  <code class="language-javascript">var str = 'AAAAAAAAAAAAAAAAAAAA';    str.match(reg1);    str.match(reg2);  </code></pre>    <p>在浏览器中运行该段代码,发现一切正常嘛。</p>    <p>然而,随着,我们不断向变量str中添加A后,重复测试,在某一刻(取决于你的浏览器),reg1就会让我们的浏览器挂起,但,回头看看最终的str字符串长度,却还不到50。而,reg2却安然无恙。</p>    <p>心里有一丝疑问,是什么造成了它们如此巨大的差别?以后我们在写正则表达式时,又该如何避免防范这类问题呢?</p>    <p>那么,接下来,我们就有必要深入理解JavaScript正则表达式的内部执行原理了。</p>    <p>如果,在此你还不是很了解正则表达式,那么可以参考如下两篇博客后,再前来,小生在此等候。</p>    <h2><strong>正则表达式工作原理</strong></h2>    <p>为了高效的使用正则表达式,理解它们的工作原理是很重要的。</p>    <p>具体如下:</p>    <p><strong>Step1.编译</strong></p>    <p>当我们创建一个正则表达式(字面量或者RegExp对象)后,浏览器会检查该正则的模板是否符合标准,然后将其转化成内部代码,用于执行匹配工作。</p>    <p>所以,如果我们将正则表达式赋予一个变量,可以避免重复执行该 <em>‘编译’</em> 步骤。</p>    <p><strong>Step2.设置开始位置</strong></p>    <p>当我们使用Step1中编译后的正则表达式时,首先它将确定从目标字符串中什么位置进行匹配。通常,是目标字符串的起始位置,或者由正则表达式的lastIndex属性指定。</p>    <p>但是,当它从Step4(匹配失败)中返回时,该位置则为匹配失败的位置的下一个位置。</p>    <p><strong>Step3.正则匹配</strong></p>    <p>当经历Step2后,正则表达式将从指定位置,从左到右,与目标字符串,逐个匹配。若,正则表达式在匹配过程中,遇到某个字元匹配不了时,它不会立即失败,而是尝试回溯到最近一个决策点,然后在剩余选项中选择一个,以求继续能匹配。</p>    <p><strong>Step4.匹配结果</strong></p>    <p>当经历Step3后,发现能与正则匹配成功的子字符串,那么就匹配成功。如果,经历了Step3后,发现没有能与正则匹配的子字符串,那么,它将回到Step2,继续。只有当目标字符串中的每个字符(以及最后一个字符后面的位置)都经历了Step3后,仍没有找到匹配项,才宣布失败。</p>    <p>下面就举个例子,使我们更透彻地明白以上4步。</p>    <p>如下:</p>    <pre>  <code class="language-javascript">var reg = /A(B|C)D/g;    var str = 'ABCACD';    reg.exec(str);  </code></pre>    <p>① 首先,浏览器将解析reg正则表达式(Step1)。</p>    <p>② 然后,由于是首次匹配,所以确认开始位置即为字符串起始位置(Step2)。</p>    <p>③ 首先由正则的第一个字元A与字符串起始位置字符A匹配,成功,并在之后的位置记录一个决策点,因为后面有分支嘛;然后由 (B|C)分支中的B选项去匹配字符串的B,发现匹配;然后再由正则下一个字元D去匹配目标字符串第三个字符C,发现不匹配,但是并没有放弃,而是回溯,查看是否有决策点,发现有,回溯到就近一个决策点(字符串首字母A之后的那个位置上),尝试利用第二个分支选项C去匹配字符串第二个字符B,发现不匹配,回溯,查询是否还有其他分支选项,发现没有,然后宣布该次失败(Step3)。</p>    <p>④ 经历Step3后,发现没有与正则匹配的子字符串,但是,与之匹配的目标字符串的匹配位置并不是最后一个位置,所以,回到Step2,从目标字符串的下一个位置(即,字符串首字母A之后的那个位置上)开始匹配。首先由正则表达式的第一个字元A与目标字符串B匹配,不成功,又无回溯点,故而,进入Step4,判断是否是最后一个位置,发现不是,又跳到Step2中继续。</p>    <p>⑤ 就这样一步一步,来到了目标字符串的第四个位置,首先A去与目标字符串的第三个字符A匹配,成功;接下来就是由分支(B|C),去匹配C,首先由分支中的第一个选项B去与C匹配,发现没有成功,回溯到就近一个决策点,尝试利用第二个分支选项C匹配,成功,紧接着D也成功了。</p>    <p>⑥ 匹配成功,并将lastIndex置为6。</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/edd45735af6d5f873d2a2c0b345897aa.png"></p>    <h2><strong>回溯</strong></h2>    <p>上述 “正则表达式工作原理” 一小节,Step3中的回溯我们是一笔带过的。但是,可不要忽略了,回溯在正则中是非常重要的,如果理解得不明白,我们在编写正则时,很容易造成回溯失控。</p>    <p>下面我们就来一起看看回溯在正则表达式中的运用。</p>    <p>正则表达式中有两种情况,会制造回溯点:</p>    <p>-分支(通过|操作符)</p>    <p>-量词(诸如*,+?,或者{…})</p>    <p>下面我们就分别举例来看看。</p>    <p><strong>分支和回溯</strong></p>    <p>对于分支,详见 <em>‘正则表达式工作原理’</em> 小节中Demo。</p>    <p><strong>量词和回溯</strong></p>    <p>在量词中,有贪婪量词(诸如*,+)和非贪婪量词(诸如*?,+?)之分。所以回溯形式对于它们而言也就有差别咯。我们首先写个demo看看贪婪量词是怎么回溯的。</p>    <p>Demo如下:</p>    <pre>  <code class="language-javascript">var reg = /\w*D/g;    var str = 'MonkyDorie!';    reg.exec(str);  </code></pre>    <p>就上述贪婪模式匹配流程如下:</p>    <p>提醒:正则表达式reg中\w表示匹配“字母、数字或下划线”,*这个贪婪量词表示重复匹配零次或者多次,由于是贪婪量词,故而它会尽可能多的匹配。</p>    <p>① 首先,正则中的\w*与目标字符串匹配,会一直匹配到‘!’之前,即’MonkyDorie’,并且,每个匹配位置都会记录一个决策点,便于回溯。</p>    <p>② 然后,由正则中的剩余字元D与字符串中!匹配,匹配失败;但是,它并没有放弃(因为在此之前,记录了决策点),而是回溯到就近一个决策点(字符e的前一个位置),然后正则D与字符e匹配,匹配失败;再回溯到就近一个决策点(字符i的前一个位置),然后正则D与字符i匹配,匹配失败;就这样一直回溯到字符D的前一个位置时,正则D与字符D匹配,匹配成功,并置lastIndex为6。</p>    <p>好了,这就是上述贪婪匹配流程。</p>    <p>随后,我们将上述Demo中的正则表达式,稍微调整下,在*后面加上?,变成非贪婪模式,看看非贪婪量词是怎么回溯的。</p>    <p>Demo如下:</p>    <pre>  <code class="language-javascript">var reg = /\w*?D/g;    var str = 'MonkyDorie!';    reg.exec(str);  </code></pre>    <p>就上述非贪婪模式匹配流程如下:</p>    <p>提醒:正则表达式reg中\w表示匹配“字母、数字或下划线”,*?是个非贪婪量词,也表示重复匹配零次或者多次,但是由于是非贪婪量词,故而它会尽可能少的匹配。</p>    <p>首先,正则中的\w*?会选择匹配零个字符(尽可能少的匹配),并将第一个位置(字符M的前一个位置)记录一个决策点,继而轮到字元D与字符串字符M匹配,匹配失败;回溯到就近一个决策点(字符M的前一个位置),然后\w*?选择匹配一个字符M,并记录一个回溯点(第二个字符o的前一个位置),继而轮到字元D与字符串字符o匹配,匹配失败;回溯到就近一个决策点(字符o的前一个位置),就这样一步一步,当\w*?选择匹配五个字符Monky时,继而轮到字元D与字符串字符D匹配,匹配成功,并置lastIndex为6.</p>    <p>上述两Demo,对比图如下:</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/ba16014c334db457de59ef8e5aa007dd.png"></p>    <h2><strong>利用前瞻和后向引用避免回溯</strong></h2>    <p>正如上述 <em>‘回溯’</em> 小节中谈到,重复量词和分支会记录决策点,引起回溯。但是,如果在实际需求中,我们不想让它们记录决策点呢—因为回溯太多就会导致回溯失控,影响性能,正如我们在 <em>‘前言’</em> 中看到的那样。</p>    <p>一些正则表达式引擎,支持一种叫做原子组的属性。原子组,写作(?>…),省略号表示任意正则表达式模板。存在原子组中的正则表达式组中的任何决策点都将被丢弃。利用原子组,我们就可以在必要时,消除由重复量词和分支记录的决策点了。</p>    <p>但,在JavaScript中不支持原子组,怎么办呢?</p>    <p>我们可以利用前瞻来模拟原子组,但是,前瞻在整个匹配过程中,是不消耗字符的,它只是检查自己包含的模板是否能在当前位置匹配。然而,我们又可以利用后向引用解决此问题,如下:</p>    <pre>  <code class="language-javascript">(?=(pattern to make atomic))\1  </code></pre>    <p>好了,针对 <em>‘利用前瞻和后向引用避免回溯’</em> 一节,我们写个Demo,自我测试下:</p>    <pre>  <code class="language-javascript">var str = 'ABCDM';   //目标字符串    var reg1 = /\w*M/;   //贪婪模式    var reg2 = /(?=(\w*))\1M/;  //贪婪模式,使用前瞻和后向引用    var reg3 = /\w*?M/;    //非贪婪模式    var reg4 = /(?=(\w*?))M/;    //非贪婪模式,使用前瞻和后向引用  </code></pre>    <p>对于以下匹配结果,各位看官答对否:</p>    <pre>  <code class="language-javascript">str.match(reg1);    str.match(reg2);    str.match(reg3);    str.match(reg4);  </code></pre>    <p> </p>    <p> </p>    <p>来自:http://www.cnblogs.com/giggle/p/5990486.html</p>    <p> </p>