[正则]表达式的匹配原理2

表达式主导与文本主导

NFA引擎 ：表达式主导

当用he(te|nigh|llo)匹配文本 hello world 时 ，he会先从括号中提取te然后nigh然后llo ，当进行到时llo时整个表达式匹配成功。这种表达式的控制权在不同的元素之间转换，所以称它为“表达式主导”

DFA引擎：文本主导

比较NFA与DFA

一般情况下DFA比NFA要快。

NFA为创造性思维提供了丰富的施展空间。一个调教好的表达式能带来许多收益，调教的不好则会带来严重后果。

注：NFA类似手动挡汽车

回溯

NFA最重要的性质是，它会依次处理各个表达式或组成元素。当遇到需要在两个可能成功的条件中进行选择时，它会选择其一，同时记住另一个，留作候选。

这与当年玩仙剑很像，进入一个迷宫遇到岔口时，需要在每个岔口留下一些记号，如果走了思路就可以按原路返回，直到成功到达目的地为止。

在很多情况下正则引擎必须在两个或多个选项中做出选择。

回溯的两个要点

1.在“进行尝试”和“跳过尝试”之间选择时，对于匹配优先量词，引擎会优先选择“进行尝试”，而对于忽略优先量词，会选择“跳过尝试”

2.距离当前最近存储的选项就是当本地失败强制回溯返回的。就像堆盘子一样，最后叠上去的盘子肯定是最先拿下来的。

注：如果工具软件使用的是NFA主导的回溯引擎，理解正则表达式的回溯原理就成了高效完成任务的关键。

备用状态

在需要的时候，匹配可以从这里重新开始尝试。

回溯与匹配优先

如果用[0-9]+来匹配a 1234 num，[0-9]遇到4之后的空格无法匹配，而此时+号能够回溯的位置对应了四个保存的状态（,号表示进行的位置）

a 1,234 num

a 12,34 num

a 123,4 num

a 1234, num

在每个位置，[0-9]的尝试都代表一种可能。

如果用[0-9]*来匹配a 1234 num，这些状态就不会保存。因为有*号，*号限定的部分总能够匹配，所以[0-9]*根本没有触及到那些数字。

匹配优先的问题

1.使用正则匹配””中的内容

this “is” china i “linux” it

首先可能想到的是用”.*”来匹配

this “is” china i “linux” it

最终红色部分被匹配出来。因为.*属于匹配优先。

此时需要改为”[^”]*”

使用sed的做法是

sed ’s/[^”]*”([^”]*)”[^”]*/\1 /g’

2.匹配**中的内容

` 

表达式主导与文本主导

NFA引擎 ：表达式主导

当用he(te|nigh|llo)匹配文本 hello world 时 ，he会先从括号中提取te然后nigh然后llo ，当进行到时llo时整个表达式匹配成功。这种表达式的控制权在不同的元素之间转换，所以称它为“表达式主导”

DFA引擎：文本主导

比较NFA与DFA

一般情况下DFA比NFA要快。

NFA为创造性思维提供了丰富的施展空间。一个调教好的表达式能带来许多收益，调教的不好则会带来严重后果。

注：NFA类似手动挡汽车

回溯

NFA最重要的性质是，它会依次处理各个表达式或组成元素。当遇到需要在两个可能成功的条件中进行选择时，它会选择其一，同时记住另一个，留作候选。

这与当年玩仙剑很像，进入一个迷宫遇到岔口时，需要在每个岔口留下一些记号，如果走了思路就可以按原路返回，直到成功到达目的地为止。

在很多情况下正则引擎必须在两个或多个选项中做出选择。

回溯的两个要点

1.在“进行尝试”和“跳过尝试”之间选择时，对于匹配优先量词，引擎会优先选择“进行尝试”，而对于忽略优先量词，会选择“跳过尝试”

2.距离当前最近存储的选项就是当本地失败强制回溯返回的。就像堆盘子一样，最后叠上去的盘子肯定是最先拿下来的。

注：如果工具软件使用的是NFA主导的回溯引擎，理解正则表达式的回溯原理就成了高效完成任务的关键。

备用状态

在需要的时候，匹配可以从这里重新开始尝试。

回溯与匹配优先

如果用[0-9]+来匹配a 1234 num，[0-9]遇到4之后的空格无法匹配，而此时+号能够回溯的位置对应了四个保存的状态（,号表示进行的位置）

a 1,234 num

a 12,34 num

a 123,4 num

a 1234, num

在每个位置，[0-9]的尝试都代表一种可能。

如果用[0-9]*来匹配a 1234 num，这些状态就不会保存。因为有*号，*号限定的部分总能够匹配，所以[0-9]*根本没有触及到那些数字。

匹配优先的问题

1.使用正则匹配””中的内容

this “is” china i “linux” it

首先可能想到的是用”.*”来匹配

this “is” china i “linux” it

最终红色部分被匹配出来。因为.*属于匹配优先。

此时需要改为”[^”]*”

使用sed的做法是

sed ’s/[^”]*”([^”]*)”[^”]*/\1 /g’

2.匹配**中的内容

`

书中使用perl脚本来实现。sed在功能上不如perl，但是也能够完成这个任务。

sed -n ’s/.**(.*)<\/B>(.*)<\/B>./ \1 \2 /p’

书中的perl脚本**

**(?!< B >)匹配< B >< / B >中非的字符</span>**

匹配优先和忽略优先都期望获得匹配
固化分组
涉及perl内容，已理解但未进行深入实验

速度和效率

DFA同时记录了所有可能的匹配，这样来提高速度。DFA引擎需要更多的时间和内存，开始尝试匹配的时候它已经内建了一张路线图（类似于locate）

一般来说，DFA的速度与正则表达式无关，而NFA中二者直接相关，表达式的效率问题非常重要。

1、除特别说明外，本博客内容皆为原创，可以自由转载传播，但请署名及注明出处，不尊重别人劳动成果的不欢迎；

2、本博客内容遵守“署名-非商业性使用-禁止演绎 2.5 中国大陆”协议；