《精通正则表达式》第3版

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

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

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

字符组

匹配若干字符之一 [ea] 匹配 a 或者 e

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

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

量词

元字符 次数下限 次数上限 含义
1 可选字符,前面字符出现0次或者1次
+ 1 前面字符出现一次或者多次
* 前面字符出现任意多次,或者不出现

正则表达式可以使用多个括号,使用 \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 对象。