前段时间看了《高性能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”。
如果看了上面的文字还不是很清楚，下面这张表或许能更好理解一点。
| 过程 | 正则 | 文本 | 结果 |
|---|---|---|---|
| 1 | h(ello|appy) hippo | hello there, happy hippo | 匹配 |
| 2 | h(ello|appy) hippo | hello there, happy hippo | 匹配 |
| 3 | h(ello|appy) hippo | hello there, happy hippo | 不匹配，回溯 |
| 4 | h(ello|appy) hippo | hello there, happy hippo | 不匹配 |
| 5 | h(ello|appy) hippo | hello there, happy hippo | 第二个字符不匹配 |
| 6 | h(ello|appy) hippo | hello there, happy hippo | 第三个字符不匹配 |
| 7-17 | ... | ... | ... |
| 18 | h(ello|appy) hippo | hello there, happy hippo | 匹配 |
| 19 | h(ello|appy) hippo | hello there, happy hippo | 不匹配，回溯 |
| 20 | h(ello|appy) hippo | hello there, happy hippo | 匹配 |
| 21 | h(ello|appy) hippo | hello there, happy hippo | 匹配 |
| 22 | h(ello|appy) hippo | hello there, happy hippo | 匹配 |
| 23 | h(ello|appy) hippo | hello there, happy hippo | 匹配 |
| 24 | h(ello|appy) hippo | hello there, happy hippo | 匹配 |
| 25 | h(ello|appy) hippo | hello there, happy hippo | 完全匹配 |
下面我们再来看看带重复量词回溯的例子。
var str = "<p>Para 1.</p>" +
"<img src='smiley.jpg'>" +
"<p>Para 2.</p>" +
"<div>Div.</div>";
/<p>.*<\/p>/i.test(str);
正则表达式一上来就匹配了字符串开始的三个字母<p>，然后是.*，点号匹配除换行符以外的任意字符，星号也就是贪婪量词，会尽可能多地匹配。因为目标字符串中没有换行符，它将吞噬剩下的全部字符串！
不过正则表达式模板中还有更多内容需要匹配，所以正则表达式尝试匹配<。它在字符串末尾匹配不成功，所以它每次回溯一个字符，继续尝试匹配<，直到它回到</div>标签的<位置。
然后它尝试匹配/（转义反斜杠），匹配成功，然后是p，匹配不成功。
正则表达式继续回溯，重复此过程，直到第二段末尾时它终于匹配了</p>。匹配返回成功，它从第一段头部一直扫描到最后一个的末尾，这可能不是你想要的结果，因为匹配结果包含了</p>和<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步其实是会经过多次向后查找匹配，直到遇到换行符，因为目标字符串没有换行符，所以会一直匹配到字符串结尾。
如果要匹配单个段落，那么懒惰量词*?就派上用场了。懒惰量词的回溯工作以相反方式进行。当正则表达式推进到.*?时，它首先尝试全部跳过然后继续匹配</p>。最后它找到了第一个</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> | 尝试匹配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> | 完全匹配 |
如果目标字符串只有一个段落，你可以看到此正则表达式的贪婪版本和懒惰版本是等价的，但是他们尝试匹配的过程不同。
参考：
http://www.cnblogs.com/aaronjs/archive/2012/06/30/2570805.html
https://zhuanlan.zhihu.com/p/27417442
