编写高质量的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='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>/

此正则表达式匹配在正常HTML 字符串时工作良好,但当目标字符串缺少一个或多个标签时,就会变得十分糟糕。例如</html>标签缺失,最后一个[\s\S]*?将扩展到字符串的末尾,因为在那里没有发现</html>标签,然后正则表达式将查看此前的[\s\S]*?队列记录的回溯位置,使它们进一步扩大。正则表达式尝试扩展倒数第二个[\s\S]*?—用它匹配</body>标签,就是此前匹配过正则表达式模板<\/body>的那个标签,然后继续查找第二个</body>标签,直到字符串的末尾。当所有这些步骤都失败时,倒数第三个[\s\S]*?将被扩展,直至字符串的末尾,依此类推。

此类问题的解决办法在于尽可能具体地指出分隔符之间的字符匹配形式,如模板“.*?”用于匹配双引号包围的一个字符串。用更具体的[^"\rn]*取代过于宽泛的.*?就去除了回溯时可能发生的几种情况,如尝试用点号匹配引号,或者扩展搜索超出预期范围。

在HTML 的例子中解决办法不是那么简单。不能使用否定字符类型,如用[^<]替代[\s\S],因为在搜索过程中可能会遇到其他类型的标签。但是,可以通过重复一个非捕获组来达到同样效果,它包含一个回溯(阻塞下一个所需的标签)和[\s\S](任意字符)元序列。这样可以确保中间位置上查找的每个标签都会失败。然后,更重要的是,[\s\S]模板在回溯过程中阻塞的标签在被发现之前不能被扩展。应用此方法后对正则表达式的最终修改如下:

/<html>(?:(?!<head>)[\s\S])*<head>(?:(?!<title>)[\s\S])*<title> (?:(?!<\/title>)[\s\S])*<\/title>(?:(?!<\/head>)[\s\S])*<\/head> (?:(?!<body>)[\s\S])*<body>(?:(?!<\/body>)[\s\S])*<\/body> (?:(?!<\/html>)[\s\S])*<\/html>/

虽然这样做消除了潜在的回溯失控,并允许正则表达式在匹配不完整HTML字符串失败时的使用时间与文本长度呈线性关系,但是正则表达式的效率并没有提高。像这样为每个匹配字符进行多次前瞻,缺乏效率,而且成功匹配过程也相当慢。匹配较短字符串时使用此方法相当不错,而匹配一个HTML 文件可能需要前瞻并测试上千次。

时间: 2024-08-02 08:42:23

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

如何编写高质量JS代码(续)_javascript技巧

继续上一篇文章<如何编写高质量JS代码>今次整理一下javascript函数知识点. 2.使用函数 函数给程序员提供了主要的抽象功能,又提供实现机制.函数可以独立实现其他语言中的多个不同的特性,例如,过程.方法.构造函数,甚至类或模块. 2.1 理解函数调用.方法调用以及构造函数调用之间的不同 针对面向对象编程,函数.方法和类的构造函数是三种不同的概念. 使用模式: 1,函数调用 复制代码 代码如下: function hello(username){     return "hel

深入理解JavaScript系列(1) 编写高质量JavaScript代码的基本要点_javascript技巧

具体一点就是编写高质量JavaScript的一些要素,例如避免全局变量,使用单变量声明,在循环中预缓存length(长度),遵循代码阅读,以及更多. 此摘要也包括一些与代码不太相关的习惯,但对整体代码的创建息息相关,包括撰写API文档.执行同行评审以及运行JSLint.这些习惯和最佳做法可以帮助你写出更好的,更易于理解和维护的代码,这些代码在几个月或是几年之后再回过头看看也是会觉得很自豪的. 书写可维护的代码(Writing Maintainable Code ) 软件bug的修复是昂贵的,并且

如何编写高质量的Javascript代码(1)

优秀的Stoyan Stefanov在他的新书中(<Javascript Patterns>)介绍了很多编写高质量代码的技巧,比如避免使用全局变量,使用单一的var关键字,循环式预存长度等等. 这篇文章不仅仅从代码本身来考虑如何优化编码,也从代码的设计阶段来考虑,包括书写API文档,同事的review,使用JSLint.这些习惯都能帮助你编写更加高质量的.更易于理解的.可维护的代码(让你的代码在多年之后仍使你引以为傲). 编写可维护的代码 软件的BUG修复需要花费大量的精力.尤其当代码已经发布

浅谈对编写高质量文章的三要点

导读:在网络推广中高质量的文章对网站的推广与排名是不言而喻的,但对于许多新站长来说想要独立编写高质量的文章还是有些困难的.今天笔者就以往的经验为大家分享一下,如何编写高质量的文章. 通常我们所说的高质量的文章,并不是你原创一篇文章,然后发布到网站或大型网站后被百度收录就叫高质量的文章.对于高质量的文章不仅仅只是针对搜索引擎,同时还要具有一定的阅读价值以及对需求者的创造价值,只有这样你的文章才可能被更多的人所采用以及宣传,这样一篇高质量的文章才算符合目标. 首先笔者将编写文章可以分为三个部分,即:

《编写高质量代码:改善c程序代码的125个建议》—— 导读

前 言 为什么写作本书 众所周知,C语言是一门既具有高级语言特点,又有汇编语言特点的通用计算机编程语言,无论是操作系统(如Microsoft Windows.Mac OS X.Linux和UNIX等).嵌入式系统与普通应用软件,还是目前流行的移动智能设备开发,随处都可以看见它依然矫健的身影.它能够轻松地应用于各类层次的开发中,从设备驱动程序和操作系统组件到大规模应用程序,它都能够很好地胜任.毋庸置疑,它是二十几年来使用最为广泛.生命力最强的编程语言,它的设计思想也影响了众多后来的编程语言,例如C

编写高质量代码改善C#程序的157个建议[用抛异常替代返回错误、不要在不恰当的场合下引发异常、重新引发异常时使用inner Exception]

原文:编写高质量代码改善C#程序的157个建议[用抛异常替代返回错误.不要在不恰当的场合下引发异常.重新引发异常时使用inner Exception] 前言 自从.NET出现后,关于CLR异常机制的讨论就几乎从未停止过.迄今为止,CLR异常机制让人关注最多的一点就是"效率"问题.其实,这里存在认识上的误区,因为正常控制流程下的代码运行并不会出现问题,只有引发异常时才会带来效率问题.基于这一点,很多开发者已经达成共识:不应将异常机制用于正常控制流中.达成的另一个共识是:CLR异常机制带来

编写高质量代码改善C#程序的157个建议[1-3]

原文:编写高质量代码改善C#程序的157个建议[1-3] 前言 本文主要来学习记录前三个建议. 建议1.正确操作字符串 建议2.使用默认转型方法 建议3.区别对待强制转换与as和is 其中有很多需要理解的东西,有些地方可能理解的不太到位,还望指正. 建议1.正确操作字符串 字符串应该是所有编程语言中使用最频繁的一种基础数据类型.如果使用不慎,我们就会为一次字符串的操作所带来的额外性能开销而付出代价.本条建议将从两个方面来探讨如何规避这类性能开销: 1.确保尽量少的装箱 2.避免分配额外的内存空间

如何编写高质量的VB代码(1)

如何编写高质量的VB代码 简介: 本文描述了如何通过一些技术手段来提高VB代码的执行效率.这些手段可以分为两个大的部分:编码技术和编译优化技术.在编码技术中介绍了如何通过使用高效的数据类型.减少外部引用等编程手段来提高代码执行速度,减少代码消耗的系统资源.在编译优化技术中介绍了如何正确地利用VB提供的编译选项对在编译时最后生成的可执行文件进行优化. 前言 什么是一个高效的软件?一个高效的软件不仅应该比实现同样功能的软件运行得更快,还应该消耗更少的系统资源.这篇文章汇集了作者在使用VB进行软件开发

如何编写高质量的VB代码(2)

如何编写高质量的VB代码(2) 12. 销毁对象 无论编写的是什么软件,程序员都需要考虑在用户决定终止软件运行后释放软件占用的内存空间.但遗憾的是很多程序员对这一点好像并不是很在意.正确的做法是在退出程序前需要销毁程序中使用的对象.例如:Dim FSO as New FileSystemObject注释: 执行操作注释: 销毁对象Set FSO = Nothing对于窗体,可以进行卸载:Unload frmMain 或Set frmMain = Nothing 13. 变长和定长字符串 从技术上