Skip to content

Latest commit

 

History

History
95 lines (64 loc) · 4.86 KB

regex.md

File metadata and controls

95 lines (64 loc) · 4.86 KB
Raw

regex

在线工具

表达式资源

常用正则表达式

手机号

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

Ipv4

(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

(([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

[^@ \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