理解正则表达式中的回溯

作者: flyingjimmy | 来源:发表于2017-11-24 09:34 被阅读0次

前段时间看了《高性能JavaScript》一书，其中一章讲到了正则表达式中的回溯对性能的影响。当时看的时候一知半解，现在利用这篇文章重新学习一遍。

这两个量词是理解下面第二个例子的前提。

/h(ello|appy) hippo/.test("hello there, happy hippo");

此正则表达式匹配“hello hippo”或“happy hippo”。

测试一开始，它要查找一个h，目标字符串的第一个字母恰好就是h，它立刻就被找到了。

接下来，子表达式（ello|appy）提供了两个处理选项（分支）。正则表达式首先选择最左边的选项，检查ello是否匹配字符串的下一个字符，确实匹配。然后正则表达式又匹配了后面的空格。再下一步hippo中的h不能匹配字符串中的下一个字母t。

这时就要回溯了，因为前面遇到过分支，我们要试试别的分支的情况。

另一个分支是appy，显然不能匹配hello，并且已经没有别的分支了。所以正则表达式认为从字符串的第一个字符开始匹配是不能成功的，因此它从第二个字符开始，重新进行查找。

它没有找到h，所以就继续向后找，直到第14 个字母才找到，它匹配happy的那个h。

然后它再次进入分支过程。这次ello未能匹配，然后进行第二次回溯，最终它匹配了整个字符串“happy hippo”。

如果看了上面的文字还不是很清楚，下面这张表或许能更好理解一点。

下面我们再来看看带重复量词回溯的例子。

var str = "<p>Para 1.</p>" +
      "<img src='smiley.jpg'>" +
      "<p>Para 2.</p>" +
      "<div>Div.</div>";

/<p>.*<\/p>/i.test(str);

正则表达式一上来就匹配了字符串开始的三个字母，然后是.*，点号匹配除换行符以外的任意字符，星号也就是贪婪量词，会尽可能多地匹配。因为目标字符串中没有换行符，它将吞噬剩下的全部字符串！

不过正则表达式模板中还有更多内容需要匹配，所以正则表达式尝试匹配<。它在字符串末尾匹配不成功，所以它每次回溯一个字符，继续尝试匹配<，直到它回到</div>标签的<位置。

然后它尝试匹配/（转义反斜杠），匹配成功，然后是p，匹配不成功。

正则表达式继续回溯，重复此过程，直到第二段末尾时它终于匹配了。匹配返回成功，它从第一段头部一直扫描到最后一个的末尾，这可能不是你想要的结果，因为匹配结果包含了和。

下面还是用表格来显示匹配过程：

过程	正则	文本	结果
1	<p>.*</p>	<p>Para 1.</p>text<p>Para 2.</p><div>Div.</div>	匹配
2	<p>.*</p>	<p>Para 1.</p>text<p>Para 2.</p><div>Div.</div>	匹配
3	*<p>.<**/p>	<p>Para 1.</p>text<p>Para 2.</p><div>Div.</div>	不匹配，回溯
4	*<p>.<**/p>	<p>Para 1.</p>text<p>Para 2.</p><div>Div.</div>	不匹配，继续回溯
5-7	...	...	...
8	*<p>.<**/p>	<p>Para 1.</p>text<p>Para 2.</p><div>Div.</div>	匹配
9	*<p>.</**p>	<p>Para 1.</p>text<p>Para 2.</p><div>Div.</ div>	匹配
10	*<p>.</p**>	<p>Para 1.</p>text<p>Para 2.</p><div>Div.</div>	不匹配，回溯
11	*<p>.<**/p>	<p>Para 1.</p>text<p>Para 2.</p><div>Div .</div>	不匹配，继续回溯
12-18	...	...	...
19	*<p>.<**/p>	<p>Para 1.</p>text<p>Para 2.</p><div>Div.</div>	匹配
20	*<p>.</**p>	<p>Para 1.</p>text<p>Para 2.</p><div>Div.</div>	不匹配，回溯
21	*<p>.<**/p>	<p>Para 1.</p>text<p>Para 2.</p><div>Div.</div>	不匹配，继续回溯
22-23	...	...	...
24	*<p>.<**/p>	<p>Para 1.</p>text<p>Para 2.</p><div>Div.</div>	匹配
25	*<p>.</**p>	<p>Para 1.</p>text<p>Para 2.</ p><div>Div.</div>	匹配
26	<p>.*</p>	<p>Para 1.</p>text<p>Para 2.</p><div>Div.</div>	匹配
27	<p>.*</p>	<p>Para 1.</p>text<p>Para 2.</p><div>Div.</div>	完全匹配

注：上面第2步其实是会经过多次向后查找匹配，直到遇到换行符，因为目标字符串没有换行符，所以会一直匹配到字符串结尾。

如果要匹配单个段落，那么懒惰量词*?就派上用场了。懒惰量词的回溯工作以相反方式进行。当正则表达式推进到.*?时，它首先尝试全部跳过然后继续匹配。最后它找到了第一个。

还是以表格方式来显示匹配过程吧：

过程	正则	文本	结果
1	<p>.*</p>	<p>Para 1.</p>text<p>Para 2.</p><div>Div.</div>	匹配
2	*<p>.<**/p>	<p>Para 1.</p>text<p>Para 2.</p><div>Div.</div>	尝试匹配0次，不成功
3	<p>.*</p>	<p>Para 1.</p>text<p>Para 2.</p><div>Div.</div>	不匹配
4-8	...	...	...
9	<p>.*</p>	<p>Para 1.</p>text<p>Para 2.</p><div>Div.</div>	匹配
10	<p>.*</p>	<p>Para 1.</ p>text<p>Para 2.</p><div>Div.</ div>	匹配
11	<p>.*</p>	<p>Para 1.</p>text<p>Para 2.</p><div>Div.</div>	匹配
12	<p>.*</p>	<p>Para 1.</p> text<p>Para 2.</p><div>Div.</div>	完全匹配