觅迹寻踪之正则表达式
2023 - 05 - 17
Posted by CDCer
背景
把 正则表达式 理解为一门编程语言，那它可能会有 解析引擎 和 执行引擎。
希望通过介绍正则表达式的执行引擎，了解其实现原理，能帮助大家写出更优雅的正则表达式。
执行引擎
正则表达式的执行引擎主要分为两个大类：
-
DFA (Deterministic finite automaton)确定型有穷自动机 -
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 NFA, POSIX NFA, DFA, DFA/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 思否
正则表达式里的底层原理是什么
一个由正则表达式引发的血案