一次性搞懂JavaScript正则表达式之引擎

时间: 2018-12-12阅读: 738标签: 正则

我们说正则表达式是语言无关的,是因为驱动正则表达式的引擎是相似的。鉴于正则表达式是一种古老的语法,它的引擎也在历史长河中衍生出了几个大的分支。

我会关注到正则表达式引擎这样比较底层的实现,缘起于在一次业务实践中,追踪到一个由正则引起的BUG。业务中使用的一个markdown解析库Remarkable在解析一段不规则文本时引起浏览器崩溃,调试之后发现是某一个正则在匹配时陷入了死循环,严格的说(后来才知道)是匹配花费了过多时间导致浏览器卡死。

我当时很震惊,正则匹配的性能不是很高的么?匹配到就是匹配到,没匹配到就是没匹配到,怎么会在里面走不出来了呢?


有限自动机

什么叫有限自动机(Finite Automate)呢?

我们把有限自动机理解为一个机器人,在这个机器人眼里,所有的事物都是由有限节点组成的。机器人按照顺序读取有限节点,并表达成有限状态,最终机器人输出接受或者拒绝作为结束。

关注它的两个特点:

  • 有限状态集。
  • 只根据当前状态和当前输入来决定下一个状态。它有点一板一眼。

怎么理解第二个特点?我们看一个例子:

'aab'.match(/a*?b/);
// ["aab", index: 0, input: "aab", groups: undefined]

我们知道*?是非贪婪匹配,按照我们人类灵活的尿性,直接把匹配结果ab甩他脸上。

但有限自动机不会。第一步它用a匹配a非常完美,然后发现对于a是非贪婪模式,于是试着用b匹配下一个a,结果非常沮丧。于是它只能继续用a匹配,匹配成功后依然没忘非贪婪特性,继续试着用b匹配下一个字符b,成功,收官。

其实写出这段代码的开发者想要的结果应该是ab,但有限自动机从来不仰望星空,只低头做事,一板一眼的根据当前状态和当前输入来决定下一个状态。


DFA与NFA

有限自动机大体上又可以分为两类:DFA是确定性有限自动机的缩写,NFA是非确定性有限自动机的缩写。

我没办法告诉你DFA与NFA在原理上的差别,但咱们可以探讨一下它们在处理正则上的表现差异。

总的来说,DFA可以称为文本主导的正则引擎,NFA可以称为表达式主导的正则引擎。

怎么讲?

我们常常说用正则去匹配文本,这是NFA的思路,DFA本质上其实是用文本去匹配正则。哪个是攻,哪个是受,大家心里应该有个B数了吧。

我们来看一个例子:

'tonight'.match(/to(nite|knite|night)/);

如果是NFA引擎,表达式占主导地位。表达式中的t和o不在话下。然后就面临三种选择,它也不嫌累,每一种都去尝试一下,第一个分支在t这里停止了,接着第二个分支在k这里也停止了。终于在第三个分支柳暗花明,找到了自己的归宿。

换作是DFA引擎呢,文本占主导地位。同样文本中的t和o不在话下。文本走到n时,它发现正则只有两个分支符合要求,经过i走到g的时候,只剩一个分支符合要求了。当然,还要继续匹配。果然没有令它失望,第三个分支完美符合要求,下班。

大家发现什么问题了吗?

只有正则表达式才有分支和范围,文本仅仅是一个字符流。这带来什么样的后果?就是NFA引擎在匹配失败的时候,如果有其他的分支或者范围,它会返回,记住,返回,去尝试其他的分支。而DFA引擎一旦匹配失败,就结束了,它没有退路。

这就是它们之间的本质区别。其他的不同都是这个特性衍生出来的。

首先,正则表达式在计算机看来只是一串符号,正则引擎首先肯定要解析它。NFA引擎只需要编译就好了;而DFA引擎则比较繁琐,编译完还不算,还要遍历出表达式中所有的可能。因为对DFA引擎来说机会只有一次,它必须得提前知道所有的可能,才能匹配出最优的结果。

所以,在编译阶段,NFA引擎比DFA引擎快。

其次,DFA引擎在匹配途中一遍过,溜得飞起。相反NFA引擎就比较苦逼了,它得不厌其烦的去尝试每一种可能性,可能一段文本它得不停返回又匹配,重复好多次。当然运气好的话也是可以一遍过的。

所以,在运行阶段,NFA引擎比DFA引擎慢。

最后,因为NFA引擎是表达式占主导地位,所以它的表达能力更强,开发者的控制度更高,也就是说开发者更容易写出性能好又强大的正则来,当然也更容易造成性能的浪费甚至撑爆CPU。DFA引擎下的表达式,只要可能性是一样的,任何一种写法都是没有差别(可能对编译有细微的差别)的,因为对DFA引擎来说,表达式其实是死的。而NFA引擎下的表达式,高手写的正则和新手写的正则,性能可能相差10倍甚至更多。

也正是因为主导权的不同,正则中的很多概念,比如非贪婪模式、反向引用、零宽断言等只有NFA引擎才有。

所以,在表达能力上,NFA引擎秒杀DFA引擎。

当今市面上大多数正则引擎都是NFA引擎,应该就是胜在表达能力上。


测试引擎类型

现在我们知道正则表达式的驱动引擎分为两大类:DFA引擎与NFA引擎。

但是因为NFA引擎比较灵活,很多语言在实现上有细微的差别。所以后来大家弄了一个标准,符合这个标准的正则引擎就叫做POSIX NFA引擎,其余的就只能叫做传统型NFA引擎咯。

我们来看看JavaScript到底是哪种引擎类型吧。

'123456'.match(/\d{3,6}/);
// ["123456", index: 0, input: "123456", groups: undefined]
'123456'.match(/\d{3,6}?/);
// ["123", index: 0, input: "123456", groups: undefined]

《精通正则表达式》书中说POSIX NFA引擎不支持非贪婪模式,很明显JavaScript不是POSIX NFA引擎。

TODO: 为什么POSIX NFA引擎不支持也没有必要支持非贪婪模式?

区分DFA引擎与传统型NFA引擎就简单咯,捕获组你有么?花式零宽断言你有么?

结论就是:JavaScript的正则引擎是传统型NFA引擎。


回溯

现在我们知道,NFA引擎是用表达式去匹配文本,而表达式又有若干分支和范围,一个分支或者范围匹配失败并不意味着最终匹配失败,正则引擎会去尝试下一个分支或者范围。

正是因为这样的机制,引申出了NFA引擎的核心特点——回溯。

首先我们要区分备选状态和回溯。

什么是备选状态?就是说这一个分支不行,那我就换一个分支,这个范围不行,那我就换一个范围。正则表达式中可以商榷的部分就叫做备选状态。

备选状态是个好东西,它可以实现模糊匹配,是正则表达能力的一方面。

回溯可不是个好东西。想象一下,面前有两条路,你选择了一条,走到尽头发现是条死路,你只好原路返回尝试另一条路。这个原路返回的过程就叫回溯,它在正则中的含义是吐出已经匹配过的文本。

我们来看两个例子:

'abbbc'.match(/ab{1,3}c/);
// ["abbbc", index: 0, input: "abbbc", groups: undefined]
'abc'.match(/ab{1,3}c/);
// ["abc", index: 0, input: "abc", groups: undefined]

第一个例子,第一次a匹配a成功,接着碰到贪婪匹配,不巧正好是三个b贪婪得逞,最后用c匹配c成功。

正则文本
/a/a
/ab{1,3}/ab
/ab{1,3}/abb
/ab{1,3}/abbb
/ab{1,3}c/abbbc

第二个例子的区别在于文本只有一个b。所以表达式在匹配第一个b成功后继续尝试匹配b,然而它见到的只有黄脸婆c。不得已将c吐出来,委屈一下,毕竟贪婪匹配也只是尽量匹配更多嘛,还是要臣服于匹配成功这个目标。最后不负众望用c匹配c成功。

正则文本
/a/a
/ab{1,3}/ab
/ab{1,3}/abc
/ab{1,3}/ab
/ab{1,3}c/abc

请问,第二个例子发生回溯了吗?

并没有。

诶,你这样就不讲道理了。不是把c吐出来了嘛,怎么就不叫回溯了?

回溯是吐出已经匹配过的文本。匹配过程中造成的匹配失败不算回溯。

为了让大家更好的理解,我举一个例子:

你和一个女孩子(或者男孩子)谈恋爱,接触了半个月后发现实在不合适,于是提出分手。这不叫回溯,仅仅是不合适而已。

你和一个女孩子(或者男孩子)谈恋爱,这段关系维持了两年,并且已经同居。但由于某些不可描述的原因,疲惫挣扎之后,两人最终还是和平分手。这才叫回溯。

虽然都是分手,但你们应该能理解它们的区别吧。

网络上有很多文章都认为上面第二个例子发生了回溯。至少根据我查阅的资料,第二个例子发生的情况不能被称为回溯。当然也有可能我是错的,欢迎讨论。

我们再来看一个真正的回溯例子:

'ababc'.match(/ab{1,3}c/);
// ["abc", index: 2, input: "ababc", groups: undefined]

匹配文本到ab为止,都没什么问题。然而苍天饶过谁,后面既匹配不到b,也匹配不到c。引擎只好将文本ab吐出来,从下一个位置开始匹配。因为上一次是从第一个字符a开始匹配,所以下一个位置当然就是从第二个字符b开始咯。

正则文本
/a/a
/ab{1,3}/ab
/ab{1,3}/aba
/ab{1,3}/ab
/ab{1,3}c/aba
/a/ab
/a/aba
/ab{1,3}/abab
/ab{1,3}/ababc
/ab{1,3}/abab
/ab{1,3}c/ababc

一开始引擎是以为会和最早的ab走完余生的,然而命运弄人,从此天涯。

这他妈才叫回溯!

还有一个细节。上面例子中的回溯并没有往回吐呀,吐出来之后不应该往回走嘛,怎么往后走了?

我们再来看一个例子:

'"abc"def'.match(/".*"/);
// [""abc"", index: 0, input: ""abc"def", groups: undefined]

因为.*是贪婪匹配,所以它把后面的字符都吞进去了。直到发现目标完不成,不得已往回吐,吐到第二个"为止,终于匹配成功。这就好比结了婚还在外面养小三,几经折腾才发现家庭才是最重要的,自己的行为背离了初衷,于是幡然悔悟。

正则文本
/"/"
/".*/"a
/".*/"ab
/".*/"abc
/".*/"abc"
/".*/"abc"d
/".*/"abc"de
/".*/"abc"def
/".*"/"abc"def
/".*"/"abc"de
/".*"/"abc"d
/".*"/"abc"

我想说的是,不要被回溯的回字迷惑了。它的本质是把已经吞进去的字符吐出来。至于吐出来之后是往回走还是往后走,是要根据情况而定的。


回溯引发的浏览器卡死惨案

现在我邀请读者回到文章开始提起的正则BUG。

`
<img src=# onerror=’alert(document.cookie)/><!--‘
<img src=https://avatar.veedrin.com />
`.match(/<!--([^-]+|[-][^-]+)*-->/g);

这是测试妹子用于测试XSS攻击的一段代码,测试的脑洞你不要去猜。正则是Remarkable用于匹配注释的,虽然我没搞清楚到底为什么这样写。src我篡改了一下,不影响效果。

不怕事大的可以去Chrome开发者工具跑上一跑。

不卖关子。它会导致浏览器卡死,是因为分支和范围太多了。[^-]+是一个范围,[-][^-]+是一个范围,[^-]+|[-][^-]+是一个分支,([^-]+|[-][^-]+)*又是一个范围。另外注意,嵌套的分支和范围生成的备选状态是呈指数级增长的。

我们知道这段语句肯定会匹配失败,因为文本中压根就没有-->。那浏览器为什么会卡死呢?因为正则引擎的回溯实在过多,导致浏览器的CPU进程飙到98%以上。这和你在Chrome开发者工具跑一段巨大运算量的for循环是一个道理。

但是呢,正则永远不会走入死循环。正则引擎叫有限状态机,就是因为它的备选状态是有限的。既然是有限的,那就一定可以遍历完。10的2次方叫有限,10的200000000次方也叫有限。只不过计算机的硬件水平有限,容不得你进行这么大的运算量。我以前也以为是正则进入了死循环,其实这种说法是不对的,应该叫浏览器卡死或者撑爆CPU。

那么,怎么解决?

最粗暴也最贵的方式当然是换一台计算机咯。拉一台超级计算机过来肯定是可以打服它的吧。

第二就是减少分支和范围,尤其是嵌套的分支和范围。因为分支和范围越多,备选状态就越多,早早的就匹配成功还好,如果匹配能成功的备选状态在很后头或者压根就无法匹配成功,那你家的CPU就得嗷嗷叫咯。

我们来看一下:

`
<img src=# onerror=’alert(document.cookie)/><!--‘
<img src=https://avatar.veedrin.com />-->
`.match(/<!--([^-]+|[-][^-]+)*-->/g);
// ["<!--‘↵<img src=https://avatar.veedrin.com />-->"]

你看,备选状态再多,我已经找到了我的白马王子,你们都歇着去吧。

这个正则我不知道它这样写的用意何在,所以也不知道怎么优化。明白备选状态是回溯的罪魁祸首就好了。

第三就是缩减文本。会发生回溯的情况,其实文本也是一个变量。你想想,总要往回跑,如果路途能短一点是不是也不那么累呢?

'<!--<img src=https://jd.com>'.match(/<!--([^-]+|[-][^-]+)*-->/g);
// null

试的时候悠着点,不同的浏览器可能承受能力不一样,你可以一个个字符往上加,看看极限在哪里。

当然,缩减文本是最不可行的。正则正则,就是不知道文本是什么才用正则呀。


优化正则表达式

现在我们知道了控制回溯是控制正则表达式性能的关键。

控制回溯又可以拆分成两部分:第一是控制备选状态的数量,第二是控制备选状态的顺序。

备选状态的数量当然是核心,然而如果备选状态虽然多,却早早的匹配成功了,早匹配早下班,也就没那么多糟心事了。

至于面对具体的正则表达式应该如何优化,那就是经验的问题了。思考和实践的越多,就越游刃有余。无他,唯手熟尔。


工具

[regex101 ]是一个很多人推荐过的工具,可以拆分解释正则的含义,还可以查看匹配过程,帮助理解正则引擎。如果只能要一个正则工具,那就是它了。

[regexper ]是一个能让正则的备选状态可视化的工具,也有助于理解复杂的正则语法

本文是『horseshoe·Regex专题』系列文章之一,后续会有更多专题推出
GitHub地址:https://github.com/veedrin/horseshoe
博客地址(文章排版真的很漂亮):https://veedrin.com
站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

2.广告联盟: 整理了目前主流的广告联盟平台,如果你有流量,可以作为参考选择适合你的平台点击进入

链接: http://www.fly63.com/article/detial/1563

关闭

JS常用正则表达&RegExp对象

本来想细致整理一下正则表达式和RegExp对象的,但是发现网上完善的教程一抓一大把,于是这篇文章只会记录一些常常用到的正则表达式以及稍做分析。

js正则

正则表达式是构成搜索模式(search pattern)的字符序列。当您搜索文本中的数据时,您可使用搜索模式来描述您搜索的内容。正则表达式可以是单字符,或者更复杂的模式

从vue模板解析学习正则表达式

最近在看vue的模板解析成render这一块,顺便补一下正则的知识。attribute这段正则很长,他的主要作用是匹配标签里的指令,可以分几个分组来解读

超好用的6种正则表达式,前端开发人员必知

正则表达式已经成为程序员的必备工具。几乎所有流行的编程语言都支持正则表达式,原因如下:正则表达式为开发人员提供了强有力的工具,使之能快速执行需要几十行代码才能完成的任务。本文主要研究前端开发人员经常要面对的六大文本处理和操作任务

正则匹配身份证有bug你知道么?

在开发中,我们需要验证用户的输入信息,多半采用正则验证,下面就是身份证证号的几种常用的正则表达式:但是这些并不能管用,是不是很气人?这是为什么呢?

js使用正则过滤emoji表情符号

手机端常常会遇到用户输入框,输入emoji,如果是数据库是UTF8,会遇到报错,原因是:UTF-8编码有可能是两个、三个、四个字节。Emoji表情是4个字节,而Mysql的utf8编码最多3个字节,所以数据插不进去。

理解Javascript的正则表达式

相信很多人第一次见到正则表达式的第一印象都是懵逼的,对新手而言一个正则表达式就是一串毫无意义的字符串,让人摸不着头脑。但正则表达式是个非常有用的特性,不管是Javascript、PHP、Java还是Python都有正则表达式。俨然正则表达式已经发展成了一门小语言

密码强度的正则表达式(JavaScript)总结

本文给出了两个密码强度的正则表达式方案,一个简单,一个更复杂和安全。并分别给出了两个方案的解析和测试程序。一般大家可以根据自己的项目的实际需要,自行定义自己的密码正则约定。

Js正则表达式位数和零宽断言

在有需要正则表达式,很常见的操作就百度一下。看能不能找到满足我需求的。有时候你会找到的,比如手机校验,密码校验,邮箱校验。但是很多人往往都看不懂网上的正则的意思

常用JavaScript正则表达式整理

在表单验证中,正则表达式书写起来特别繁琐,本文整理了15个常用的JavaScript正则表达式,其中包括用户名、密码强度、整数、数字、电子邮件地址(Email)、手机号码、身份证号、URL地址、 IPv4地址

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!