陈颂光
全栈工程师,承接从编译器到网站的各类软件开发与咨询,也可以聊历史哲学。
关注我的 GitHub

正则表达式概览

一个正则表达式是一个描述了一个字符串集合的模式,在文本处理中是极为重要的工具。

语法

不同软件支持的“正则表达式”会略有不同,可能已经有上千种“正则表达式”。我们介绍正则表达式的应当是绝大多数正则表达式系统都支持的,具体情况请参考文档。

从最基本的正则表达式谈起

正则表达式的构造类似于算术表达式,使用各种各样的操作符来将更小的表达式连在一起。最基本的正则表达式如下构成:

  • 单个字符(除\、(、)、 、*等有特殊意义字符,这些字符用下面方法表示)。匹配恰由一个指定字符组成的字符串。
  • \后接单个有特殊意义字符。匹配恰由一个指定字符组成的字符串。
  • 若$A$为正则表达式,则$(A)$为正则表达式。匹配匹配$A$的字符串。
  • 若$A$为正则表达式,则$(A*)$为正则表达式。匹配的字符串$a_1\dots a_n(n\geq 0)$,其中每个$a_i$都匹配A
  • 若$A$和$B$为正则表达式,则$(AB)$为正则表达式。匹配字符串$ab$,其中$a$匹配$A$且$b$匹配$B$的字符串。
  • 若$A$和$B$为正则表达式,则$(A|B)$为正则表达式。匹配匹配$A$或匹配$B$的字符串。
这样构造虽然不会有歧义,但括号太多了。显然,$((AB)C)$与$(A(BC))$匹配同一字符串类,所以不妨把它简记为$(ABC)$。类似地,$((A|B)|C)$$匹配同一字符串类,所以不妨把它简记为$(A|B|C)$。再假定*、连接、 的优先级递减。这些规则可递归地应用,最后再可去掉暴露在最外面的括号对。这样,ab*匹配abbb但不匹配abab,匹配bc但不匹配ac

现在,假设我们想匹配五个英语的主要元音字符,我们可以用a|e|i|o|u,这不太方便,于是规定$[c_1\dots c_n]$为$c_1|\dots|c_n$的简写(语法糖),于是可写为[aeiou]。类似地,十六进制数字可写为[0123456789abcdefABCDEF],这也太累人了,于是把它写为[0-9a-fA-F],不过这要假定0到9在字符集中是相继出现等等(至少在unicode上成立)。由于一些字符类特别常用,人们常给它们特别记号。

另一个常见需求是指定一个模式的出现次数,例如假如要匹配七到八位的电话号可能要写[0-9][0-9][0-9][0-9][0-9][0-9][0-9]|[0-9][0-9][0-9][0-9][0-9][0-9][0-9][0-9],这种重复当然是不理想的,于是约定用{m,n}表示前面最小的完整子正则表达式重复m次到n次,这样上例化为[0-9]{7,8}。其中省略n表示不设上限,{1,}{0,1}也可记为+?。相应地需要转义的特殊意义字符以要加几个。

我们看到,这里提到的非基本扩展并没增大正则表达式能刻画的字符串类的集合,因为这些非基本的构造都可以宏展开的方式化为等价的最基本的正则表达式。在应用时非基本的构造是方便的,而且更不易出错。而在理论探讨时,则最基本的正则表达式更好处理。

正则表达式

构造 匹配的字符串类
单个没有特殊含义的字符 该字符自身
\具有特殊含义的字符 具有特殊含义的字符本身
[字符类表达式] 字符类表达式指定的其中一个字符,其中字符类表达式由一系列字符类组成,其中字符类除上两行外还可用范围表达式字符-字符,它匹配在给定字符集中这两个字符之间的任何一个字符。大多数元字符失去它们的特殊意义,若要字面的]^-,需要将它放在最前、最前之外的其他位置、最后。
^ 匹配一行的首部的空字符串
$ 匹配一行的尾部的空字符串
\b 匹配一个词边缘的空字串
\B 匹配不处于一个词的边缘的空字串。
XY 匹配X的后跟匹配Y的
X|Y 匹配X或匹配Y的,优先级低于连接
(X) 匹配X的,作为捕获组

一个正则表达式项后面可以接以下量词之一:

量词 意义
? 先前的项是可选的,最多匹配一次。
* 先前的项可以匹配零次或多次。
+ 先前的项可以匹配一次或多次。
{n} 先前的项将匹配恰好 n 次。
{n,} 先前的项可以匹配 n 或更多次。
{n,m} 先前的项将匹配至少n次至多m次。

通常正则表达式会尽可能多地匹配,在perl和java正则表达式中,在量词后再加?可以实现尽可能少地匹配,java正则表达式中量词后再加+可以实现尽可能多地匹配即使导致整体匹配失败。

扩展的正则表达式

字符类

Java正则表达式支持以下字符类:

Java字符类 意义
. 任何字符(与行结束符可能匹配也可能不匹配)
\d 数字:[0-9]
\D 非数字:[^0-9]
\s 空白字符:[ \t\n\x0B\f\r]
\S 非空白字符:[^\s]
\w 单词字符:[a-zA-Z_0-9]
\W 非单词字符:[^\w]
\p{javaLowerCase} 等效于 java.lang.Character.isLowerCase(),类似地LowerCase可换为其它Character类的is方法
\p{InGreek} Greek 块中的字符,同理其它Unicode块
\p{Lu} 大写字母,同理其它Unicode类别
\P{InGreek} Greek 块除外所有字符,同理可否定其它属性
POSIX字符类 Java字符类 意义  
[:lower:] \p{Lower} 小写字母字符:[a-z]  
[:upper:] \p{Upper} 大写字母字符:[A-Z]  
  \p{ASCII} 所有 ASCII:[\x00-\x7F]  
[:alpha:] \p{Alpha} 字母字符:[\p{Lower}\p{Upper}]  
[:digit:] \p{Digit} 十进制数字:[0-9]  
[:alnum:] \p{Alnum} 字母数字字符:[\p{Alpha}\p{Digit}]  
[:punct:] \p{Punct} 标点符号:!”#$%&’()*+,-./:;<=>?@[]^_`{ }~
[:graph:] \p{Graph} 可见字符:[\p{Alnum}\p{Punct}]  
[:print:] \p{Print} 可打印字符:[\p{Graph}\x20]  
[:blank:] \p{Blank} 空格或制表符:[ \t]  
[:cntrl:] \p{Cntrl} 控制字符:[\x00-\x1F\x7F]  
[:xdigit:] \p{XDigit}十六进制数字:[0-9a-fA-F]    
[:space:] \p{Space} 空白字符:[ \t\n\x0B\f\r]  

另外,java支持在字符类表达式中用并集和交集运算,如[a-z&&[^aeiou]]匹配非元音小写字母。

反向引用

很多正则表达式系统都可以用反向引用,用\n引用前面的第n个捕获组,即正则表达式的第n个没有被转义的左括号与对应的右括号包围的子正则表达式匹配的子字符串。捕获组的概念还常用于对匹配的文本进行替换或提取等操作。

正则表达式的性质

显然,每个正则表达式(不含反向引用的)决定的字符串类都可由某非确定型有限自动机识别(构造是直截了当的),这实际上指出了实现正则表达式匹配的一种方法:把正则表达式编译成有限自动机的一种表示,然后用字符串为输入模拟执行它。进一步,由于非确定型有限自动机都可化为确定型有限自动机,所以执行过程时间复杂度仅为$\Theta (n)$,额外空间复杂度为常数,其中$n$为待匹配的字符串长度,这当然已经不可能改进。至于编译过程,由于对每个正则表达式只用进行一次,可以接受。

假定确定型有限自动机有m个状态,如果给它长度大于m的输入则肯定有两个时刻机器处于相同状态,于是输入可分成三段A、B、C,其中B非空,而且这机器接受$ABC$当且仅当它接受$AB^nC$对任何$n\in \mathbb{N}$成立。回到正则表达式,我们看到,(1*)0\1不能化为基本的正则表达式,反向引用实质性地增多了正则表达式可刻画的字符串类。

举例

正则表达式 字符类
\d|\d\d|1\d\d|2[0-4]\d|25[0-5] 0到255的整数

很坦白说,正则表达式本身很简单,但应用之妙存乎一心,期望读者能举一反三。

应用

  • 分词。只要写出各种标记满足的正则表达式,lex或flex之类程序就可以自动为这语言生成分词程序,这在快速实现(小型)语言时配合yacc或bison之类很有用。
  • 验证输入的有效性。
  • 修正。常见编辑器的替换功能都支持正则表达式。
  • 定位。常见编辑器的搜索功能都支持正则表达式。

总结

正则表达式是描述字符串模式的一个方便的工具,应用广泛,但使用时宜注意以下事项:

  • 我们往往可轻易写出适用于常见情况的正则表达式,但要做到准确描述所需的字符串类仍是相当有挑战性的(或者根本不可能)。
  • 正则表达式的紧凑有时令它成为一种只写语言,易写难读。
  • 正则表达式通常嵌入其它语言中,因而被多次解析(如先shell再sed),因此可能要在书写时对正则表达式按外部语言的规则再转义