编写高质量的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 文件可能需要前瞻并测试上千次。

赞 (0)

相关推荐

  • VBS创建正则表达式对象的两种方法

    一直以来,我都是用 New RegExp 来创建正则表达式对象的: Set regex = New RegExp然而最新才发现 VBS 的正则表达式对象也可以这样创建: Set regex = CreateObject("VBScript.RegExp")貌似我看过的 VBScript 书籍没有一本介绍过这种写法,当然,书上没写的东西还有很多. 既然提到了正则表达式,那么就顺便说一下,VBS 的正则表达式对象是支持 MultiLine 模式的,对象有一个 MultiLine 属性.运行

  • 用正则表达式 动态创建/增加css style script 兼容IE firefox

    str 是表示通过ajax返回的XMLRequest /*动态加载css style*/ function loadStyle(str) { var regExp_src=/<style.*src\s*=\s*["'][^"']*["'].*>[^<>]*<\/style\s*>/gi; var matchArray_src=str.match(regExp_src); alert(matchArray_src[0]); if(matchA

  • js编写trim()函数及正则表达式的运用

    1.js中本身是没有trim函数的,不过你可以自己写一个 复制代码 代码如下: function trim(str) { var newStr = str.replace(/^\s*$/g,'') retrun newStr; } 2.去除字符串左右两端的空格,在vbscript里面可以轻松地使用 trim.ltrim 或 rtrim,但在js中却没有这3个内置方法,需要手工编写.下面的实现方法是用到了正则表达式,效率不错,并把这三个方法加入String对象的内置方法中去. 写成类的方法格式如下

  • 正则表达式创建方式的区别及编写简单的正则方式(js学习总结)

    在字面量方式中,我们//之间包起来的所有的内容都是元字符,有的具有特殊意义,大部分都是代表本身含义的普通的元字符 var name = 'wo'; var reg = /^\d+"+name+"\d+$/ 为了解决上述想在正则里面加上一个变量这样的需求,我们只能使用实例创建的方式了 var reg = new RegExp("^\\d+"+name+"\\d+$","g") 字面量方式和实例创建的方式在正则中的区别? 1.字面

  • 使用Ruby re模块创建复杂的正则表达式

    例如,考虑下面的匹配日期的正则表达式: 复制代码 代码如下: /\A((?:19|20)[0-9]{2})[\- \/.](0[1-9]|1[012])[\- \/.](0[1-9]|[12][0-9]|3[01])\z/ 使用Re之后,正则表达式可以短小易读的表达式为基础,一步一步地构建出来,例如: 复制代码 代码如下: require 're' include Re delim                = re.any("- /.")century_prefix      

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

    当一个正则表达式扫描目标字符串时,从左到右逐个扫描正则表达式的组成部分,在每个位置上测试能不能找到一个匹配.对于每一个量词和分支,都必须确定如何继续进行.如果是一个量词(如*.+?或者{2,}),那么正则表达式必须确定何时尝试匹配更多的字符:如果遇到分支(通过|操作符),那么正则表达式必须从这些选项中选择一个进行尝试. 当正则表达式做出这样的决定时,如果有必要,它会记住另一个选项,以备返回后使用.如果所选方案匹配成功,正则表达式将继续扫描正则表达式模板,如果其余部分匹配也成功了,那么匹配就结束了

  • 如何编写高质量JS代码(续)

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

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

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

  • 编写高质量代码的30条黄金守则(首选隐式类型转换)

    编写高质量代码的30条黄金守则-Day 01(首选隐式类型转换),本文由比特飞原创发布,转载务必在文章开头附带链接:https://www.byteflying.com/archives/6455 该系列文章由比特飞原创发布,计划用三个月时间写完全30篇文章,为大家提供编写高质量代码的一般准则. 1.概述 隐式类型转换是微软为了 C# 支持匿名类型而加入的,使用 var 通常可以使代码的可读性更强,甚至是帮我们解决一些严重的性能问题.为了清楚的明白 var 的作用机制,我们首先来看看编译器为 v

  • 如何编写高质量 JavaScript 代码

    如何编写高质量 JavaScript 代码

    目录 一.易阅读的代码 1.统一代码格式 2.去除魔术数字 3.单一功能原则 二.高性能的代码 1.优化算法 2.使用内置方法 3.减少作用域链查找 4.避免做重复的代码 三.健壮性的代码 1.使用新语法 2.随时可扩展 3.避免副作用 4.整合逻辑关注点 前段时间有一个叫做"人类高质量男性"的视频火了,相信很多同学都刷到过.所以今天给大家分享下,什么叫做"人类高质量代码",哈哈,开个玩笑. 其实分享的都是一些自己平时总结的小技巧,算是抛砖引玉吧,希望能给大家带来一

  • 编写高质量JavaScript代码的基本要点

    才华横溢的Stoyan Stefanov,在他写的由O'Reilly初版的新书<JavaScript Patterns>(JavaScript模式)中,我想要是为我们的读者贡献其摘要,那会是件很美妙的事情.具体一点就是编写高质量JavaScript的一些要素,例如避免全局变量,使用单变量声明,在循环中预缓存length(长度),遵循代码阅读,以及更多. 此摘要也包括一些与代码不太相关的习惯,但对整体代码的创建息息相关,包括撰写API文档.执行同行评审以及运行JSLint.这些习惯和最佳做法可以

  • 编写高质量代码改善C#程序——使用泛型集合代替非泛型集合(建议20)

    软件开发过程中,不可避免会用到集合,C#中的集合表现为数组和若干集合类.不管是数组还是集合类,它们都有各自的优缺点.如何使用好集合是我们在开发过程中必须掌握的技巧.不要小看这些技巧,一旦在开发中使用了错误的集合或针对集合的方法,应用程序将会背离你的预想而运行. 建议20:使用泛型集合代替非泛型集合 在建议1中我们知道,如果要让代码高效运行,应该尽量避免装箱和拆箱,以及尽量减少转型.很遗憾,在微软提供给我们的第一代集合类型中没有做到这一点,下面我们看ArrayList这个类的使用情况: Array

  • 如何编写高质量JS代码

    想写出高效的javascript类库却无从下手: 尝试阅读别人的类库,却理解得似懂给懂: 打算好好钻研js高级函数,但权威书上的内容太零散, 即使记住"用法",但到要"用"的时候却没有想"法". 也许你和我一样,好像有一顾无形的力量约束着我们的计划,让我们一再认为知识面的局限性,致使我们原地踏步,难以向前跨越. 这段时间,各种作业.课程设计.实验报告,压力倍增.难得挤出一点点时间,绝不睡懒觉,整理总结往日所看的书,只为了可以离写自己的类库近一点.

  • 深入理解javascript学习笔记（一） 编写高质量代码

    一.变量 •全局变量 JavaScript的两个特征,不自觉地创建出全局变量是出乎意料的容易.首先,你可以甚至不需要声明就可以使用变量:第二,JavaScript有隐含的全局概念,意味着你不声明的任何变量都会成为一个全局对象属性(不是真正意义上的全局变量,可以用delete删除) 复制代码 代码如下: function sum(x,y) { // result 未声明,为隐式全局变量 result = x + y; return result; } function foo() { // 使用任

  • 编写高质量易语言代码注意点

    今天在淘百度的时候看到了这篇文章.觉得很不错.就给亲们分享下. 如果你想学好易语言的话请仔细看看以下的内容吧.看完此文之后保证你大有收获. 什么是一个高效的软件?一个高效的软件不仅应该比实现同样功能的软件运行得更快,还应该消耗更少的系统资源.程序的时间效率是指运行速度,空间效率是指程序占用内存或者外存的状况.另外程序的效率我们也可以分为全局效率和局部效率.全局效率是指站在整个系统的角度上考虑的效率,局部效率是指站在模块或函数角度上考虑的效率. 1. 使用整数和长整数 提高代码运行速度最简单的方法

随机推荐