# regex

<p align="center">
    <img src="../../../assets/img/banner/regex.jpg" width="58%">
</p>

---

**在线工具**
- **正则测试**
    - http://tool.chinaz.com/regex/
    - https://tool.oschina.net/regex

- **正则分析**
    - https://regexper.com/
    - https://ihateregex.io/
    - https://www.sojson.com/regex/generate
    - https://regex101.com/
    - https://regexr.com/
    - https://jex.im/regulex/#!flags=

**表达式资源**
- [cdoco/common-regex](https://github.com/cdoco/common-regex)

---

# 常用正则表达式

手机号
```re
^[\+]?[(]?[0-9]{3}[)]?[-\s\.]?[0-9]{3}[-\s\.]?[0-9]{4,6}$
```

Ipv4
```re
(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)(\.(25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)){3}
```

Ipv6
```re
(([0-9a-fA-F]{1,4}:){7,7}[0-9a-fA-F]{1,4}|([0-9a-fA-F]{1,4}:){1,7}:|([0-9a-fA-F]{1,4}:){1,6}:[0-9a-fA-F]{1,4}|([0-9a-fA-F]{1,4}:){1,5}(:[0-9a-fA-F]{1,4}){1,2}|([0-9a-fA-F]{1,4}:){1,4}(:[0-9a-fA-F]{1,4}){1,3}|([0-9a-fA-F]{1,4}:){1,3}(:[0-9a-fA-F]{1,4}){1,4}|([0-9a-fA-F]{1,4}:){1,2}(:[0-9a-fA-F]{1,4}){1,5}|[0-9a-fA-F]{1,4}:((:[0-9a-fA-F]{1,4}){1,6})|:((:[0-9a-fA-F]{1,4}){1,7}|:)|fe80:(:[0-9a-fA-F]{0,4}){0,4}%[0-9a-zA-Z]{1,}|::(ffff(:0{1,4}){0,1}:){0,1}((25[0-5]|(2[0-4]|1{0,1}[0-9]){0,1}[0-9])\.){3,3}(25[0-5]|(2[0-4]|1{0,1}[0-9]){0,1}[0-9])|([0-9a-fA-F]{1,4}:){1,4}:((25[0-5]|(2[0-4]|1{0,1}[0-9]){0,1}[0-9])\.){3,3}(25[0-5]|(2[0-4]|1{0,1}[0-9]){0,1}[0-9]))
```

email
```re
[^@ \t\r\n]+@[^@ \t\r\n]+\.[^@ \t\r\n]+
```

---

# 正则表达式引擎

正则表达式引擎分成两类：一类称为 DFA（确定性有限状态自动机），另一类称为 NFA（非确定性有限状态自动机）。

两类引擎要顺利工作，都必须有一个正则式和一个文本串，一个捏在手里，一个吃下去。

**举个例子**

现在有个文本为： perlmanbook ，一个正则表达式为 `/perl|perlman/` ，而这个正则表达式在两种引擎下的匹配结果我们可以看下。

首先是 DFA 引擎的情况下，它是以文本为导向，针对正则从左开始进行扫描，当扫描到 `/p/` 的时候，发现匹配的上了，然后继续往下匹配，当将第一个子正则 `/perl/` 全部匹配上之后，这时候就会把这个正则甩开，去吃第二个子正则式的 `/p/` 。这一吃好了，因为又匹配上了，于是接着往下吃。直到把正则式吃完，心满意足往上报告说成功匹配了 *‘perlman’ *。

若是 NFA，它是以正则为导向，比如第一个子正则表达式为 `/perl/` ，而该引擎针对 perlmanbook 字符串进行扫描，从左开始，当进度进行到 perl manbook 的时候，最开始部分的 perl 已经和第一个子正则表达式匹配而上，而当引擎进度扫描到 m 字符的时候，发现与第一个子正则表达式不匹配，于是把 m 吐出来，向上汇报说成功匹配 perl ，不再关心其他，也不尝试第二个子正则式 `/perlman/` 。

也就是说我们可以总结一下，NFA 引擎要翻来覆去吃字符、吐字符，速度慢，且可能会陷入递归险境导致性能极差。因此使用 NFA 引擎的正则表达式就可能出现 ReDOS 的问题。

## DFA

从起始状态开始，一个字符一个字符地读取输入串，并根据正则来一步步确定至下一个转移状态，直到匹配不上或走完整个输入

DFA 按文本串去比较正则式，看到一个子正则式，就把可能的匹配串全标注出来，然后再看正则式的下一个部分，根据新的匹配结果更新标注。
- DFA 对于文本串里的每一个字符只需扫描一次，比较快，但特性较少；
- DFA则是“最长的左子正则式优先匹配成功”。

---

## NFA

从起始状态开始，一个字符一个字符地读取输入串，并与正则表达式进行匹配，如果匹配不上，则进行回溯，尝试其他状态

NFA 是按着正则式去比文本，吃掉一个字符，就把它跟正则式比较，匹配就记下来：“某年某月某日在某处匹配上了！”，然后接着往下干。一旦不匹配，就把刚吃的这个字符吐出来，一个个的吐，直到回到上一次匹配的地方。

由于 NFA 的执行过程存在回溯，所以其性能会劣于 DFA，但它支持更多功能。大多数程序语言都使用了 NFA 作为正则引擎，其中也包括 PHP 使用的 PCRE 库。

- NFA 应用广泛，当今主要的正则表达式引擎，如 Perl、Ruby、Python 的 re 模块、Java 和. NET 的 regex 库，都是 NFA 的。
- 只有 NFA 才支持 lazy 和 backreference 等特性；
- NFA 追求速度，所以最左子正则式优先匹配成功，因此偶尔会错过最佳匹配结果；
- NFA 缺省采用 greedy 量词
- NFA 可能会陷入递归调用的陷阱而表现得性能极差。

---

**Source & Reference**
- [正则表达式](https://zh.wikipedia.org/wiki/%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F)
- [ReDOS初探](http://th1e.com/article/26)