NFA灵魂—回溯

NFA灵魂—回溯

回溯的原理：记录所有可能的表达式分支，尝试匹配，若失败则返回，选择上次正确标记处按新的表达式（备用状态）开始新的尝试匹配。

可以回溯到特性：优先匹配、忽略优先的匹配、多选结构、环视、条件判断、反向引用、固化分组

回溯的两条原则： 1、进行尝试：匹配优先量词(?、*、+、{m, n}) 2、跳过尝试：忽略优先量词(??、*?)

强制回溯时候，执行“后进先出”原则，即从右向左进行回溯

一、当匹配优先量词为’？’时回溯

匹配优先	回溯	未回溯
成功匹配	「ab?c」匹配「ac」	「ab?c」匹配「abc」
不成功匹配	「ab?c」匹配「abx」	「ab?c」匹配「ax」

1、?表示优先匹配量词，0次或1次，尝试匹配
2、回溯-成功匹配：
初始状态：「a」与「 a」匹配成功
备用状态：「ab?,c」+「a,c」–「b?」与「 c」匹配不成功，