正则表达式之回溯

 更新时间:2010年04月11日 21:22:25   作者:   我要评论

我通常在匹配一个字符串或是一组数字的时候会用到正则表达式,但很少会了解它是如何真正开始工作的?它的工作原理是什么?其实正则表达式里面的猫腻还挺多水也挺深的,有时候还不太好理解。
关于“回溯”我也是第一次接触,对它也不算很了解。下面就把我所了解的做为一个心德记录下来,以备查看。

我们所使用的正则表达式的匹配基础大概分为:优先选择最左端(最靠开头)的匹配结果和标准的匹配量词(*、+、?和{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 可能的匹配位置:/to(nite|knight|nigth)/

 

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

 

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

 

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

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

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

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

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

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

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

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

        1、未进行回溯的匹配

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

“abc” ab?c

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

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

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

        2、进行了回溯的匹配

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

“ac” ab?c

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

        3、不成功的匹配

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

“abx” ab?c

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

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

相关文章

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

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

    在正则表达式实现中,回溯是匹配过程的基本组成部分,它是正则表达式如此好用和强大的根源。然而,回溯计算代价很高,如果设计失误,将导致失控。回溯是影响整体性能的唯一因素,理解它的工作原理,以及如何减小使用频率,可能是编写高效正则表达式的关键点
    2016-12-12
  • 最全最实用的正则表达式大全分享

    最全最实用的正则表达式大全分享

    正则式太难学,而且容易忘记 。很多不太懂正则的朋友,在遇到需要用正则校验数据时,往往是在网上去找很久,结果找来的还是不很符合要求。所以我最近把开发中常用的一些正则表达式整理了一下,在这里分享一下。给自己留个底,也给朋友们做个参考。
    2015-10-10
  • php半小时精通正则表达式

    php半小时精通正则表达式

    php半小时精通正则表达式...
    2006-11-11
  • 能说明一下GETROWS的用法吗?

    能说明一下GETROWS的用法吗?

    能说明一下GETROWS的用法吗?...
    2006-06-06
  • js正则表达式之RegExp对象之compile方法  编译正则表达式

    js正则表达式之RegExp对象之compile方法 编译正则表达式

    该方法可以编译指定的正则表达式,编译之后的正则表达式执行速度将会提高,如果正则表达式多次被调用,那么调用compile方法可以有效的提高代码的执行速度,如果该正则表达式只能被使用一次,则不会有明显的效果
    2012-10-10
  • 20个正则表达式必知(能让你少写1,000行代码)

    20个正则表达式必知(能让你少写1,000行代码)

    这篇文章主要介绍了20个正则表达式必知(能让你少写1,000行代码)的相关资料,需要的朋友可以参考下
    2016-04-04
  • 比较常用的几个正则表达式匹配数字(收藏)

    比较常用的几个正则表达式匹配数字(收藏)

    正则表达式用于字符串处理、表单验证等场合,实用高效。今天小编给大家分享比较常用的几个正则表达式匹配数字,需要的朋友参考下
    2017-03-03
  • 匹配中文的正则(utf-8/utf-8)

    匹配中文的正则(utf-8/utf-8)

    下面列出了当前在 PCRE 中可能使用的修正符。括号中是这些修正符的内部 PCRE 名。修正符中的空格和换行被忽略,其它字符会导致错误。
    2009-08-08
  • 正则的几个基本概念

    正则的几个基本概念

    正则的几个基本概念...
    2006-11-11
  • JS 密码强度校验的正则表达式(简单且好用)

    JS 密码强度校验的正则表达式(简单且好用)

    最近在做一个通行证的项目,在项目中有这样的需求,注册模块中输入密码需要显示密码强度,今天小编给大家分享JS 密码强度校验的正则表达式,简单好用,需要的朋友参考下
    2017-01-01

最新评论