您的位置:

php正则之贪婪和非贪婪模式(正则的贪婪与非贪婪)

本文目录一览:

正则表达式之原理篇

背景

       最近公司规范出来后,关于字符串不提倡用 “ + ”  进行拼接,于是自己写了个function,利用正则表达式来进行匹配。对于正则表达式,之前不了解原理,每次要用的时候查一下,很浪费时间。

内容

基础知识;

正则表达式引擎;

贪婪与非贪婪模式;

DFA与NFA引擎;

回溯机制及常见的回溯形式

基础知识

1. 占有字符:正则表达式匹配过程中,如果子表达式匹配到东西,而并非是一个位置,并最终保存到匹配的结果当中

2. 零宽度:只匹配一个位置,或者是匹配的内容并不保存到匹配结果中

一个字符,同一时间只能由一个子表达式匹配,而一个位置,却可以同时由多个零宽度的子表达式匹配

3.控制权:正则表达式由左到右依次进行匹配,通常情况下是由一个表达式取得控制权,从字符串的的某个位置进行匹配,一个子表达式开始尝试匹配的位置,是从前一子表达匹配成功的结束位置开始的(例如:(表达式一)(表达式二)意思就是表达式一匹配完成后才能匹配表达式二,而匹配表达式二的位置是从表达式一的位置匹配结束后的位置开始)。如果表达式一是零宽度,那表达式一匹配完成后,表达式二匹配的位置还是原来表达式以匹配的位置。也就是说它匹配开始和结束的位置是同一个

4. 元字符 

5. 反义元字符

6. 转义字符:\  使元字符失去它的意义,仅代表其输入中字符的意义

需要转义的字符列表 \ * + ? | { [ ( ) ^ $ . # 和 空白

7. 重复限定符:匹配优先量词,忽略优先量词,即:贪婪与非贪婪

{n,}、 {n, m}、 {, m}、 ’+’ 、‘?’、 '*'

8. 字符类:[ ],区分大小写

9. 分支条件: |

10. 分组 :()指定子表达式,可限制多选项的范围、将若干字符组合为一个单元、受问号或星号之类的量词作用,例:(\d{1,3}){3}\d{3}

断言;(?

11. 括号及反向引用:(子表达式一)(子表达式二)\1      此时括号作用为分组,它具有记忆的功能,即在正则表达式内部仍然能回忆上次匹配到的是什么;\1、\2、\n 是用在正则表达式的匹配环节。在正则表达式的替换环节,则要使用像 $1、$2、$n 这样的语法

12. 平衡组 参考

正则表达式引擎

有两个主要特点:

1. 默认贪婪匹配;( 贪婪匹配与非贪婪匹配 )

2. 返回最先匹配到的结果

针对简单的正则匹配进行分析,例:

        当把cat应用到“He captured a catfish for his cat”,引擎先比较c和“H”,结果失败了。于是引擎再比较c和“e”,也失败了。直到第四个字符,c匹配了“c”。a匹配了第五个字符。到第六个字符t没能匹配“p”,也失败了。引擎再继续从第五个字符重新检查匹配性。直到第十五个字符开始,cat匹配上了“catfish”中的“cat”,正则表达式引擎急切的返回第一个匹配的结果,而不会再继续查找是否有其他更好的匹配

Rubular: 基于 Web 的 Ruby 正则表达式编辑器

贪婪与非贪婪(又称惰性、懒惰等)模式

两者影响的是被量词修饰的子表达式的行为。

贪婪模式在整个表达式匹配成功的前提下,尽可能多的匹配;而非贪婪模式(只被部分NFA引擎支持)在整个表达式匹配成功的前提下,尽可能少的匹配。

匹配优先量词(属于贪婪模式的量词):

“{m,n}”、“{m,}”、“?”、“*”和“+”。

忽略优先量词(匹配优先量词后加上“?”:非贪婪模式的量词):

“{m,n}?”、“{m,}?”、“??”、“*?”和“+?”

例:

源字符串:aa

正则表达式一:

正则表达式二:

DFA与NFA引擎(JS的正则引擎是NFA:非确定型有限自动机)

参考: 正则表达式引擎及其分类

DFA引擎:在线性时状态下执行,不要求回溯(因此永远不测试相同的字符两次);确保匹配最长的可能的字符串;因为只包含有限的状态(?),所以它不能匹配具有反向引用的模式;并且因为它不构造显示扩展,所以它不可以捕获子表达式

传统的NFA引擎:运行匹配回溯算法——以指定顺序测试正则表达式的所有可能的扩展并接受第一个匹配项。因为传统的 NFA 构造正则表达式的特定扩展以获得成功的匹配,所以它可以捕获子表达式匹配和匹配的反向引用。但传统 NFA的 回溯使它可以访问完全相同的状态多次(如果通过不同的路径到达该状态)。因此,在最坏情况下,它的执行速度可能非常慢。因为传统的 NFA 接受它找到的第一个匹配,所以它还可能会导致其他(可能更长)匹配未被发现

POSIX NFA 引擎:与传统 NFA 引擎类似,不同点:在可以确保已找到了可能的最长的匹配之前,它们将继续回溯(更慢);并且在使用 POSIX NFA 时,您恐怕不会愿意在更改回溯搜索的顺序的情况下来支持较短的匹配搜索,而非较长的匹配搜索

例:

字符串: this is yansen’s dog

正则表达式: /ya(msen|nsen|nsem)/

NFA工作方式:先在字符串中查找 y, 然后匹配其后是否为 a;  如果是 a 则继续查找其后是否为 m; 如果不是则匹配其后是否为 n (此时淘汰 msen 支分支); 然后继续看其后是否依次为 s,e; 接着测试是否为 n ,是 n 则匹配成功,不是则测试是否为 m 。为什么是 m ?因为 NFA 工作方式是以正则表达式为标准,反复测试字符串,这样同样一个字符串有可能被反复测试了很多次!

DFA:从 this 中 t 开始依次查找 y ,定位到 y ,已知其后为 a ,则查看表达式是否有 a ,此处正好有 a; 然后字符串 a 后为 n ,DFA依次测试表达式,此时 msen 不符合要求淘汰。 nsen 和 nsem 符合要求,然后DFA依次检查字符串,检测到 sen 中的 n 时只有 nsen 分支符合,则匹配成功!

由此两种引擎是完全不同的工作方式:NFA以表达式为主导,更容易操纵;DFA以文本为主导(搜索更快)

回溯机制

引擎是如何来处理那些模糊的条件匹配?

从问题的某一种状态(初始状态)出发,搜索从这种状态出发所能达到的所有“状态”,当一条路走到“尽头”的时候(不能再前进),再后退一步或若干步,从另一种可能“状态”出发,继续搜索,直到所有的“路径”(状态)都试探过。这种不断“前进”、不断“回溯”寻找解的方法,就称作“回溯法”

--来自百度百科

本质上就是深度优先搜索算法:尝试匹配失败时的下一步通常就是回溯

JS中正则表达式会产生回溯的地方都有哪些呢?

常见的回溯形式

1.贪婪量词

例:正则:/ab{1,3}c/

可视化形式

1. 没有回溯的匹配:当目标字符串是"abbbc"时

匹配过程

2. 有回溯的匹配:当目标字符串是“abbc”时

匹配过程

上图第5步有红颜色(仅表示匹配不成功):此时b{1,3}已经匹配到了2个字符“b”,准备尝试第三个时,结果发现接下来的字符是“c”。那么就认为b{1,3}就已经匹配完毕。然后状态又回到之前的状态(即第6步,与第4步一样),最后再用子表达式c,去匹配字符“c”。当然,此时整个表达式匹配成功了;上图的第6步,就是“回溯”

即:尝试可能的顺序是“从多往少”的方向去尝试:首先会尝试"bbb",然后再看整个正则是否能匹配。不能匹配时,吐出一个"b",即在"bb"的基础上,再继续尝试。如果还不行,再吐出一个,再试。如果还不行呢?只能说明匹配失败了

另一个清晰的回溯:

正则:/".*"/

目标字符串:"acd"ef

省略了尝试匹配双引号失败的匹配过程

其实“.*”最简单但也是非常影响效率的

2.惰性量词

虽然惰性量词不贪,但也会有回溯的现象(为了整体匹配成)

正则表达式

目标字符串:"12345"

匹配过程

3.分支结构

分支也是惰性的,比如/Java|JavaScript/,去匹配字符串"JavaScript",得到的结果是"Java",因为分支会一个一个尝试,如果前面的满足了,后面就不会再试验了。

分支结构中可能前面的子模式会形成了局部匹配,如果接下来表达式整体不匹配时,仍会继续尝试剩下的分支。这种尝试也可以看成一种回溯:

正则表达式

匹配过程

虽然第五步没有回到之前的状态,但仍然回到了分支结构,尝试下一种可能

总结:有回溯的过程,那么匹配效率肯定比DFA相对低一些;别看匹配慢,但是编译快而且还挺有趣

参考: 正则表达式的回溯机制

正则表达式的贪婪模式和非贪婪模式,如何取div ,li 标签的循环内容,采集别人网站的内容

MTracer正则表达式验证工具,一般好用,我是只下载了个这个玩了一会觉得上手挺简单的,就推荐下。正则表达式工具下载地址:MTracer.rar(首先打开工具,在右边有上下两个输入框,上面那个是输入正则的,下面那个是输入要匹配字符串的,上下内容输入好以后,就可以单击匹配按钮了,如果觉得匹配ok的话,就可以直接单击上面菜单的代码生成,来生成你要的C#代码,java代码,Script代码等等)比如我要匹配两个标签里的所有东西如asdawdsadwdasdmwioasdasd我要匹配两个Div之间的东西,那么就应该写[/S/s]*注意,你用request对象去请求回来的页面是带有/r 、/n 、/t这些标签的,所有你要学会如何去表示这些标签,另外捕获标签的时候,你是否要最大限度的匹配还是要最小限度的去匹配,下面就说明下这两种模式 贪婪模式 和 非贪婪模式 :在正则表达式的匹配次数后面再添加一个 ? 表示 非贪婪模式

常用的匹配次数有 *、{m.n}、+贪婪模式:表达式在可匹配可不匹配的时候,也是尽可能的 "要匹配"。

非贪婪模式表达式尽可能少的匹配,使可匹配可不匹配的表达式,尽可能的 "不匹配"。

如bdxxx taaaa

表达式A1: .*

结果: 匹配1次

表达式A2:.*?

结果:匹配2次

表达式B1:[/w/s/]{1,}?

结果:匹配2次去掉问号结果:匹配1次同理 将{1,}改+ 也可以得到相同的匹配结果,好了今天就写这么多了,哪天有空了再写写

正则贪婪模式vs非贪婪模式详解

作为开始,我们看看下面的正则:

我们本来预想上面会匹配得到 witch 和 broom 两个字符串,运行上面的例子,却发现结果只匹配到 "witch" and her "broom" 一个字符串。

之所以出现这个结局,是因为正则的贪婪模式在起作用。查找算法首先我们假设自己是正则引擎,来模拟搜索实现的过程。 正则引擎先从字符串的第0位开始搜索。 1. 第一个查找字符是 " ,正则引擎在第三个位置匹配到了它:

. 代表任意字符重复一次到多次,因此正则引擎匹配到所有字符

当文本结束后,点的匹配停止了,但仍然有剩余的的正则需要匹配,即: "

因此,正则引擎开始倒过来回溯,换句话说,就是一个字符一个字符缩减匹配。

因此正则继续缩减 . 所重复的字符,再继续尝试。

现在 " 终于匹配上了。 如果正则是global的,正则引擎会从上次匹配结果之后继续查找更多结果。

再看一个例子:

在这个例子中,因为 * 的存在,使得正则表达式具有贪婪属性,操作模式同上,先匹配第一个 " 找到了witch前的 " ,第二步匹配 . ,因为可以代表除了行结束符和换行符号的所有符号,因此直接跳到文本结尾 e ,接下来匹配 " ,找到 m 后面的 " ,接着匹配 " 后的空格,在匹配空格后的 a ,此时发现没有,则失败,重新寻找 " ;最终匹配到 "witch" a 。

总结:在贪婪(默认)模式下,正则引擎尽可能多的重复匹配字符

非贪婪模式

非贪婪模式和贪婪模式相反,可通过在代表数量的标示符后放置 ? 来开启非贪婪模式,如 ? 、 +? 甚至是 ?? 。

我们来看看非贪婪模式 .? 是怎么运转的。

下面是二者的重要区别。 正则引擎尝试用 最小可能 的重复次数来进行匹配,因此在 . 匹配了 w 后,它立即尝试 " 的匹配

下面终于匹配上了

因为正则是global的,所以正则引擎继续后面的匹配,从引号后面的 a 字符开始。后面有匹配到第二个字符串

总结:在非贪婪模式下,正则引擎尽可能少的重复匹配字符

( 本文引用若愚老师博客,仅用于学习使用,特此声明! )

02-贪婪模式与懒惰模式(非贪婪模式)

以字符串“daaadcccd”为源字符串作为栗子。

同理,除了"+"之外,带 "*" 和 "{m,n}" 的表达式都是尽可能地多匹配,这种匹配原则就叫作 "贪婪" 模式 。

在修饰匹配次数的特殊符号(+、*、{m,n})后再加上一个 "?" 号,就由贪婪模式变成懒惰模式。

以字符串“daaadcccd”为源字符串作为栗子。

举例来讲就可以明白,对于“daaadcccd”字符串“daaad”和“daaadcccd”都符合 (d)(\w+)(d) 正则,取最长的那个“daaadcccd”。而 (d)(\w+?)(d) 正则则取最短的那个“daaad”。

(d)(\w+) 和 (d)(\w+?) 也是同理。

以字符串“tdpaa/p/td tdpbb/p/td”为源字符串作为栗子。