稍微深入一些的正则表达式总结

稍微深入一些的正则表达式总结

[TOC]

本文是不满足网上那些所谓的十分钟速成正则表达式, 而通过阅读《精通正则表达式(第3版) (Jeffrey E. F. Friedl) 》得到的一些粗浅总结.

总结的背景

只要是有代码经历的, 可以说必然接触过正则表达式, 即便是不码代码的也至少接触过 Office 下的通配符来进行查找替换等操作. 估计很多人像我一样, 想要稍微掌握一下这个实用但入门门槛又不低的技术. 网上充斥着速成的教程, 基本上是把基础的语法列出来, 例如各个元字符的作用, 然后附加上几个常用的例子就结束了. 到了实际应用环境, 我们还是得检阅网上现成的例子, 然后陷入试错调试的循环中, 好不容易调出了自己想要的效果, 但也不知道什么原理, 性能如何, 如何指导/改进下一次的使用体验. 也就是迷迷糊糊地去使用. 对这种状态不爽已久的我, 花了一天半的时间学习了《精通正则表达式(第3版) (Jeffrey E. F. Friedl) 》的前 5 章. 本文是对学习后的总结. PS. 中文版翻译的很不错, 哪怕是英文与中文语法不同的问题, 都会在注释中写明, 点赞.

专门学习这本书的动机已经在上面进行了解释, 那为什么是这本书而不是其他书或者是其他方式?

  • 知名度以及书本书的质量. 这里就不展开书好在哪里了, 豆瓣评分 8.9 分.
  • 系统并且带有深度地学习一门技术, 还是书本教材更靠谱. 书籍作为编辑界千锤百炼的信息载体, 尤其还是更新多版的书, 是更凝练, 逻辑体系更完整, 组织更符合人认知习惯的. 视频教程虽然比书籍还要符合人对知识的接受习惯, 但视频的回放不如书籍那么方便, 遇到一时不明白的内容可以方便地反复看.
  • 触类旁通. 技术大牛们虽然聚焦在一个狭窄的领域内发表了一门技术的总结, 但这些总结来自于他们更广泛的阅历以及日常深刻的思考. 直白地说就是格局很高, 层次很深. 阅读他们的书, 能习得他们问题拆解方式, 相关联知识/领域的具体联系. 例如, 从这本书我入门了 Perl 这门语言, 明白了 Unicode 概念与文字处理的一些基础注意点, 文本处理技术发展的历史等. 这些是在利用技术解决实际问题中遇到的, 也就是说接下来我再遇到类似的额问题, 至少有了参考, 甚至是 best practice.

因为我认为这一天半的投资是值得的. 当然, 学完(也只是 5 章)并意味着掌握, 只能说理解了书中每一行每个字的意思以及背景, 距离灵活应用以及举一反三还需要实际中多应用多总结. 这篇文章也会持续更新的以后的感悟.

Update@20210705: 这本书是从用户的角度出发探索如何使用正则表达式, 如果探究其数学模型或者求解算法的话, 可以参考《编译原理》里的相关内容进行入门.

正则表达式的宏观一些的东西

本节的内容可以先跳过, 或者当成小说阅读即可.

正则表达式的目标

  1. 判断匹配与否: 例如 grep.
  2. 查找与替换: 例如 AWK 中的文本修改.

起源与发展

数学理论

最初的想法来自 20 世纪 40 年代的两位神经学家, Warren McCulloch 和 Walter Pitts, 他们研究出一种模型, 认为神经系统在神经元层面上就是这样工作的. 若干年后, 数学家 Stephen Kleene 在代数学中正式描述了这种被他称为”正则集合”(regular sets)的模型, 正则表达式才成为现实. Stephen 发明了一套简洁的表示正则集合的方法, 他称之为”正则表达式”(regular expressions).

计算机实现

最早发表的正则表达式”是 1968 年 Ken Thompson 的文章 Regular Expression Search Algorithm, 在文中, 他描述了一种正则表达式编译器, 该编译器生成了 IBM 7094 的 object 代码. 由此也诞生了他的 qed, 这种编辑器后来成了 Unix 中 ed 编辑器的基础. ed 的正则表达式并不如 qed 的先进, 但是这是正则表达式第一次在非技术领域大规模使用.

在 ed 的基础上出现了独立工具 grep, 以及拓展的 grep – egrep. 与此同时, awk,lex 和 sed, 也在按各自的脚步前进.

流派

多年的变化也造就了数目众多的正则表达式 流派(flavor). 不同流派虽然基于的思想都是一样的, 但在具体的实施细节以及算法上都有很多不同. 并且在一个流派的不同历史版本上, 也不尽相同. 因此网上很多的教程都是抛开流派来讲正则表达式, 虽然方便, 但着实有些误导人. 这也是我推荐用此书学习的原因.

POSIX 标准化的尝试

诞生于 1986 年的 POSIX 是 Portable Operating System Interface(可移植操作系统接口)的缩写, 它是一系列标准, 确保操作系统之间的移植性.

POSIX 把各种常见的流派分为两大类: Basic Regular Expressions(BREs)和 Extended Regular Expressions(EREs). POSIX 程序必须支持其中的任意一种.

各个语言上的正则表达式

Henry Spencer 的正则表达式包: 1986 年, Henry Spencer 发布了用 C 语言写的正则表达式包, 这个包可以毫无困难地置入其他程序中. 这在当时具有开创性的意义. 每一个使用 Henry 的包的程序的确存在很多都属于相同的流派, 除非程序的作者费尽周折去修改.

Perl 语言的发展: 1987 年 12 月, Larry Wall 发布了 Perl Version 1. Perl 的初衷是文本处理, 而 Web 页的生成其实正是文本处理, 所以 Perl 迅速成为了开发 Web 程序的语言. Perl 广受欢迎, 其中强大的正则流派也是如此. 其他语言的开发人员当然不会视而不见, 最终在某种程度上”兼容 Perl”(Perl compatible)的正则表达式包出现了. Tcl,Python,.NET,Ruby,PHP,C/C++ 都有各自的正则表达式包, Java 语言中还有多个正则表达式包.

本书在最开始使用了 egrep 流派, 后面涉及到较复杂的讲解时使用了 Perl, 最后面的几章分别讲解了 Perl, Java, .Net, PHP 下的具体使用.

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

  1. 支持的元字符, 以及这些元字符的意义. 在这些元字符中最容易被忽略的一些中有如下 2 条:
    • 点号能否匹配换行符?排除型字符组能否匹配换行符?以上两者能否匹配 NUL 字符?
    • 行锚点(line anchor)是名符其实的吗(例如, 他们能否识别目标字符串内部的换行符)?它们算正则表达式中的基础级别(first-class)的元字符吗?还是只能应用在某些结构中?
  2. 正则表达式与语言或工具的”交互”(interface)方式. 譬如如何进行正则表达式操作, 容许进行哪些操作, 以及这些操作的目标文本类型.
  3. 正则表达式引擎如何将表达式应用到文本. 语言或工具的设计者实现正则表达式的方法, 对正则表达式能够取得的结果有重要的影响.

正则表达式的作用符

本节会把书中涉及到的作用符, 整理到一起, 基本上都是 Perl 流派支持的. 不能保证其他流派都有或者是含义一致, 具体应用时需要查找宿主语言/工具的说明手册. 即便宿主语言/工具中不存在 Perl 中完全一致的用法, 但 Perl 的实现也非常具有参考意义.

另外, 这里只是草草地进行了整理, 至于每个字符的含义以及由来使用场景还是推荐读原书进行翻阅.

字符与元字符

字符(character): 是正则表达式需要处理的对象.

更深入一些: 在计算机中数据保存在字节中, 对字节如何解释只是视角(称为”编码”encoding)的问题, 我们要做的只是确保自己的视角和正在使用的工具的视角相同. 一直以来, 文本处理软件一般都把数据视为一些 ASCII 编码的字节, 而不考虑使用者期望采用的字符编码. 不过, 近来已经有越来越多的系统在内部使用某些格式的 Unicode 编码来处理数据. 这在把正则表达式应用到更复杂的文本处理时需要付出额外的注意.

人眼习惯于把空格和普通字符区分开来. 在阅读正则表达式时, 我们必须改变这种习惯, 因为空格符也是普通字符之一, 它与 j 或者 4 这样的字符没有任何差别.

元字符(Matacharacter): 这是用来表达正则表达式语法本身的字符, 分为很多类与用法, 对它们的不熟悉, 可能是正则表达式看起来像是天书一样的首个门槛.

元字符汇总

下面的汇总表, 很多不是常用的或者只在有限的流派中被支持, 常用的在第一列标记了星号.

常用 形式 小类 大类 作用/注意点
. - 匹配单个字符 流派中是否支持匹配换行.
[] - 字符组 在字符组里面和外面, 元字符的定义和意义是不一样的.
例如 [.] 表示匹配句号, 在 [] 外面则是匹配单个字符
[^...] 排除型字符组 字符组 ^必须在最前面.
排除型字符组表示”匹配一个未列出的字符(match a character that’s not listed)”,
而不是”不要匹配列出的字符(don’t match what is listed)”.
[0-9] 连续省略字符组 字符组 - 只有在两侧都没有字符时才表示连字符 [-0-9], 否则就是连续省略字符.
? 匹配优先量词 量词 可选项元素. 匹配 0 或者 1 个.
* 匹配优先量词 量词 匹配尽可能多的次数, 如果实在无法匹配, 也不要紧. 匹配 0 或者 多个.
+ 匹配优先量词 量词 匹配尽可能多的次数, 但如果连一次匹配都无法完成, 就报告失败. 匹配 1 或者 多个.
{min, max} 匹配优先量词区间量词 量词 指定匹配的次数.
?? *? +? {m, n}? 忽略优先量词 量词 在匹配优先量词后面加上 ? 解除匹配优先量词的优先性,
也就是说, 原本匹配优先级高的量词(greedy) 现在优先级没有其他的高了.
仅有一部分流派支持.
?+ *+ ++ {m, n}+ 占有优先量词 量词 占有优先量词与匹配优先量词很相似, 只是它们从来不交还已经匹配的字符.
这个概念在使用回溯算法的流派中被定义和使用.
^ 简单锚点 锚定符 匹配开头
$ 简单锚点 锚定符 匹配结尾
\b 简单锚点 锚定符 匹配一个单词分界符
但是在字符组中, 它匹配一个退格符.
\G 简单锚点 锚定符 上次的匹配点
(?=...) 复杂锚点-环视
肯定顺序环视
锚定符 子表达式能够匹配右侧文本
(?!...) 复杂锚点-环视
否定顺序环视
锚定符 子表达式不能够匹配右侧文本
(?<=...) 复杂锚点-环视
肯定逆序环视
锚定符 子表达式能够匹配左侧文本
(?<!...) 复杂锚点-环视
否定逆序环视
锚定符 子表达式不能够匹配左侧文本
(...) - 分组 括号内整体为一个子表达式
\1 \2 \3 反向引用 分组 分组 () 后可以使用反向引用来引用每个 () 里的内容.
括号是按照开括号‘(’从左至右的出现顺序进行的.
(?:...) 非捕获分组 分组 分组, 但是无法使用反向引用
(?>...) 固化分组 分组 如果匹配进行到此结构之后(也就是, 进行到闭括号之后),
那么此结构体中的所有备用状态都会被放弃.
用于回溯算法的流派.
` ` - 多选结构
\* \加上元字符 转义符 表示匹配元字符所使用的普通字符
\> \加上非元字符 转义符 组成一种由具体实现方式规定其意义的元字符序列
\加上任意其他字符 转义符 默认情况就是匹配此字符(也就是说, 反斜线被忽略了)
\< \>
\b
元字符序列
(转义符)
匹配单词分界的位置
\t 元字符序列 制表符
\n 元字符序列 换行符
\r 元字符序列 回车符
\s 元字符序列 任何空白符(例如空格符, 制表符, 进纸符等)
\S 元字符序列 \s 以外的任何字符
\w 元字符序列 [a-zA-Z0-9] 匹配一个单词(含数字)
\W 元字符序列 \w 以外的任何字符, [^a-zA-Z0-9]
\d 元字符序列 [0-9], 匹配数字
\D 元字符序列 \d 以外的任何字符, ^[0-9].
\123 元字符序列 八进制转义符, 注意如何与返回引用区分开.

作者的符号汇总:

一些注意点与使用举例

  1. 行末锚定问题.

很多流派(egrep)中行末的换行符 \n 会被删除, 不会进行匹配.

1
2
Where is Irap
a question

q[^u] 就不会去不匹配 Iraq\n, 原因是 \n 被删除了, 并且 [^u] 要求一定要有一个字符(非 u 的字符).

  1. 子表达式

|() 和其他元字符不太一样的地方是, 它们规定了正则表达式的子表达式, 是一种结构性的层次性的区分. 分隔开的内容整体是一个子表达式. 有些元字符只能作用于子表达式上, 例如, 量词.

  1. 忽略优先量词

量词默认是优先级很高的, 也就是贪心的 greedy, 只要匹配了会继续一致匹配下去直到无法匹配. 有时候我们希望关闭这种贪心性. 就会使用到忽略优先量词.

例如: 用<B>.*?</B>来匹配: …<B>Billions</B> and <B>Zillions</B> of suns…. 开始的<B> 匹配之后, .*? 首先决定不需要匹配任何字符, 因为它是忽略优先的. 于是, 控制权交给后面的 < 符号.

注意只有某些 NFA (具体后面展开)支持忽略优先的量词.

  1. 环视(lookaround)

除了开头以及结尾的 ^ $ 之外, 有时候我们希望查找别的地方, 这个时候就可以使用环视.

例子1. 要把所有格 Jeffs 替换为 Jeff’s

几种方法的对比:

环视的图解:

例子2. 单词分界符

在不支持单词分界符(\b, \<,\>)的流派, 可以用下面的方式实现:

(?<!\w)(?=\w)来表示单词起始分界符, 用 (?<=\w)(?!\w) 表示单词结束分界符. 把两者结合起来, (?<!\w)(?=\w) | (?<=\w)(?!\w) 就等价于\b.

  1. 反向引用的例子

检查文章拼写中是否有重复的单词(不区分大小写), 例如 the the 是语法错误. 注意下面右括号后面有一个空格.

1
egrep -i'\<([a-z]+) +\1\>'files…
  1. 非捕获分组

^([-+]?[0-9]+(?:\.[0-9]*)?)\s*([CF])$:第二个括号里的不会被捕捉为 $2. 非捕获分组的好处有 2 个: 1. 避免了不必要的捕获, 提高匹配效率. 2. 增加了易读性.

  1. 多选结构 | 与分组 ()的差别

可能会让人觉得多选结构与字符组没太大的区别, 但是请留神不要混淆这两个概念. 一个字符组只能匹配目标文本中的单个字符, 而每个多选结构自身都可能是完整的正则表达式, 都可以匹配任意长度的文本.

正则引擎的分类

依据是否使用回溯算法以及是否符合 POSIX 标准划分为如下三种:

  1. DFA(Deterministic Finite Automata)(符合或不符合POSIX标准的都属此类): 文本主导, 不使用回溯算法, 因此其对其不同的正则表达式, 执行的效率基本不变. 因为 DFA引擎在扫描字符串时, 会记录 当前有效(currently in the works)的所有匹配, 即通过 map 的形式保存下来. 因此当字符串被读到 DFA 中时, 所有的状态都已经被确认了, 也就是 Deterministic. 优点如下:
    • DFA匹配很迅速.
    • DFA匹配很一致.
  2. 传统型 NFA(Nondeterministic Finite Automata): 表达式主导, 依靠回溯算法, 即通过匹配前进, 保存分支->贪心推进到上限, 保存分支->不满足回溯, 从新的分支开始匹配前进, 以此循环往复. 也就是说 NFA 是摸着石头过河, 按照既定算法走下去, 因此是 Nondeterministic. 所以不同的正则表达式写法对最终的效率影响很大, 但是如果都是逻辑正确的写法, 不同的写法得到结果都是一致的. 优点如下:
    • 在表达式主导的匹配过程中, 每一个子表达式都是独立的. 在子表达式与正则表达式的控制结构(多选分支,括号以及匹配量词)的层级关系(layout)控制了整个匹配过程.
    • 因为NFA引擎是正则表达式主导的, 编写表达式的人有充足的机会来实现他/她期望的结果.
  3. POSIX NFA: 最大的特点是传统 NFA + 靠左最长匹配结果. 传统 NFA 的匹配结果是最左侧的匹配结果, POSIX 的标准是靠左侧最长的匹配结果, POSXI NFA 是对传统 NFA 的改进.

不同语言/工具使用的正则引擎如下:

不同引擎的共同点

1.优先选择最左端(最靠开头)的匹配结果

如果引擎不能在字符串开始的位置找到匹配的结果, 传动装置就会推动引擎, 从字符串的下一个位置开始尝试, 然后是下一个, 再下一个, 如此继续. 这个过程形成了正则表达式引擎内部的循环逻辑之一.

2.标准的匹配量词(,+,?{m, n})是匹配优先的

标准匹配量词都是”匹配优先(greedy)”的, 除非对它们限制为忽略优先量词.

为什么要限制匹配优先呢? 因为有时候会产生过度匹配的问题. 例如, 用^.*[0-9]+来匹配匹配 Copyright 2003.. $1 最终为 3, 而不是 2003.

这是因为”匹配优先组件首先会匹配尽可能多的字符, 但为了整个表达式的匹配, 它们通常需要”释放”一些字符(抑制自己的天性). 当然, 它们并不”愿意”这样做, 只是不得已而为之. 当然, “交还”绝不能破坏匹配成立必须的条件, 比如加号的第一次匹配. 当发现交出一个最末尾的 3 即可满足要求后匹配完成退出返回结果.

NFA 回溯算法

NFA 引擎最重要的性质是, 它会依次处理各个子表达式或组成元素, 遇到需要在两个可能成功的可能中进行选择的时候, 它会选择其一, 同时记住另一个, 以备稍后可能的需要.

回溯的两个要点就成为了:

  1. 面对众多选择时, 哪个分支应当首先选择?

如果需要在”进行尝试”和”跳过尝试”之间选择, 对于匹配优先量词, 引擎会优先选择”进行尝试”, 而对于忽略优先量词, 会选择”跳过尝试”.

  1. 回溯进行时, 应该选取哪个保存的状态?

距离当前最近储存的选项就是当本地失败强制回溯时返回的. 使用的原则是 LIFO(last in first out, 后进先出).

(?>...)实现固化分组

如果匹配进行到此结构之后(也就是, 进行到闭括号之后), 那么此结构体中的所有备用状态都会被放弃. 也就是说, 在固化分组匹配结束时, 它已经匹配的文本已经固化为一个单元, 只能作为整体而保留或放弃. 括号内的子表达式中未尝试过的备用状态都不复存在了, 所以回溯永远也不能选择其中的状态(至少是, 当此结构匹配完成时, “锁定(locked in)”在其中的状态).

常用的场景: 加快报告匹配失败的速度 如果不能找到匹配对象, 放弃备用状态可能能让正则引擎更快地报告匹配失败. 例如:

^\w+:无法匹配 Subject, 因为 Subject 中不含冒号, 但正则引擎必须经过尝试才能得到这个结论. 既然我们知道, \w+匹配结束之后, 从任何备用状态开始测试都不能得到全局匹配, 就可以命令正则引擎不必检查它们: ^(?>\w+).

占有优先量词

占有优先量词和固化分组关系非常紧密. 像\w++这样的占有优先量词与 ^(?>\w+)的匹配结果完全相同, 只是写起来更加方便而已.

正则模式和匹配模式

不区分大小写的匹配模式

egrep 的命令行参数 -i 表示进行忽略大小写的匹配.

Perl 的 /i 修饰符表示此测试不区分大小写. 其他的修饰符, 例如 /g(表示”全局匹配(global match)”).

宽松排列和注释模式

Perl 的 /x 参数(表示”宽松排列的表达式(free-form expressions)”).

点号通配模式

点号通配模式(dot-match-all match mode, 也叫”单行模式”): 用 .* 来匹配本行的剩余全部字符.

增强的行锚点模式

增强的行锚点模式(Enhanced line-anchor match mode, 也叫”多行文本模式”)

增强的行锚点模式会影响到行锚点 ^$ 的匹配. 通常情况下, 锚点 ^不能匹配字符串内部的换行符, 而只能匹配目标字符串的起始位置. 但是在此增强模式下, 它能够匹配字符串中内嵌的文本行的开头位置.

长期以来, 这种模式被称为”多行模式(multiline mode)”. 尽管它与”单行模式”没有什么关系, 但看名字总容易觉得二者有关联. 其实并不是对应的概念.

文字文本模式

“文字文本(literal text)”模式几乎不能识别任何正则表达式元字符. 完整的文字搜索(literal search)等于简单的字符串搜索

一些实用的例子

  • 变量名: [a-zA-Z_][a-zA-Z_0-9]*, 如果最长只能是 32 个字符, [a-zA-Z_][a-zA-Z_0-9]{0, 31}.

  • 引号内的字符串: "[^"]*".

  • HTTP/HTML URL, 通用格式 http://hostname/path.html: egrep -i '\<http://[-a-z0-9_.:]+/[-a-z0-9_:@&?=+,.!/~*%$]*\.html?\>' files. 更简单的 egrep -i '\<http://[^]*\.html?\>' files…

  • 表示时刻的文字, 例如 9:17 am 或者 12:30 pm: (1[012]|[1-9]):[0-5][0-9]·(am|pm). 24 小时制: 0?[0-9]|1[0-9]|2[0-3]:[0-5][0-9]·(am|pm).

  • 匹配对称的括号: 处理单层嵌套的正则表达式是\([^()]*(\([^()]*\)[^()]*)*\). 注意一般而言, 正则表达式无法处理无限层嵌套的对称括号内的内容提取.

  • 去除文本首尾的空白字符: s/^\s+// 或者s/\s+$//;

  • 去掉 Linux 下文件名开头的路径: s/^.*//.

  • 匹配IP地址: ^([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])$

  • Text-to-HTML转换:

    • 处理特殊字符: &,< 和 ‘>’ 字符转换为对应的HTML编码, 分别是 &amp,&lt&gt.
    • 分隔段落: 增强的行锚点(enhanced line anchor)匹配模式: ^$会从字符串模式切换到本例中需要的逻辑行模式. 在 Perl 中, 使用 /m 修饰符来选择此模式: $text=~s/^$/<p>/mg;, 考虑到空格: 「^\s*$」.
    • 将 E-mail 地址转换为超链接形式: 基础模板为$text =~ s{\b(usernameregex\@hostnameregex)\b}{<a href="mailto:$1">$1</a>}gi;
    • 把HTTP URL转换为链接形式: 参考上一条例子.
    • 最终的 Perl 结果如下:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    $HostnameRegex = qr/[-a-z0-9]+(\.[-a-z0-9]+)*\.(com|edu|info)/i;

    # Turn email addresses into links . . .
    $text =~ s{
    \b
    # Capture the address to $1 . . .
    (
    \w[-.\w]* # username
    \@
    $HostnameRegex # hostname
    )
    \b
    }{<a href="mailto:$1">$1</a>}gix;

    # Turn HTTP URLs into links . . .
    $text =~ s{
    \b
    # Capture the URL to $1 . . .
    (
    http:// $HostnameRegex \b # hostname
    (
    / [-a-z0-9_:\@&?=+,.!/~*'%\$]* # Optional path
    (?<![.,?!]) # not allowed to end with [.,?!]
    )?
    )
    }{<a href="$1">$1</a>}gix;

几个实用的正则表达式网站

  1. https://regexper.com/https://jex.im/regulex/, 将复杂的正则表达式可视化的网站.

例如上面 IP 地址的可视化结果:

  1. Regex正则表达式在线测试生成工具: https://www.mklab.cn/utils/regex

检查上面 IP 地址的例子:

稍微深入一些的正则表达式总结

https://www.chuxin911.com/regex_summary_20220406/

作者

cx

发布于

2022-04-06

更新于

2022-07-16

许可协议