这是 《精通正则表达式》第 3 版 的读书笔记。

技术图书的主要使命是传播专业知识,专业知识分为框架性知识和具体知识。框架性知识需要通过系统的阅读和学习掌握,而大量的具体知识,则主要通过日常生活的积累以及随用随查的学习来填充。

完整的正则表达式由两种字符构成,特殊字符,元字符,另外一种就是普通文本字符。

完整的正则表达式由小的构建模块单元 building block unit 构成,每个单元都很简单,不过他们能够以无穷多种方式组合,所以可以提供无限的可能。

字符组

匹配若干字符之一,使用中括号 [ea] 匹配 a 或者 e

gr[ae]y 表示匹配 gray 或者 grey

元字符 名称 匹配对象
. 单个任意字符
[abc] 字符组 列出的字符
[^abc] 排除字符组 未列出的字符
^   行起始
$   行尾
\<   单词起始
\>   单词结束
| 竖线
() 小括号 限制竖线的作用范围

其他元字符

元字符 描述
\d [0-9]
\D [^0-9]
\s [ \t\n\x0b\r\f]
\S 非空格
\w 单词字符
\W 非单词字符

量词,定义了元素可以发生的频率

元字符 次数下限 次数上限 含义
* 0 字符出现任意多次,或者不出现 {0,}
0 1 字符出现 0 次或者 1 次 ,{0,1}
+ 1 >=1, {1,}
{X}     匹配 X 个字符
{X,Y}     匹配 >=X<=Y

正则表达式可以使用多个括号,使用 \1, \2, \3 等来匹配括号的内容

([a-z])([0-9])\1\2 其中的 \1 代表的就是 [a-z] 匹配的内容,而 \2 就代表 [0-9] 匹配的内容

匹配引号内的字符串

"[^"]*"

两端引号用来匹配字符串开头和结尾的引号,中间 [^"] 用来匹配除引号之外的任何字符,* 用来表示任意数量的非引号字符

匹配 URL

grep, 和 egrep 的历史

正则表达式的流派

正则表达式的处理方式

集成式

Perl 中的例子

if ($line =~ m/^Subject: (.*)/i) {
    $subject = $1
}

取邮件标题的正则,内建在程序内,隐藏了正则表达式的预处理,匹配,应用,返回结果,减轻了常见任务的难度。

程序式处理和面向对象式处理

由普通函数和方法来提供

Java 中处理正则,Sun 提供了 java.util.regex 包来在 Java 中更加方便的使用正则。

import java.util.regex.*;

Pattern r = Pattern.compile("^Subject: (.*)", Pattern.CASE_INSENSITIVE);
Matcher m = r.matcher(line);
if (m.find()) {
    subject = m.group(1);
}

Perl 隐藏了绝大部分细节, Java 则暴露了一些正则的细节,编译正则表达式到 Pattern 对象,将正则和匹配的文本联系到一起,得到 Matcher 对象,在应用正则之前,检查是否存在匹配,返回结果,如果存在匹配,则捕获括号内的子表达式文本。

Java 也提供了函数式处理的例子, Pattern 类提供了静态方法

if (! Pattern.matches("\\s*", line)) {
    // 如果 line 不是空行
}

函数包装一个隐式的正则表达式,返回一个 Boolean。

Sun 也会把正则表达式整合到 Java 的其他部分,比如 String 类中 matches 函数

if (! line.matches("\\s*")) {
    // line 不为空行
}

String 中的方法不适合在对时间要求很高的循环中使用。

Python 中的处理,Python 也使用面向对象的方法

import re

r = re.compile("^Subject: (.*)", re.IGNORECASE)
m = r.search(line)
if m:
    subject = m.group(1)

这个例子和 Java 中的非常类似。

正则匹配规则

优先选择最左端匹配结果

从左往右匹配,左侧的结果优先于右侧

标准量词优先匹配

标准量词 ?, *, +, {m,n} 都是优先匹配 greedy 的。例如 a? 中的 a[0-9]+ 中的 [0-9],在匹配成功之前,进行尝试的次数是有上限和下限的,规则 2 表明,尝试总是获得最长的匹配。

标准匹配量词的结果可能并非所有可能中最长的,但是它们总是尝试匹配尽可能多的字符,直到匹配上限为止。如果最终结果并非该表达式的所有可能中最长的,原因肯定是匹配字符过多导致匹配失败。

举例, \b\w+s\b 来匹配包含 s 的字符串,比如 regexes\w+ 完全能够匹配整个单词,但如果 \w+ 来匹配整个单词 s 就无法匹配,为了完成匹配, \w+ 必须匹配 regexes ,最后把 s\b 留出来。

NFA 称为“表达式主导”引擎,对应的 DFA 称为 “文本主导” 引擎。

NFA 引擎

NFA 引擎中,每一个子表达式都是独立的,子表达式之间不存在内在的联系,子表达式和正则表达式的控制结构(多选分支、括号以及匹配量词)的层次关系控制了整个匹配过程。NFA 引擎是正则表达式主导,编写正则的人有充分的机会来实现期望的结果

DFA 文本主导

DFA 在扫描字符串时,会记录“当前有效”的所有匹配。比如正则

to(nite|knight|night)

来匹配文本

after ... tonight ...

当文本扫描到 t^onight 时,记录可能的匹配 t^o(nite|knight|night)

接下来扫描每一个字符都会更新可能的匹配序列,比如扫描到 toni^ght ... 时,可能的匹配就是 to(ni^te|knight|ni^ght)。此时 knight 就已经无法匹配。当扫描到 g 时只有一个匹配,等完成 h 和 t 的扫描之后,引擎发线匹配完成,报告成功。

对比

一般情况下,文本主导的 DFA 引擎要快一些,NFA 正则表达式引擎,因为需要对同样的文本尝试不同的表达式匹配,可能会产生不同的分支浪费时间。

NFA 匹配的过程中,目标文本中的某个字符串可能会被正则表达式中不同部分重复检查。相反,DFA 引擎是确定性,目标文本中的每个字符只会检查一遍。

这两种技术,都有对应的正式名字:非确定型有穷自动机 NFA,和 确定型有穷自动机 DFA。

正则引擎的分类

粗略分为三类

  • DFA 符合或者不符合 POSIX 标准的都属于此类
  • 传统 NFA
  • POSIX NFA

部分程序及其所使用的正则引擎

引擎 程序
DFA 大多数版本的 awk, egrep, flex, lex, MySQL
传统型 NFA GNU Emacs, Java, 大多数版本的 grep, less, more, .NET ,Perl, PHP,Python, Ruby, 大多数版本的 sed, vi
POSIX NFA mawk, GUN Emacs 明确指定时使用
DFA/NFA 混合 GNU awk, GNU grep/egrep, Tcl

实用技巧

匹配 IP 地址

匹配 IPv4 的地址,用点号分开的四个数组,0-255

[01]?[d\d?|2[0-4][d|25[0-5]

这个表达式能够匹配 0 到 255 之间的数,然后重复 4 遍。这样这个表达式会异常复杂,通常情况下,更合适的做法是不依赖正则完成全部的工作,使用

^\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}\$

来匹配,然后将匹配的数字拿出来,使用其他程序来进行验证。

匹配堆成括号

匹配括号的内容,或许会想到 \bfoo\([^)])

为了匹配括号

`(.*)`    括号及括号内任何字符
`([^)]*)`  从一个开括号到最近的闭括号
`([^()]*)` 从一个开括号到最近的闭括号,但是不容许其中包含开括号

对于文本

var = foo(bar(this), 3.7) + 2 * (that - 1);

第一个正则会匹配 (bar(this), 3.7) + 2 * (that - 1) , 而第二个正则表达式只会匹配 (bar(this) , 而第三个表达式能够匹配 (this) ,但是如果想要匹配 foo 后面的括号,则无能为力,所以三个表达式都不合格。

Java 正则

通过 java.util.regex 使用正则非常简单,一个接口一个 exception

java.util.regex.Pattern
java.util.regex.Matcher
java.util.regex.MatchResult
java.util.regex.PatternSyntaxException

通过 Pattern 构造编译正则表达式,通过正则匹配构建 Matcher 对象。

优化 Java 正则表达式

Java 的正则对性能影响非常大,如果在程序中大量使用正则,一定要对正则进行一定优化。

  • 多次使用同一个正则,Pattern.compile() 预先编译正则表达式
  • 选择 (X|Y|Z) 会显著降低正则的匹配速度,优先考虑 ac(cd|ef) 而不是 (abcd|abef)
  • 如果不需要分组内文本,尽量使用非捕获分组

reference