Something about Regular Expressions

Posted on 2020-12-09 Edited on 2021-05-26 In Programming Views:

开始

当在使用正则表达式时，你的目的就是从字符串中提取出你想要的东西，而正则表达式就是描述你要提取对象的一种语言；这种语言是跨平台的，在.NET, Java, JS, Py, Ruby, PHP上都可以使用。

为了学习这种描述被提取对象的语言，需要一些基础知识。

以下教程主要使用Python标准库的re模块与.NET平台的RegularExpressions模块，并在最后会提供其他语言的范例。

字符串

字符串(String)是一串字符，类似由字符组成的数组，是编程语言中表示文本的数据类型。

以字符串 “Betty Botter bought some butter.” 为例1

字符串中有元素和位置(或锚点)(Anchor)，这个字符串包含字母，数字，空格，”B”就是一个元素；而位置是指两个字符之间的地方，如”Betty”的”B”和”e”之间的就是一个位置。

任一字符串总有一个开始和结束，即字符串第一个元素之前的位置和最后一个元素之后的位置。

字符

字符(character)，即字符(难以解释)，可以用不同的编码方式来表示；不了解编码的，可以看阮一峰的字符编码笔记：ASCII，Unicode 和 UTF-8。

字符可分为可显示的不显示的，不显示的又有很多种，例如控制字符，半角空格(就是空格)，全角空格(很烦，用这个的见一次打一次)，无中断空格(使单词在结尾不换行显示)，及其他等

常见不显示字符	含义	Unicode
\f	窗体换页符	\u000C
\n	换行符(LineFeed/LF)	\u000A
\r	回车符(Carriage Return/CR)	\u000D
\t	制表符(Tab)	\u0009
\v	垂直制表符	\u000B
“ ”	半角空格	\u0020
“　”	全角空格	\u3000
“ ”	无中断空格	\u00A0

多行与行终止符

对于字符串来说，如果内部具有换行符/回车符，它可能是一个多行的文本，而多行则需要定义行终止符。

一行的结束并开启新行需要用字符表明，因为在三类主流的操作系统中，完成这个操作的字符不尽相同，因此统称为行终止符(NL)。

操作系统(类)	行终止符	缩写
Windos	\r\n	CRLF
Unix/Linux	\n	LF
MacOS	\r	CR

1 入门

“入门” 是正则表达式的基础阶段，如果有一定的正则基础的可以跳过，没有接触过的可以认真阅读。

提前声明：本教程不会让你读完就变成高手，需要大量的练习与自我反思才能够提高使用它的能力。

模式、被匹配对象和结果

一个正则表达式（以下简称表达式/模式）（pattern）可以用来在一个字符串中获得一些结果，相当于查找，被查找对象即被匹配对象（通常为字符串），查找到的结果可以是一个或一组，正则表达式会将所有符合该模式的结果显示出来。

构造表达式的方法和创建数学表达式的方法一样。也就是用多种元字符与运算符可以将小的表达式结合在一起来创建更大的表达式。正则表达式的组件可以是单个的字符、字符集合、字符范围、字符间的选择或者所有这些组件的任意组合。

普通字符与元字符

一个模式由元字符(metacharacter)与普通字符构成，并且不必须包含其中一项；普通字符包括没有显式指定为元字符的所有可打印和不可打印字符，即其代表其本身含义的字符，而元字符可以用来代表或确定一些普通字符。

如果一个模式只含有普通字符，它只匹配与自身一致的字符，
如在 “Betty Botter bought some butter.” 中
模式 "butter" 匹配时，会得到结果'butter' (因为有1个’butter’)
而模式 "o" 会得到 ['o','o','o'] (因为有3个’o’)

而元字符由一些特殊的符号组成，在学习时并不需要完全熟记并背诵，只需记住常见的即可。所有单独出现的元字符仅代表一个字符。

基本元字符

*以下表格出现补集的字符集合的全集均为ASCII字符集

匹配元素的元字符	含义
.	匹配1个除行终止符(NL)外的字符(全集为所有字符)
[A-B]	字符范围，匹配自然意义上从A到B之间的所有字符(含A,B)，如[0-9]匹配1个从0到9中的任意数字字符
[ABC]	字符集合，匹配1个集合中的所有字符(不包括字符集合中的’-‘)，如[abc]匹配1个a或1个b或1个c
^ (位于[]中)	集合取反，匹配1个集合的补集中的字符如[^a]匹配1个a之外的字符
\|	逻辑或，匹配满足”\|“两侧任一子模式的字符，可嵌套使用
\d	匹配1个0-9之中的任意数字字符，等价于 [0-9]
\D	匹配1个非数字字符，等价于 [^0-9]
\w	匹配1个a-z,A-Z,0-9及下划线_中的字符，等价于 [a-zA-Z0-9_]
\W	匹配1个非\w匹配的字符符，等价于 [^a-zA-Z0-9\_]
\s	匹配1个空白字符，等价于[ \f\n\r\t\v]
\S	匹配1个非空白字符，等价于[^\f\n\r\t\v]
\	将下一个字符标记为：一个特殊字符(\n表示换行符) 或一个原义字符(\\表示\) 或一个向后引用(\1表示第一个分组) 或一个八进制转义符

如果要匹配一个被显式定义为元字符的字符，在其前面加上'\'即可将其转义为代表其本身的普通字符

例：

s = 'Betty bought butter.'

reg = re.compile(r'.')
reg.findall(s)
# ['B', 'e', 't', 't', 'y', ' ', 'b', 'o', 'u', 'g', 'h', 't', ' ', 'b', 'u', 't', 't', 'e', 'r', '.']

reg = re.compile(r'\.')
reg.findall(s)
# ['.']

reg = re.compile(r'[Bbt]')
reg.findall(s)
# ['B', 't', 't', 'b', 't', 'b', 't', 't']

reg = re.compile(r'[^Bbt]')
reg.findall(s)
# ['e', 'y', ' ', 'o', 'u', 'g', 'h', ' ', 'u', 'e', 'r', '.']

reg = re.compile(r'[^ \w]')
reg.findall(s)
# ['.']

reg = re.compile(r'[B....]')
reg.findall(s)
# ['Betty']

表示重复含义的元字符

在上节最后一个例子中，为了匹配B开头的五个字符的元素，将”.”重复的4遍，这是没有必要且不简洁的，因此还有一些元字符是为了修饰其之前的字符的，表达重复的含义

表示重复含义的元字符	含义
*	尽可能多的重复匹配前一个字符零次或多次 (>=0)
+	尽可能多的重复匹配前一个字符一次或多次 (>=1)
? (前一个字符非*或+时)	重复匹配前一个字符零次或一次 (==0 “&#124” ==1)
{n}	重复n次 (==n)
{n,}	重复n次或更多次 (>=n)
{n,m}	重复n到m次 (>=n && <=m)

当"?"修饰"*"或"+"时，会尽可能少的重复匹配，下节详讲。

例：

s = 'Betty Tom 12345678 123455'

reg = re.compile(r'\d*')
reg.findall(s)
# ['', '', '', '', '', '', '', '', '', '', '12345678', '', '123455', '']

reg = re.compile(r'\d+')
reg.findall(s)
# ['12345678', '123455']

reg = re.compile(r'5?')
reg.findall(s)
# ['', '', '', '', '', '', '', '', '', '', '', '', '', '', '5', '', '', '', '', '', '', '', '', '5', '5', '']

reg = re.compile(r'5{1,}')
reg.findall(s)
# ['5', '55']

reg = re.compile(r'5{1,}?')
reg.findall(s)
# ['5', '5', '5']

重复的贪婪与懒惰

当正则表达式中包含能接受重复的元字符时，在使整个表达式能得到匹配的前提下匹配尽可能多的字符，这是默认的，也叫贪婪匹配。如：
a\w*n在匹配"amazon"时，"amazon"与"azon"都符合这个模式，但贪婪情况下只会匹配到"amazon"。

但有时不需要贪婪匹配，需要得到含有尽可能少的符合模式的字符串，就需要使用懒惰匹配。所有的表示重复的元字符都可以被转化为懒惰匹配，需要在其后加上一个"?"。如：
a\w*?[mn]在匹配"amazon"时，会得到"am"与"azon"

逻辑或

"|"元字符表示前后的条件为或的关系，即匹配满足左右任一模式的字符串，也叫做分支条件(Branch Condition), 但分支条件与一般的高级语言一样，若满足左侧的模式，则不会去匹配右侧的模式。

例：

s = '13812345678 13912345678 14012345678'

reg = re.compile(r'138.{8}|139.{8}')
reg.findall(s)
# ['13812345678', '13912345678']

2 进阶

“进阶” 会提到常用的和不常用的非初级方法，但不都是必须掌握的。

提前声明：本教程不会让你读完就变成高手，需要大量的练习与自我反思才能够提高使用它的能力。

分组

在 表示重复含义的元字符 里提到了通过特殊的元字符修饰之前的元字符，可以重复单个字符，但不能重复多个字符，此时需要引入分组的概念。

分组也叫子表达式，是指使用半角括号"(",")"包围的表达式，这个表达式可作为一个整体被重复。

分组可以简单的分为捕获组和非捕获组。

捕获

在之前的例子中，匹配的结果包含模式中的所有字符，但如果想要在字符串"Betty bought butter"中获得"bought", 就需要理解捕获(Capture)的概念了。

当需要从一个模式中提取一部分内容而不是全部内容的时候，需要在模式中加入分组，即用括号包住一部分表达式，这样在匹配时，如果负荷模式，就将这一部分存入内存，并加入标签，之后可以使用它。

例：

s = "Betty bought butter"

reg = re.compile(r'Betty .+? butter')
reg.findall(s)
# ['Betty bought butter']

#加入分组
reg = re.compile(r'Betty (.+?) butter')
reg.findall(s)
# ['bought']

可以理解分组为匹配一个”条件A(条件B)条件C”的模式，然后将条件B匹配得到的结果存储在内存备用。

因为分组是默认捕获的，那么问题又来了，当我需要重复一个分组重复出现，但不需要这个分组的内容出现在结果中占用内存，如何处理？

非捕获组，顾名思义，就是匹配分组但不捕获分组，从而减少内存的消耗。而定义一个非捕获组的形式如下：

"(?:pattern)" 其中pattern表示一个子模式

例：

s = 'Betty bought butterBetty.butter.'

reg = re.compile(r'Betty(?:[ ]?)(.+?)(?:butter)')
reg.findall(s)
# ['bought', '.']

reg = re.compile(r'Betty([ ]?)(.+?)(butter)')
reg.findall(s)
# [(' ', 'bought ', 'butter'), ('', '.', 'butter')]
# 以上说明共匹配到两组结果，第一组由' '等三个组成，第二组由''等三个组成

组和引用

当了解了分组后，问题又来了，如果我想在表达式的后面某一部分使用前方匹配到的结果，怎么处理？比如"@Andy, Andy:Class1, Andrew:Class2, Albert:Class3"中需要把”@”后面的人名代表的班级找出来，但是”@”后可以是任意一人，这是就需要引用之前的结果。

当一个模式完成匹配后，会得到一个组(Group) (以Py为例),其中的每一个子项代表了一次捕获，以上一个例子，

s = 'Betty bought butterBetty.butter.'

reg = re.compile(r'Betty([ ]?)(.+?)(butter)')
s = 'Betty bought butterBetty.butter.'
a = reg.match(s)
print(a.groups())
print(a.group(0))
print(a.group(1))
print(a.group(2))
print(a.group(3))

#(' ', 'bought ', 'butter')
#Betty bought butter
# 
#bought 
#butter


reg = re.compile(r'Betty([ ]?)(.+?)(?:butter)')
s = 'Betty bought butterBetty.butter.'
a = reg.match(s)
print(a.groups())
print(a.group(0))
print(a.group(1))
print(a.group(2))

#(' ', 'bought ')
#Betty bought butter
# 
#bought

可看到组0代表整个表达式本身，也是一个元组，组1即第一个结果，以此类推。

这是结果中的体现，在表达式中，使用元字符"\X"其中X为一个数字，也是这个组的编号可以表示一个捕获的组(的内容)，实质上是一个字符串，如'Betty([ ]?)(.+?)(\1)'中’\1’代表的是’’或’ ‘，而不是这个表达式”([ ]?)”

需要注意的是，因为引用实质上是一个捕获后的字符串，所以非捕获组无法被引用。

以上是通过数字进行引用，分组还可以被命名，从而通过一个名字来引用

语言	分组记法	表达式中的引用记法	替换时的引用的记法
.NET	(<name>…)	\k<name>	${name}
PHP	(?P<name>…)	(?P=name)	PHP 5.2.2 以后可以使用\k<name> 或者\k’name’ PHP 5.2.4 之后可以使用\k{name}和\g{name}
Python	(?P<name>…)	(?P=name)	\g<name>
Ruby	(?<name>…)	\k<name>	\k<name>

例：

reg = re.compile(r'Betty(?P<a>[ ]?)(.+?)(?P=a)')
s = 'Betty bought butter.'
a = reg.match(s)
print(a.groups())
print(a.group(0))
print(a.group(1))
print(a.group(2))

NFA引擎基础知识

基本概念

正则表达式引擎可以理解为不同语言下正则表达式的内核，而目前主要使用的引擎是NFA引擎(Non-deterministic finite automaton, 非确定型有穷自动机)，还有使用DFA引擎的语言，暂不做讨论

大多数语言和工具使用的是传统型的NFA引擎，它有一些DFA不支持的特性：

捕获组、反向引用和$number引用方式；
环视(Lookaround，(?<=…)、(?<!…)、(?=…)、(?!…))，或者有的有文章叫做预搜索；
忽略优化量词（??、*?、+?、{m,n}?、{m,}?），或者有的文章叫做非贪婪模式；
占有优先量词（?+、*+、++、{m,n}+、{m,}+，目前仅Java和PCRE支持），固化分组(?>…)。

占有字符和零宽度

正则表达式匹配过程中，如果子表达式匹配到的是字符内容，而非位置，并被保存到最终的匹配结果中，那么就认为这个子表达式是占有字符的；如果子表达式匹配的仅仅是位置，或者匹配的内容并不保存到最终的匹配结果中，那么就认为这个子表达式是零宽度的。

占有字符是互斥的，零宽度是非互斥的。也就是一个字符，同一时间只能由一个子表达式匹配，而一个位置，却可以同时由多个零宽度的子表达式匹配。

控制权和传动

正则的匹配过程，通常情况下都是由一个子表达式（可能为一个普通字符、元字符或元字符序列组成）取得控制权，从字符串的某一位置开始尝试匹配，一个子表达式开始尝试匹配的位置，是从前一子表达匹配成功的结束位置开始的。如正则表达式：

"(Pattern1)(Pattern2)"

假设"(Pattern1)"为零宽度表达式，由于它匹配开始和结束的位置是同一个，如位置0，那么"(Pattern2)"是从位置0开始尝试匹配的。

假设"(Pattern1)"为占有字符的表达式，由于它匹配开始和结束的位置不是同一个，如匹配成功开始于位置0，结束于位置2，那么"(Pattern2)"是从位置2开始尝试匹配的。

而对于整个表达式来说，通常是由字符串位置0开始尝试匹配的。如果在位置0开始的尝试，匹配到字符串某一位置时整个表达式匹配失败，那么引擎会使表达式整体向前传动，整个表达式从位置1开始重新尝试匹配，依此类推，直到报告匹配成功或尝试到最后一个位置后报告匹配失败。

零宽断言/环视/预搜索

当一个字符被一个模式占有了，但还是需要匹配这个字符，就会产生问题。

因此，产生了匹配位置的元字符，这种东西也叫断言(Assert)/环视(Lookaround)/预搜索(Presearch)，具体的名字无关紧要，它本身是用来匹配字符串内的一个位置的，具体格式如下：

表达式	说明
(?=Pattern)	顺序肯定环视，匹配某位置右侧能够匹配Pattern的位置
(?!Pattern)	顺序否定环视，匹配某位置右侧不能匹配Pattern的位置
(?<=Pattern)	逆序肯定环视，匹配某位置左侧能够匹配Pattern的位置
(?<!Pattern)	逆序否定环视，匹配某位置左侧不能匹配Pattern的位置

顺序环视

顺序环视都是匹配一个位置右侧满足/不满足条件的位置。

对于肯定环视(?=P1)来说，当子表达式P1匹配成功时，(?=P1)匹配成功，并报告(?=P1)匹配当前位置成功，控制权移交下一个元字符，并从当前位置开始匹配；否则报告失败，返回备选或整体移动。

对于否定环视(?!P1)来说，当子表达式P1匹配成功时，(?!P1)匹配失败，并报告失败，返回备选或整体移动；若P1匹配失败，(?!P1)匹配当前位置成功，控制权移交下一个元字符，并从当前位置开始匹配。

例：

s = '13712345678 13912345679'

#如果需要找一个137或138开头的十一位的手机号，用之前的元字符如何写？
reg = re.compile(r'((137|138)\d{8})')
s = '13712345678 13812345679 13911111111'
a = reg.findall(s)
print(a)
#[('13712345678', '137'), ('13812345679', '138')]
#虽然得到了想要的输出，但多了些别的东西

#使用环视后
reg = re.compile(r'(?=137|138)\d{11}')
a = reg.findall(s)
print(a)
#['13712345679', '13812345679']

reg = re.compile(r'(?!137|138)\d{11}')
a = reg.findall(s)
print(a)
#['13912345679']

逆序环视

逆序环视都是匹配一个位置左侧满足/不满足条件的位置。

逆序环视的成功失败过程与顺序类似，但：

顺序环视相当于在当前位置右侧附加一个条件，所以它的匹配尝试是从当前位置开始的，然后向右尝试匹配，直到成功或失败。而逆序环视的特殊处在于，它相当于在当前位置左侧附加一个条件，所以它不是在当前位置开始尝试匹配的，而是从当前位置左侧某一位置开始，匹配到当前位置为止，报告匹配成功或失败。

顺序环视尝试匹配的起点是确定的，就是当前位置，而匹配的终点是不确定的。逆序环视匹配的起点是不确定的，是当前位置左侧某一位置，而终点是确定的，就是当前位置。

所以顺序环视相对是简单的，而逆序环视相对是复杂的。这也就是为什么大多数语言和工具都提供了对顺序环视的支持，而只有少数语言提供了对逆序环视支持的原因。

JavaScript中只支持顺序环视，不支持逆序环视。
Java中虽然顺序环视和逆序环视都支持，但是逆序环视只支持长度确定的表达式，逆序环视中量词只支持“?”，不支持其它长度不定的量词。长度确定时，引擎可以向左查找固定长度的位置作为起点开始尝试匹配，而如果长度不确定时，就要从当前位置向左逐个位置开始尝试匹配，不成功则回溯，再向左侧位置进行尝试匹配，然后重复以上过程，直到匹配成功，或是尝试到位置0处以后，报告匹配失败，处理的复杂度是显而易见的。
目前只有.NET中支持不确定长度的逆序环视。

如果想要深入了解逆序环视，请直接阅读以下文章正则匹配原理之——逆序环视深入

其他锚字符

当需要匹配一个特殊的位置，比如字符串首与字符串末，单词边界等，有对应的元字符可以匹配，这些元字符也叫锚字符

其中，单词的定义是很关键的，但是基本情况下，正则表达式的单词即为'\w'定的字符集合；而'\w'定义的字符集合又是不确定的。在支持ASCII码的语言中，如JavaScript，'\w'等价于[a-zA-Z0-9_] ；在支持Unicode的语言中，如.NET，默认情况下，'\w'除可以匹配[a-zA-Z0-9_]外，还可以匹配一些Unicode字符集，如汉字，全角数字等等,但是Java是支持Unicode的，但Java的正则中的'\w'却是等价于[a-zA-Z0-9_]的，但Java的正则中的'\b'却是支持Unicode字符的。

那么'\b'匹配的位置就可以这样描述，匹配一个'\w与\W'、'^与\w'或'\w与$'之间的位置

例：

s = '13712345678 13812345679 13911111111'

reg = re.compile(r'\b138.+?\b')
a = reg.findall(s)
print(a)
#['13812345679']

reg = re.compile(r'\B.+?\b')
a = reg.findall(s)
print(a)
#['3712345678', '3812345679', '3911111111']

模式修饰符

这个小节的内容以Python的re模块为例，不是所有语言下的正则表达式均支持。

使用模式修饰符(modifier)对整个表达式进行设置，可以达到不同的效果

模式修饰符	英文	意义
I	IGNORECASE	对于英文字符忽略大小写的区别
L	LOCALE	字符集本地化，使\w\b\s及其反义取决与当前语言环境解决\w在法语中不能匹配”é”等字符类似问题
M	MULTILINE	改变”^”和”$“的含义，使其不再匹配字符串的首尾，匹配行的开始与结束 “^”匹配？？？的位置，”$“匹配？？？的位置
S	DOTALL	使”.”匹配任何字符，包括行终止符
X	VERBOSE	使正则表达式为多行，并且忽略表达式中的行终止符与注释，方便注释
U	UNICODE	用来正确处理大于 \uFFFF 的Unicode字符。也就是说，会正确处理四个字符的 UTF-16 编码。
G	GLOBAL	用来进行全局匹配，不限制下一次匹配开始的位置。
Y	STICKY	用来进行全局匹配，限制下一次匹配开始的位置为上一次匹配结束的位置。

模式修饰符可以被设定为全局的(整个表达式)，或部分的(只对某个子表达式起作用)，但在不同的语言有不同的表现形式。

其他元字符

元字符	意义
(?#comment)	注释，即这个分组内的文字不会被使用，当作零宽字符处理在多行模式下适合加入注释
$	单行模式中，匹配字符串的结束(最后一个位置) 多行模式中，匹配行终止符前的位置
\A	在单行与多行模式中，均匹配字符串的开始(第0个位置)
\Z \z	在单行与多行模式中，均匹配字符串的结束(最后一个位置)
\b \<	匹配一个单词边界位置 \b 在字符组中，表示一个退格键
\B \>	匹配一个非单词边界位置
(?=) (?!) (?<=) (?<!)	环视也是锚字符

优先级

平衡组

3 思维

4 在不同语言的具体应用

5 正则的底层运作过程

参考文献

http://www.zjmainstay.cn/my-regexp
http://www.zjmainstay.cn/deep-regexp
https://www.php.net/manual/zh/reference.pcre.pattern.modifiers.php
https://www.runoob.com/python/python-reg-expressions.html#flags
https://blog.csdn.net/lxcnn/article/details/4355364
https://blog.csdn.net/lxcnn/article/details/4304651
https://blog.csdn.net/zx48822821/article/details/80743997
https://blog.csdn.net/ww430430/article/details/78403536
https://blog.csdn.net/qq_20412595/article/details/82633501