觅迹寻踪之正则表达式

2023 - 05 - 17

Posted by CDCer

背景

把 正则表达式 理解为一门编程语言,那它可能会有 解析引擎 和 执行引擎。

希望通过介绍正则表达式的执行引擎,了解其实现原理,能帮助大家写出更优雅的正则表达式。

执行引擎

正则表达式的执行引擎主要分为两个大类:

  1. DFA (Deterministic finite automaton) 确定型有穷自动机

  2. NFA (Non-deterministic finite automaton) 非确定型有穷自动机

其中:
1. NFA 中可以再进行细分,分为 POSIX NFA 和 Traditional NFA
2. 还有些程序支持 DFA 和 NFA 混合体

整理为表格如下:

     

> 章节原因,FA,DFA,NFA 之间的关系,留待下一次叙述

DFA 执行引擎

由上可以得出,DFA 的特点:

1.先看文本,再看正则,以文本主导

2.编译完表达式后,还需要遍历出表达式中所有的可能

3.匹配过程,字符串只看一次

NFA 执行引擎

> 文中的 NFA ,指的都是 Traditional NFA

由上可以得出,NFA 的特点:

1.先看正则,再看文本,以正则主导

2.编译完表达式即完成

3.匹配过程中,可能会发生回退,字符串同一部分会比较多次 (通常将回退称为回溯)

敲重点

图片

如何区分

如何区分 Traditional NFAPOSIX NFADFADFA/NFA

  • 第一步:

看是否支持 忽略优先量词。如果支持,基本就能确定是 Traditional NFA

正则表达式 nfa|nfa.not,文本 nfa.not

          如果只匹配到 nfa ,基本就能确定是 Traditional NFA

  • 第二步:

看是否支持 捕获型括号 或者 回溯。如果支持,基本能确定是 POSIX NFA

正则表达式 X(.+)+X,文本 XxX==============

如果出现灾难性回溯,基本能确定是 POSIX NFA

          但是可能存在 DFA 和 NFA 两种引擎的混合的工具

细品 NFA 回溯

上文提到,NFA 具有回溯的能力,该能力是一把双刃剑

因为回溯会增加匹配的步骤,步骤过量会导致 CPU 使用率飙升

正所谓

图片

因此了解回溯出现的场景十分有必要

常见场景

贪婪模式

  • 过程

图片

  • 关键点

1.贪婪,每次都尽可能多标绿匹配的内容。

图片

2.回溯。当正则需要匹配下一个文本内容时候,发现不匹配,文本只能回退一步。

图片

惰性模式

  • 过程

图片

  • 关键点

1.懒惰,每次尽可能少标绿匹配的内容。

图片

2.回溯。当正则需要匹配下一个文本内容时候,发现不匹配,文本只能回退一步。

图片

分组模式

  • 过程

图片

  • 关键点

1.分组,按照分支的顺序逐个匹配。

图片

2.回溯。当正则需要匹配下一个文本内容时候,发现不匹配,文本只能回退一步。

> 关于什么是贪婪模式,懒惰模式,独占模式,分组模式 不在这里展开详细叙述,留待下一次讲解

实(踩)战(坑)例子

检验 商店名字 地址是否合法

  • 背景

检验 商店名字 地址是否合法,规则:
1.英文字母大小写 2.数字 3. 越南文 4.一些特殊字符,如 &-_ 等使用以下正则作示例:

^([A-Za-z0-9._()&'\- ]|[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])+$

  • 调试

我们使用正则验证工具(regex101)进行调试

1.文本:this is good

图片

2.文本:this is good,

图片

发现输入 this is good, 竟然要多达 17599 步才完成匹配

图片

3.抽丝剥茧

上述的正则表达式看上去写得很复杂,实际可以简化一下:

^([符合要求的组成1]|[符合要求的组成2])+$

能发现正则表达式中有 + 出现,意味着有贪婪匹配,可能会有大量回溯

利用 regex101 工具中的调试功能,发现当到 30+ 步数,就开始进行回溯

图片

我们尝试将贪婪模式改成独占模式,即修改为:

^([A-Za-z0-9._()&'\- ]|[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])++$

再尝试:

图片

改为独占模式后,匹配步数锐减到 29 步

> 使用独占模式,需要注意两点:1. 是否满足业务需求;2. 使用的编程语言是否支持

  • 再优化

正则表达千万条,还有其他优化的方案

在原有 ^([A-Za-z0-9._()&'\- ]|[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])+$ 基础上优化

  • 移除重复的字母(不要在多选择分支中,出现重复的元素)

^([0-9._()&'\- ]|[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])+$

图片

  • 移除多选分支选择结构(直接用中括号表示多选一)

^([A-Za-z0-9._()&'\- aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])+$

图片

检验 URL 地址是否合法

  • 背景

检验 URL 地址是否合法,规则如下:

1.校验协议 2. 校验域名 3. 校验参数使用以下正则作示例:
^([hH][tT]{2}[pP]:\/\/|[hH][tT]{2}[pP][sS]:\/\/)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\\\/])+$

  • 调试

1.文本:

http://www.fapiao.com/index.html

图片

2.文本:

http://www.fapiao.com/dzfp-web/pdf/download?request=6e7JGm38jfjghVrv4ILd-kEn64HcUX4qL4a4qJ4-CHLmqVnenXC692m74H5oxkjgdsYazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf

图片

发现输入案例后出现 catastrophic backgracking (灾难性回溯)

图片

  • 抽丝剥茧

重新梳理一下正则表达:

1.校验协议:^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)

2.校验域名:(([A-Za-z0-9-~]+).)+

3.校验参数:([A-Za-z0-9-~\\/])+$

看出来,是因为用户传入的内容中存在_% ,那我们修改一下[校验参数]部分,把 _% 加上:

^([hH][tT]{2}[pP]:\/\/|[hH][tT]{2}[pP][sS]:\/\/)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~_%\\\/])+$

图片

从 catastrophic backgracking 变成 84 步 完成

但问题来了,如果用户在文本中加上 , 呢?

图片

图片

刚刚的修改仅仅是优化了参数中可能会出现 _% 的情况

要想彻底解决问题,可以尝试一下使用独占模式,那需要修改哪部分呢?

利用 regex101 工具中的调试功能,能发现当到 60+ 步数,就开始进行回溯

图片

我们可以尝试将[校验域名]修改为独占模式,即修改为:

^([hH][tT]{2}[pP]:\/\/|[hH][tT]{2}[pP][sS]:\/\/)(([A-Za-z0-9-~]+).)++([A-Za-z0-9-~\\\/])+$

再尝试:

图片

改为独占模式后,匹配步数也锐减到 58 步

课代表

从上面案例可知,避免回溯地狱

1.在满足需求情况下,尝试使用独占模式 -> 案例 1,2 可知

2.移除重复的字母(不要在多选择分支中,出现重复的元素) -> 案例 1 可知

3.移除多选分支选择结构(直接用中括号表示多选一)-> 案例 1 可知

本章节不过多介绍,优化内容,期待下次透析….

参考资料

如何理解正则的匹配原理以及优化原则?

把握开发利器 — 正则表达式

正则表达式引擎执行原理——从未如此清晰!- SegmentFault 思否

正则表达式里的底层原理是什么

一个由正则表达式引发的血案

Table of Contents