觅迹寻踪之正则表达式
灵魂拷问
“应该是没有”
“在多个文本中，找到 【我最帅】”
这篇是原理篇，可能有点晦涩。
背景
把 正则表达式 理解为一门编程语言，那它可能会有 解析引擎 和 执行引擎。
希望通过介绍正则表达式的执行引擎，了解其实现原理，能帮助大家写出更优雅的正则表达式。
执行引擎
DFA (Deterministic finite automaton)确定型有穷自动机NFA (Non-deterministic finite automaton)非确定型有穷自动机
1. NFA 中可以再进行细分，分为 POSIX NFA 和 Traditional NFA
2. 还有些程序支持 DFA 和 NFA 混合体
DFA 执行引擎
DFA 的特点：1.先看文本，再看正则，以文本主导
2.编译完表达式后，还需要遍历出表达式中所有的可能
3.匹配过程，字符串只看一次
NFA 执行引擎
NFA ，指的都是 Traditional NFANFA 的特点：1.先看正则，再看文本，以正则主导
2.编译完表达式即完成
敲重点
如何区分
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 使用率飙升常见场景
贪婪模式
过程
关键点
2.回溯。当正则需要匹配下一个文本内容时候，发现不匹配，文本只能回退一步。
惰性模式
过程
关键点
分组模式
过程
关键点
实（踩）战（坑）例子
检验 商店名字 地址是否合法
背景
1.英文字母大小写 2.数字 3. 越南文 4.一些特殊字符，如
&，-，_ 等使用以下正则作示例：
^([A-Za-z0-9._()&'\- ]|[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])+$调试
我们使用正则验证工具(regex101)进行调试
this is goodthis is good，this is good， 竟然要多达 17599 步才完成匹配，^([符合要求的组成1]|[符合要求的组成2])+$^([A-Za-z0-9._()&'\- ]|[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])++$使用独占模式，需要注意两点：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 地址是否合法，规则如下：
使用以下正则作示例：
^([hH][tT]{2}[pP]:\/\/|[hH][tT]{2}[pP][sS]:\/\/)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\\\/])+$调试
http://www.fapiao.com/index.html2.文本：
catastrophic backgracking （灾难性回溯），抽丝剥茧
重新梳理一下正则表达：
^([hH][tT]{2}[pP]://|[hH][tT]{2}[pP][sS]://)(([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 步 完成
但问题来了，如果用户在文本中加上 , 呢？
_% 的情况^([hH][tT]{2}[pP]:\/\/|[hH][tT]{2}[pP][sS]:\/\/)(([A-Za-z0-9-~]+).)++([A-Za-z0-9-~\\\/])+$再尝试：
课代表
从上面案例可知，避免回溯地狱
1.在满足需求情况下，尝试使用独占模式 -> 案例 1，2 可知
2.移除重复的字母（不要在多选择分支中，出现重复的元素） -> 案例 1 可知
参考资料
如何理解正则的匹配原理以及优化原则？
把握开发利器 — 正则表达式
正则表达式引擎执行原理——从未如此清晰！- SegmentFault 思否
正则表达式里的底层原理是什么
一个由正则表达式引发的血案