摘录与 《精通正则表达式》

一、正则表达式入门

正则表达式（Regular Expression）是强大、便捷、高效的文本处理工具。正则表达式本身，加上如同一门袖珍编程语言的通用模式表示法（general pattern notation），赋予使用者描述和分析文本的能力。配合上特定工具提供的额外支持，正则表达式能够添加、删除、分离、叠加、插入和修整各种类型的文本和数据。

1.1 检索文本文件：Egrep

egrep -i  '^func' cache.go  // 匹配 func 开头的
egrep -i  '^$' cache.go | wc -l // 计算文件 空行数
egrep '\<ctx' cache.go // 含有 ctx 开头单词的行
egrep 'Get\>' cache.go //  Get结尾的单词

1.2 正则表达式术语汇总

Regular Expression Nomenclature

正则（regex）

你或许已经猜到了，“正则表达式”（regular expression）这个全名念起来有点麻烦，写出来就更麻烦。所以，我一般会采用“正则”（regex）的说法。这个单词念起来很流畅，而且说“如果你写一个正则”，“巧妙的正则”（budding regexers），甚至是“正则化”（regexification）。

匹配（matching）

一个正则表达式“匹配”一个字符串，其实是指这个正则表达式能在字符串中找到匹配文本。严格地说，正则表达式「a」不能匹配cat，但是能匹配cat中的a。几乎没人会混淆这两个概念，但澄清一下还是有必要的。

元字符（metacharacter）

一个字符是否元字符（或者是“元字符序列”（metasequence），这两个概念是相等的），取决于应用的具体情况。例如，只有在字符组外部并且是在未转义的情况下，「＊」才是一个元字符。“转义”（escaped）的意思是，通常情况下在这个字符之前有一个反斜线。「\＊」是对「＊」的转义，而「\\＊」则不是（第一个反斜线用来转义第二个反斜线），虽然在两个例子中，星号之前都有一个反斜线。

流派（flavor）

我已经说过，不同的工具使用不同的正则表达式完成不同的任务，每样工具支持的元字符和其他特性各有不同。我们再举单词分界符的例子。某些版本的 egrep 支持我们曾见过的\＜…\＞表示法。而另一些版本不支持单独的起始和结束边界，只提供了统一的「\b」元字符。还有些工具同时支持这两种表示法，另有许多工具哪种也不支持。

“我用“流派（flavor）”这个词来描述所有这些细微的实现规定。这就好像不同的人说不同的方言一样。从表面上看，“流派”指的是关于元字符的规定，但它的内容远远不止这些。

即使两个程序都支持「\＜…\＞」，它们可能对这两个元字符的意义有不同的理解，对单词的理解也不相同。在使用具体的工具软件时，这个问题尤其重要。

请不要混淆“流派（flavor）”和“工具（tool）”这两个概念。两个人可以说同样的方言，两个完全不同的程序也可能属于同样的流派。同样，两个名字相同的程序（解决的任务也相同）所属的流派可能有细微（有时可能并非细微）的差别。有许多程序都叫egrep，它们所属的流派也五花八门。

子表达式（subexpression）

“子表达式”指的是整个正则表达式中的一部分，通常是括号内的表达式，或者是由「|」分隔的多选分支。例如，在「^（Subject|Date）：·」中，「Subject|Date」通常被视为一个子表达式。其中的「Subject」和「Date」也算得上子表达式。而且，严格说起来，「S」、「u」、「b」、「j」这些字符，都算子表达式。

1-6 这样的字符序列并不能算「H[1-6]·＊」的子表达式，因为1-6所属的字符组是不可分割的“单元（unit）”。但是，「H」、「[1-6]」、「·＊」都是「H[1-6]·＊」的子表达式。

与多选分支不同的是，量词（星号、加号和问号）作用的对象是它们之前紧邻的子表达式。所以「mis+pell」中的+作用的是「s」，而不是「mis」或者「is」。当然，如果量词之前紧邻的是一个括号包围的子表达式，整个子表达式（无论多复杂）都被视为一个单元。

字符（character）

“字符”在计算机领域是一个有特殊意义的单词。一个字节所代表的单词取决于计算机如何解释。单个字节的值不会变化，但这个值所代表的字符却是由解释所用的编码来决定的。例如，值为64和53的字节，在ASCII编码中分别代表了字符“@”和“5”，但在EBCDIC编码中，则是完全不同的字符（一个是空格，一个是控制字符）。

1.3 元字符总结

此外，请务必理解以下几点：

• 各个 egrep 程序是有差别的。它们支持的元字符，以及这些元字符的确切含义，通常都有差别——请参考相应的文档（☞23）。
• 使用括号的3个理由是：限制多选结构（☞13）、分组（☞14）和捕获文本（☞21）。
• 字符组的特殊性在于，关于元字符的规定是完全独立于正则表达式语言“主体”的。
• 多选结构和字符组是截然不同的，它们的功能完全不同，只是在有限的情况下，它们的表现相同（☞13）。
• 排除型字符组同样是一种“肯定断言”（positive assertion）——即使它的名字里包含了“排除”两个字，它仍然需要匹配一个字符。只是因为列出的字符都会被排除，所以最终匹配的字符肯定不在列出的字符之内（☞12）。
• -i的参数很有用，它能进行忽略大小写的匹配（☞15）。
• 转义有3种情况：
  • 「\」加上元字符，表示匹配元字符所使用的普通字符（例如「\＊」匹配普通的星号）。
  • 「\」加上非元字符，组成一种由具体实现方式规定其意义的元字符序列（例如，「\＜」表示“单词的起始边界”）。”
  • 「\」加上任意其他字符，默认情况就是匹配此字符（也就是说，反斜线被忽略了）。请记住，对大多数版本的egrep来说，字符组内部的反斜线没有任何特殊意义，所以此时它并不是一个转义字符。
• 由星号和问号限定的对象在“匹配成功”时可能并没有匹配任何字符。即使什么字符都不能匹配到，它们仍然会报告“匹配成功”。

二、入门实例拓展

2.1 Perl

三、正则表达式的特性和流派概览

在某种特定的宿主语言或工具软件中使用正则表达式时，主要有3个问题值得注意：

• 支持的元字符，以及这些元字符的意义。这通常称为正则表达式的“流派（flavor）”。
• 正则表达式与语言或工具的“交互”（interface）方式。譬如如何进行正则表达式操作，容许进行哪些操作，以及这些操作的目标文本类型。
• 正则表达式引擎如何将表达式应用到文本。语言或工具的设计者实现正则表达式的方法，对正则表达式能够取得的结果有重要的影响。

脚本语言中的行锚点

若干工具软件中使用的单词分界符元字符

四、表达式的匹配原理

4.1 正则引擎的分类

正则引擎主要可以分为基本不同的两大类：一种是DFA（相当于之前说的电动机），另一种是NFA（相当于前面的汽油机）。

DFA 和NFA 都有很长的历史，不过，正如汽油机一样，NFA 的历史更长一些。使用NFA的工具包括.NET、PHP、Ruby、Perl、Python、GNU Emacs、ed、sec、vi、grep的多数版本，甚至还有某些版本的egrep和awk。而采用DFA的工具主要有egrep、awk、lex和flex。也有些系统采用了混合引擎，它们会根据任务的不同选择合适的引擎（甚至对同一表达式中的不同部分采用不同的引擎，以求得功能与速度之间的最佳平衡）。

4.2 NFA与DFA的比较

DFA与NFA：在预编译阶段（pre-use compile）的区别

在使用正则表达式搜索之前，两种引擎都会编译表达式，得到一套内化形式，适应各自的匹配算法。NFA的编译过程通常要快一些，需要的内存也更少一些。传统型NFA和POSIX NFA之间并没有实质的差别。

DFA与NFA：匹配速度的差别

对于“正常”情况下的简单文本匹配测试，两种引擎的速度差不多。一般来说，DFA 的速度与正则表达式无关，而NFA中两者直接相关。

传统的NFA在报告无法匹配以前，必须尝试正则表达式的所有变体。这就是为什么我要用整章（第6章）来论述提高NFA表达式匹配速度的技巧。我们将会看到，有时候一个NFA永远无法结束匹配。传统型NFA如果能找到一个匹配，肯定会停止匹配。

相反，POSIX NFA必须尝试正则表达式的所有变体，确保获得最长的匹配文本，所以如果匹配失败，它所花的时间与传统型NFA一样（有可能很长）。因此，对POSIX NFA来说，表达式的效率问题更为重要。

在某种意义上，我说得绝对了一点，因为优化措施通常能够减少获得匹配结果的时间。我们已经看到，优化引擎不会在字符串开头之外的任何地方尝试带「^」锚点的表达式，我们会在第6章看到更多的优化措施。

DFA不需要做太多的优化，因为它的匹配速度很快，不过最重要的是，DFA在预编译阶段所作的工作提供的优化效果，要好于大多数NFA引擎复杂的优化措施。

现代DFA引擎经常会尝试在匹配需要时再进行预编译，减少所需的时间和内存。因为应用的文本各异，通常情况下大部分的预编译都是白费工夫。因此，如果在匹配过程确实需要的情况下再进行编译，有时候能节省相当的时间和内存（技术术语就是“延迟求值（lazy evaluation）”）。这样，正则表达式、待匹配的文本和匹配速度之间就建立了某种联系。

DFA与NFA：匹配结果的差别

DFA（或者POSIX NFA）返回最左边的最长的匹配文本。传统型NFA可能返回同样的结果，当然也可能是别的文本。针对某一型具体的引擎，同样的正则表达式，同样的文本，总是得到同样的结果，在这个意义上来说，它不是“随机”的，但是其他NFA引擎可能返回不一样的结果。事实上，我见过的所有传统型NFA返回的结果都是一样的，但并没有任何标准来硬性规定。

DFA与NFA：能力的差异

NFA引擎能提供一些DFA不支持的功能，例如：

• 捕获由括号内的子表达式匹配的文本。相关的功能是反向引用和后匹配信息（after-match information），它们描述匹配的文本中每个括号内的子表达式所匹配文本的位置。
• 环视，以及其他复杂的零长度断言
• 非匹配优先的量词，以及有序的多选结构。DFA很容易就能支持选择最短的匹配文本（尽管因为某些原因，这个选项似乎从未向用户提供过），但是它无法实现我们讨论过的局部的忽略优先性和有序的多选结构。
• 占有优先量词（☞142）和固化分组（☞139）

DFA与NFA：实现难度的差异

尽管存在限制，但简单的DFA和NFA引擎都很容易理解和实现。对效率（包括时间和空间效率）和增强性能的追求，令实现越来越复杂。

用代码长度来衡量的话，支持NFA正则表达式的ed Version 7（1979年1月发布）只有不到350行的C代码（所以，整个grep只有区区478行代码）。Henry Spencer1986年免费提供的Version 8正则程序差不多有1 900行C代码，1992年Tom Lord的POSIX NFA package rx（被GNU sed和其他工具采用）长达9700行。

为了糅合DFA和NFA的优点，GNU egrep Version 2.4.2使用了两个功能完整的引擎（差不多8900行代码），Tcl的DFA/NFA混合引擎（请看上一页的补充内容）更是长达9500行。

某些实现很简单，但这并不是说它们支持的功能有限。我曾经想要用Pascal的正则表达式来处理某些文本。从毕业以后我就没用过Pascal了，但是写个简单的NFA引擎并不需要太多工夫。它并不追求花哨，也不追求速度，但是提供了相对全面的功能，非常实用。

未完待续….