JavaScript中正则表达式的工作原理和优化
1.前言
正则表达式的优化是一个相当广泛和细致入微的话题。粗浅地编写正则表达式是造成性能瓶颈的主要原因,有很多可以改进正则表达式效率的地方。两个正则表达式匹配相同的文本并不意味着他们具有同等的速度。
2.正则表达式工作原理
一个正则表达式处理的基本步骤:
第一步:编译
当创建了一个正则表达式对象之后(使用一个正则表达式直接量或者 RegExp 构造器),浏览器检查你的模板有没有错误,然后开始执行匹配工作。如果你将正则表达式赋给一个变量,你可以避免重复执行此步骤。
第二步:设置起始位置
当一个正则表达式投入使用时,目标字符串从起始位置开始匹配,或者由正则表达式的 lastIndex 属性指定。当执行到第四步执行失败后,回到上次起始位置的后面一个字符上开始匹配。
第三步:匹配每个正则表达式的字元
正则表达式一旦找好起始位置,它将一个一个地扫描目标文本和正则表达式模板。当一个特定字元匹配失败时,正则表达式将试图回溯到扫描之前的位置上,然后进入正则表达式其他可能的路径上。
第四步:匹配成功或失败
如果在字符串的当前位置上发现一个完全匹配,那么正则表达式宣布成功。如果正则表达式的所有可能路径都尝试过了,但是没有成功地匹配,那么正则表达式引擎回到第二步,从字符串的下一个字符重新尝试。只有字符串中的每个字符(以及最后一个字符后面的位置)都经历了这样的过程之后,还没有成功匹配,那么正则表达式就宣布彻底失败。
3.正则表达式的回溯
正则表达式对目标字符串从左到右依次扫面,在每个字符的位置上是否匹配。对于每一个量词和分支,都必须决定如何继续进行。如果是一个量词(诸如*, +?,或者{2,}),正则表达式必须决定何时尝试匹配更多的字符;如果遇到分支(通过|操作符),它必须从这些选项中选择一个进行尝试。
正则表达式对于每一个量词和分支的匹配,会选择一个方案,然后记住其他选项返回备用。当所选方案匹配成功,继续扫描,如果其他部分的匹配也成功,则匹配结束。而如果所选方案匹配失败,或者其他部分的匹配失败,正则表达式会回溯到上一个选择点,选择其他方案执行上面的过程匹配,如果量词和分支的所有排列组合都匹配失败了,就放弃该位置的匹配,到该位置的下一个字符上重复此过程。
分支结构的栗子:
1 | /h(ello|appy) hippo/.test("hello there, happy hippo"); |
匹配过程:
该正则表达式匹配“hello hippo”或“happy hippo”。
首先查找字符”h”,目标字符串的第一个字符就是h。
接下来有一个分支结构(ello|appy),它提供了两个选项,正则表达式先选择最左边的”ello”匹配,发现匹配。
接下来匹配空格,成功。
下面匹配”h”,不能匹配接下来的字符t,匹配失败。
回溯到上一个检查点(匹配首字符h的下一个字符),匹配下一个分支选项”appy”,匹配失败。
由于没有更多选项,从第二个字符开始重新匹配该字符串。
由于没有找到h继续找到,知道找到第14个字符找到,匹配到h。
接下来匹配分支结构,和上面的过程一个,”ello”匹配失败,回溯到分支过程开始匹配”appy”。
下面匹配”hippo”,匹配成功结束。
量词结构的栗子:
1 | var str = "<p>Para 1.</p><img src='smiley.jpg'><p>Para 2.</p><div>Div.</div>" |
匹配过程:
首先开始匹配了字符串开始三个字符<p>
。
接下来匹配.*
。.
匹配除换行符以外的任意字符,*
是一个贪婪量词,表示重复零次或多次,并且匹配尽量多的次数。因为目标字符串中没有换行符,它将吞噬
剩下的全部字符串!
接下来正则表达式从字符串末尾来时匹配<
,匹配最后一个字符失败,回溯上一个字符继续匹配,直到回到</div>
的<
位置。
然后匹配反斜杠/
。成功。
然后匹配p,失败。
继续回溯,重复上面的过程,直到匹配了</p>
,成功。
这是贪婪匹配的模式,可能有时想要的匹配过程不是这样的。这时可以将贪婪量词*
,改为懒惰量词*?
。懒惰量词的回溯是和贪婪量词相反。当正则表达式/<p>.*?<\/p>/
推进到.*?
时。由于它是尽量少重复的匹配,下面就开始匹配</p>
,匹配字符”P”失败,直到遇到</p>
停止匹配,匹配到的就是<p>Para 1.</p>
。
如果目标字符串只有一个段落,此正则表达式的贪婪版本和懒惰版本是等价的,只是他们尝试匹配的过程不同。
3.提高正则表达式效率的方法
关注如何让匹配更快失败
正则表达式处理慢往往是因为匹配失败过程慢,而不是匹配成功过程慢。让正则匹配更快失效是提高效率的方法之一。
正则表达式以简单的,必需的字元开始
最理想的情况是,一个正则表达式的起始字元应当尽可能快速地排除明显不匹配的位置。用于此目的好的起始字元通常是一个锚( ^或$),特定字符(例如 x 或\u363A),字符类(例如, [a-z]或\d),和单词边界( \b)。如果可能的话,避免以分组或选择字元开头,避免顶级分支例如/one|two/,因为它强迫正则表达式识别多种起始字元。例如例如,以\s\s*
替代\s+
或\s{1,}
。
具体化正则表达式模板
例如当你想表达“[^"\r\n]*
”时不要使用“.*?
”
减少分支的数量,缩小它们的范围
分支使用 |
,可通过使用字符类和选项组件减少对分支的需求,或将分支在正则表达式上的位置推后。例如:
用[cb]at
代替cat|bat
;
用rea?d
代替red|read
;
用r(?:ed|aw)
代替red|raw
;
用[\s\S]
代替(.|\r|\n)
;
字符类比分支更快,因为他们没有使用回溯,避免了性能开销。
将正则表达式赋给变量,以重用它们
将正则表达式赋给变量以避免对它们重新编译。
将复杂的正则表达式拆分为简单的片断
尽量避免一个正则表达式做太多的工作。复杂的搜索问题需要条件逻辑,拆分为两个或多个正则表达式
更容易解决,通常也更高效。
4.什么时候不应该使用正则表达式
小心使用它,正则表达式是非常快的。然而,当你只是搜索文字字符串时就没有必要使用了。
1 | /;$/.test(str); |
上面的正则是匹配末尾分号的。正则表达式一个一个匹配字符串,当遇到分号,就匹配下一个字符看是不是字符串末尾,不是就继续匹配,这样就匹配了整个字符串。这是没有必要的。
更好的办法是跳过正则表达式所需的所有中间步骤, 简单地检查最后一个字符是不是分号:
1 | str.charAt(str.length - 1) == ";"; |
字符串函数 slice, substr,和 substring 可用于在特定位置上提取并检查字符串的值。此外, indexOff和 lastIndexOf函数非常适合查找特定字符串的位置,或者判断它们是否存在。灵活的使用这些函数,可以避免使用正则表达式带来的性能开销。