编写高质量的js之正确理解正则表达式回溯

当一个正则表达式扫描目标字符串时,从左到右逐个扫描正则表达式的组成部分,在每个位置上测试能不能找到一个匹配。对于每一个量词和分支,都必须确定如何继续进行。如果是一个量词(如*、+?或者{2,}),那么正则表达式必须确定何时尝试匹配更多的字符;如果遇到分支(通过|操作符),那么正则表达式必须从这些选项中选择一个进行尝试。

当正则表达式做出这样的决定时,如果有必要,它会记住另一个选项,以备返回后使用。如果所选方案匹配成功,正则表达式将继续扫描正则表达式模板,如果其余部分匹配也成功了,那么匹配就结束了。但是,如果所选择的方案未能发现相应匹配,或者后来的匹配也失败了,正则表达式将回溯到最后一个决策点,然后在剩余的选项中选择一个。继续这样,直到找到一个匹配,或者量词和分支选项的所有可能的排列组合都尝试失败后放弃这一过程,然后移动到此过程开始位置的下一个字符上,重复此过程。

例如,下面的代码演示了这一过程是如何通过回溯处理分支的。

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

上面一行正则表达式用于匹配“hello hippo”或“happy hippo”。测试一开始要查找一个h,目标字符串的第一个字母恰好就是h,立刻就找到了。接下来,子表达式(ello|appy)提供了两个处理选项。正则表达式选择最左边的选项(分支选择总是从左到右进行),检查ello 是否匹配字符串的下一个字符,确实匹配,然后正则表达式又匹配了后面的空格。

然而,在接下来的匹配中正则表达式“走进了死胡同”,因为hippo 中的h 不能匹配字符串中的下一个字母t。此时正则表达式还不能放弃,因为它还没有尝试过所有的选择,随后它回溯到最后一个检查点(在匹配了首字母h 之后的那个位置上)并尝试匹配第二个分支选项。但由于匹配没有成功,而且也没有更多的选项了,正则表达式认为从字符串的第一个字符开始匹配是不能成功的,因此它从第二个字符开始重新进行查找。正则表达式没有找到h,继续向后找,直到第14 个字母才找到,它匹配happy 的那个h。随后正则表达式再次进入分支过程,这次ello 未能匹配,但在回溯之后的第二次分支中,它匹配了整个字符串“happy hippo”,匹配成功了。

再如,下面代码演示了带重复量词的回溯。

var str = "<p>Para 1.</p>" +"<img src='https://www.jb51.net/smiley.jpg'>" +"<p>Para 2.</p>" +"<div>Div.</div>"; /<p>.*<\/p>/i.test(str);

正则表达式先匹配了字符串开始的3个字母<p>,然后是.*。点号表示匹配除换行符以外的任意字符,星号这个“贪婪”量词表示重复零次或多次,匹配尽量多的次数。因为目标字符串中没有换行符,正则表达式将匹配剩下的全部字符串!不过由于正则表达式模板中还有更多内容需要匹配,所以正则表达式尝试匹配<。由于在字符串末尾匹配不成功,因此每次回溯一个字符,继续尝试匹配<,直到正则表达式回到</div>标签的<位置。接下来尝试匹配\/(转义反斜杠),匹配成功,然后匹配p,匹配不成功。正则表达式继续回溯,重复此过程,直到第二段末尾时终于匹配了</p>。匹配返回成功需要从第一段头部一直扫描到最后一个的末尾,这可能不是我们想要的结果。

将正则表达式中的“贪婪”量词*改为“懒惰”(又名“非贪婪”)量词*?,以匹配单个段落。“懒惰”量词的回溯工作以相反方式进行。当正则表达式/<p>.*?<\/p>/推进到.*?时,首先尝试全部跳过,然后继续匹配<\/p>。

这样做是因为*?匹配零次或多次,尽可能少重复,尽可能少意味着可以重复零次。但是,当随后的<在字符串的这一点上匹配失败时,正则表达式回溯并尝试下一个最小的字符数:1个。正则表达式继续像这样向前回溯到第一段的末尾,在那里量词后面的<\/p>得到完全匹配。

如果目标字符串只有一个段落,那么此正则表达式的“贪婪”版本和“懒惰”版本是等价的,但尝试匹配的过程不同。

当一个正则表达式占用浏览器几秒甚至更长时间时,问题原因很可能是回溯失控。为说明此问题,给出下面的正则表达式,它的目标是匹配整个HTML文件。此表达式被拆分成多行是为了适合页面显示。与其他正则表达式不同,JavaScript在没有选项时可使点号匹配任意字符,包括换行符,所以此例中以[\s\S]匹配任意字符。

/<html>[\s\S]*?<head>[\s\S]*?<title>[\s\S]*?<\/title>[\s\S]*?<\/head> [\s\S]*?<body>[\s\S]*?<\/body>[\s\S]*?<\/html>/

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wjssjg.html