这是 《精通正则表达式》第 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) - 如果不需要分组内文本，尽量使用非捕获分组