正则表达式学习 | 闪耀旅途

在计算机科学中, 正则表达式是指一个用来描述或者匹配一系列符合某个句法规则的字符串的单个字符串. 在很多文本编辑器或其他工具里, 正则表达式通常被用来检索或替换那些符合某个模式的文本内容. 许多程序设计语言都支持利用正则表达式进行字符串操作.

本文就对正则表达式的原理与使用进行汇总, 读者可以将本文作为学习资料或查询手册使用

• 由于正则流派众多, 除明确指出某种流派的使用方式时, 本文中的其他任何正则均指 PCRE 流派
• 把必须匹配的情况考虑周全并写出一个匹配结果符合预期的正则表达式很容易, 但把不需要匹配的情况也考虑周全并确保它们都将被排除在匹配结果以外往往要困难得多.

正则表达式发展简史

关于正则表达式, 最初的想法来自 20 世纪 40 年代的两位神经学家, Warren McCulloch 和 Walter Pitts, 研究出了一种用数学方式来描述神经网络的方法.

1956 年, 数学家 Stephen Kleene 发表了一篇标题为 神经网络事件表示法和有穷自动机 的论文. 这篇论文描述了一种叫做 正则集合 (Regular Sets) 的符号.

20 世纪 50 年代和 60 年代, 理论数学界对正则表达式进行了充分的研究. Robert Constable 的文章为那些对数学感兴趣的读者提供了很不错的简介.

关于在计算方面使用正则表达式的资料, 最早发表的是 1968 年 Ken Thompson 的文章 Regular Expression Search Algorithm, 在文中, 他描述了一种正则表达式编译器, 该编译器生成了 IBM 7094 的 object 代码. 由此也诞生了他的 qed, 这种编辑器后来成了 Unix 中 ed 编辑器的基础.

g/Regular Expression/pgrep

由于正则功能强大, 非常实用, 越来越多的语言和工具都开始支持正则. 不过遗憾的是, 由于没有尽早确立标准, 导致各种语言和工具中的正则虽然功能大致类似, 但仍然有不少细微差别.

诞生于 1986 年的 POSIX 开始进行标准化的尝试. POSIX 作为一系列规范, 定义了 Unix 操作系统应当支持的功能, 其中也包括正则表达式的规范. 因此, Unix 系统或类 Unix 系统上的大部分工具, 如 grep, sed, awk 等, 均遵循该标准. 我们把这些遵循 POSIX 正则表达式规范的正则表达式, 称为 POSIX 流派 的正则表达式. POSIX 把各种常见的流派分为两大类: Basic Regular Expressions(BREs) 和 Extended Regular Expressions(EREs). POSIX 程序必须支持其中的任意一种

在 1987 年 12 月, Larry Wall 发布了 Perl 语言第一版, 因其功能强大一票走红, 所引入的正则表达式功能大放异彩. 之后 Perl 语言中的正则表达式不断改进, 影响越来越大.

Perl Compatible Regular Expressions)

之后, 正则表达式在各种计算机语言或各种应用领域得到了更为广泛的应用和发展.

正则表达式元字符

＊.txtfile globswildcards＊.txt＊.txt.txt

正则表达式与文件名模式 (filename pattern) 的区别就在于, 正则表达式的元字符提供了更强大的描述能力. 文件名模式只为有限的需求提供了有限的元字符, 但是正则表达式”语言”为高级应用提供了丰富而且描述力极强的元字符.

Shell 中的元字符会在传递给程序之前进行展开, 因此如果传递到程序的选项中含有 Shell 元字符, 那么需要使用引用的方式让其避免被提前展开

完整的正则表达式由两种字符构成:

*

根据类型不同, 我将元字符进行以下分类:

字符及字符组

[xyz][char]coo[kl]cookcool[^xyz][^ char]123[^45]1234123512361237[a-z][][0-9]123.\n\rab.abcbadabcdabde\d[0-9]b\dbb2bbcb\D[^0-9]b\Dbbcbb2b\w[A-Za-z0-9_]\w1a&\W[^A-Za-z0-9_]\W1a\n\x0a\cJ\n\r\x0d\cM\s[ \f\n\r\t\v]x\sxx xxx\S[^ \f\n\r\t\v]x\S\xxkxxx\t\x09\cl\v\x0b\cK\f\x0c\cL\a\e\metachara\.ba.b,ajb\xnn\x41A\x{nnnn}\x{0041}A\o{nn}\o53+\nnn\033ESC\cC

[0-9A-Z_!.?]

不妨把字符组看作独立的微型语言. 在字符组内部和外部, 关于元字符的规定 (哪些是元字符, 以及它们的意义) 是不同的.

字符组通常表示肯定断言 (positive assertion). 也就是说, 它们必须匹配一个字符. 排除型字符组仍然需要匹配一个字符, 只是它没有在字符组中列出而已. 把排除型字符组理解为”匹配未列出字符的字符组”更容易一些

量词

每个量词都规定了匹配成功至少需要的次数下限, 以及尝试匹配的次数上限.

?10{0,1}colou?rcolorcolourcolouur??10?+10+1{1,}sa-6+sa-6sa-666sa-+?1++1*0{0,}co*lclcolcoolcoool*?0*+0{n}nn0[0-9]{3}[0-9][0-9][0-9]{n}?nn0{n}+nn0{n,}n[0-9]{2,}{n,}?n{n,}+n{n,m}nmn<=m[0-9]{2,5}{n,m}?nmn<=m{n,m}+nmn<=m

• 贪婪式匹配(匹配优先): 尽可能多地匹配内容
• 懒惰式匹配(忽略优先): 尽可能少地匹配
• 占有式匹配: 与贪婪式匹配相似, 尽可能多的内容, 但是不进行回溯; 也就是说, 它不会放弃已匹配的内容, 很自私

零长度断言

^^tuxtux$tux$tux\A\Atuxtux\z\Ztux\Ztux\G\<\>\b\bcool\bcoolcoolant\Bcool\BcoolantcoolX(?=Y)six(?=\d)sixsix6X(?!Y)hi(?!\d)hihigh(?<=Y)X(?<=\d)thth9th(?

分组与捕获

(pattern)ma(tri|tt)?maxmaxtrixmatt\1(?:pattern)x|yab(c|d)abcabd\1[ ]+(\w+)[ ]+\1

模式

(?i)((?i)cat) \1(?s)(?s).+(?#)(\w+)(?#word) \1(?#word repeat again)(?m)^$(?m)^the|cat$

Modifier

\l\L\E\u\U\E\Q\E\E\L\U

POSIX 字符类

[:...:]

[:alnum:][a-zA-Z0-9][[:alnum:]]+[:alpha:][a-zA-Z][[:alpha:]]{4}[:blank:][\t ][[:blank:]]*[:digit:][0-9][[:digit:]]?[:lower:][a-z][[:lower:]]{5,}[:upper:][A-Z]([[:upper:]]+)?[:punct:][:alnum:][:cntrl:][[:punct:]][:space:][\f\n\r\t\v ][[:space:]]+[:print:][[:print:]][:graph:][:print:][[:graph:]][:xdigit:][a-fA-F0-9][[:xdigit:]]+[:cntrl:][[:cntrl:]][:ascii:][[:cntrl:]][:word:][[:cntrl:]]

BREsEREsPCRE

#[[:xdigit:]][[:xdigit:]][[:xdigit:]][[:xdigit:]][[:xdigit:]][[:xdigit:]]#336633#FFFFFF[:xdigit:]:xdigit:[][]

Unicode Property Escape

Unicode 为我们提供了一些属性转义用于正则匹配, 这些属性转义我们可以认为也是元字符, 常用的有三种, 分别是:

• Unicode Property: 按功能分类, 每个字符只属于一个分类
• Unicode Blocks: 按码值区间分类, 各区间不相交(PCRE 不支持)
• Unicode Scripts: 按照书写系统来划分, 如汉语

Unicode Property

语言支持: Java, PHP, Golang, Ruby, Objective-C, JavaScript(ES8),.NET 等

\p{L}\p{Letter}\p{Ll}\p{Lowercase_Letter}\p{Lu}\p{Uppercase_Letter}\p{Lt}\p{Titlecase_Letter}\p{L&}\P{Ll}\p{Lu}\p{Lt}\p{Lm}\p{Modifier_Letter}\p{Lo}\p{Other_Letter}\p{M}\p{Mark}\p{Mn}\p{Non_Spacing_Mark}\p{c}\p{Spacing_Combining_Mark}\p{Me}\p{Encolsing_Mark}\p{Z}\p{Zs}\p{Space_Separator}\p{Zl}\p{Line_Separator}\p{Zp}\p{Paragraph_Separator}\p{S}\p{Math_Symbol}\p{Sm}\p{Math_Symbol}\p{Sc}\p{Math_Symbol}\p{Sk}\p{Math_Symbol}\p{So}\p{Math_Symbol}\p{N}\p{Nd}\p{Decimal_Digit_Number}\p{Nl}\p{Letter_Number}\p{No}\p{Other_Number}\p{P}\p{Punctuation}\p{Pd}\p{Dash_Punctuation}\p{Ps}\p{Open_Punctuation}\p{Pe}\p{Close_Punctuation}\p{Pi}\p{Initial_Punctuation}\p{Pf}\p{Final_Punctuation}\p{Pc}\p{Connector_Punctuation}\p{Po}\p{Other_Punctuation}\p{C}\p{Other}\p{Cc}\p{Control}\p{Cf}\p{Format}\p{Co}\p{Private_Use}\p{Cn}\p{Unassigned}

Unicode Blocks

语言支持: Java, Golang,.NET 等

\p{Arrows}\p{Bopomofo}

Unicode Script

语言支持: PHP, Ruby 等

\p{Common}\p{Arabic}\p{Armenian}\p{Bengali}\p{Bopomofo}\p{Braille}\p{Buhid}\p{Canadian_Aboriginal}\p{Cherokee}\p{Cyrillic}\p{Devanagari}\p{Ethiopic}\p{Georgian}\p{Greek}\p{Gujarati}\p{Gurmukhi}\p{Han}\p{Hangul}\p{Hanunoo}\p{Hebrew}\p{Hiragana}\p{Inherited}\p{Kannada}\p{Katakana}\p{Khmer}\p{Lao}\p{Latin}\p{Limbu}\p{Malayalam}\p{Mongolian}\p{Myanmar}\p{Ogham}\p{Oriya}\p{Runic}\p{Sinhala}\p{Syriac}\p{Tagalog}\p{Tagbanwa}\p{TaiLe}\p{Tamil}\p{Telugu}\p{Thaana}\p{Thai}\p{Tibetan}\p{Yi}

\PP

元字符流派对比

根据 前面 的描述 POSIX 流派 与 PCRE 流派 是目前正则表达式流派中的两大最主要的流派. 具体如下:

POSIX Basic Regular ExpressionsBREsgrepvi/vimsedcsplitdbxdbxtoolmoreedexprlexpgnlrdistPOSIX Extended Regular ExpressionsEREsgrep -Esed -EawknawkbashzshPerl Compatible Regular ExpressionsPCRE

以下列出各流派之间的元字符对比(如果意义和用法都相同的则省略)

?\??\?\=*?\{-}+\++\++?{-1,}{n,m}\{i,j\}{n,m}\{n,m}{n,m}?\{i,j\}?{n,m}?{-n,m}()\(\)()\(\)\1\1\1\1|\||\|\A^\z\Z\G\b\b\b\B\B\B\<\<\<\>\>\>\w\w\w\w\W\W\W\W\s\s\s\s\S\S\S\S\d\d\D\D\E\Q\n\n\r\r\t\t\v\v\f\fX(?=Y)X\(Y\)\@=X(?!Y)X\(Y\)\@!(?<=Y)X\(Y\)\@<=X(?

\|||

正则的转义

对于一个给定的字母表, 一个转义字符的目的是开始一个字符序列, 使得转义字符开头的该字符序列具有不同于该字符序列单独出现时的语义. 转义字符开头的字符序列被叫做 转义序列.

转义序列通常有两种应用场景:

\n

\

从字符串到正则表达式过程的转义

从输入的字符串到正则表达式, 其实有两步转换过程, 分别是 字符串转义 和 正则转义.

例如: 在正则中正确表示反斜杠时, 具体的过程是这样子:

\\\\\\\

元字符转义

*+?

[]{}()

\*\+\?\\d\\w

\d\d\d\d\\d

字符组中的转义

字符组里只有三种情况需要转义

[\^ab][a\-c][a\]b]

正则引擎

正则之所以能够处理复杂文本, 就是因为采用了有穷状态自动机 (finite automaton).

有穷状态是指一个系统具有有限个状态, 不同的状态代表不同的意义.

自动机是指系统可以根据相应的条件, 在不同的状态下进行转移. 从一个初始状态, 根据对应的操作 (比如录入的字符集) 执行状态转移, 最终达到终止状态 (可能有一到多个终止状态).

有穷自动机的具体实现称为正则引擎, 主要有 DFA 和 NFA 两种, 其中 NFA 又分为传统的 NFA 和 POSIX NFA:

Deterministic finite automatonNon-deterministic finite automaton

NFA 与 DFA 匹配的过程

str: we_live_in_shenzhen
regex: in_(beijing|shenzhen|shanghai)

NFA 引擎匹配过程

NFA 引擎的工作方式是, 先看正则, 再看文本, 而且以正则为主导.

iinnin_

regex: in_(beijing|shenzhen|shanghai)
       ^
text: we_live_in_shenzhen
      ^

regex: in_(beijing|shenzhen|shanghai)
         ^
text: we_live_in_shenzhen
                ^

sbeijing

regex: in_(beijing|shenzhen|shanghai)
           ^
         淘汰此分支(beijing)
str: we_live_in_shenzhen
                ^

sshenzhenshenzhenshanghaishenzhenshanghai

we_live_in_shenzhenwe_live_in_shanghaishenzheneshanghaiashanghais

第二个分支匹配失败
regex: in_(beijing|shenzhen|shanghai)
                     ^
                  淘汰此分支(正则 e 匹配不上文本 a)
str: we_live_in_shanghai
                  ^
再次尝试第三个分支
regex: in_(beijing|shenzhen|shanghai)
                            ^
str: we_live_in_shanghai
                ^

也就是说, NFA 是以正则为主导, 反复测试字符串, 这样字符串中同一部分, 有可能被反复测试很多次.

DFA 引擎匹配过程

而 DFA 不是这样的, DFA 会先看文本, 再看正则表达式, 是以文本为主导的.

wewiinnn_

str: we_live_in_shenzhen
     ^
regex: in_(beijing|shenzhen|shanghai)
       ^

str: we_live_in_shenzhen
               ^
regex: in_(beijing|shenzhen|shanghai)
         ^

_sbeijingsshenzhenshanghai

str: we_live_in_shenzhen
                ^
regex: in_(beijing|shenzhen|shanghai)
           ^       ^        ^
          淘汰    符合     符合

shenzheneshenzhenshanghainzhen

str: we_live_in_shenzhen
                  ^
regex: in_(beijing|shenzhen|shanghai)
                     ^        ^
                    符合     淘汰

从这个示例你可以看到, DFA 和 NFA 两种引擎的工作方式完全不同.

• NFA 是以表达式为主导的, 先看正则表达式, 再看文本.
• 而 DFA 则是以文本为主导, 先看文本, 再看正则表达式.

一般来说, DFA 引擎会更快一些, 因为整个匹配过程中, 字符串只看一遍, 不会发生回溯, 相同的字符不会被测试两次. 也就是说 DFA 引擎执行的时间一般是线性的. DFA 引擎可以确保匹配到可能的最长字符串. 但由于 DFA 引擎只包含有限的状态, 所以它没有反向引用功能, 它也不支持捕获子组.

NFA 以表达式为主导, 它的引擎是使用 贪心匹配回溯算法实现. NFA 通过构造特定扩展, 支持子组和反向引用. 但由于 NFA 引擎会发生回溯, 即它会对字符串中的同一部分, 进行很多次对比. 因此, 在最坏情况下, 它的执行速度可能非常慢.

POSIX NFA 与 传统 NFA 区别

pos|posixposixposposixposix

POSIX NFA 的应用很少, 主要是 Unix/Linux 中的某些工具. POSIX NFA 引擎与传统的 NFA 引擎类似, 但不同之处在于, POSIX NFA 在找到可能的最长匹配之前会继续回溯, 也就是说它会尽可能找最长的, 如果分支一样长, 以最左边的为准 (The Longest-Leftmost). 因此, POSIX NFA 引擎的速度要慢于传统的 NFA 引擎.

我们日常面对的, 一般都是传统的 NFA, 所以通常都是 最左侧 的分支优先, 在书写正则的时候务必要注意这一点.

下面是 DFA, 传统 NFA 以及 POSIX NFA 引擎的特点总结:

正则引擎的回溯

回溯是 NFA 引擎才有的, 并且只有在正则中出现 量词 或 多选分支结构 时, 才可能会发生回溯.

a+abaab

a+aaba+a.*ab.*ab.*

The lab assistant was wearing a white overall.
                                             ^
The lab assistant was wearing a white overall.
                                            ^
The lab assistant was wearing a white overall.
                                           ^
The lab assistant was wearing a white overall.
                                          ^
中间过程省略, 一直回溯到 l, 发现 l 后面的 ab 可以匹配上, 停止回溯, 匹配成功

The lab assistant was wearing a white overall.
    ^

.*

"[^"]+"".+?"

正则匹配中文字符

4E00~9FFF\p{Han}\p{IsHan}

常用正则实例(PCRE)

[\x{4e00}-\x{9fa5}][^\x00-\xff]\w+([-+.]\w+)*@\w+([-.]\w+)*\.\w+([-.]\w+)*(\w+\.)*\w+@(\w+\.)+[A-Za-z]+[a-zA-Z0-9_.+-]+@[a-zA-Z0-9-]+\.[a-zA-Z0-9-.]+[a-zA-z]+://[^\s]*https?://[-\w.]+(:\d+)?(/([\w/_.]*)?)?https?://(\w*:\w*@)?[-\w.]+(:\d+)?(/([\w/_.]*(\?\S+)?)?)?[a-zA-Z0-9][-a-zA-Z0-9]{0,62}(\.[a-zA-Z0-9][-a-zA-Z0-9]{0,62})+\.?[a-zA-Z][a-zA-Z0-9_]{4,15}[a-zA-Z]\w{5,17}(?=.*\d)(?=.*[a-z])(?=.*[A-Z])[a-zA-Z0-9]{8,10}(?=.*\d)(?=.*[a-z])(?=.*[A-Z]).{8,10}\d{3}-\d{8}|\d{4}-\{7,8}\d{4}-\d{1,2}-\d{1,2}\d{4}-(1[0-2]|0?[1-9])-([12]\d|3[01]|0?[1-9])(\(\d{3,4}-)|\d{3.4}-)?\d{7,8}(13[0-9]|14[5|7]|15[0|1|2|3|4|5|6|7|8|9]|18[0|1|2|3|5|6|7|8|9])\d{8}1[3-9]\d{9}1(?:3\d|4[5-9]|5[0-35-9]|6[2567]|7[0-8]|8\d|9[1389])\d{8}[1-9][0-9]{4,9}(?]*>.*?|<.*? />([a-zA-Z]+-?)+[a-zA-Z0-9]+\\.[x|X][m|M][l|L]\d+\.\d+\.\d+\.\d+(((\d{1,2})|(1\d{2})|(2[0-4]\d)|(25[0-5]))\.){3}((\d{1,2})|(1\d{2})|(2[0-4]\d)|(25[0-5]))5[1-5]\d{14}[1-9]\d*-[1-9]\d*-?[1-9]\d*[1-9]\d*|0-[1-9]\d*|0\+?(\d+(\.\d+)?|\.\d+)-\d+(\.\d+)+-?([1-9]\d*\.\d*|0\.\d*[1-9]\d*|0?\.0+|0)[1-9]\d*\.\d*|0\.\d*[1-9]\d*|0?\.0+|0(-([1-9]\d*\.\d*|0\.\d*[1-9]\d*))|0?\.0+|0[-+]?\d+(?:\.\d+)?[ ]+(\w+)[ ]+\1"[^"]+"\$\d+(\.\d\d)?[0-9A-Fa-f]+

Ref

• 精通正则表达式 第三版 - Jeffrey E.F.Friedl