正则引擎与回溯

正则引擎

说到正则表达式,我们先从正则表达式引擎说起。正则表达式引擎分为两大类:DFA(确定型有穷自动机),另一种是NFA(不确定型有穷自动机),简单的说NFA是指正则表达式主导的匹配,而DFA对应的是文本主导的匹配

DFA在线性状态下运行,从匹配文本入手,从左到右,每个字符不会匹配两次,所以通常情况下,它的速度更快,但支持的特性很少,不支持捕获组、各种引用等等
NFA从正则表达式入手,不断读入字符,尝试是否匹配当前正则,不匹配则吐出字符重新尝试,通常它的速度比较慢,最优时间复杂度为多项式的,最差情况为指数级的。但NFA支持更多的特性,比如PHP,Java,python等

文本 = 'interesting' 
正则表达式 = ‘es(sing | tng | ting)’

对DFA举例如下:
DFA采用的是文本匹配正则表达式的方式,从左到右,首先匹配到第一个ter中的e, ter中的e和匹配要求中的e相同,在匹配下一个r,由于rs不同,匹配失败,于是继续,直到ee匹配,ss匹配,然后发现正则里面有三个可以选择的匹配,于是进行并行匹配(t,t,s)tt匹配,sing被淘汰出局,后进行并行匹配tingtng中的i,n,于是tng被淘汰出局。后对ting完成后续的匹配,整个匹配完成。

对NFA的匹配如下:
NFA采用的是正则表达式匹配文本的方式,正则表达式中的e去匹配文本中的i,匹配错误,继续向下匹配,直到ee匹配,ss匹配。正则表达式后面有三个可选条件,依次匹配,第一个失败,接着二、三,直到匹配。

正则回溯

假设正则为/ab{1,3}c/

  • 当目标字符串是”abbbc”时,就没有所谓的“回溯”
    匹配过程如下:

Alt text

  • 如果目标字符串是“abbc”,中间就有回溯
    匹配过程如下:

Alt text
这里我们看到在第五步时出现了回溯,这里是正则的贪婪特性,这是因为正则中b{1,3},也就是说b可以出现1-3个。这里当b出现两次匹配后,正则还要去进行一次b的对比,这时发现下一个字母是c,及不匹配,也就是说b{1,3}会竭尽所能的匹配最多的字符。然后状态又回到之前的状态(即第6步,与第4步一样),最后再用子表达式c,去匹配字符“c”。当然,此时整个表达式匹配成功了。

  • 再看一个比较清晰的回溯
    正则为:/".*"/

目标字符串为:"acd"ef
匹配过程为:
Alt text

参考链接:
https://www.jianshu.com/p/d1030a7a078b
https://www.cnblogs.com/leeego-123/p/11119416.html
https://forum.90sec.com/t/topic/677

最后修改:2020 年 02 月 03 日 01 : 40 PM
如果觉得我的文章对你有用,请随意赞赏