- 浏览: 287574 次
- 性别:
- 来自: 北京
文章分类
最新评论
-
全站唯一是我么:
请问下该功能的jdk版本是1.4的么,还是以上的?
Java实现给图片添加水印 -
Janne:
请问,你解决这问题没?是怎么回事?我今天也遇到了,没解决
myeclipse6.5中使用jax-ws启动tomcat报错问题 -
xuedong:
studypi 写道你是怎么和新浪的技术联系的?能告诉一下我吗 ...
新浪微博第三方接口调用学习 -
studypi:
你是怎么和新浪的技术联系的?能告诉一下我吗,谢谢
新浪微博第三方接口调用学习 -
dove19900520:
有用,呵呵
IE,Firefox都不放弃(兼容性问题总结)
NFA引擎匹配原理
1 为什么要了解引擎匹配原理
一个个音符杂乱无章的组合在一起,弹奏出的或许就是噪音,同样的音符经过作曲家的手,就可以谱出非常动听的乐曲,一个演奏者同样可以照着乐谱奏出动听的乐曲,但他/她或许不知道该如何去改变音符的组合,使得乐曲更动听。
作为正则的使用者也一样,不懂正则引擎原理的情况下,同样可以写出满足需求的正则,但是不知道原理,却很难写出高效且没有隐患的正则。所以对于经常使用正则,或是有兴趣深入学习正则的人,还是有必要了解一下正则引擎的匹配原理的。
2 正则表达式引擎
正则引擎大体上可分为不同的两类:DFA和NFA,而NFA又基本上可以分为传统型NFA和POSIX NFA。
DFA Deterministic finite automaton 确定型有穷自动机
NFA Non-deterministic finite automaton 非确定型有穷自动机
Traditional NFA
POSIX NFA
DFA引擎因为不需要回溯,所以匹配快速,但不支持捕获组,所以也就不支持反向引用和$number这种引用方式,目前使用DFA引擎的语言和工具主要有awk、egrep 和 lex。
POSIX NFA主要指符合POSIX标准的NFA引擎,它的特点主要是提供longest-leftmost匹配,也就是在找到最左侧最长匹配之前,它将继续回溯。同DFA一样,非贪婪模式或者说忽略优先量词对于POSIX NFA同样是没有意义的。
大多数语言和工具使用的是传统型的NFA引擎,它有一些DFA不支持的特性:
捕获组、反向引用和$number引用方式;
环视(Lookaround,(?<=…)、(?<!…)、(?=…)、(?!…)),或者有的有文章叫做预搜索;
忽略优化量词(??、*?、+?、{m,n}?、{m,}?),或者有的文章叫做非贪婪模式;
占有优先量词(?+、*+、++、{m,n}+、{m,}+,目前仅Java和PCRE支持),固化分组(?>…)。
引擎间的区别不是本文的重点,仅做简要的介绍,有兴趣的可参考相关文献。
3 预备知识
3.1 字符串组成
对于字符串“abc”而言,包括三个字符和四个位置。
3.2 占有字符和零宽度
正则表达式匹配过程中,如果子表达式匹配到的是字符内容,而非位置,并被保存到最终的匹配结果中,那么就认为这个子表达式是占有字符的;如果子表达式匹配的仅仅是位置,或者匹配的内容并不保存到最终的匹配结果中,那么就认为这个子表达式是零宽度的。
占有字符是互斥的,零宽度是非互斥的。也就是一个字符,同一时间只能由一个子表达式匹配,而一个位置,却可以同时由多个零宽度的子表达式匹配。
3.3 控制权和传动
正则的匹配过程,通常情况下都是由一个子表达式(可能为一个普通字符、元字符或元字符序列组成)取得控制权,从字符串的某一位置开始尝试匹配,一个子表达式开始尝试匹配的位置,是从前一子表达匹配成功的结束位置开始的。如正则表达式:
(子表达式一)(子表达式二)
假设(子表达式一)为零宽度表达式,由于它匹配开始和结束的位置是同一个,如位置0,那么(子表达式二)是从位置0开始尝试匹配的。
假设(子表达式一)为占有字符的表达式,由于它匹配开始和结束的位置不是同一个,如匹配成功开始于位置0,结束于位置2,那么(子表达式二)是从位置2开始尝试匹配的。
而对于整个表达式来说,通常是由字符串位置0开始尝试匹配的。如果在位置0开始的尝试,匹配到字符串某一位置时整个表达式匹配失败,那么引擎会使正则向前传动,整个表达式从位置1开始重新尝试匹配,依此类推,直到报告匹配成功或尝试到最后一个位置后报告匹配失败。
4 正则表达式简单匹本过程
4.1 基础匹配过程
源字符串:abc
正则表达式:abc
匹配过程:
首先由字符“a”取得控制权,从位置0开始匹配,由“a”来匹配“a”,匹配成功,控制权交给字符“b”;由于“a”已被“a”匹配,所以“b”从位置1开始尝试匹配,由“b”来匹配“b”,匹配成功,控制权交给“c”;由“c”来匹配“c”,匹配成功。
此时正则表达式匹配完成,报告匹配成功。匹配结果为“abc”,开始位置为0,结束位置为3。
4.2 含有匹配优先量词的匹配过程——匹配成功(一)
源字符串:abc
正则表达式:ab?c
量词“?”属于匹配优先量词,在可匹配可不匹配时,会先选择尝试匹配,只有这种选择会使整个表达式无法匹配成功时,才会尝试让出匹配到的内容。这里的量词“?”是用来修饰字符“b”的,所以“b?”是一个整体。
匹配过程:
首先由字符“a”取得控制权,从位置0开始匹配,由“a”来匹配“a”,匹配成功,控制权交给字符“b?”;由于“?”是匹配优先量词,所以会先尝试进行匹配,由“b?”来匹配“b”,匹配成功,控制权交给“c”,同时记录一个备选状态;由“c”来匹配“c”,匹配成功。记录的备选状态丢弃。
此时正则表达式匹配完成,报告匹配成功。匹配结果为“abc”,开始位置为0,结束位置为3。
4.3 含有匹配优先量词的匹配过程——匹配成功(二)
源字符串:ac
正则表达式:ab?c
匹配过程:
首先由字符“a”取得控制权,从位置0开始匹配,由“a”来匹配“a”,匹配成功,控制权交给字符“b?”;先尝试进行匹配,由“b?”来匹配“c”,同时记录一个备选状态,匹配失败,此时进行回溯,找到备选状态,“b?”忽略匹配,让出控制权,把控制权交给“c”;由“c”来匹配“c”,匹配成功。
此时正则表达式匹配完成,报告匹配成功。匹配结果为“ac”,开始位置为0,结束位置为2。其中“b?”不匹配任何内容。
4.4 含有匹配优先量词的匹配过程——匹配失败
源字符串:abd
正则表达式:ab?c
匹配过程:
首先由字符“a”取得控制权,从位置0开始匹配,由“a”来匹配“a”,匹配成功,控制权交给字符“b?”;先尝试进行匹配,由“b?”来匹配“b”,同时记录一个备选状态,匹配成功,控制权交给“c”;由“c”来匹配“d”,匹配失败,此时进行回溯,找到记录的备选状态,“b?”忽略匹配,即“b?”不匹配“b”,让出控制权,把控制权交给“c”;由“c”来匹配“b”,匹配失败。此时第一轮匹配尝试失败。
正则引擎使正则向前传动,由位置1开始尝试匹配,由“a”来匹配“b”,匹配失败,没有备选状态,第二轮匹配尝试失败。
继续向前传动,直到在位置3尝试匹配失败,匹配结束。此时报告整个表达式匹配失败。
4.5 含有忽略优先量词的匹配过程——匹配成功
源字符串:abc
正则表达式:ab??c
量词“??”属于忽略优先量词,在可匹配可不匹配时,会先选择不匹配,只有这种选择会使整个表达式无法匹配成功时,才会尝试进行匹配。这里的量词“??”是用来修饰字符“b”的,所以“b??”是一个整体。
匹配过程:
首先由字符“a”取得控制权,从位置0开始匹配,由“a”来匹配“a”,匹配成功,控制权交给字符“b??”;先尝试忽略匹配,即“b??”不进行匹配,同时记录一个备选状态,控制权交给“c”;由“c”来匹配“b”,匹配失败,此时进行回溯,找到记录的备选状态,“b??”尝试匹配,即“b??”来匹配“b”,匹配成功,把控制权交给“c”;由“c”来匹配“c”,匹配成功。
此时正则表达式匹配完成,报告匹配成功。匹配结果为“abc”,开始位置为0,结束位置为3。其中“b??”匹配字符“b”。
4.6 零宽度匹配过程
源字符串:a12
正则表达式:^(?=[a-z])[a-z0-9]+$
元字符“^”和“$”匹配的只是位置,顺序环视“(?=[a-z])”只进行匹配,并不占有字符,也不将匹配的内容保存到最终的匹配结果,所以都是零宽度的。
这个正则的意义就是匹配由字母或数字组成的,第一个字符是字母的字符串。
匹配过程:
首先由元字符“^”取得控制权,从位置0开始匹配,“^”匹配的就是开始位置“位置0”,匹配成功,控制权交给顺序环视“(?=[a-z])”;
“(?=[a-z])”要求它所在位置右侧必须是字母才能匹配成功,零宽度的子表达式之间是不互斥的,即同一个位置可以同时由多个零宽度子表达式匹配,所以它也是从位置0尝试进行匹配,位置0的右侧是字符“a”,符合要求,匹配成功,控制权交给“[a-z0-9]+”;
因为“(?=[a-z])”只进行匹配,并不将匹配到的内容保存到最后结果,并且“(?=[a-z])”匹配成功的位置是位置0,所以“[a-z0-9]+”也是从位置0开始尝试匹配的,“[a-z0-9]+”首先尝试匹配“a”,匹配成功,继续尝试匹配,可以成功匹配接下来的“1”和“2”,此时已经匹配到位置3,位置3的右侧已没有字符,这时会把控制权交给“$”;
元字符“$”从位置3开始尝试匹配,它匹配的是结束位置,也就是“位置3”,匹配成功。
此时正则表达式匹配完成,报告匹配成功。匹配结果为“a12”,开始位置为0,结束位置为3。其中“^”匹配位置0,“(?=[a-z])”匹配位置0,“[a-z0-9]+”匹配字符串“a12”,“$”匹配位置3。
转自:http://blog.csdn.net/lxcnn/article/details/4304651
发表评论
-
(从网上考过来的,收藏) javascript 正则表达式的贪婪与非贪婪
2012-10-08 10:35 843以下内容转自:http://www.cnitblog.com ... -
正则表达式常用验证
2011-08-24 12:20 819在前台很多地方需要验证输入格式,为了方便以后使用,把常用的整理 ... -
正则判断一个字符串里是否包含一些词
2011-08-16 16:53 3208今天项目里用到了正则,判断一个字符串里是不是包含这些词,词出 ... -
js取当前url参数
2011-07-19 11:14 1904js没有提供取当前url参数的方法,只能是自己从中截取了,在 ... -
正则手册
2011-07-07 16:53 989给大家共享个正则手册 欢迎查看本人博客: ... -
[ ] 字符组(Character Classes) .
2011-07-06 17:31 795[]能够匹配所包含的一系列字符中的任意一个。需要注意的是,[ ... -
正则基础之——捕获组(capture group) .
2011-07-06 17:30 9691 概述 1.1 什么是捕获组 ... -
正则表达式学习参考
2011-07-06 17:28 719正则表达式学习参考 1 ... -
正则基础之——小数点 .
2011-07-06 17:23 756小数点可以匹配除了换行符“/n”以外的任意一个字符 一 ... -
正则基础之——环视 .
2011-07-06 17:21 530环视只进行子表达式的匹配,不占有字符,匹配到的内容不保存到最终 ... -
正则基础之——/b 单词边界 .
2011-07-06 17:20 7931 概述 “/b”匹配单词边界,不匹配任何 ... -
正则应用之——日期正则表达式
2011-07-06 17:18 10121 概述 首先需要说明的一点,无论是Win ... -
.NET正则基础之——.NET正则匹配模式 .
2011-07-06 17:16 22771 概述 匹配模式指的是一些可以改变正则表 ... -
.NET正则基础之——平衡组 .
2011-07-06 17:14 17671 概述 平衡组是微软在.NET中提出的一 ... -
正则基础之——非捕获组 .
2011-07-06 17:10 1315非捕获组:(?:Expression) 接触正则表达式不久的 ... -
正则基础之——反向引用 .
2011-07-06 17:09 12651 概述 捕获组捕获到的内容,不仅可以在 ... -
.NET正则基础——.NET正则类及方法应用 .
2011-07-06 17:07 10731 概述 初学 ... -
NET正则基础之——正则委托 .
2011-07-06 17:05 7851 概述 一般的正则替换,只能对匹配的子串做 ... -
正则基础之——贪婪与非贪婪模式 .
2011-07-06 17:03 9131 概述 贪婪 ... -
正则应用之——逆序环视探索
2011-07-06 17:01 11741 问题引出 前几天在CSDN论坛遇到这样 ...
相关推荐
正则基础之——NFA引擎匹配原理.rar
正则基础之——NFA引擎匹配原理[参照].pdf
这是编译原理的一个实验, 是把一个正则表达式转化为不确定有穷自动机NFA的算法程序,朋兴趣的朋友可以下载来看看哦. 一个正则表达式就是由普通字符(例如字符 a 到 z)以及特殊字符(称为元字符)组成的文字模式...
用JAVA写的一个将正则表达式转换为NFA的代码,基于Thompson算法的思想,递归构建NFA。jar为源码文件。 输出非确定有限自动状态机的有向图。如正则表达式: c(a|b)NFA为:0-c->1-ep->2-a->3-ep->7 ,0-c->1-ep->4-b->5-...
编译原理课的大作业 包含三个小实验 在一个cpp文件里 正则表达式转换为nfa nfa转换为dfa dfa最小化 个人原创代码
代码相对简单; c语言实现; 正则表达式转换为nfa;
所以对于经常使用正则,或是有兴趣深入学习正则的人,还是有必要了解一下正则引擎的匹配原理的。 2 正则表达式引擎 正则引擎大体上可分为不同的两类:DFA和NFA,而NFA又基本上可以分为传统型NFA和POSIX N
正则表达式转换为NFA,dfa,确定化 简单 方便实现
Java把一个正则表达式转化为不确定的有穷自动机NFA算法,本实例的符号包括: 1. 基本正则表达式, 如ab 2. 重复, 如a* 3. 在各项中选择, 如a|b 使用时在Convert的Reg Exp中点击输入正则表达式, 然后...
第4章:表达式的匹配原理.... 143 发动引擎... 143 两类引擎... 144 新的标准... 144 正则引擎的分类... 145 几句题外话... 146 测试引擎的类型... 146 匹配的基础... 147 关于范例... 147 规则1:优先...
输入一个正则表达式,然后将此正则表达式转换为NFA,最后将此NFA输出 【实验要求】: 写出程序运行环境, 体会,程序结构,程序清单, 典型结果,以及结果分析 【程序运行环境】: 此程序是在Visual C++下,新建一...
C语言编写的将正则表达式转换为NFA,可以运行
用VC 6.0运行,完美编译运行,反正我们老师检查是完美的过
课程设计 正规式构造nfa.这是编译原理的一个实验, 是把一个正则表达式转化为不确定有穷自动机NFA的算法程序,朋兴趣的朋友可以下载来看看哦。
正则表达式
正则表达式转化为NFA
编译原理的一个实验,正则表达式到NFA
正则引擎:DFA和NFA.rar