正则匹配
引擎
正则引擎是一种对正则表达式进行匹配的程序，根据不同的标准和方式实现。
分类
引擎主要分为：DFA、传统型 NFA和POSIX NFA，有时候还有DFA/NFA混合型。
判断
- 支持忽略优先量词的只能是传统型 NFA
- DFA 不支持捕获型括号和回溯
1
echo =XX========================================== | egrep 'X(.+)+X'
如果执行需要花很长时间，就是 NFA；如果时间很短，就是 DFA，或支持某些高级优化的 NFA；如果出现堆栈溢出或者超时，则是 NFA。
构造
- 文字文本：例如 a、*、!、枝…
- 字符组、点号、Unicode 属性以及其他
- 捕获型括号
- 锚点
- 非捕获型括号、反向引用和忽略优先量词
NFA 引擎（非确定性有穷自动机）
NFA 引擎是表达式主导，表达式中的控制权在不同的元素之间转换。在表达式主导的匹配过程中，每一个子表达式都是独立的。子表达式与正则表达式的控制结构的层级关系控制了整个匹配过程。
DFA 引擎（确定性有穷自动机）
DFA 引擎是表达式主导，扫描的字符串中的每个字符都对引擎进行了控制。DFA 引擎在扫描字符串时，会记录“当前有效”的所有匹配可能。某个为完成的匹配也许是任意多个匹配的开始，不合适的匹配可能在扫描后继文字时会被去除。
基础
优先选择最左端的匹配结果
匹配先从需要查找的字符串的起始位置尝试匹配。
标准量词是匹配优先
标准匹配量词（?、*、+以及{min,max}）都是“匹配优先”的。标准匹配量词的结果“可能”并非所有可能中最长的，但它们总是尝试匹配尽可能多的字符，直到匹配上限为止。而且总是匹配多余匹配成功下限的字符。例如使用[0-9]+来匹配“March 1998”，在匹配到 1 之后，还会继续匹配下去，直到字符串末尾。
1
"about 24 times".match(/^.*([0-9][0-9])/);
在某些表达式中，表达式的某些部分可能“强迫”之前的匹配优先的部分释放（或称“交还”）某些字符。例如正则**/^.([0-9][0-9])/去匹配“about 24 times”字符串时，/./会先匹配到字符串末尾，然后先释放 s 去匹配/[0-9]/**，如果匹配不上在依次释放，直到匹配“24”为止，匹配结果为“about 24”，第一个引用值为 24。
1
"copyright 2021.".match(/^.*([0-9]+)/);
如果用**/^.([0-9]+)/去匹配“copyright 2021.”，则得到匹配字符串为“copyright 2021”，第一个引用值为 1，并不是期望的 2021。/./只释放了“3.”，“3”能够被/[0-9]/匹配，由于“+”量词修饰，所以现在还只做到了最小的匹配可能，但是遇到了“.”，找不到其他可以匹配的字符了。此时没有“必须”匹配的元素，所以/.*/不会被迫交出 0。这也是先来先服务**的原则。
多选结构
多选结构既不是匹配优先的，也不是忽略优先的，而是按顺序排列的。
回溯
NFA 引擎会依次处理各个子表达式或组成元素，遇到需要在两个可能成功的可能中进行选择的时候，会选择其一，同时记住另一个，以备稍后可能的需要。需要做出选择的情形包括量词和多选结构。不论选择那一种途径，如果能匹配成功，而且正则表示式的余下部分也成功了，匹配即告完成。如果正则表达式中余下的部分最终匹配失败，引起需要回溯到之前做出选择的地方，选择其他备用分支继续尝试。
要点
- 如果需要在“进行尝试”和“跳过尝试”之间选择，对于匹配优先量词，引擎会优先选择“进行尝试”，而对于忽略优先量词，会选择“跳过尝试”。、
- 距离当前最近储存的选项就是当本地失败强制回溯时返回的。使用的原则是 LIFO（last in fast out，后进先出）
备用状态
备用状态是用来标记，在需要的时候，匹配可以从这里重新开始尝试。它们保存了两个位置：正则表达式中的位置和未尝试的分支在字符串中的位置。
未进行回溯的匹配
1
/ab?c/.test("abc");
由于?是匹配优先量词，所以引擎会选择尝试匹配，并且能够匹配成功以及后续也能匹配成功，所以引擎不会进行回溯
进行了回溯的匹配
1
/ab?c/.test("ac");
由于 b 在匹配 c 的时候失败了，引擎需要进行一次回溯，忽略 b 后再进行匹配
不成功的匹配
1
/ab?c/.test("abX");
经过 c 和 X 匹配失败后，进行回溯到忽略 b，然后 c 和 b 进行匹配，再次失败，到此整个匹配失败
忽略优先的匹配
1
/ab??c/.test("abc");
由于优先选择忽略，第一次 c 和 b 匹配失败，引擎进行回溯，直至匹配成功
星号、加号的回溯
1
2
"a 1234 num".match(/[0-9]+/);
"a 1234 num".match(/[0-9]*/);
使用加号的时候会有 4 个状态可以进行回溯，而使用星号的时候在开始的位置就匹配成功，匹配结果为’’
注意事项
- 回溯机制不但需要重新计算正则表达式和文本的对应位置，也需要维护括号内的子表达式所匹配文本的状态
- 由星号（或其他任何匹配优先量词）限定的部分不受后面元素影响，而只是匹配尽可能多的内容