Home

zhangyiqun

Thoughts, stories and ideas.

2014年以前 About Feed

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 中国大陆”协议;


zhangyiqun

scribble

2014年以前 About Feed