正则表达式之回溯

关于“回溯”我也是第一次接触,对它也不算很了解。下面就把我所了解的做为一个心德记录下来,以备查看。

我们所使用的正则表达式的匹配基础大概分为:优先选择最左端(最靠开头)的匹配结果和标准的匹配量词(*、+、?和{m, n})是匹配优先的。

“优先选择最左端的匹配”顾名思义就是从字符串的起始位置开始匹配直到匹配结束这是基础;“标准匹配量词”又分为“非确定型有穷自动机(NFA)”也可以叫做“表达式主导”;另外一种是“确定型有穷自动机(DFA)”也可以叫做“文本主导”。我们目前在JavaScript中所使用的正则表达式为“表达式主导”。表达式主导和文本主导解释起来有些麻烦,先看来一个例子可能会清楚些。

代码如下:

// 使用正则表达式匹配文本
var reg = /to(nite|knight|night)/;
var str = 'doing tonight';
reg.test(str);

在上面的这个例子中,第一个元素[t],它将会重复尝试,直到目标字符串中找到‘t'为止。之后,就检查紧随其后的字符是否能由[o]匹配,如果能,就检查下面的元素(nite|knight|night)。它的真正含义是“nite”或者“knight”或者“night”。引擎会依次尝试这3种可能。尝试[nite]的过程是先尝试[n],然后[i],然后[t],最后是[e]。如果这种尝试失败,引擎会尝试另一种可能,如此继续下去,直到匹配成功或是报告失败。表达式中的控制权在不同的元素之间转换,所以称为“表达式主导”。

同样是上面的例子“文本主导”在扫描字符串时,会记录当前有效的所有匹配可。当引擎移动到t时,它会在当前处理的匹配可能中添加一个潜在的可能:








字符串中的位置 正则表达中的位置
……doing tonight 可能的匹配位置:/t↑o(nite|knight|nigth)/

接下来扫描的每个字符,都会更新当前的可能匹配序列。继续扫描两个字符以后的情况是:








字符串中的位置 正则表达中的位置
……doing tonight 可能的匹配位置:/to(ni↑te|knight|ni↑gth)/

有效的可能匹配变为两个(knight被淘汰出局)。扫描到g时,就只剩下一个可能匹配了。当h和t匹配完成后,引擎发现匹配已经完成,报告成功。“文本主导”是因为它扫描的字符串中的每个字符都对引擎进行了控制。

如果想要弄明白“表达式主导”是如何工作的,那就要看一下我们今天的主题“回溯(backtracking)”。回溯就像是在走岔路口,当遇到岔路的时候就先在每个路口做一个标记。如果走了死路,就可以照原路返回,直到遇见之前所做过的标记,标记着还未尝试过的道路。如果那条路也走不能,可以继续返回,找到下一个标记,如此重复,直到找到出路,或者直到完成所有没有尝试过的路。

在许多情况下,正则引擎必须在两个(或更多)选项中做出选择。当遇到/……x?……/时,引擎必须是否尝试匹配X。对于/……X+……/的情况,毫无疑问,X至少尝试匹配一次——因为加号要求必须匹配至少一次。第一个X匹配之后,此要求已经满足,需要决定是否尝试下一个X。如果决定进行,还要决定是否匹配第三个X,第四个X,如此继续。每次选择,其实就是做一个标记,用于提示此处还有另一个可能的选择,保留起来以备用。在回溯的过程中要考虑两个要点:哪个分支应当首先选择?回溯的时候使用的是哪个(或者是哪些个)之前保存的分支?

第一个问题是按下面这条重要原则来选择的:

如果需要在“进行尝试”和“路过尝试”之间选择,对于匹配优先量词,引擎会优先选择“进行尝试”,而对于忽略优先量词,会选择“路过尝试”。

第二个问题是按以下这条原则:

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

我们先来看几个在道路中做标记的例子:

1、未进行回溯的匹配

用[ab?c]来匹配“abc”。[a]匹配之后,匹配的当前状态如下:





“a↑bc” a↑b?c

现在轮到[b?]了,正则引擎需要决定:是需要尝试[b]呢,还是跳过?因为[?]是匹配优先的,它会尝试匹配。但是,为了确保在这个尝试最终失败之后能够恢复,引擎会把:





“a↑bc” ab?↑c
            添加到备用状态序列中。也就是说,稍后引擎可能从下面的位置继续匹配:从正则表达式中的[b?]之后,字符串的c之前(也就是说当前的位置)匹配。这实际上就是跳过[b]的匹配,而问题容许这样做。引擎做好标记后,就会继续向前检查[b]。在示例中,它能够匹配,所以新的当前状态变为:




“ab↑c” ab?↑c

最终的[c]也能成功匹配,所以整个匹配完成。备用状态不再需要了,所以不再保存它们。

2、进行了回溯的匹配

下面要匹配的文本是“ac”,在尝试[b]之前,一切都与之前的过程相同。显然,这次[b]无法匹配。也就是说,对[……?]进行尝试的路走不通了。因为有一个备用状态,这个“局部匹配失败”产工会导致整体匹配失败。引擎会进行回溯,也就是说,把“当前状态”切换为最近保存的状态。





“a↑c” ab?↑c

在[b]尝试之前保存的尚未尝试的选项。这时候,[c]可以匹配c,所以整个匹配宣告完成。

3、不成功的匹配

现在要匹配的文本是“abx”。在尝试[b]以前,因为存在问号,保存了这个备用状态:





“a↑bx” ab?↑c

[b]能够匹配,但这条路往下却走不通了,因为[c]无法匹配x。于是引擎会回溯到之前的状态,“交还”b给[c]来匹配。显然,这次测试也失败了。如果还有其他保存的状态,回溯会继续进行,但是此时不存在其他状态,在字符串中当前位置开始的整个匹配也就宣告失败。

目前对正则表达式的回溯只能理解这么多,以后我再慢慢补充吧!

(0)

相关推荐

  • 深度分析正则(pcre)最大回溯/递归限制

    今天,Tank问了一个问题, 对于如下的正则: 复制代码 代码如下: /<script>.*?<\/script>/i 当要匹配的字符串长度大于100014的时候, 就不会得出正确结果: 复制代码 代码如下: $reg = "/<script>.*?<\/script>/is"; $str = "<script>********</script>"; //长度大于100014 $ret = pr

  • PHP正则表达式的逆向引用与子模式分析

    正则表达式一个最重要的特性就是将匹配成功的模式的某部分进行存储供以后使用这一能力. 对一个正则表达式模式或部分模式两边添加圆括号()可以把这部分表达式存储到一个临时缓冲区中. 所捕获的每个子匹配都按照在正则表达式模式中从左至右所遇到的内容按顺序存储. 存储子匹配的缓冲区编号从1开始,连续编号至最大99个子表达式. 每个缓冲区都可以使用'\n'(或用'$n')访问,其中n为1至99的阿拉伯数字,用来按顺序标识特定缓冲区(子表达式). 例1:最简单最有用的例子是确定文字中连续出现两个相同单词的位置

  • JavaScript正则表达式之后向引用实例代码

    function isIP(strIP) { if (strIP=="") return false; var re=/^(\d+)\.(\d+)\.(\d+)\.(\d+)$/g //匹配IP地址的正 则表达式 if(re.test(strIP)) { if( RegExp.$1 function RegExpTest(){ var src = ""; var re = /]*)>/g; var arr,msg=""; while ((a

  • AS3 js正则表达式 反向引用(backreference)

    as3代码: var str = ""; var reg = /(\d{}) \/gx; // \ 即为反向分组,代表前一个分组相同的匹配结果字符.如\d{} 匹配了,那么\也只能为匹配, var first=str.match(reg); //match(),返回一个对象,如果reg有全局属性g,对象的数字索引为各完全匹配字符, //如果无全局属性g,索引为第一次完全匹配字符,其他索引依次为各分组匹配字符 for(var key in first) { trace("第一次

  • 详解JavaScript正则表达式之分组匹配及反向引用

    语法 元字符:(pattern) 作用:用于反复匹配的分组 属性$1~$9 如果它(们)存在,用于得到对应分组中匹配到的子串 \1或$1 用于匹配第一个分组中的内容 \2或$2 用于匹配第一个分组中的内容 ... \9或$9 用于匹配第一个分组中的内容 用法示例 var reg = /(A+)((B|C|D)+)(E+)/gi;//该正则表达式有4个分组 //对应关系 //RegExp.$1 <-> (A+) //RegExp.$2 <-> ((B|C|D)+) //RegExp.

  • php正则表达式的模式修正符和逆向引用使用介绍

    正则表达式的匹配先后顺序: 1.模式单元 2.重复匹配 ? * + {} 3.边界限定 ^ $ b B 4.模式选择 | 模式修正符: 模式修正符是标记在整个模式之外的. i :模式中的字符将同时匹配大小写字母. m :字符串视为多行. s :将字符串视为单行,换行符作为普通字符. x :将模式中的空白忽略. A :强制仅从目标字符串的开头开始匹配. D :模式中的美元元字符仅匹配目标字符串的结尾. U :匹配最近的字符串. PHP与正则表达式中的模式修正符 下面列出了当前在 PCRE 中可能使

  • 编写高质量的js之正确理解正则表达式回溯

    当一个正则表达式扫描目标字符串时,从左到右逐个扫描正则表达式的组成部分,在每个位置上测试能不能找到一个匹配.对于每一个量词和分支,都必须确定如何继续进行.如果是一个量词(如*.+?或者{2,}),那么正则表达式必须确定何时尝试匹配更多的字符:如果遇到分支(通过|操作符),那么正则表达式必须从这些选项中选择一个进行尝试. 当正则表达式做出这样的决定时,如果有必要,它会记住另一个选项,以备返回后使用.如果所选方案匹配成功,正则表达式将继续扫描正则表达式模板,如果其余部分匹配也成功了,那么匹配就结束了

  • 小议正则表达式效率 贪婪、非贪婪与回溯

    先扫盲一下什么是正则表达式的贪婪,什么是非贪婪?或者说什么是匹配优先量词,什么是忽略优先量词? 好吧,我也不知道概念是什么,来举个例子吧. 某同学想过滤之间的内容,那是这么写正则以及程序的. 复制代码 代码如下: $str = preg_replace('%<script>.+?</script>%i','',$str);//非贪婪 看起来,好像没什么问题,其实则不然.若 复制代码 代码如下: $str = '<script<script>alert(docume

  • PHP正则表达式的效率 回溯与固化分组

    先来看下问题. 字符串 复制代码 代码如下: $str = '<script>123456</script>'; 正则表达式为 复制代码 代码如下: $strRegex1 = '%<script>.+<\/script>%'; $strRegex2 = '%<script>.+?<\/script>%'; $strRegex3 = '%<script>(?:(?!<\/script>).)+<\/scri

  • VBS教程:正则表达式简介 -后向引用

    后向引用正则表达式一个最重要的特性就是将匹配成功的模式的某部分进行存储供以后使用这一能力.请回想一下,对一个正则表达式模式或部分模式两边添加圆括号将导致这部分表达式存储到一个临时缓冲区中.可以使用非捕获元字符 '?:', '?=', or '?!' 来忽略对这部分正则表达式的保存. 所捕获的每个子匹配都按照在正则表达式模式中从左至右所遇到的内容存储.存储子匹配的缓冲区编号从 1 开始,连续编号直至最大 99 个子表达式.每个缓冲区都可以使用 '\n' 访问,其中 n 为一个标识特定缓冲区的一位或

  • 正则中的回溯定义与用法分析【JS与java实现】

    本文实例分析了正则中的回溯定义与用法.分享给大家供大家参考,具体如下: 关于"回溯"我也是第一次接触,对它也不算很了解.下面就把我所了解的做为一个心德记录下来,以备查看. 我们所使用的正则表达式的匹配基础大概分为:优先选择最左端(最靠开头)的匹配结果和标准的匹配量词(*.+.?和{m, n})是匹配优先的. "优先选择最左端的匹配"顾名思义就是从字符串的起始位置开始匹配直到匹配结束这是基础:"标准匹配量词"又分为"非确定型有穷自动机(N

  • PHP 正则表达式效率 贪婪、非贪婪与回溯分析(推荐)

    先扫盲一下什么是正则表达式的贪婪,什么是非贪婪?或者说什么是匹配优先量词,什么是忽略优先量词? 好吧,我也不知道概念是什么,来举个例子吧. 某同学想过滤之间的内容,那是这么写正则以及程序的. $str = preg_replace('%<script>.+?</script>%i','',$str);//非贪婪 看起来,好像没什么问题,其实则不然.若 $str = '<script<script>alert(document.cookie)</script&

  • 正则表达式学习教程之回溯引用backreference详解

    本文实例讲述了正则表达式回溯引用backreference.分享给大家供大家参考,具体如下: 在所有例子中正则表达式匹配结果包含在源文本中的[和]之间,有的例子会使用Java来实现,如果是java本身正则表达式的用法,会在相应的地方说明.所有java例子都在JDK1.6.0_13下测试通过. 一.问题引入 一个在HTML页面中匹配标题标签(H1-H6)的问题: 文本: <body> <h1>Welcome to my page</H1> Content is divid

随机推荐