21 Feb 2009
[正则]表达式的匹配原理2
表达式主导与文本主导
NFA引擎 ：表达式主导
当用he(te|nigh|llo)匹配文本 hello world 时 ，he会先从括号中提取te然后nigh然后llo ，当进行到时llo时整个表达式匹配成功。这种表达式的控制权在不同的元素之间转换，所以称它为“表达式主导”
DFA引擎：文本主导
| 当用he(te | nigh | llo)匹配文本 hello world 时 ，引擎会同时对te,nigh,llo进行检查。这种方式为“文本主导”，是因为它扫描的字符串中的每个字符都对引擎进行了控制。 |
比较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引擎：文本主导
| 当用he(te | nigh | llo)匹配文本 hello world 时 ，引擎会同时对te,nigh,llo进行检查。这种方式为“文本主导”，是因为它扫描的字符串中的每个字符都对引擎进行了控制。 |
比较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 中国大陆”协议；