网站导航网学 原创论文 网站设计 最新系统 最新研究 原创论文 获取论文 论文降重 发表论文 论文发表 UI设计定制 论文答辩PPT格式排版 期刊发表 论文专题
返回网学首页
网学原创论文
最新论文 推荐专题 热门论文 论文专题
当前位置: 网学 > 设计资源 > 正则表达式 > 正文

正则表达式之贪婪与非贪婪模式详解(概述)

来源:http://myeducs.cn 联系QQ:点击这里给我发消息 作者: 用户投稿 来源: 网络 发布时间: 13/06/29
位置11处匹配失败,一轮匹配尝试结束。

正则引擎传动装置使正则向前传动,进入下一轮尝试。后续匹配过程与第一轮尝试匹配过程基本类似,可以参考图3-1。

从匹配过程中可以看到,非贪婪模式的匹配失败过程,几乎每一步都伴随着回溯过程,对匹配效率的影响是很大的。

3.2.2 贪婪模式匹配失败过程分析——大范围子表达式
3-2

图3-2

PS:以上分析过程图示参考了《精通正则表达式》一书相关章节图示。

构建匹配失败的贪婪模式的正则表达式:".*"@

其中量词修饰的子表达式为匹配范围较大的“.”,由于最后的“@”的存在,这个正则表达式最后也是一定匹配失败的,看一下匹配过程。

首先由“"”取得控制权,由位置0处开始尝试匹配,匹配失败,直到图中标示的A处匹配成功,控制权交给“.*”。

“.*”取得控制权后,由A后面的位置开始尝试匹配,由于是贪婪模式,优化尝试匹配,一直匹配到字符串的结束位置,将控制权交给“"”。“"”取得控制权后,由于已经是字符串的结束位置,匹配失败,查找可供回溯的状态,将控制权交给“.*”,由“.*”让出已匹配字符“.”。重复以上过程,直到后面“"”匹配了C处后面的字符“””,将控制权交给“@”。由“@”匹配接下来D处的空格“ ”,匹配失败,查找可供回溯的状态,控制权交给“.*”,由“.*”让出已匹配文本。继续重复以上匹配过程,直到由“.*”让出所有已匹配的文本到I处,将控制权交给“"”。“"”匹配失败,由于已经没有可供回溯的状态,报告整个表达式在位置11处匹配失败,一轮匹配尝试结束。

正则引擎传动装置使正则向前传动,进入下一轮尝试。后续匹配过程与第一轮尝试匹配过程基本类似,可以参考图3-2。

从匹配过程中可以看到,大范围子表达式贪婪模式的匹配失败过程,从总体上看,与非贪婪模式没有什么区别,最终进行的回溯次数与非贪婪模式基本一致,对匹配效率的影响仍然很大。

3.2.3 贪婪模式匹配失败过程分析——改进的子表达式
3-3
图3-3

构建匹配失败的贪婪模式的正则表达式:"[^"]*"@

其中量词修饰的子表达式,改为匹配范围较小的排除型字符组“[^"]”,由于最后的“@”的存在,这个正则表达式最后也是一定匹配失败的,看一下匹配过程。

首先由“"”取得控制权,由位置0处开始尝试匹配,匹配失败,直到图中标示的A处匹配成功,控制权交给“[^"]*”。

“[^"]*”取得控制权后,由A后面的位置开始尝试匹配,由于是贪婪模式,优先尝试匹配,一直匹配到B处,将控制权交给“"”。“"”匹配接下来的的字符“"”,匹配成功,将控制权交给“@”。由“@”匹配接下来的空格“ ”,匹配失败,查找可供回溯的状态,控制权交给“[^"]*”,由“[^"]*”让出已匹配文本。继续重复以上匹配过程,直到由“[^"]*”让出所有已匹配的文本到C处,将控制权交给“"”。“"”匹配失败,由于已经没有可供回溯的状态,报告整个表达式在位置11处匹配失败,一轮匹配尝试结束。

正则引擎传动装置使正则向前传动,进入下一轮尝试。后续匹配过程与第一轮尝试匹配过程基本类似,可以参考图3-3。

从匹配过程中可以看到,使用了排除型字符组的贪婪模式的匹配失败过程,从总体上看,大量减少了每轮回溯的次数,可以有效的提升匹配效率。

3.2.4 贪婪模式匹配失败过程分析——固化分组
通过3.2.3节的分析可以知道,由于“[^"]*”使用了排除型字符组,那么图3-3中,在A和B之间被匹配到的字符,就一定不会是字符“"”,所以B到C之间回溯过程就是多余的,也就是说在这之间的可供回溯的状态完全可以不记录。.NET中可以使用固化分组,Java中可以使用占有优先量词来实现这一效果。

3-4
图3-4

首先由“"”取得控制权,由位置0处开始尝试匹配,匹配失败,直到图中标示的A处匹配成功,控制权交给“(?>[^"]*)”。

“(?>[^"]*)”取得控制
  • 下一篇资讯: 正则基础之神奇的转义
  • 网学推荐

  • ·【推荐参考】最新可过维普检测低于30%
  • ·【推荐】原创参考论文 原创资料
  • ·【推荐】原创参考论文导航
  • ·咨询参考QQ:3710167
  • ·咨询参考微信号:yclw90
  • ·扫一扫 加微信 咨询
  • ·我们提供原创参考论文和原创的参考资料!
  • ·很多朋友如果想要查重指导等,请沟通我们!
  • ·原创的论文资料参考省时间!
  • ·论文格式排版可以找我们!
  • ·论文答辩PPT格式排版定制!
  • ·程序和网站等UI设计定制!
  • ·程序设计定制!
  • ·网站设计定制!
  • ·UI设计定制!
  • ·程序和网站等UI设计定制!
  • ·原创参考论文参考定制!
  • 免费论文

    原创论文

    设为首页 | 加入收藏 | 论文首页 |原创论文 |
    版权所有 QQ:3710167 邮箱:3710167@qq.com 网学网 [Myeducs.cn] 您电脑的分辨率是 像素
    Copyright 2008-2020 myeducs.Cn www.myeducs.Cn All Rights Reserved 湘ICP备09003080号 常年法律顾问:王律师