正则表达式生成算法(在线生成正则表达式工具)

本文目录：

• 1、正则表达式
• 2、正则表达式之原理篇
• 3、如何将正则表达式转换为NFA

正则表达式

首先我们要了解正则表达式是什么，它是一种匹配模式， 不仅能匹配匹配字符，还能匹配位置 ，不少人忽略了匹配字符这个作用，往往碰到这种问题就手足无措。

如果正则只有精确匹配是没有多大意义的，比如：

正则表达式的强大之处在于它的模糊匹配，分为横向模糊和纵向模糊

横向模糊：一个正则可匹配的字符串的长度不是固定的，可以是多种情况的

其实现的方式是使用量词：

比如：

横向模糊匹配到了多种情况，案例中用的正则是/ab{2,5}c/g，后面多了g，它是正则的一个修饰符。表示全局匹配，即在目标字符串中按顺序找到满足匹配模式的所有子串，强调的是“所有”，而不只是“第一个”。

纵向模糊：一个正则匹配的字符串，具体到某一位字符时，它可以不是某个确定的字符，可以有多种可能

其实现的方式是使用范围类

-表示连字符，在此处作特殊用处，但是如果我要匹配'a-z'这三个字符呢？可以这么写：

这样引擎就不会认为它们是一个氛围了， 符号在范围类中起取反的作用， a表示除了a的所有字符。

系统根据范围类又预定义了一些类方便我们使用：

不加g就是惰性匹配，我匹配完一个就不敢了，懒得再干其他事儿了，加了g就是贪婪模式了,我现在精力无限，会尽可能的干事儿，但是我还有些理智，不会干超出能力之外的事儿，比如你给我的范围是{2,5}，我会尽可能做5件事儿，但是不会超过5件事,反正只要在能力范围内，越多越好

此时我既想尽可能的匹配又想让它不那么贪婪有没有办法呢？办法是有的, 贪婪模式一般作用在量词这里，限制在量词这里就好了 ，可以在量词这里加一个？即可搞定。

其中/\d{2,5}?/表示，虽然2到5次都行，当2个就够的时候，就不在往下尝试了。

此时就达到了我们的要求,不过这里完全是为了讲解贪婪模式和惰性模式，并不推荐这么做，我完全可以将{2,5}改成{2}，一样的效果

知道了惰性模式的原理，我们完全可以鼓捣出其他的各式各样的情形：

一个模式可以实现横向和纵向模糊匹配。而多选分支可以支持多个子模式任选其一

具体形式如下：(p1|p2|p3)，其中p1、p2和p3是子模式，用“|”（管道符）分隔，表示其中任何之一

但有个事实我们应该注意，比如我用/good|goodbye/，去匹配"goodbye"字符串时，结果是"good"

而把正则改成/goodbye|good/，结果是

也就是说，分支结构也是惰性的，即当前面的分支匹配上了，后面的就不再尝试了

并且，使用分支的时候注意使用括号，

匹配字符，无非就是范围类、量词和分支结构的组合使用罢了

分析：

表示一个16进制字符，可以用范围类[0-9a-fA-F]

其中字符可以出现3或6次，需要是用量词和分支结构

使用分支结构时，需要注意顺序(惰性)

分析：

对每个地方的数字进行分析：

共4位数字，第一位数字可以为[0-2]。

当第1位为2时，第2位可以为[0-3]，其他情况时，第2位为[0-9]。

第3位数字为[0-5]，第4位为[0-9]

如果也要求匹配7:9，也就是说时分前面的0可以省略:

分析：

年，四位数字即可，可用[0-9]{4}。

月，共12个月，分两种情况01、02、……、09和10、11、12，可用(0[1-9]|1[0-2])。

日，最大31天，可用(0[1-9]|[12][0-9]|3[01])

分析：

整体模式是: 盘符:\文件夹\文件夹\文件夹

其中匹配F:\，需要使用[a-zA-Z]:\，其中盘符不区分大小写，注意\字符需要转义。

文件名或者文件夹名，不能包含一些特殊字符，此时我们需要排除范围类[ \:*|"?\r\n/]来表示合法字符。另外不能为空名，至少有一个字符，也就是要使用量词+。因此匹配“文件夹\”，可用[ \:*|"?\r\n/]+\。

另外“文件夹\”，可以出现任意次。也就是([^\: |"?\r\n/]+\) 。其中括号提供子表达式。

路径的最后一部分可以是“文件夹”，没有\，因此需要添加([^\:*|"?\r\n/]+)?。

最后拼接成了一个看起来比较复杂的正则：

用到了惰性匹配，防止把class也提取出来

优化：

^（脱字符）匹配开头，在多行匹配中匹配行开头。

$（美元符号）匹配结尾，在多行匹配中匹配行结尾

比如我们把字符串的开头和结尾用"#"替换（位置可以替换成字符的！）：

多行匹配模式时，二者是行的概念，这个需要我们的注意

\b是单词边界，具体就是\w和\W之间的位置，也包括\w和^之间的位置，也包括\w和$之间的位置

首先，我们知道，\w是范围类[0-9a-zA-Z_]的简写形式，即\w是字母数字或者下划线的中任何一个字符。而\W是排除范围类[^0-9a-zA-Z_]的简写形式，即\W是\w以外的任何一个字符

此时我们可以看看"[#JS#] #Lesson_01#.#mp4#"中的每一个"#"，是怎么来的。

第一个"#"，两边是"["与"J"，是\W和\w之间的位置。

第二个"#"，两边是"S"与"]"，也就是\w和\W之间的位置。

第三个"#"，两边是空格与"L"，也就是\W和\w之间的位置。

第四个"#"，两边是"1"与"."，也就是\w和\W之间的位置。

第五个"#"，两边是"."与"m"，也就是\W和\w之间的位置。

第六个"#"，其对应的位置是结尾，但其前面的字符"4"是\w，即\w和$之间的位置。

知道了\b的概念后，那么\B也就相对好理解了。

\B就是\b的反面的意思，非单词边界。例如在字符串中所有位置中，扣掉\b，剩下的都是\B的。

具体说来就是\w与\w、\W与\W、^与\W，\W与$之间的位置

exp1(?=exp2) 表达式会匹配exp1表达式，但只有其后面内容是exp2的时候才会匹配

exp1(?=exp2) 表达式会匹配exp1表达式，但只有其后面内容不是exp2的时候才会匹配

(?=p)，其中p是一个子模式，即p前面的位置

比如(?=l)，表示'l'字符前面的位置，例如：

而(?!p)就是(?=p)的反面意思

对于位置的理解，我们可以理解成空字符""

因此，把/ hello$/写成/ ^hello$$$/，是没有任何问题的：

也就是说字符之间的位置，可以写成多个。

把位置理解空字符，是对位置非常有效的理解方式

此正则要求只有一个字符，但该字符后面是开头。

比如把"12345678"，变成"12,345,678"。

可见是需要把相应的位置替换成","

使用(?=\d{3}$)就可以做到：

因为逗号出现的位置，要求后面3个数字一组，也就是\d{3}至少出现一次。

此时可以使用量词+：

此时会出现问题：

上面的正则，仅仅表示把从结尾向前数，一但是3的倍数，就把其前面的位置替换成逗号

怎么解决呢？我们要求匹配的到这个位置不能是开头。

我们知道匹配开头可以使用^，但要求这个位置不是开头怎么办？

easy，(?!^)

如果要把"12345678 123456789"替换成"12,345,678 123,456,789"。

此时我们需要修改正则，把里面的开头^和结尾$，替换成\b

其中(?!\b)怎么理解呢？

要求当前是一个位置，但不是\b前面的位置，其实(?!\b)说的就是\B。

因此最终正则变成了：/\B(?=(\d{3})+\b)/g

此题，如果写成多个正则来判断，比较容易。但要写成一个正则就比较困难。

那么，我们就来挑战一下。看看我们对位置的理解是否深刻

我们可以把原题变成下列几种情况之一：

1.同时包含数字和小写字母

2.同时包含数字和大写字母

3.同时包含小写字母和大写字母

4.同时包含数字、小写字母和大写字母

上面的正则看起来比较复杂，只要理解了第二步，其余就全部理解了。

/(?=.*[0-9])^[0-9A-Za-z]{6,12}$/

对于这个正则，我们只需要弄明白(?=.*[0-9])^即可。

分开来看就是(?=.*[0-9])和^。

表示开头前面还有个位置（当然也是开头，即同一个位置，想想之前的空字符类比）。

(?=. [0-9])表示该位置后面的字符匹配. [0-9]，即，有任何多个任意字符，后面再跟个数字。

另一种解法：

“至少包含两种字符”的意思就是说，不能全部都是数字，也不能全部都是小写字母，也不能全部都是大写字母。

那么要求“不能全部都是数字”，怎么做呢？(?!p)出马！

三种'都不能'呢？

1.分组和分支结构

括号是提供分组功能，使量词'+'作用于z和这个整体

而在多选分支结构(p1|p2)中，此处括号的作用也是不言而喻的，提供了子表达式的所有可能

而要使用它带来的好处，必须配合使用实现环境的API

以日期为例。假设格式是yyyy-mm-dd的

提取数据：

match返回的一个数组，第一个元素是整体匹配结果，然后是各个分组（括号里）匹配的内容，然后是匹配下标，最后是输入的文本

可以使用正则对象的exec方法：

也可以使用构造函数的全局属性$1至$9来获取：

替换:

想把yyyy-mm-dd格式，替换成mm/dd/yyyy怎么做？

反向引用:

比如要写一个正则支持匹配如下三种格式：

注意里面的\1，表示的引用之前的那个分组(-|/|.)。不管它匹配到什么（比如-），\1都匹配那个同样的具体某个字符

括号嵌套怎么办？

以左括号（开括号）为准

\10是表示第10个分组，还是\1和0呢？答案是前者，虽然一个正则里出现\10比较罕见

引用不存在的分组会怎样？

因为反向引用，是引用前面的分组，但我们在正则里引用了不存在的分组时，此时正则不会报错，只是匹配反向引用的字符本身。例如\2，就匹配"\2"。注意"\2"表示对2进行了转意

非捕获分组:

之前文中出现的分组，都会捕获它们匹配到的数据，以便后续引用，因此也称他们是捕获型分组。

如果只想要括号最原始的功能，但不会引用它，即，既不在API里引用，也不在正则里反向引用。此时可以使用非捕获分组(?:p)

第二种，匹配整个字符串，然后用引用来提取出相应的数据

思路是找到每个单词的首字母，当然这里不使用非捕获匹配也是可以的

首字母不会转化为大写的。其中分组(.)表示首字母，单词的界定，前面的字符可以是多个连字符、下划线以及空白符。正则后面的?的目的，是为了应对str尾部的字符可能不是单词字符，比如str是'-moz-transform '

通过key获取相应的分组引用，然后作为对象的键

匹配一个开标签，可以使用正则[^]+，

匹配一个闭标签，可以使用/[^]+，

但是要求匹配成对标签，那就需要使用反向引用

其中开标签[ ]+改成([ ]+)，使用括号的目的是为了后面使用反向引用，而提供分组。闭标签使用了反向引用，/\1。

另外[\d\D]的意思是，这个字符是数字或者不是数字，因此，也就是匹配任意字符的意思

而当目标字符串是"abbbc"时，就没有所谓的“回溯”。其匹配过程是：

其中子表达式b{1,3}表示“b”字符连续出现1到3次。

图中第5步有红颜色，表示匹配不成功。此时b{1,3}已经匹配到了2个字符“b”，准备尝试第三个时，结果发现接下来的字符是“c”。那么就认为b{1,3}就已经匹配完毕。然后状态又回到之前的状态（即第6步，与第4步一样），最后再用子表达式c，去匹配字符“c”。当然，此时整个表达式匹配成功了。

图中的第6步，就是“回溯”。

你可能对此没有感觉，这里我们再举一个例子。正则是：

目标字符串是"abbbc"，匹配过程是：

其中第7步和第10步是回溯。第7步与第4步一样，此时b{1,3}匹配了两个"b"，而第10步与第3步一样，此时b{1,3}只匹配了一个"b"，这也是b{1,3}的最终匹配结果。

这里再看一个清晰的回溯，正则是：

目标字符串是："acd"ef，匹配过程是：

图中省略了尝试匹配双引号失败的过程。可以看出“.*”是非常影响效率的。

为了减少一些不必要的回溯，可以把正则修改为/"[^"]*"/。

正则表达式匹配字符串的这种方式，有个学名，叫回溯法。

回溯法也称试探法，它的基本思想是： 从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法” 。

本质上就是深度优先搜索算法。其中 退到之前的某一步这一过程，我们称为“回溯” 。从上面的描述过程中，可以看出，路走不通时，就会发生“回溯”。即， 尝试匹配失败时，接下来的一步通常就是回溯

道理，我们是懂了。那么JS中正则表达式会产生回溯的地方都有哪些呢？

3.1 贪婪量词

之前的例子都是贪婪量词相关的。比如b{1,3}，因为其是贪婪的，尝试可能的顺序是从多往少的方向去尝试。首先会尝试"bbb"，然后再看整个正则是否能匹配。不能匹配时，吐出一个"b"，即在"bb"的基础上，再继续尝试。如果还不行，再吐出一个，再试。如果还不行呢？只能说明匹配失败了。

虽然局部匹配是贪婪的，但也要满足整体能正确匹配。否则，皮之不存，毛将焉附？

此时我们不禁会问，如果当多个贪婪量词挨着存在，并相互有冲突时，此时会是怎样？

答案是，先下手为强！因为深度优先搜索。测试如下：

其中，前面的\d{1,3}匹配的是"123"，后面的\d{1,3}匹配的是"45"。

3.2 惰性量词

惰性量词就是在贪婪量词后面加个问号。表示尽可能少的匹配，比如：

其中\d{1,3}?只匹配到一个字符"1"，而后面的\d{1,3}匹配了"234"。

虽然惰性量词不贪，但也会有回溯的现象。比如正则是：

目标字符串是"12345"，匹配过程是：

知道你不贪、很知足，但是为了整体匹配成，没办法，也只能给你多塞点了。因此最后\d{1,3}?匹配的字符是"12"，是两个数字，而不是一个。

3.3 分支结构

我们知道分支也是惰性的，比如/can|candy/，去匹配字符串"candy"，得到的结果是"can"，因为分支会一个一个尝试，如果前面的满足了，后面就不会再试验了。

分支结构，可能前面的子模式会形成了局部匹配，如果接下来表达式整体不匹配时，仍会继续尝试剩下的分支。这种尝试也可以看成一种回溯。

比如正则：

目标字符串是"candy"，匹配过程：

上面第5步，虽然没有回到之前的状态，但仍然回到了分支结构，尝试下一种可能。所以，可以认为它是一种回溯的

简单总结就是，正因为有多种可能，所以要一个一个试。直到，要么到某一步时，整体匹配成功了；要么最后都试完后，发现整体匹配不成功。

既然有回溯的过程，那么匹配效率肯定低一些。相对谁呢？相对那些DFA引擎。

而JS的正则引擎是NFA，NFA是“非确定型有限自动机”的简写。

大部分语言中的正则都是NFA，为啥它这么流行呢？

答：你别看我匹配慢，但是我编译快啊，而且我还有趣哦。

而在正则表达式中，操作符都体现在结构中，即由特殊字符和普通字符所代表的一个个特殊整体。

JS正则表达式中，都有哪些结构呢？

其中涉及到的操作符有：

上面操作符的优先级从上至下，由高到低。

这里，我们来分析一个正则：

因为是要匹配整个字符串，我们经常会在正则前后中加上锚字符^和$。

比如要匹配目标字符串"abc"或者"bcd"时，如果一不小心，就会写成/^abc|bcd$/。

而位置字符和字符序列优先级要比竖杠高，故其匹配的结构是：

应该修改成:

2.2 量词连缀问题

假设，要匹配这样的字符串：

此时正则不能想当然地写成/^[abc]{3}+$/，这样会报错，说“+”前面没什么可重复的：

此时要修改成：

2.3 元字符转义问题

所谓元字符，就是正则中有特殊含义的字符。

所有结构里，用到的元字符总结如下：

当匹配上面的字符本身时，可以一律转义：

在string中，也可以把每个字符转义，当然，转义后的结果仍是本身：

现在的问题是，是不是每个字符都需要转义呢？否，看情况。

2.3.1 范围类中的元字符

跟范围类相关的元字符有 []、^、- 。因此在会引起歧义的地方进行转义。例如开头的^必须转义，不然会把整个范围类，看成反义范围类。

2.3.2 匹配“[abc]”和“{3,5}”

我们知道[abc]，是个字符组。如果要匹配字符串"[abc]"时，该怎么办？

可以写成/[abc]/，也可以写成/[abc]/，测试如下:

只需要在第一个方括号转义即可，因为后面的方括号构不成字符组，正则不会引发歧义，自然不需要转义。

同理，要匹配字符串"{3,5}"，只需要把正则写成/{3,5}/即可。

另外，我们知道量词有简写形式{m,}，却没有{,n}的情况。虽然后者不构成量词的形式，但此时并不会报错。当然，匹配的字符串也是"{,n}"，测试如下：

var str = "{,3}";

var reg = /{,3}/g;

console.log( str.match(reg)[0] );

// = "{,3}"

2.3.3 其余情况

比如= ! : - ,等符号，只要不在特殊结构中，也不需要转义。

但是，括号需要前后都转义的，如/(123)/。

至于剩下的^ $ . * + ? | \ /等字符，只要不在字符组内，都需要转义的。

因为竖杠“|”,的优先级最低，所以正则分成了两部分\d{15}和\d{17}[\dxX]。

\d{15}表示15位连续数字。

\d{17}[\dxX]表示17位连续数字，最后一位可以是数字可以大小写字母"x"。

可视化如下：

3.2 IPV4地址

正则表达式是：

这个正则，看起来非常吓人。但是熟悉优先级后，会立马得出如下的结构：

((...)\.){3}(...)

上面的两个(...)是一样的结构。表示匹配的是3位数字。因此整个结构是

3位数.3位数.3位数.3位数

然后再来分析(...)：

(0{0,2}\d|0?\d{2}|1\d{2}|2[0-4]\d|25[0-5])

它是一个多选结构，分成5个部分：

0{0,2}\d ，匹配一位数，包括0补齐的。比如，9、09、009；

0?\d{2} ，匹配两位数，包括0补齐的，也包括一位数；

1\d{2} ，匹配100到199;

2[0-4]\d ，匹配200-249；

25[0-5] ，匹配250-255。

最后来看一下其可视化形式：

掌握正则表达式中的优先级后，再看任何正则应该都有信心分析下去了。

至于例子，不一而足，没有写太多。

这里稍微总结一下，竖杠的优先级最低，即最后运算。

只要知道这一点，就能读懂大部分正则。

另外关于元字符转义问题，当自己不确定与否时，尽管去转义，总之是不会错的。

本文就解决该问题，内容包括：

2.1 是否能使用正则

正则太强大了，以至于我们随便遇到一个操作字符串问题时，都会下意识地去想，用正则该怎么做。但我们始终要提醒自己，正则虽然强大，但不是万能的，很多看似很简单的事情，还是做不到的。

比如匹配这样的字符串：1010010001....

虽然很有规律，但是只靠正则就是无能为力。

2.2 是否有必要使用正则

要认识到正则的局限，不要去研究根本无法完成的任务。同时，也不能走入另一个极端：无所不用正则。能用字符串API解决的简单问题，就不该正则出马。

比如，从日期中提取出年月日，虽然可以使用正则：

其实，可以使用字符串的split方法来做，即可：

比如，判断是否有问号，虽然可以使用：

其实，可以使用字符串的indexOf方法：

比如获取子串，虽然可以使用正则：

其实，可以直接使用字符串的substring或substr方法来做：

var str = "JavaScript";

console.log( str.substring(4) );

// = Script

2.3 是否有必要构建一个复杂的正则

比如密码匹配问题，要求密码长度6-12位，由数字、小写字符和大写字母组成，但必须至少包括2种字符。

在匹配位置那篇文章里，我们写出了正则是：

其实可以使用多个小正则来做：

所谓准确性，就是能匹配预期的目标，并且不匹配非预期的目标。

这里提到了“预期”二字，那么我们就需要知道目标的组成规则。

不然没法界定什么样的目标字符串是符合预期的，什么样的又不是符合预期的。

下面将举例说明，当目标字符串构成比较复杂时，该如何构建正则，并考虑到哪些平衡。

3.1 匹配固定电话

比如要匹配如下格式的固定电话号码：

055188888888 0551-88888888 (0551)88888888

第一步，了解各部分的模式规则。

上面的电话，总体上分为区号和号码两部分（不考虑分机号和+86的情形）。

区号是0开头的3到4位数字，对应的正则是：0\d{2,3}

号码是非0开头的7到8位数字，对应的正则是：[1-9]\d{6,7}

因此，匹配055188888888的正则是：/^0\d{2,3}[1-9]\d{6,7}$/

匹配0551-88888888的正则是：/^0\d{2,3}-[1-9]\d{6,7}$/

匹配(0551)88888888的正则是：/^(0\d{2,3})[1-9]\d{6,7}$/

第二步，明确形式关系。

这三者情形是或的关系，可以构建分支：

提取公共部分：

进一步简写：

上面的正则构建过程略显罗嗦，但是这样做，能保证正则是准确的。

上述三种情形是或的关系，这一点很重要，不然很容易按字符是否出现的情形把正则写成：

/^(?0\d{2,3})?-?[1-9]\d{6,7}$/

虽然也能匹配上述目标字符串，但也会匹配(0551-88888888这样的字符串。当然，这不是我们想要的。

其实这个正则也不是完美的，因为现实中，并不是每个3位数和4位数都是一个真实的区号。

这就

正则表达式之原理篇

背景

       最近公司规范出来后，关于字符串不提倡用 “ + ”  进行拼接，于是自己写了个function，利用正则表达式来进行匹配。对于正则表达式，之前不了解原理，每次要用的时候查一下，很浪费时间。

内容

基础知识；

正则表达式引擎；

贪婪与非贪婪模式；

DFA与NFA引擎；

回溯机制及常见的回溯形式

基础知识

1. 占有字符：正则表达式匹配过程中，如果子表达式匹配到东西，而并非是一个位置，并最终保存到匹配的结果当中

2. 零宽度：只匹配一个位置，或者是匹配的内容并不保存到匹配结果中

一个字符，同一时间只能由一个子表达式匹配，而一个位置，却可以同时由多个零宽度的子表达式匹配

3.控制权：正则表达式由左到右依次进行匹配，通常情况下是由一个表达式取得控制权，从字符串的的某个位置进行匹配，一个子表达式开始尝试匹配的位置，是从前一子表达匹配成功的结束位置开始的（例如：（表达式一）（表达式二）意思就是表达式一匹配完成后才能匹配表达式二，而匹配表达式二的位置是从表达式一的位置匹配结束后的位置开始）。如果表达式一是零宽度，那表达式一匹配完成后，表达式二匹配的位置还是原来表达式以匹配的位置。也就是说它匹配开始和结束的位置是同一个

4. 元字符 

5. 反义元字符

6. 转义字符：\  使元字符失去它的意义，仅代表其输入中字符的意义

需要转义的字符列表 \ * + ? | { [ ( ) ^ $ . # 和 空白

7. 重复限定符：匹配优先量词，忽略优先量词，即：贪婪与非贪婪

{n,}、 {n, m}、 {, m}、 ’+’ 、‘?’、 '*'

8. 字符类：[ ]，区分大小写

9. 分支条件： |

10. 分组 ：（）指定子表达式，可限制多选项的范围、将若干字符组合为一个单元、受问号或星号之类的量词作用，例：(\d{1,3}){3}\d{3}

断言；(?

11. 括号及反向引用：（子表达式一）（子表达式二）\1      此时括号作用为分组，它具有记忆的功能，即在正则表达式内部仍然能回忆上次匹配到的是什么；\1、\2、\n 是用在正则表达式的匹配环节。在正则表达式的替换环节，则要使用像 $1、$2、$n 这样的语法

12. 平衡组 参考

正则表达式引擎

有两个主要特点：

1. 默认贪婪匹配；（ 贪婪匹配与非贪婪匹配 ）

2. 返回最先匹配到的结果

针对简单的正则匹配进行分析，例：

        当把cat应用到“He captured a catfish for his cat”，引擎先比较c和“H”，结果失败了。于是引擎再比较c和“e”，也失败了。直到第四个字符，c匹配了“c”。a匹配了第五个字符。到第六个字符t没能匹配“p”，也失败了。引擎再继续从第五个字符重新检查匹配性。直到第十五个字符开始，cat匹配上了“catfish”中的“cat”，正则表达式引擎急切的返回第一个匹配的结果，而不会再继续查找是否有其他更好的匹配

Rubular: 基于 Web 的 Ruby 正则表达式编辑器

贪婪与非贪婪（又称惰性、懒惰等）模式

两者影响的是被量词修饰的子表达式的行为。

贪婪模式在整个表达式匹配成功的前提下，尽可能多的匹配；而非贪婪模式（只被部分NFA引擎支持）在整个表达式匹配成功的前提下，尽可能少的匹配。

匹配优先量词（属于贪婪模式的量词）：

“{m,n}”、“{m,}”、“?”、“*”和“+”。

忽略优先量词（匹配优先量词后加上“?”：非贪婪模式的量词）：

“{m,n}?”、“{m,}?”、“??”、“*?”和“+?”

例：

源字符串：aa

正则表达式一：

正则表达式二：

DFA与NFA引擎（JS的正则引擎是NFA：非确定型有限自动机）

参考： 正则表达式引擎及其分类

DFA引擎：在线性时状态下执行，不要求回溯（因此永远不测试相同的字符两次）；确保匹配最长的可能的字符串；因为只包含有限的状态（？），所以它不能匹配具有反向引用的模式；并且因为它不构造显示扩展，所以它不可以捕获子表达式

传统的NFA引擎：运行匹配回溯算法——以指定顺序测试正则表达式的所有可能的扩展并接受第一个匹配项。因为传统的 NFA 构造正则表达式的特定扩展以获得成功的匹配，所以它可以捕获子表达式匹配和匹配的反向引用。但传统 NFA的 回溯使它可以访问完全相同的状态多次（如果通过不同的路径到达该状态）。因此，在最坏情况下，它的执行速度可能非常慢。因为传统的 NFA 接受它找到的第一个匹配，所以它还可能会导致其他（可能更长）匹配未被发现

POSIX NFA 引擎：与传统 NFA 引擎类似，不同点：在可以确保已找到了可能的最长的匹配之前，它们将继续回溯（更慢）；并且在使用 POSIX NFA 时，您恐怕不会愿意在更改回溯搜索的顺序的情况下来支持较短的匹配搜索，而非较长的匹配搜索

例：

字符串： this is yansen’s dog

正则表达式： /ya(msen|nsen|nsem)/

NFA工作方式：先在字符串中查找 y， 然后匹配其后是否为 a；  如果是 a 则继续查找其后是否为 m； 如果不是则匹配其后是否为 n (此时淘汰 msen 支分支)； 然后继续看其后是否依次为 s,e； 接着测试是否为 n ，是 n 则匹配成功，不是则测试是否为 m 。为什么是 m ？因为 NFA 工作方式是以正则表达式为标准，反复测试字符串，这样同样一个字符串有可能被反复测试了很多次！

DFA：从 this 中 t 开始依次查找 y ，定位到 y ，已知其后为 a ，则查看表达式是否有 a ，此处正好有 a； 然后字符串 a 后为 n ，DFA依次测试表达式，此时 msen 不符合要求淘汰。 nsen 和 nsem 符合要求，然后DFA依次检查字符串，检测到 sen 中的 n 时只有 nsen 分支符合，则匹配成功！

由此两种引擎是完全不同的工作方式：NFA以表达式为主导，更容易操纵；DFA以文本为主导（搜索更快）

回溯机制

引擎是如何来处理那些模糊的条件匹配？

从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法”

--来自百度百科

本质上就是深度优先搜索算法：尝试匹配失败时的下一步通常就是回溯

JS中正则表达式会产生回溯的地方都有哪些呢？

常见的回溯形式

1.贪婪量词

例：正则：/ab{1,3}c/

可视化形式

1. 没有回溯的匹配：当目标字符串是"abbbc"时

匹配过程

2. 有回溯的匹配：当目标字符串是“abbc”时

匹配过程

上图第5步有红颜色（仅表示匹配不成功）：此时b{1,3}已经匹配到了2个字符“b”，准备尝试第三个时，结果发现接下来的字符是“c”。那么就认为b{1,3}就已经匹配完毕。然后状态又回到之前的状态（即第6步，与第4步一样），最后再用子表达式c，去匹配字符“c”。当然，此时整个表达式匹配成功了；上图的第6步，就是“回溯”

即：尝试可能的顺序是“从多往少”的方向去尝试：首先会尝试"bbb"，然后再看整个正则是否能匹配。不能匹配时，吐出一个"b"，即在"bb"的基础上，再继续尝试。如果还不行，再吐出一个，再试。如果还不行呢？只能说明匹配失败了

另一个清晰的回溯：

正则：/".*"/

目标字符串："acd"ef

省略了尝试匹配双引号失败的匹配过程

其实“.*”最简单但也是非常影响效率的

2.惰性量词

虽然惰性量词不贪，但也会有回溯的现象（为了整体匹配成）

正则表达式

目标字符串："12345"

匹配过程

3.分支结构

分支也是惰性的，比如/Java|JavaScript/，去匹配字符串"JavaScript"，得到的结果是"Java"，因为分支会一个一个尝试，如果前面的满足了，后面就不会再试验了。

分支结构中可能前面的子模式会形成了局部匹配，如果接下来表达式整体不匹配时，仍会继续尝试剩下的分支。这种尝试也可以看成一种回溯：

正则表达式

匹配过程

虽然第五步没有回到之前的状态，但仍然回到了分支结构，尝试下一种可能

总结：有回溯的过程，那么匹配效率肯定比DFA相对低一些；别看匹配慢，但是编译快而且还挺有趣

参考： 正则表达式的回溯机制

如何将正则表达式转换为NFA

正则表达式转换NFA算法

基础的正则表达式：

对于正则表达式应用运算符部分构造方法：

1.符号栈，即运算的符号，其存储的为wchar_t类型，为连接，左括号，选择3种运算符。

2.NFA栈，即保存的NFA，这里因为整个计算过程都是更新一个Graph结构，所以这里的NFA栈保留的其实是当前NFA的开始和结束信息，即start和end。

3.具体的主要算法执行流程：

1.遍历输入的正则表达式，这里正则表达式的保存在CString变量中，可以通过下标访问；

2.首先初始化一张保存NFA的Graph结构，算法过程中的节点的数量不会超过正则表达式长度的2倍，所以这里直接开辟一个大小为正则表达式长度为2倍的Graph结构；

3.遇到非运算符，及正则表达式里面的转移符号的时候，这里就需要构造一个基本的NFA， 一个初始状态，一个终止状态，然后由初始状态至终止状态有一条为该转移符号的边，此时仍然需要检查正则表达式的下一个符号，如果不是运算符或者为左括号，此时应该运算栈中添加一个连接运算符，然后将构造的基本NFA添加入NFA栈中，方便以后将基本的NFA进行其他选择，重复，连接运算；

4.遇到非运算符时，需要分一下四种运算符的情况；

5.如果是运算符“）”，即右括号，此符号属于运算级最高的符号了，所以它要在符号栈中弹出所有符号运算，直到遇到“）”匹配，运算过程中根据符号栈中弹出的符号计算；

6.如果是运算符“（”，即左括号，此符号只是用来和右括号结合的，所以直接将该运算符压入符号栈中即可；

7.如果是运算符“*”，即重复符号，这个在正则表达式中运算级最高，直接进行计算，计算方法就是从NFA栈中弹出一张图，然后得到两个未分配的新节点，添加4条上面图表示的那样的边，然后重新设定NFA的start和end之后将新的NFA压入NFA栈中即可，运算后检查其后跟随的元素，如果是转移符号或者左括号，则必须要向符号栈中添加连接符号；

8.如果是运算符“+”，即选择符号，由于此符号的优先级没有连接符号高，所以此时应该弹出符号栈中优先级高于它的符号，但是“（”不参与弹出，所以这里只是弹出连接符号和自身“+”符号运算，然后将该符号压入符号栈等候计算；

9.正则表达式遍历完毕之后，需要弹出所有的符号栈进行计算，最后NFA栈中的唯一NFA就是所求的NFA；

接下来就是具体的运算的算法，这里点与点的连接通过更新Graph中相应的点的邻接链表即可；

10.连接运算，此时需要弹出NFA栈中的两个NFA，然后将其中一个的end连接至另一个的start，然后更新新的NFA的start和end，压入NFA栈中。

11.选择运算，此时需要弹出NFA栈中的两个NFA，然后Graph重新分配两个节点，作为新的NFA的start和end，然后新的start分别连接弹出的两个NFA的start，弹出的两个NFA的end分别连接新的end即构成新的NFA，压入NFA栈中。

12.闭包运算，此时需要弹出NFA栈中的一个NFA，然后Graph重新分配两个节点，作为新的NFA的start和end，然后新的start连接弹出NFA的start，弹出NFA的end连接新的end，然后添加一条新的start到新的end的一条空边和一条旧的end到旧的start的一条空边，将新的NFA压入NFA栈中。

最终的运行Graph的结果输出样式：

NFA的显示是根据上面算法生成的Graph的结构进行显示结果：

【正则表达式生成算法】的内容来源于互联网，如引用不当，请联系我们修改。