正则引擎NFA与回溯

正则引擎是基于回溯的NFA实现的时候，那么就有可能出现灾难性回溯(Catastrophic Backtracking)，即正则在匹配的时候回溯过多，造成CPU 100%，正常服务被阻塞。

看到这句话的时候，我是懵圈的，平时写正则表达式的时候都是能用就行了😰，没注意过这种事啊，又多叒遇到知识盲区了…

正则引擎

正则引擎主要分为两类:
1)DFA: 确定有限状态自动机，对应的是文本主导的匹配，其扫描的字符串中的每个字符都对引擎进行了控制。

2)NFA: 非确定有限状态自动机，对应的是正则表达式主导的匹配，其会依次处理各个子表达式或组成元素，遇到需要在两个可能成功的可能中进行选择的时候，它会选择其一，同时记住另一个，以备稍后可能的需要。

NFA

用to(nite|knight|night)匹配文本'...tonight...'的一种办法。

正则表达式从t开始，每次检查一部分(由引擎查看表达式的一部分)，同时检查”当前文本”是否匹配表达式的当前部分。如果是，则继续表达式的下一部分，如此继续，直到表达式的所有部分都能匹配，即整个表达式都能够匹配成功。

第一个元素是t，将重复尝试，直到在目标字符串中找到’t’为止。之后，检查紧随其后的字符是否能由o匹配，如果能，就检查'(nite|knight|night)'。引擎会依次尝试三种可能性: ‘nite’、’knight’、’night’。

尝试’nite’的过程与之前一样，会尝试匹配’n’，’i’，’t’，’e’。如果尝试失败，就继续下去，直到匹配成功或者报告失败。

DFA

DFA引擎在扫描字符串时，会记录”当前有效”的所有匹配可能。以tonight为例，引擎移动到t，它会在当前处理的匹配可能中添加一个潜在的可能，用空格作为标记:

字符串中的位置:

1	after...t onight...

正则表达式中可能的匹配位置:

1	t o(nite\|knight\|night)

接下来扫描的每个字符，都会更新当前的可能匹配序列。继续扫描两个字符以后的情况:

字符串中的位置:

1	after...toni ght...

正则表达式中可能的匹配位置:

1	to(ni te\|knight\|ni ght)

有效的可能匹配变为两个: ‘nite’、’knight’，当接下来扫描到’g’时，就只剩下一个可能的匹配，等待’h’和’t’匹配完成后，引擎发现匹配已经完成，报告成功。

回溯

在使用贪婪匹配或者惰性匹配或者或匹配进入到匹配路径选择的时候，遇到失败的匹配路径，尝试走另外一个匹配路径的这种行为，称作回溯。

用to(nite|knight|night)匹配字符串hot tonic tonight!。

第一个元素t从字符串的最左端开始尝试，无法匹配’h’，匹配失败。引擎向后移动，匹配’o’失败。

当匹配到第三个元素’t’，此时是可以匹配的，但接下来的o因对应位置是一个空格，无法匹配，所以本轮尝试失败。

继续匹配从... tonic ...开始的尝试，当to匹配成功之后，剩下的3个分支都会成为可能，引擎会选择其中一个作为尝试，其他的作为备用。在逐字符匹配’nite’的时候，会失败。引擎会继续尝试匹配备用字符，当引擎从... tonight!处开始匹配，多选分支night可以匹配字符串的结尾部分，引擎可以报告匹配成功。