手机网站建设的背景,有别墅的件怎么写者,网络营销与策划形考任务答案,做h5的网站页面设计1 概述 贪婪与非贪婪模式影响的是被量词修饰的子表达式的匹配行为#xff0c;贪婪模式在整个表达式匹配成功的前提下#xff0c;尽可能多的匹配#xff0c;而非贪婪模式在整个表达式匹配成功的前提下#xff0c;尽可能少的匹配。非贪婪模式只被部分NFA引擎所支持。 属于贪婪…1 概述 贪婪与非贪婪模式影响的是被量词修饰的子表达式的匹配行为贪婪模式在整个表达式匹配成功的前提下尽可能多的匹配而非贪婪模式在整个表达式匹配成功的前提下尽可能少的匹配。非贪婪模式只被部分NFA引擎所支持。 属于贪婪模式的量词也叫做匹配优先量词包括 “{m,n}”、“{m,}”、“?”、“*”和“”。 在一些使用NFA引擎的语言中在匹配优先量词后加上“?”即变成属于非贪婪模式的量词也叫做忽略优先量词包括 “{m,n}?”、“{m,}?”、“??”、“*?”和“?”。 从正则语法的角度来讲被匹配优先量词修饰的子表达式使用的就是贪婪模式如“(Expression)”被忽略优先量词修饰的子表达式使用的就是非贪婪模式如“(Expression)?”。 对于贪婪模式各种文档的叫法基本一致但是对于非贪婪模式有的叫懒惰模式或惰性模式有的叫勉强模式其实叫什么无所谓只要掌握原理和用法能够运用自如也就是了。个人习惯使用贪婪与非贪婪的叫法所以文中都会使用这种叫法进行介绍。 2 贪婪与非贪婪模式匹配原理
对于贪婪与非贪婪模式可以从应用和原理两个角度进行理解但如果想真正掌握还是要从匹配原理来理解的。 先从应用的角度回答一下“什么是贪婪与非贪婪模式” 2.1 从应用角度分析贪婪与非贪婪模式
2.1.1 什么是贪婪与非贪婪模式
先看一个例子 举例 源字符串aadivtest1/divbbdivtest2/divcc 正则表达式一div.*/div 匹配结果一divtest1/divbbdivtest2/div 正则表达式二div.*?/div 匹配结果二divtest1/div这里指的是一次匹配结果所以没包括divtest2/div 根据上面的例子从匹配行为上分析一下什是贪婪与非贪婪模式。 正则表达式一采用的是贪婪模式在匹配到第一个“/div”时已经可以使整个表达式匹配成功但是由于采用的是贪婪模式所以仍然要向右尝试匹配查看是否还有更长的可以成功匹配的子串匹配到第二个“/div”后向右再没有可以成功匹配的子串匹配结束匹配结果为“divtest1/divbbdivtest2/div”。当然实际的匹配过程并不是这样的后面的匹配原理会详细介绍。 仅从应用角度分析可以这样认为贪婪模式就是在整个表达式匹配成功的前提下尽可能多的匹配也就是所谓的“贪婪”通俗点讲就是看到想要的有多少就捡多少除非再也没有想要的了。 正则表达式二采用的是非贪婪模式在匹配到第一个“/div”时使整个表达式匹配成功由于采用的是非贪婪模式所以结束匹配不再向右尝试匹配结果为“divtest1/div”。 仅从应用角度分析可以这样认为非贪婪模式就是在整个表达式匹配成功的前提下尽可能少的匹配也就是所谓的“非贪婪”通俗点讲就是找到一个想要的捡起来就行了至于还有没有没捡的就不管了。 2.1.2 关于前提条件的说明
在上面从应用角度分析贪婪与非贪婪模式时一直提到的一个前提条件就是“整个表达式匹配成功”为什么要强调这个前提我们看下下面的例子。 正则表达式三div.*/divbb 匹配结果三divtest1/divbb 修饰“.”的仍然是匹配优先量词“*”所以这里还是贪婪模式前面的“div.*/div”仍然可以匹配到“divtest1/divbbdivtest2/div”但是由于后面的“bb”无法匹配成功这时“div.*/div”必须让出已匹配的“bbdivtest2/div”以使整个表达式匹配成功。这时整个表达式匹配的结果为“divtest1/divbb”“div.*/div”匹配的内容为“divtest1/div”。可以看到在“整个表达式匹配成功”的前提下贪婪模式才真正的影响着子表达式的匹配行为如果整个表达式匹配失败贪婪模式只会影响匹配过程对匹配结果的影响无从谈起。 非贪婪模式也存在同样的问题来看下面的例子。
正则表达式四div.*?/divcc 匹配结果四divtest1/divbbdivtest2/divcc 这里采用的是非贪婪模式前面的“div.*?/div”仍然是匹配到“divtest1/div”为止此时后面的“cc”无法匹配成功要求“div.*?/div”必须继续向右尝试匹配直到匹配内容为“divtest1/divbbdivtest2/div”时后面的“cc”才能匹配成功整个表达式匹配成功匹配的内容为“divtest1/divbbdivtest2/divcc”其中“div.*?/div”匹配的内容为“divtest1/divbbdivtest2/div”。可以看到在“整个表达式匹配成功”的前提下非贪婪模式才真正的影响着子表达式的匹配行为如果整个表达式匹配失败非贪婪模式无法影响子表达式的匹配行为。 2.1.3 贪婪还是非贪婪——应用的抉择
通过应用角度的分析已基本了解了贪婪与非贪婪模式的特性那么在实际应用中究竟是选择贪婪模式还是非贪婪模式呢这要根据需求来确定。 对于一些简单的需求比如源字符为“aadivtest1/divbb”那么取得div标签使用贪婪与非贪婪模式都可以取得想要的结果使用哪一种或许关系不大。 但是就2.1.1中的例子来说实际应用中一般一次只需要取得一个配对出现的div标签也就是非贪婪模式匹配到的内容贪婪模式所匹配到的内容通常并不是我们所需要的。 那为什么还要有贪婪模式的存在呢从应用角度很难给出满意的解答了这就需要从匹配原理的角度去分析贪婪与非贪婪模式。 2.2 从匹配原理角度分析贪婪与非贪婪模式
如果想真正了解什么是贪婪模式什么是非贪婪模式分别在什么情况下使用各自的效率如何那就不能仅仅从应用角度分析而要充分了解贪婪与非贪婪模式的匹配原理。 2.2.1 从基本匹配原理谈起
NFA引擎基本匹配原理参考正则基础之——NFA引擎匹配原理。 这里主要针对贪婪与非贪婪模式涉及到的匹配原理进行介绍。先看一下贪婪模式简单的匹配过程。 源字符串Regex 正则表达式.* 图2-1 注为了能够看清晰匹配过程上面的空隙留得较大实际源字符串为“”Regex””下同。 来看一下匹配过程。首先由第一个“”取得控制权匹配位置0位的“”匹配成功控制权交给“.*”。 “.*”取得控制权后由于“*”是匹配优先量词在可匹配可不匹配的情况下优先尝试匹配。从位置1处的“R”开始尝试匹配匹配成功继续向右匹配匹配位置2处的“e”匹配成功继续向右匹配直到匹配到结尾的“””匹配成功由于此时已匹配到字符串的结尾所以“.*”结束匹配将控制权交给正则表达式最后的“”。 “”取得控制权后由于已经在字符串结束位置匹配失败向前查找可供回溯的状态控制权交给“.*”由“.*”让出一个字符也就是字符串结尾处的“””再把控制权交给正则表达式最后的“”由“”匹配字符串结尾处的“”匹配成功。 此时整个正则表达式匹配成功其中“.*”匹配的内容为“Regex”匹配过程中进行了一次回溯。 接下来看一下非贪婪模式简单的匹配过程。 源字符串Regex 正则表达式.*? 图2-2 看一下非贪婪模式的匹配过程。首先由第一个“”取得控制权匹配位置0位的“”匹配成功控制权交给“.*?”。 “.*?”取得控制权后由于“*?”是忽略优先量词在可匹配可不匹配的情况下优先尝试不匹配由于“*”等价于“{0,}”所以在忽略优先的情况下可以不匹配任何内容。从位置1处尝试忽略匹配也就是不匹配任何内容将控制权交给正则表达式最后的“””。 “”取得控制权后从位置1处尝试匹配由“”匹配位置1处的“R”匹配失败向前查找可供回溯的状态控制权交给“.*?”由“.*?”吃进一个字符匹配位置1处的“R”再把控制权交给正则表达式最后的“”。 “”取得控制权后从位置2处尝试匹配由“”匹配位置1处的“e”匹配失败向前查找可供回溯的状态重复以上过程直到由“.*?”匹配到“x”为止再把控制权交给正则表达式最后的“”。 “”取得控制权后从位置6处尝试匹配由“”匹配字符串最后的“”匹配成功。 此时整个正则表达式匹配成功其中“.*?”匹配的内容为“Regex”匹配过程中进行了五次回溯。 2.2.2 贪婪还是非贪婪——匹配效率的抉择
通过匹配原理的分析可以看到在匹配成功的情况下贪婪模式进行了更少的回溯而回溯的过程需要进行控制权的交接让出已匹配内容或匹配未匹配内容并重新尝试匹配在很大程度上降低匹配效率所以贪婪模式与非贪婪模式相比存在匹配效率上的优势。 但2.2.1中的例子仅仅是一个简单的应用读者看到这里时是否会存在这样的疑问贪婪模式就一定比非贪婪模式匹配效率高吗答案是否定的。 举例 需求取得两个“”中的子串其中不能再包含“”。 正则表达式一.* 正则表达式二.*? 情况一当贪婪模式匹配到更多不需要的内容时可能存在比非贪婪模式更多的回溯。比如源字符串为“The word Regex means regular expression.”。 情况二贪婪模式无法满足需求。比如源字符串为“The phrase regular expression is called Regex for short.”。 对于情况一正则表达式一采用的贪婪模式“.*”会一直匹配到字符串结束位置控制权交给最后的“””匹配不成功后再进行回溯由于多匹配的内容“means regular expression.”远远超过需匹配内容本身所以采用正则表达式一时匹配效率会比使用正则表达式二的非贪婪模式低。 对于情况二正则表达式一匹配到的是“regular expression is called Regex”连需求都不满足自然也谈不上什么匹配效率的高低了。 以上两种情况是普遍存在的那么是不是为了满足需求又兼顾效率就只能使用非贪婪模式了呢当然不是根据实际情况变更匹配优先量词修饰的子表达式不但可以满足需求还可以提高匹配效率。 源字符串Regex 给出正则表达式三[^]* 看一下正则表达式三的匹配过程。 图2-3 首先由第一个“”取得控制权匹配位置0位的“”匹配成功控制权交给“[^]*”。 “[^]*”取得控制权后由于“*”是匹配优先量词在可匹配可不匹配的情况下优先尝试匹配。从位置1处的“R”开始尝试匹配匹配成功继续向右匹配匹配位置2处的“e”匹配成功继续向右匹配直到匹配到“x”匹配成功再匹配结尾的“””时匹配失败将控制权交给正则表达式最后的“”。 “””取得控制权后匹配字符串结尾处的“””匹配成功。 此时整个正则表达式匹配成功其中“[^]*”匹配的内容为“Regex”匹配过程中没有进行回溯。 将量词修饰的子表达式由范围较大的“.”换成了排除型字符组“[^]”使用的仍是贪婪模式很完美的解决了需求和效率问题。当然由于这一匹配过程没有进行回溯所以也不需要记录回溯状态这样就可以使用固化分组对正则做进一步的优化。 给出正则表达式四(?[^]*) 固化分组并不是所有语言都支持的如.NET支持而Java就不支持但是在Java中却可以使用更简单的占有优先量词来代替[^]*。 3 贪婪还是非贪婪模式——再谈匹配效率 一般来说贪婪与非贪婪模式如果量词修饰的子表达式相同比如“.*”和“.*?”它们的应用场景通常是不同的所以效率上一般不具有可比性。 而对于改变量词修饰的子表达式以满足需求时比如把“.*”改为“[^]*”由于修饰的子表达式已不同也不具有直接的可对比性。但是在相同的子表达式又都可以满足需求的情况下比如“[^]*”和“[^]*?”贪婪模式的匹配效率通常要高些。 同时还有一个事实就是非贪婪模式可以实现的通过优化量词修饰的子表达式的贪婪模式都可以实现而贪婪模式可以实现的一些优化效果却未必是非贪婪模式可以实现的。 贪婪模式还有一点优势就是在匹配失败时贪婪模式可以更快速的报告失败从而提升匹配效率。下面将全面考察贪婪与非贪婪模式的匹配效率。 3.1 效率提升——演进过程
在了解了贪婪与非贪婪模式的匹配基本原理之后我们再来重新看一下正则效率提升的演进过程。 需求取得两个“”中的子串其中不能再包含“”。 源字符串The phrase regular expression is called Regex for short. 正则表达式一.* 正则表达式一匹配的内容为“regular expression is called Regex”不符合要求。 提出正则表达式二.*? 首先“”取得控制权由位置0位开始尝试匹配直到位置11处匹配成功控制权交给“.*?”匹配过程同2.2.1中非贪婪模式的匹配过程。“.*?”匹配的内容为“Regex”匹配过程中进行了四次回溯。 如何消除回溯带来的匹配效率的损失就是使用更小范围的子表达式采用贪婪模式提出正则表达式三[^]* 首先“”取得控制权由位置0位开始尝试匹配直到位置11处匹配成功控制权交给“[^]*”匹配过程同2.2.2节中非贪婪模式的匹配过程。“[^]*”匹配的内容为“Regex”匹配过程中没有进行回溯。 3.2 效率提升——更快的报告失败
以上讨论的是匹配成功的演进过程而对于一个正则表达式在匹配失败的情况下如果能够以最快的速度报告匹配失败也会提升匹配效率这或许是我们设计正则过程中最容易忽略的。而在源字符串数据量非常大或正则表达式比较复杂的情况下是否能够快速报告匹配失败将对匹配效率产生直接的影响。 下面将构建匹配失败的正则表达式对匹配过程进行分析。 以下匹配过程分析中源字符串统一为The phrase regular expression is called Regex for short. 3.2.1 非贪婪模式匹配失败过程分析图3-1 构建匹配失败的非贪婪模式的正则表达式.*? 由于最后的“”的存在这个正则表达式最后一定是匹配失败的那么看一下匹配过程。 首先由“”取得控制权由位置0处开始尝试匹配匹配失败直到图中标示的A处匹配成功控制权交给“.*?”。 “.*?”取得控制权后由A后面的位置开始尝试匹配由于是非贪婪模式首先忽略匹配将控制权交给“”同时记录一下回溯状态。“”取得控制权后由A后面的位置开始尝试匹配匹配字符“r”失败查找可供回溯的状态将控制权交给“.*?”由“.*?”匹配字符“r”。重复以上过程直到“.*?”匹配了B处前面的字符“n”“”匹配了B处的字符“””将控制权交给“”。由“”匹配接下来的空格“ ”匹配失败查找可供回溯的状态控制权交给“.*?”由“.*?”匹配空格。继续重复以上匹配过程直到由“.*?”匹配到字符串结束位置将控制权交给“”。由于已经是字符串结束位置匹配失败报告整个表达式在位置11处匹配失败一轮匹配尝试结束。 正则引擎传动装置使正则向前传动进入下一轮尝试。后续匹配过程与第一轮尝试匹配过程基本类似可以参考图3-1。 从匹配过程中可以看到非贪婪模式的匹配失败过程几乎每一步都伴随着回溯过程对匹配效率的影响是很大的。 3.2.2 贪婪模式匹配失败过程分析——大范围子表达式图3-2 PS以上分析过程图示参考了《精通正则表达式》一书相关章节图示。 构建匹配失败的贪婪模式的正则表达式.* 其中量词修饰的子表达式为匹配范围较大的“.”由于最后的“”的存在这个正则表达式最后也是一定匹配失败的看一下匹配过程。 首先由“”取得控制权由位置0处开始尝试匹配匹配失败直到图中标示的A处匹配成功控制权交给“.*”。 “.*”取得控制权后由A后面的位置开始尝试匹配由于是贪婪模式优化尝试匹配一直匹配到字符串的结束位置将控制权交给“”。“”取得控制权后由于已经是字符串的结束位置匹配失败查找可供回溯的状态将控制权交给“.*”由“.*”让出已匹配字符“.”。重复以上过程直到后面“”匹配了C处后面的字符“””将控制权交给“”。由“”匹配接下来D处的空格“ ”匹配失败查找可供回溯的状态控制权交给“.*”由“.*”让出已匹配文本。继续重复以上匹配过程直到由“.*”让出所有已匹配的文本到I处将控制权交给“”。“”匹配失败由于已经没有可供回溯的状态报告整个表达式在位置11处匹配失败一轮匹配尝试结束。 正则引擎传动装置使正则向前传动进入下一轮尝试。后续匹配过程与第一轮尝试匹配过程基本类似可以参考图3-2。 从匹配过程中可以看到大范围子表达式贪婪模式的匹配失败过程从总体上看与非贪婪模式没有什么区别最终进行的回溯次数与非贪婪模式基本一致对匹配效率的影响仍然很大。 3.2.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 首先由“”取得控制权由位置0处开始尝试匹配匹配失败直到图中标示的A处匹配成功控制权交给“(?[^]*)”。 “(?[^]*)”取得控制权后由A后面的位置开始尝试匹配由于是贪婪模式优先尝试匹配一直匹配到B处将控制权交给“”在这一匹配过程中不记录任何可供回溯的状态。“”匹配接下来的字符“””匹配成功将控制权交给“”。由“”匹配接下来的空格“ ”匹配失败查找可供回溯的状态由于已经没有可供回溯的状态报告整个表达式在位置11处匹配失败一轮匹配尝试结束。 正则引擎传动装置使正则向前传动进入下一轮尝试。后续匹配过程与第一轮尝试匹配过程基本类似可以参考图3-4。 从匹配过程中可以看到使用了固化分组的贪婪模式的匹配失败过程没有涉及到回溯可以最大限度的提升匹配效率。 3.3 非贪婪模式向贪婪模式的转换
使用匹配范围较大的子表达式时贪婪模式与非贪婪模式匹配到的内容会有所不同但是通过优化子表达式非贪婪模式可以实现的匹配贪婪模式都可以实现。 比如在实际应用中匹配img标签的内容。 举例 需求取得img标签中的图片地址src后固定为“”” 源字符串img classtest src/img/logo.gif title测试 / 正则表达式一img\b.*?src(.*?).*? 匹配结果中捕获组1的内容即为图片地址。可以看到这个例子中使用的都是非贪婪模式而根据上面章节的分析后面两个非贪婪模式都可以使用排除型字符组将非贪婪模式转换为贪婪模式。 正则表达式二img\b.*?src([^]*)[^]* 注“src…”和标签结束标记符“”之间的属性中也可能出现字符“”但那是极端情况这里不予讨论。 后两处非贪婪模式可以通过排除型字符组转换为贪婪模式提高匹配效率而“src”前的非贪婪模式由于要排除的是一个字符序列“src”而不是单独的某一个或几个字符所以不能使用排除型字符组。当然也不是没有办法可以使用顺序环视来达到这一效果。 正则表达式三img\b(?:(?!src).)*src([^]*)[^]* “(?!src).”表示这样一个字符从它开始右侧不能是字符序列“src”而“(?:(?!src).)*”就表示符合上面规则的字符有0个或无限多个。这样就达到排除字符序列的目的实现的效果同排除型字符组一样只不过排除型字符组排除的是一个或多个字符而这种环视结构排除的是一个或多个有序的字符序列。 但是以顺序环视的方式排除字符序列由于在匹配每一个字符时都要进行较多的判断所以相对于非贪婪模式是提升效率还是降低效率要根据实际情况进行分析。对于简单的正则表达式或是简单的源字符串一般来说是非贪婪模式效率高些而对于数量较大源字符串或是复杂的正则表达式一般来说是贪婪模式效率高些。 比如上面取得img标签中的图片地址需求基本上用正则表达二就可以了对于复杂的应用如平衡组中就需要使用结合环视的贪婪模式了。 以匹配嵌套div标签的平衡组为例 Regex reg new Regex((?isx) #匹配模式忽略大小写“.”匹配任意字符 div[^]* #开始标记“div...” (? #分组构造用来限定量词“*”修饰范围 div[^]* (?Open) #命名捕获组遇到开始标记入栈Open计数加1 | #分支结构 /div (?-Open) #狭义平衡组遇到结束标记出栈Open计数减1 | #分支结构 (?:(?!/?div\b).)* #右侧不为开始或结束标记的任意字符 )* #以上子串出现0次或任意多次 (?(Open)(?!)) #判断是否还有OPEN有则说明不配对什么都不匹配 /div #结束标记“/div” ); “(?:(?!/?div\b).)*”这里使用的就是结合环视的贪婪模式虽然每匹一个字符都要做很多判断但这种判断是基于字符的速度很快而如果这里使用非贪婪模式那么每次要做的就是分支结构“|”的判断了而分支结构是非常影响匹配效率的其代价远远高于对确定字符的判断。而另外一个原因就是贪婪模式可以结合固化分组来提升效率而对非贪婪模式使用固化分组却是没有意义的。 4 贪婪与非贪婪——最后的回顾
4.1 一个例子的匹配原理回顾
再回过头来看一下2.1.1节例子中正则前面从应用角度进行了分析但讨论过匹配原理后会发现匹配过程并不是那么简单的下面从匹配原理角度分析的匹配过程。 图4-1 首先由“”取得控制权由位置0位开始尝试匹配匹配字符“a”匹配失败第一轮匹配结束。第二轮匹配从位置1开始尝试匹配同样匹配失败。第三轮从位置3开始尝试匹配匹配字符“”匹配成功控制权交给“d”。 “d”尝试匹配字符“d”匹配成功控制权交给“i”。重复以上过程直到由“”匹配到字符“”控制权交给“.*”。 “.*”属于贪婪模式将从B处后的字符“t”开始一直匹配到E处也就是字符串结束位置将控制权交给“”。 “”从字符串结束位置尝试匹配匹配失败向前查找可供回溯的状态把控制权交给“.*”由“.*”让出一个字符“c”把控制权再交给“”尝试匹配匹配失败向前查找可供回溯的状态。一直重复以上过程直到“.*”让出已匹配的字符“”实际上也就是让出了已匹配的子串“/divcc”为止“”才匹配字符“”成功控制权交给“/”。 接下来由“/”、“d”、“i”、“v”分别匹配对应的字符成功此时整个正则表达式匹配完毕。 4.2 贪婪与非贪婪——量词的细节 4.2.1 区间量词的非贪婪模式
前面提到的非贪婪模式一直都是使用的“*?”而没有涉及到其它的区间量词对于“*?”和“?”这样的非贪婪模式大多数接触过正则表达式的人都可以理解但是对于区间量词的非贪婪模式比如“{m,n}?”要么是没见过要么是不理解主要是这种应用场景非常少所以被忽略了。 首先需要明确的一点就是量词“{m,n}”是匹配优先量词虽然它有了上限但是在达到上限之前能够匹配还是要尽可能多的匹配的。而“{m,n}?”就是对应的忽略优先量词了在可匹配可不匹配的情况下尽可能少的匹配。 接下来举一个例子说明这种非贪婪模式的应用。 举例参考 限制字符长度与最小匹配 需求如何限制在长度为100的字符串中从头匹配到最先出现的abc csdn.{1,100}abc 这样写是最大匹配(1-100个字符串中我需要最小的) 比如csdnfddabckjdsfjabc匹配结果应为csdnfddabc 正则表达式csdn.{1,100}?abc 或许对这个例子还有人不是很理解但是想想其实“*”就等价于“{0,}”“”就等价于“{1,}”“*?”也就是“{0,}?”抽象出来也就是“{m,}?”即上限为无穷大。如果上限为一个固定值那就是“{m,n}?”这样应该也就可以理解了。 “{m}”没有放在匹配优先量词中同样的“{m}?”虽然被部分语言所支持但是也没有放在忽略优先量词中主要是因为这两种量词实现的效果是一样的只有被修饰的子表达式匹配m次才能匹配成功且没有可供回溯的状态所以也不存在是匹配优先还是忽略优先的问题也就不在本文的讨论范围内。事实上即使讨论也没有意义的只要知道它们的匹配行为也就是了。 4.2.2 忽略优先量词的匹配下限
对于匹配优先量词的匹配下限很好理解“?”等价于“{0,1}”它修饰的子表达式最少匹配0次最多匹配1次“*”等价于“{0,}”它修饰的子表达式最少匹配0次最多匹配无穷多次“”等价于“{1,}”它修饰的子表达式最少匹配1次最多匹配无穷多次。 对于忽略优先量词的下限也是容易忽略的。 “??”也是忽略优先量词被修饰的子表达式使用的也是非贪婪模式“??”修饰的子表达式最少匹配0次最多匹配1次。在匹配过程中遵循非贪婪模式匹配原则先不匹配即匹配0次记录回溯状态只有不得不匹配时才去尝试匹配。 “*?”修饰的子表达式最少匹配0次最多匹配无穷多次“?”修饰的子表达式最少匹配1次最多匹配无穷多次“?”虽然使用的是非贪婪模式在匹配过程中首先要匹配一个字符之后才是忽略匹配的这一点也需要注意。 4.3 贪婪与非贪婪模式小结
Ø 从语法角度看贪婪与非贪婪 被匹配优先量词修饰的子表达式使用的是贪婪模式被忽略优先量词修饰的子表达式使用的是非贪婪模式。 匹配优先量词包括“{m,n}”、“{m,}”、“?”、“*”和“”。 忽略优先量词包括“{m,n}?”、“{m,}?”、“??”、“*?”和“?”。 Ø 从应用角度看贪婪与非贪婪 贪婪与非贪婪模式影响的是被量词修饰的子表达式的匹配行为贪婪模式在整个表达式匹配成功的前提下尽可能多的匹配而非贪婪模式在整个表达式匹配成功的前提下尽可能少的匹配。非贪婪模式只被部分NFA引擎所支持。 Ø 从匹配原理角度看贪婪与非贪婪 能达到同样匹配结果的贪婪与非贪婪模式通常是贪婪模式的匹配效率较高。 所有的非贪婪模式都可以通过修改量词修饰的子表达式转换为贪婪模式。 贪婪模式可以与固化分组结合提升匹配效率而非贪婪模式却不可以。
