`
su1216
  • 浏览: 670434 次
  • 性别: Icon_minigender_1
  • 来自: 北京
博客专栏
Group-logo
深入入门正则表达式(jav...
浏览量:71872
E60283d7-4822-3dfb-9de4-f2377e30189c
android手机的安全问...
浏览量:128680
社区版块
存档分类
最新评论

深入入门正则表达式(java) - 匹配原理 - 2 - 回溯

阅读更多

内容可能有些不严谨的地方,希望大家落脚前先拍砖,多谢

 

深入入门正则表达式(java) - 引言

深入入门正则表达式(java) - 1 - 入门基础 
深入入门正则表达式(java) - 2 - 基本实例

深入入门正则表达式(java) - 3 - 正则在java中的使用

深入入门正则表达式(java) - 匹配原理 - 1 - 引擎分类与普适原则

深入入门正则表达式(java) - 匹配原理 - 2 - 回溯

 


回溯(backtracking)

NFA引擎最重要的性质是:它会一次处理各个子表达式或组成元素,遇到需要在两个可能成功的可能中进行选择的时候,它会选择其一,同时记住其他结果,以备后续需要

需要做出选择的情形包括 量词(决定是否尝试另一次匹配)和多选结构(决定选择哪个多选分支)

两个要点:

1.如果需要在“进行尝试”和“跳过尝试”之间选择,对于匹配优先量词来说,引擎会优先选择“进行尝试”,对于忽略优先量词来说,会选择“跳过尝试”

2.距离当前最近存储的选项就是当本地失败强制回溯返回的。使用的原则是LIFO(last in first out,后进先出)。

 

实际上,NFA搜索的过程算法就是深度优先(关于深度优先介绍见文章末尾,内容来自中文维机百科),只不过并不一定完全遍历,完成匹配之后就停止搜索了。下面我举几个简单的例子,画图来描述一下。

例,假如我们要匹配一串数字中的最后两位,目标字符串“3456”,正则“\d+(\d\d)”,下面是一个流程示意图

匹配过程比较简单,首先\d+匹配3、4、5、6,其中绿色的圆圈是\d+的备用位置。

\d+继续尝试匹配,发现没有字符了,所以它的匹配结束,把控制权交给了\d,然而\d也无法匹配,所以需要进行回溯。

 

正则回到第二个绿色圆圈那里,然后控制权交给\d。现在\d可以匹配到数字6了,匹配结束,控制权交给\d,发现没有字符留给它,所以还需要回溯。

正则回到第一个绿色圆圈那里,然后控制权交给\d。现在\d可以匹配到数字5了,匹配结束,控制权交给\d,匹配到了数字6,匹配结束,至此整个表达式完成了匹配。

这里红色的圆圈表示交换控制权,这样方便理解。只有在绿色圆圈处才可能产生新的分支,其余地方,如果匹配失败,只需要原路返回到绿色圆圈处即可,然后尝试量词和多选结构的备用状态)

 

环视中的回溯

如果环视结构的匹配尝试结束,那么它就不会留下任何备用状态。如果匹配成功,它会放弃剩余的备用状态;如果匹配失败,则继续尝试匹配,直到所有备用状态用光,所以也不会留下备用状态。

环视中,是有可能放弃备用状态的,下面要介绍的固化分组和占有优先量词也会具有这样的性质。

 

 

下面有一条显而易见,但是又容易让大家忽略的事实。

无论是匹配优先还是忽略优先,只要引擎报告匹配失败,它就必然尝试了所有可能。

所以,如果有太多的回溯的可能,那么可能会使得你的程序阻塞,在android里面会产生ANR。之后会给出能阻塞程序的例子。

(对于传统NFA来说,选择结构是按顺序的,并不是匹配优先也不是忽略优先)

 

固化分组与占有优先量词

(?>...) :固化分组

“?+”、“*+”、“++”、“{m,n}+” :占有优先量词

 

固化分组

对于“(?>...)” 中的内容部分(省略号省略的部分)来说,与之前将过的匹配规则一致,没有什么区别,但是,当此部分表达式匹配完毕,开始匹配括号外面的部分时,括号内的所有备用状态都会被放弃,也就是说,如果之后的匹配失败,也不会回退固化分组之前记录的状态(因为出了固化分组后,它就忘了之前的状态了,这哥们记性不是很好)。

 

固化分组和环视都有放弃备用状态的特点,我们可以考虑使用肯定环视来模拟固化分组。

对于“(?>regex)” ,我们希望匹配了regex之后就放弃其备用状态,我们知道“(?=regex)”匹配结束之后会放弃其备选状态,那么可以使用“(?=(?:regex))\1”,这样会比真正的固化分组慢一些,因为还要重新匹配“\1”。

 

下面给出一个简单的例子:目标字符串“abc”,正则“(?=\w+)\1”

首先\w+会匹配abc,匹配完成后放弃其所有备选状态,把控制权交给“\1”。“\1”再次重新匹配abc。

如果正则改为:“(?=\w+)\1c”

我想让\w+匹配到“ab”,这样“\1”就匹配到了“ab”,“c”对应“c”,匹配成功。但是,结果并不是这样的!

和上面的匹配过程一样:首先\w+会匹配abc,匹配完成后放弃其所有备选状态,把控制权交给“\1”。“\1”再次重新匹配abc。然后把控制权交给“c”,发现匹配失败,没有备用状态,整体匹配就失败了。有的同学可能会想,如果我让正则回溯到环视之前呢?其实也是一样的,当把控制权交给环视的时候,“\w+”依然直接匹配“abc”,后面大家都知道了,然后再次回溯……

所以当“c”无法匹配字符时,没有必要进行回溯,可以直接宣告匹配失败。

 

下面看看这个正则表达式:“(?>.*?)”

如果上面的内容理解了,那么这个正则也不难了,它永远也匹配不到任何字符。

 

 

占有优先量词

占有优先量词与匹配优先量词(贪婪匹配)很像,区别在于:占有优先量词不会交还字符,而匹配优先在需要的时候会交还字符。

下面给大家一个例子:

字符串:aaaaa

正则1:“\w+a”

正则2:“\w++a”

正则1:首先“\w+a” 的\w+部分会匹配所有字符,它会占有5个a,然后“\w+a” 对其中的a进行匹配,发现已经没有字符留给它了,这时候\w会交还之前占有的字符,每次交还一个。交还一个后,\w拥有“aaaa”,这时候“\w+a” 的a发现,它能匹配\w交还的字符,于是匹配成功,匹配结束。

 

正则2:同样,“\w++a” 的\w++部分会匹配所有字符,然后发现“\w++a” 的a部分无法匹配,但是\w++不会交还之前匹配到的字符,于是,匹配宣告失败!

 

 

区分固化分组与占有优先

作者告诉我们:请务必区分 下面两个表达式

表达式1:“(?>M)+”

表达式2:“(?>M+)”

表达式1放弃了M的备用状态,但是M并没有创造状态,所以这样做没有什么意义

表达式2放弃了M+的备用状态,这样显然有意义。

表达式3:“M++”

与表达式2一样,占有优先量词可以用固化分组来实现。

 

下面是一个稍微复杂点的占有优先表达式,如何将它转化为固化分组呢?

(\\"|[^"])*+

其实我觉得,如果理解了上面的文字,那么转化还是挺简单的,结果如下

(?>(\\"|[^"])*)

可作者觉得,可能会有很多人写成下面错误 的形式

(?>\\"|[^"])*

所以作者特意总结了一下:去掉表示占有优先的加号,用固化分组把余下的部分包括起来。

 

 

深度优先算法(Depth-First-Search)

类别: 搜索算法
数据结构:
时间复杂度:
空间复杂度:
最佳解:
完全性:
其他:

b-分支系数

m-图的最大深度

搜索算法的一种。是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

 

转贴请保留以下链接

本人blog地址

http://su1216.iteye.com/

http://blog.csdn.net/su1216/

2
3
分享到:
评论
2 楼 gtandsn 2014-04-14  
感觉看不懂
1 楼 cjp1989 2012-12-21  
楼主的正则讲的太详细了,顶下了!

相关推荐

    正则表达式素材5

    通过学习上述知识点,结合《正则表达式入门经典》和“正则表达式解释器实现原理”,你可以构建起坚实的正则表达式基础,从而在日常工作中更高效地处理文本数据,解决各种复杂的字符串匹配问题。同时,不断实践和调试...

    精通正则表达式-第三版-简体中文版

    【正则表达式基础】 ...总之,《精通正则表达式》旨在通过深入讲解正则表达式的原理和应用,帮助读者提升技能,更好地利用这一工具处理文本问题。无论是入门者还是经验丰富的开发者,都能从中获取宝贵的洞见和技巧。

    简单入门正则表达式(侧重原理,附属实例)

    最后,本章将专注于Java和.NET平台下正则表达式的使用,包括API调用、编译正则表达式、执行匹配和替换操作等,并可能包含一些平台特有功能的介绍。 通过这个压缩包的学习,你将能够掌握正则表达式的基本概念和常用...

    正则表达式详细文档CHM版.rar

    正则表达式是一种强大的文本处理工具,用于在字符串中匹配、查找、替换或提取特定模式。它是编程语言中不可或缺的一部分,被广泛应用于数据验证、文本分析、搜索与替换等场景。"正则表达式详细文档CHM版"包含了丰富...

    正则表达式学习书PDF

    此外,书中可能还会涉及正则表达式的扩展特性,比如非贪婪匹配、回溯、预查等高级主题,以及在不同编程语言中的实现差异。 2. **《正则表达式30分钟入门教程》** 这个教程可能是一个快速上手的指南,旨在短时间内...

    正则表达式的搜集,快速入门正则表达式

    快速入门正则表达式,你需要掌握以下几个核心概念: 1. **基本元素**: - 字符匹配:包括字母、数字、空格等基本字符。 - 位置匹配:如`^`表示行首,`$`表示行尾,`\b`表示单词边界。 - 量词:`*`表示零或多个,...

    正则表达式素材3

    在《正则表达式入门经典》(Watt, 美国作者)这本书中,作者深入浅出地介绍了正则表达式的基础知识和高级技巧,为初学者提供了宝贵的资源。 正则表达式的概念始于文本编辑器,如vi和emacs,后来被广泛应用于各种编程...

    正则表达式30分钟入门教程

    在这个30分钟入门教程中,我们将深入探讨正则表达式的基础概念、语法和常见用法,帮助你快速掌握这一强大的工具。 一、基础概念 1. 元字符:在正则表达式中,一些特殊字符如`.`、`*`、`+`、`?`、`^`、`$`、`|`、`()...

    精通正则表达式~~~

    第1章:正则表达式入门.... 1 解决实际问题... 2 作为编程语言的正则表达式... 4 以文件名做类比... 4 以语言做类比... 5 正则表达式的知识框架... 6 对于有部分经验的读者... 6 检索文本文件:Egrep. 6 ...

    精通正则表达式第三版(chm)

    《精通正则表达式第三版...《精通正则表达式第三版》不仅适合初学者入门,也对经验丰富的开发者提供了深入的理解和实践指导。通过学习这本书,读者将能够熟练地运用正则表达式解决实际问题,提升编程和数据处理的效率。

    正则表达式(含RegEx Tool正则表达式测试工具)

    - **深入浅出**:进阶学习包括理解回溯、预查、条件分支等高级技巧,以及对Unicode字符集的支持,提高正则表达式的灵活性和效率。 4. **应用实例** - **日期校验**:正则表达式可以用于验证日期格式,如`\d{4}-\d...

    【转载】正则表达式教程

    正则表达式是一种强大的文本处理工具,用于匹配、查找、替换和分析字符串。在IT行业中,正则表达式被广泛应用于各种场景,如数据验证、文本挖掘、日志分析等。下面将根据提供的资源,为你详细解读正则表达式的基础...

    正则表达式详细教程加测试工具

    《精通正则表达式.pdf》这本书是学习正则表达式的经典教材,它涵盖了正则表达式的各种核心概念,如字符类、量词、分组、断言以及回溯等。通过阅读这本书,你可以系统地学习到正则表达式的语法和用法,进一步提升你在...

    正则表达式资料完整版

    正则表达式是一种强大的文本处理工具,用于在字符串中匹配、查找、替换或者提取符合特定模式的文本。它在编程语言、数据处理、文本编辑器等众多领域有着广泛的应用。"正则表达式资料完整版"这个压缩包文件很可能是为...

    30分钟教你轻松掌握正则表达式

    2. **编程语言支持**:多数编程语言如JavaScript、Python、Java都内置了正则表达式支持。 通过这个30分钟的学习,你应该能够初步掌握正则表达式的基本用法,并开始在实际项目中应用。但请记住,正则表达式的深度和...

Global site tag (gtag.js) - Google Analytics