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

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