正则基础之 NFA引擎匹配原理

1       为什么要了解引擎匹配原理


一个个音符杂乱无章的组合在一起,弹奏出的或许就是噪音,同样的音符经过作曲家的手,就可以谱出非常动听的乐曲,一个演奏者同样可以照着乐谱奏出动听的乐曲,但他/她或许不知道该如何去改变音符的组合,使得乐曲更动听。

作为正则的使用者也一样,不懂正则引擎原理的情况下,同样可以写出满足需求的正则,但是不知道原理,却很难写出高效且没有隐患的正则。所以对于经常使用正则,或是有兴趣深入学习正则的人,还是有必要了解一下正则引擎的匹配原理的。

2       正则表达式引擎

正则引擎大体上可分为不同的两类:DFA和NFA,而NFA又基本上可以分为传统型NFA和POSIX NFA。

DFA Deterministic finite automaton 确定型有穷自动机

NFA Non-deterministic finite automaton 非确定型有穷自动机

Traditional NFA

POSIX NFA

DFA引擎因为不需要回溯,所以匹配快速,但不支持捕获组,所以也就不支持反向引用和$number这种引用方式,目前使用DFA引擎的语言和工具主要有awk、egrep 和 lex。

POSIX NFA主要指符合POSIX标准的NFA引擎,它的特点主要是提供longest-leftmost匹配,也就是在找到最左侧最长匹配之前,它将继续回溯。同DFA一样,非贪婪模式或者说忽略优先量词对于POSIX NFA同样是没有意义的。

大多数语言和工具使用的是传统型的NFA引擎,它有一些DFA不支持的特性:

  捕获组、反向引用和$number引用方式;

  环视(Lookaround,(?<=…)、(?<!…)、(?=…)、(?!…)),或者有的有文章叫做预搜索;

  忽略优化量词(??、*?、+?、{m,n}?、{m,}?),或者有的文章叫做非贪婪模式;

  占有优先量词(?+、*+、++、{m,n}+、{m,}+,目前仅Java和PCRE支持),固化分组(?>…)。

引擎间的区别不是本文的重点,仅做简要的介绍,有兴趣的可参考相关文献。

3       预备知识


3.1     字符串组成

对于字符串“abc”而言,包括三个字符和四个位置。

3.2     占有字符和零宽度

正则表达式匹配过程中,如果子表达式匹配到的是字符内容,而非位置,并被保存到最终的匹配结果中,那么就认为这个子表达式是占有字符的;如果子表达式匹配的仅仅是位置,或者匹配的内容并不保存到最终的匹配结果中,那么就认为这个子表达式是零宽度的。

占有字符是互斥的,零宽度是非互斥的。也就是一个字符,同一时间只能由一个子表达式匹配,而一个位置,却可以同时由多个零宽度的子表达式匹配。

3.3     控制权和传动

正则的匹配过程,通常情况下都是由一个子表达式(可能为一个普通字符、元字符或元字符序列组成)取得控制权,从字符串的某一位置开始尝试匹配,一个子表达式开始尝试匹配的位置,是从前一子表达匹配成功的结束位置开始的。如正则表达式:

(子表达式一)(子表达式二)

假设(子表达式一)为零宽度表达式,由于它匹配开始和结束的位置是同一个,如位置0,那么(子表达式二)是从位置0开始尝试匹配的。

假设(子表达式一)为占有字符的表达式,由于它匹配开始和结束的位置不是同一个,如匹配成功开始于位置0,结束于位置2,那么(子表达式二)是从位置2开始尝试匹配的。

而对于整个表达式来说,通常是由字符串位置0开始尝试匹配的。如果在位置0开始的尝试,匹配到字符串某一位置时整个表达式匹配失败,那么引擎会使正则向前传动,整个表达式从位置1开始重新尝试匹配,依此类推,直到报告匹配成功或尝试到最后一个位置后报告匹配失败。

4       正则表达式简单匹本过程


4.1     基础匹配过程

源字符串:abc

正则表达式:abc

匹配过程:

首先由字符“a”取得控制权,从位置0开始匹配,由“a”来匹配“a”,匹配成功,控制权交给字符“b”;由于“a”已被“a”匹配,所以“b”从位置1开始尝试匹配,由“b”来匹配“b”,匹配成功,控制权交给“c”;由“c”来匹配“c”,匹配成功。

此时正则表达式匹配完成,报告匹配成功。匹配结果为“abc”,开始位置为0,结束位置为3。

4.2     含有匹配优先量词的匹配过程——匹配成功(一)


源字符串:abc

正则表达式:ab?c

量词“?”属于匹配优先量词,在可匹配可不匹配时,会先选择尝试匹配,只有这种选择会使整个表达式无法匹配成功时,才会尝试让出匹配到的内容。这里的量词“?”是用来修饰字符“b”的,所以“b?”是一个整体。

匹配过程:

首先由字符“a”取得控制权,从位置0开始匹配,由“a”来匹配“a”,匹配成功,控制权交给字符“b?”;由于“?”是匹配优先量词,所以会先尝试进行匹配,由“b?”来匹配“b”,匹配成功,控制权交给“c”,同时记录一个备选状态;由“c”来匹配“c”,匹配成功。记录的备选状态丢弃。

此时正则表达式匹配完成,报告匹配成功。匹配结果为“abc”,开始位置为0,结束位置为3。

4.3     含有匹配优先量词的匹配过程——匹配成功(二)

源字符串:ac

正则表达式:ab?c

匹配过程:

首先由字符“a”取得控制权,从位置0开始匹配,由“a”来匹配“a”,匹配成功,控制权交给字符“b?”;先尝试进行匹配,由“b?”来匹配“c”,同时记录一个备选状态,匹配失败,此时进行回溯,找到备选状态,“b?”忽略匹配,让出控制权,把控制权交给“c”;由“c”来匹配“c”,匹配成功。

此时正则表达式匹配完成,报告匹配成功。匹配结果为“ac”,开始位置为0,结束位置为2。其中“b?”不匹配任何内容。

4.4     含有匹配优先量词的匹配过程——匹配失败

源字符串:abd

正则表达式:ab?c

匹配过程:

首先由字符“a”取得控制权,从位置0开始匹配,由“a”来匹配“a”,匹配成功,控制权交给字符“b?”;先尝试进行匹配,由“b?”来匹配“b”,同时记录一个备选状态,匹配成功,控制权交给“c”;由“c”来匹配“d”,匹配失败,此时进行回溯,找到记录的备选状态,“b?”忽略匹配,即“b?”不匹配“b”,让出控制权,把控制权交给“c”;由“c”来匹配“b”,匹配失败。此时第一轮匹配尝试失败。

正则引擎使正则向前传动,由位置1开始尝试匹配,由“a”来匹配“b”,匹配失败,没有备选状态,第二轮匹配尝试失败。

继续向前传动,直到在位置3尝试匹配失败,匹配结束。此时报告整个表达式匹配失败。

4.5     含有忽略优先量词的匹配过程——匹配成功

源字符串:abc

正则表达式:ab??c

量词“??”属于忽略优先量词,在可匹配可不匹配时,会先选择不匹配,只有这种选择会使整个表达式无法匹配成功时,才会尝试进行匹配。这里的量词“??”是用来修饰字符“b”的,所以“b??”是一个整体。

匹配过程:

首先由字符“a”取得控制权,从位置0开始匹配,由“a”来匹配“a”,匹配成功,控制权交给字符“b??”;先尝试忽略匹配,即“b??”不进行匹配,同时记录一个备选状态,控制权交给“c”;由“c”来匹配“b”,匹配失败,此时进行回溯,找到记录的备选状态,“b??”尝试匹配,即“b??”来匹配“b”,匹配成功,把控制权交给“c”;由“c”来匹配“c”,匹配成功。

此时正则表达式匹配完成,报告匹配成功。匹配结果为“abc”,开始位置为0,结束位置为3。其中“b??”匹配字符“b”。

4.6     零宽度匹配过程

源字符串:a12

正则表达式:^(?=[a-z])[a-z0-9]+$

元字符“^”和“$”匹配的只是位置,顺序环视“(?=[a-z])”只进行匹配,并不占有字符,也不将匹配的内容保存到最终的匹配结果,所以都是零宽度的。

这个正则的意义就是匹配由字母和数字组成的,第一个字符是字母的字符串。

匹配过程:

首先由元字符“^”取得控制权,从位置0开始匹配,“^”匹配的就是开始位置“位置0”,匹配成功,控制权交给顺序环视“(?=[a-z])”;

(?=[a-z])”要求它所在位置右侧必须是字母才能匹配成功,零宽度的子表达式之间是不互斥的,即同一个位置可以同时由多个零宽度子表达式匹配,所以它也是从位置0尝试进行匹配,位置0的右侧是字符“a”,符合要求,匹配成功,控制权交给“[a-z0-9]+”;

因为“(?=[a-z])”只进行匹配,并不将匹配到的内容保存到最后结果,并且“(?=[a-z])”匹配成功的位置是位置0,所以“[a-z0-9]+”也是从位置0开始尝试匹配的,“[a-z0-9]+”首先尝试匹配“a”,匹配成功,继续尝试匹配,可以成功匹配接下来的“1”和“2”,此时已经匹配到位置3,位置3的右侧已没有字符,这时会把控制权交给“$”;

元字符“$”从位置3开始尝试匹配,它匹配的是结束位置,也就是“位置3”,匹配成功。

此时正则表达式匹配完成,报告匹配成功。匹配结果为“a12”,开始位置为0,结束位置为3。其中“^”匹配位置0,“(?=[a-z])”匹配位置0,“[a-z0-9]+”匹配字符串“a12”,“$”匹配位置3。

(0)

相关推荐

  • 正则基础之 NFA引擎匹配原理

    1       为什么要了解引擎匹配原理 一个个音符杂乱无章的组合在一起,弹奏出的或许就是噪音,同样的音符经过作曲家的手,就可以谱出非常动听的乐曲,一个演奏者同样可以照着乐谱奏出动听的乐曲,但他/她或许不知道该如何去改变音符的组合,使得乐曲更动听. 作为正则的使用者也一样,不懂正则引擎原理的情况下,同样可以写出满足需求的正则,但是不知道原理,却很难写出高效且没有隐患的正则.所以对于经常使用正则,或是有兴趣深入学习正则的人,还是有必要了解一下正则引擎的匹配原理的. 2       正则表达式引擎

  • 正则基础之 环视 Lookaround

    1       环视基础 环视只进行子表达式的匹配,不占有字符,匹配到的内容不保存到最终的匹配结果,是零宽度的.环视匹配的最终结果就是一个位置. 环视的作用相当于对所在位置加了一个附加条件,只有满足这个条件,环视子表达式才能匹配成功. 环视按照方向划分有顺序和逆序两种,按照是否匹配有肯定和否定两种,组合起来就有四种环视.顺序环视相当于在当前位置右侧附加一个条件,而逆序环视相当于在当前位置左侧附加一个条件. 表达式 说明 (?<=Expression) 逆序肯定环视,表示所在位置左侧能够匹配Exp

  • 正则匹配原理之 逆序环视深入 .

    说明:部分内容有待进一步研究和修正,因为最近工作太忙,暂时抽不出时间来,未研究过的可以跳过这一篇,想研究的不要被我的思路所左右了,有研究清楚的还请指正1 问题引出 前几天在CSDN论坛遇到这样一个问题: var str="8912341253789"; 需要将这个字符串中的重复的数字给去掉,也就是结果89123457. 首先需要说明的是,这种需求并不适合用正则来实现,至少,正则不是最好的实现方式. 这个问题本身不是本文讨论的重点,本文所要讨论的,主要是由这一问题的解决方案而引出的另一个

  • 正则表达式匹配解析过程探讨分析(正则表达式匹配原理)

    已经有多篇关于正则表达式介绍的文章,随着我们越来越多使用正则表达式,想对性能做优化.减少我们正则表达式书写匹配Bug.我们不得不进一步深入了解正则表达式执行过程了.下面我们一起学习,分析下正则表达式执行过程.我们会用regexbuddy测试工具分解执行过程,具体工具使用,可以看:正则表达式性能测试工具推荐.优化工具推荐(regexbuddy推荐).要了解正则表达式解析过程前,我们先来熟悉几个概念. 常见正则表达式引擎 引擎决定了正则表达式匹配方法及内部搜索过程,了解它至关重要的.目前主要流行引擎

  • 正则基础之 小数点

    一些细节 对于使用传统NFA引擎的大多数语言和工具,如Java..NET来说,"."的匹配范围是匹配除了换行符"\n"以外的任意一个字符. 但是对于javascript来说有些特殊,由于各浏览器的解析引擎不同,"."的匹配范围也有所不同,对于Trident内核的浏览器,如IE来说,"."同样是匹配除了换行符"\n"以外的任意一个字符,但是对于其它内核的浏览器,如Firefox.Opera.Chrome来说,

  • JavaScript模板引擎实现原理实例详解

    本文实例讲述了JavaScript模板引擎实现原理.分享给大家供大家参考,具体如下: 1.入门实例 首先我们来看一个简单模板: <script type="template" id="template"> <h2> <a href="{{href}}" rel="external nofollow" > {{title}} </a> </h2> <img src

  • URL @PathVariable 变量的匹配原理分析

    目录 URL @PathVariable 变量匹配原理 url 中带有变量的匹配原理 Demo 调试如下 总结 备注 @PathVariable @PathVariable 映射 URL 绑定的占位符 REST URL @PathVariable 变量匹配原理 url 中带有变量的匹配原理 在设置url的路径中我们可能使用变量来提高路径的灵活性,如 @RequestMapping(value="/{str}/qian",method=RequestMethod.GET) @Respon

  • 高性能JavaScript模板引擎实现原理详解

    随着 web 发展,前端应用变得越来越复杂,基于后端的 javascript(Node.js) 也开始崭露头角,此时 javascript 被寄予了更大的期望,与此同时 javascript MVC 思想也开始流行起来.javascript 模板引擎作为数据与界面分离工作中最重要一环,越来越受开发者关注,近一年来在开源社区中更是百花齐放,在 Twitter.淘宝网.新浪微博.腾讯QQ空间.腾讯微博等大型网站中均能看到它们的身影. 本文将用最简单的示例代码描述现有的 javascript 模板引擎

  • 了解CSS的查找匹配原理,让CSS更简洁、高效

    看1个简单的CSS: DIV#divBox p span.red{color:red;},按习惯我们对这个CSS 的理解是,浏览器先查找id为divBox的DIV元素,当找到后,再找其下的所有p元素,然后再查找所有span元素,当发现有span的class为red的时候,就应用该style.多么简单易懂的原理,可是这个理解却是完完全全相反.错误的. 匹配原理: 浏览器CSS匹配不是从左到右进行查找,而是从右到左进行查找.比如之前说的 DIV#divBox p span.red{color:red

  • Vue中的基础过渡动画及实现原理解析

    前言 在日常开发中 动画是必不可少的一部分 不仅能让元素直接的切换显得更加自然 同时也能极大的增强用户体验 因此 在Vue之中也提供了非常强大的关于动画这方面的支持 Vue不仅支持用CSS来写一些过渡效果 同时也是支持JS的 不过在这个文章中讲述的都是如何利用CSS来实现过渡动画.keyframes动画以及实现的原理 过渡动画实现的原理 1.首先最基础的一点在于 如果你想要在单元素/单个组件之中实现过渡动画 那么 你需要在元素/组件所在的HTML标签之外包裹一层  <transition>标签

随机推荐