精通JavaScript正则之正则原理

1、为什么要知道些正则匹配原理

知其然，知其所以然。

2、正则匹配引擎

正则引擎大体上可分为不同的两类：DFA和NFA。DFA(Deterministic finite automaton) 确定型有穷自动机，NFA (Non-deterministic finite automaton)　非确定型有穷自动机。

2.1 NFA

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

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

2.2 DFA

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

例：

字符串：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分支符合，则匹配成功！

3、基础知识

3.1 字符串组成

对于字符串“reg”而言，包括三个字符和四个位置，位置0在r前面，位置4在g后面。

3.2 占有字符和零宽度

正则表达式匹配过程中，如果子表达式匹配到的是字符内容，而非位置，并被保存到最终的匹配结果中，那么就认为这个子表达式是占有字符的；如果子表达式匹配的仅仅是位置，或者匹配的内容并不保存到最终的匹配结果中，那么就认为这个子表达式是零宽度的。

占有字符是互斥的，零宽度是非互斥的。也就是一个字符，同一时间只能由一个子表达式匹配，而一个位置，却可以同时由多个零宽度的子表达式匹配。

3.3 控制权和传动

正则的匹配过程，通常情况下都是由一个子表达式（可能为一个普通字符、元字符或元字符序列组成）取得控制权，从字符串的某一位置开始尝试匹配，一个子表达式开始尝试匹配的位置，是从前一子表达匹配成功的结束位置开始的。如正则表达式：

(子表达式一)(子表达式二)

假设**(子表达式一)为零宽度表达式，由于它匹配开始和结束的位置是同一个，如位置0，那么(子表达式二)**是从位置0开始尝试匹配的。

假设**(子表达式一)为占有字符的表达式，由于它匹配开始和结束的位置不是同一个，如匹配成功开始于位置0，结束于位置2，那么(子表达式二)**是从位置2开始尝试匹配的。

而对于整个表达式来说，通常是由字符串位置0开始尝试匹配的。如果在位置0开始的尝试，匹配到字符串某一位置时整个表达式匹配失败，那么引擎会使正则向前传动，整个表达式从位置1开始重新尝试匹配，依此类推，直到报告匹配成功或尝试到最后一个位置后报告匹配失败。

4、正则表达式简单匹配过程

4.1 基础匹配过程

原字符串：reg

正则表达式：/reg/

匹配过程：由字符r取得控制权，从位置0开始匹配，由r来匹配r，匹配成功，控制权交给字符e，因为之前字符r从位置0已经匹配成功，所以字符e从位置1开始匹配，e匹配e，匹配成功，接着到字符g匹配g，也匹配成功。

正则表达式匹配完成，匹配结果为reg，开始位置0，结束位置3。

4.2 含有量词的匹配过程（1）

原字符串：reg

正则表达式：/re?g/

量词?属于优先匹配量词，在可匹配可不匹配时，会优先选择尝试匹配，当这种选择使得整个表达式无法匹配成功时，才会让出匹配的内容。

匹配过程：由字符r取得控制权，从位置0开始匹配，r匹配r，匹配成功，控制权交给e?，e?尝试优先匹配e，匹配成功，控制权交给g，且保留一个备选状态，最后由g匹配g，匹配成功，丢弃备选状态，匹配结束。

4.3 含有量词的匹配过程（2）

原字符串：rg

正则表达式：/re?g/

匹配过程：由字符r取得控制权，从位置0开始匹配，r匹配r，匹配成功，控制权交给e?，e?匹配g，匹配失败，保留一个备选状态，由于匹配失败，进行回溯，找到备选状态，此时控制权到g，字符g匹配g，匹配成功。

4.4 含有量词的匹配过程（3）

原字符串：reg

正则表达式：/re?x/

匹配过程：由字符r取得控制权，从位置0开始匹配，r匹配r，匹配成功，控制权交给e?，e?尝试优先匹配e，匹配成功，控制权交给x，且保留一个备选状态，x匹配g，匹配失败，此时进行回溯，找到记录的备选状态，此时控制权交给x，x匹配e，匹配失败，第一轮匹配失败。

正则引擎使正则向前传动，由位置1开始尝试匹配，由r匹配e，匹配失败，没有备选状态，第二轮匹配尝试失败。正则引擎继续向前传动，知道位置3匹配失败，匹配结束，此时整个正则表达式匹配失败。

4.5 零宽度匹配过程

源字符串：a12

正则表达式：^(?=[a-z])[a-z0-9]+$

元字符^和$匹配的只是位置，顺序环视(?=[a-z])只进行匹配，并不占有字符，也不将匹配的内容保存到最终的匹配结果，所以都是零宽度的。

匹配过程：从元字符^开始，匹配位置0，匹配成功，控制权交给顺序环视(?=[a-z])；

(?=[a-z])要求它所在位置右侧必须是字母才能匹配成功，零宽度的子表达式之间是不互斥的，即同一个位置可以同时由多个零宽度子表达式匹配，所以它也是从位置0尝试进行匹配，位置0的右侧是字符“a”，符合要求，匹配成功，控制权交给[a-z0-9]+；

因为(?=[a-z])只进行匹配，并不将匹配到的内容保存到最后结果，并且(?=[a-z])匹配成功的位置是位置0，所以[a-z0-9]+也是从位置0开始尝试匹配的，[a-z0-9]+首先尝试匹配a，匹配成功，继续尝试匹配，可以成功匹配接下来的1和2，此时已经匹配到位置3，位置3的右侧已没有字符，这时会把控制权交给$；

$匹配结束位置，也就是位置3，匹配成功。

参考资料：

1、正则表达式—wiki

2、正则表达式匹配解析过程探讨分析

3、正则基础之——NFA引擎匹配原理

4、正则表达式的原理