正则表达式之进阶篇

概述

本文主要通过介绍正则表达式中的一些进阶内容,让读者了解正则表达式在日常使用中用到的比较少但是又比较重要的一部分内容,从而让大家对正则表达式有一个更加深刻的认识。

本文的主要内容为:

  • 正则表达式回溯法原理
  • 正则表达式操作符优先级

本文不介绍相关正则表达式的基本用法,如果对正则表达式的基本使用方法还不了解的同学,可以阅读我的上一篇博客——正则表达式语法入门

回溯法原理

回溯是影响正则表达式效率的一个非常重要的原因,我们在进行正则表达式匹配时,一定要尽可能的避免回溯。

很多人可能只是对听说过“回溯法”,并不了解其中具体内容和原理,接下来就先让我们看下什么是回溯法。

回溯法的定义

回溯法就是指正则表达式从头开始依次进行匹配,如果匹配到某个特定的情况下时,发现无法继续进行匹配,需要回退到之前匹配的结果,选择另一个分支继续进行匹配中的现象。这个描述可能有点抽象,我们举一个简单的例子,让大家能够更加明确的理解回溯法:

const reg = /ab{1,3}c/;

const str = 'abbc';

// 第1步:匹配/a/,得到'a'
// 第2步:匹配/ab{1}/,得到'ab'
// 第3步:匹配/ab{2}/,得到'abb'
// 第4步:匹配/ab{3}/,匹配失败,需要进行回溯
// 第5步:回溯到/ab{2}/,继续匹配/ab{2}c/,得到'abbc'
// 第6步:正则表达式匹配完成,得到'abbc'

如果我们把正则表达式的各个分支都整理成一棵树的话,正则表达式的匹配其实就是一个深度优先搜索算法。而回溯其实就是在进行深度优先匹配失败后的后退正常操作逻辑。

如果退回到了根节点仍然无法匹配的话,就会将index向后移动一位,重新构建匹配数。即/bc/'abc'时,由于第一个字符'a'无法匹配,则移动到'b'开始匹配。

回溯法产生场景

理解了回溯法和回溯操作,接下来我们来看下什么场景下会出现回溯。出现回溯的场景主要有以下几种:

  1. 贪婪量词(贪婪匹配)
  2. 惰性量词(非贪婪匹配)
  3. 分支结构(分支匹配)

接下来,让我们一个一个来看下这些场景是如何出现回溯的。

贪婪量词(贪婪匹配)

const reg = /ab{1,3}c/;

const str = 'abbc';

// 第1步:匹配/a/,得到'a'
// 第2步:匹配/ab{1}/,得到'ab'
// 第3步:匹配/ab{2}/,得到'abb'
// 第4步:匹配/ab{3}/,匹配失败,需要进行回溯
// 第5步:回溯到/ab{2}/,继续匹配/ab{2}c/,得到'abbc'
// 第6步:正则表达式匹配完成,得到'abbc'

最开始的例子其实就是一个贪婪匹配的示例,通过尽可能多的匹配b从而导致了回溯。

惰性量词(非贪婪匹配)

const reg = /ab{1,3}?c/;

const str = 'abbc';

// 第1步:匹配/a/,得到'a'
// 第2步:匹配/ab{1}/,得到'ab'
// 第3步:匹配/ab{1}c/,匹配失败,需要进行回溯
// 第4步:回溯到/ab{1}/,继续匹配/ab{2}/,得到'abb'
// 第5步:匹配/ab{2}c/,得到'abbc'
// 第6步:正则表达式匹配完成,得到'abbc'

与贪婪匹配类似,非贪婪匹配虽然每次都是去最小匹配数目,但是也会出现回溯的情况。

分支结构(分支匹配)

const reg = /(ab|abc)d/;

const str = 'abcd';

// 第1步:匹配/ab/,得到'ab'
// 第2步:匹配/abd/,匹配失败,需要进行回溯
// 第3步:回溯到//,继续匹配/abc/,得到'abc'
// 第4步:匹配/abcd/,得到'abcd'
// 第5步:正则表达式匹配完成,得到'abcd'

通过上面的示例我们可以看到,分支结构在出现两个分支情况类似的时候,也会出现回溯的情况,在这种情况下,如果一个分支无法匹配,则会回到这个分支的最初情况来重新进行匹配。

正则表达式操作符优先级

看完了回溯法,下面我们来了解下关于正则表达式操作符的优先级。

我们直接看结论,然后再根据结论来给大家提供示例进行理解。

操作符描述

操作符

优先级

转移符

\

1

小括号和中括号

(…)、(?:…)、(?=…)、(?!…)、…

2

量词限定符

{m}、{m,n}、{m,}、?、*、+

3

位置和序列

^、$、\元字符、一般字符

4

管道符

|

5

通过操作符的优先级,我们能够知道如何来读一个正则表达式。以下面这个正则表达式为例,我们来介绍一下按照优先级进行分析的方法:

const reg = /ab?(c|de*)+|fg/;

// 第一步,根据优先级先考虑(c|de*)+,再根据优先级拆分得到c de*,即匹配c或者de*(注意,位置和序列的优先级高于管道符|,所以是c或de*而不是c或d和e*)
// 第二步,得到ab?,根据优先级拆分得到a和b?
// 第三步,得到fg,这个内容和第一步+第二步的结果为或的关系

最终,我们得到的效果如下:

image (1).png

通过这个图,大家就能够理解我们的分析思路:先找括号,括号中的一定为一个整体(转移符只做转义,不分割正则,因此可以认为第一优先级其实是括号),没有括号后再从左到右按照优先级进行分析。量词限定符则看做是正则的一个整体。

注:如果大家需要话类似的正则表达式流程图,可以使用此网站

根据上面的优先级,我们就能够避免在正则表达式的理解中出现归类错误的情况。

总结

本文通过介绍在正则表达式中容易被忽略的两个内容:回溯法操作优先级,让大家能够在进行正则的阅读和书写过程中避免踩到相关的坑。

参考内容

  1. 《JavaScript正则表达式迷你书》——老姚 V1.1
  2. 《JavaScript权威指南》

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏怀英的自我修炼

Java漫谈9

上次聊String的时候聊到了String为什么可以在不new的情况下创建,说实话,这个问题我也没有答案,直到看到了这篇帖子,才敢说知道了为什么。 《Java ...

3679
来自专栏信安之路

php 弱类型问题

php 是一门简单而强大的语言,提供了很多 Web 适用的语言特性,其中就包括了变量弱类型,在弱类型机制下,你能够给一个变量赋任意类型的值。

1590
来自专栏C/C++基础

认识初始化

初始化是编码过程中的重要操作,往往由于被忽略,导致使用未初始化的变量(或内存区域),将程序置于不确定的状态,产生各种bug,严重影响的程序的健壮性。正确地理解和...

731
来自专栏小詹同学

Leetcode打卡 | No.21 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

1151
来自专栏小樱的经验随笔

【Java学习笔记之三十三】详解Java中try,catch,finally的用法及分析

这一篇我们将会介绍java中try,catch,finally的用法 以下先给出try,catch用法: try {   //需要被检测的异常代码 } ca...

3999
来自专栏Java编程

Java泛型详解

Java泛型(generics)是JDK 5中引入的一个新特性,允许在定义类和接口的时候使用类型参数(type parameter)。声明的类型参数在使用时用具...

7620
来自专栏日常分享

Java 多态方法构造器执行方法

可见,当我们试图构造一个B时,应该会优先构造B的父类A,所以会调用父类A的构造函数A(),所以会输出

1235
来自专栏Modeng的专栏

Javascript数组系列五之增删改和强大的 splice()

今天是我们介绍数组系列文章的第五篇,也是我们数组系列的最后一篇文章,只是数据系列的结束,所以大家不用担心,我们会持续的更新干货文章。

1382
来自专栏小樱的经验随笔

彻底搞定C语言指针(精华版)

1.语言中变量的实质 要理解C指针,我认为一定要理解C中“变量”的存储实质, 所以我就从“变量”这个东西开始讲起吧! 先来理解理解内存空间吧!请看下图: ...

4093
来自专栏猿人谷

Java初学者需掌握的30个概念

基本概念:       1.OOP中唯一关心的是对象的接口是什么,就像计算机的销售商她不管电源内部结构 是怎样的,他只关系能否给你提供电就行了,也就是只要知道c...

17510

扫码关注云+社区

领取腾讯云代金券