Home

zhangyiqun

Thoughts, stories and ideas.

2014年以前 About Feed

17 Feb 2009
[正则]表达式的匹配原理1

 

学习原理的意义

构建正则表达式的方式决定了某个正则表达式能否匹配一个特定字符串,在何处匹配,以及匹配成功或报告失败的速度

引擎分类

引擎有DFA,NFA

大多数awk使用DFA

grep,php使用NFA

gnu awk , gnu grep/egrep 属于混合型引擎。

引擎的类型决定了工具的特性。

引擎中的规则

1.优先选择最左端的匹配结果。只关心是否能够匹配,而不是在哪里匹配。

例如用cat来匹配

the dragging belly indicates that your cat is too fat .

2.标准量词是匹配优先的

标准量词(?,*,+,{min,max})

标准匹配量词的结果“可能”并非所有可能中最长的,但它们总是尝试匹配尽可能多的字符,直到匹配上限为止。

例如[0-9]+可以匹配March 1998中的所有数字。1匹配之后,实际上已经满足了成功的下限,但此时正则表达是匹配优先的,所以它不会停在此处,而会继续下去。

过度的匹配优先

^subject: (.*).*与subject:(.*)匹配结果一致,开头的.*会霸占整个标题的文本,而不给第二个.*留下任何字符。

强制释放

^.*([0-9][0-9])能够匹配一行字符的最后两位数字。.*会匹配尽可能多的字符,但为了整个正则表达式的匹配,它们通常要释放一些字符。

例如匹配about 24 char

[0-9][0-9]会从.匹配的字段中从后向前检测,r→h→a→r→ →2如此循环15次知道.最终释放4为止

[0-9]+能否匹配全部数字?

不能。匹配优先的结构只会在被迫的情况下交还字符。所以,最终只能匹配一个数字。

本文遵守 署名-非商业性使用-禁止演绎 2.5 中国大陆 使用协议,转载请注明作者及出处。


zhangyiqun

scribble

2014年以前 About Feed