《精通正则表达式》学习笔记(四)


编写巧妙的正则表达式不仅仅是一种手艺(skill) 而且还是一种艺术(art)。

正则引擎的平衡法则

  • 只匹配期望的文本,排除不期望的文本。
  • 易于控制和理解。
  • 使用NFA引擎时必须保证效率——能够匹配时立即返回匹配结果,不能匹配时尽快报告匹配失败。

实例

匹配 IP 地址

  • [0-9]*\.[0-9]*\.[0-9]*\.[0-9]*」会匹配 and then ......
  • ^[0-9]+\.[0-9]+\.[0-9]+\.[0-9]+$」字符组书写重复
  • ^\d+\.\d+\.\d+\.\d+$」会匹配非 IP 地址文本如:1234.5678.9101112.131415
  • ^\d\d\d\.\d\d\d\.\d\d\d\.\d\d\d$」数字部分匹配不够灵活,仅能匹配 3 位数字
  • 下面三个表达式会匹配非法 IP 地址数字 999
    • ^\d{1,3}.\d{1,3}.\d{1,3}.\d{1,3}$
    • \d\d?\d?.\d\d?\d?.\d\d?\d?.\d\d?\d?$
    • \d(\d\d?)?.\d(\d\d?)?.\d(\d\d?)?.\d(\d\d?)?$
  • 分析 IP 地址结构可以得出以下规律:
    • 只包含一个或两个数字的字段,无需考虑合法性,即「\d|\d\d」。
    • 01 开头的三位数(000-199)都合法。即「[01]\d\d」。
    • 2 开头的三位数字,第二位数字小于 5 则合法(255),即「2[0-4]\d」。
    • 若第二位数字是 5,第三位数字就必须小于 6256),即「25[0-5]」。
    • 上述结果为「\d|\d\d|[01]\d\d|2[0-4]\d|25[0-5]
    • 合并前三个多选分支「\d|\d\d|[01]\d\d」为「[01]?\d\d?
    • 综上,一个 IP 地址数字的表达式结果为「[01]?\d\d?|2[0-4]\d|25[0-5]
  • 匹配一个 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])$」
  • 在「^」后添加环视「(?!0+\.0+\.0+\.0+$)」来避免匹配 0.0.0.0

  • 在表达式首尾添加环视「(?<![\w.])(?![\w.])」或使用「(^| )( |$)」来保证匹配文本前后不出现「[\w.]」能匹配的字符,避免匹配嵌套型字符 1.2.3.4.5.6 中的 1.2.3.4 等类似 IP 地址的文本
  • 某些时候,处理各种极端情形会降低投入产出比。更合适的做法是不依赖正则表达式完成全部工作,善用其他工具辅助验证

处理文件名

文本:/usr/local/bin/gcc
期望:gcc

  1. 去掉文件名开头的路径
    RegEx:^.*/
    释义:使用匹配优先(贪婪)特性,匹配一整行,然后回溯到最后的斜线
  • 若匹配一个恰好没有斜线的字符串,正则引擎会在字符串的起始位置开始搜索。「.*」抵达字符串的末尾,但不断回退,直到最后它交还了匹配的所有字符,仍然无法匹配。此时,正则引擎得知在字符串的起始位不存在匹配。
  • 之后传动装置开始工作,从第 2 个字符开始,依次尝试匹配整个正则表达式,在字符串的每个位置进行扫描回溯。若字符串很长,就可能存在大量的回溯(DFA 不存在这个问题)。
  • 几乎所有以「.*」开头的正则表达式,在某个字符串的起始位置不能匹配,也就不能在其他任何位置匹配,它只会在字符串的起始位置尝试一次。
  • 在正则表达式中写明开头位置的匹配规则更明智一些。
  1. 从路径中获取文件名
    RegEx:([^/]*)$
    释义:在结尾设置一个锚点,忽略路径,从最后一个斜线开始匹配所有内容。
  • 该表达式的唯一要求是字符串有 $ 能够匹配的结束位置
  • 在 NFA 中,该表达式的效率很低,要进行 40+ 次回溯。
  1. 所在路径和文件名
    RegEx:^(.*)/(.*)$
    释义:使用 $1$2 来提取所在路径和文件名。第一个「.*」先捕获所有文本,不给「/」和 $2 留下任何字符,在尝试匹配「/(.*)$」时发生的回溯会把“交还的”部分留给后面的「.*」。

匹配对称的括号

  1. \(.*\)」 匹配括号及括号内部的任何字符。
  2. \([^)]*\)」 匹配从一个开括号到最近的闭括号。
  3. \([^()]*\)」 匹配从一个开括号到最近的闭括号,但是不容许其中包含开括号。
  • 上下述三个表达式用于匹配带括号的文本内容,匹配结果如图

匹配带括号的文本

  • 为解决正则表达式无法匹配任意深度的嵌套结构的问题,可以用正则表达式来匹
    配特定深度的嵌套括号,但不是任意深度的嵌套括号。
  • 处理单层嵌套的正则表达式是:「\([^()]*(\([^()]*\)[^()]*)*\)

匹配浮点数

  • -?[0-9]*\.?[0-9]*」会匹配 -.0
  • -?[0-9]*\.?[0-9]*」会产生空匹配(匹配没有任何必须的元素),如 this has no numbernothing here
  • 把真正意图表达清楚非常重要:一个浮点数必须要有至少一位数字,否则就不是一个合法的值。
  • -?[0-9]+」用于限定浮点数含有数字的特性
  • (\.[0-9]*)?」用于限定浮点数的小数点小数部分
  • 综上,「-?[0-9]+(\.[0-9]*)?」即可用于匹配浮点数而不匹配空字符,即不产生空匹配

匹配分隔符之内的文本

文本:a passport needs a "2\"x3\" likeness" of the holder
期望:"2\"x3\" likeness"

  • 匹配分隔符之内的文本的主要步骤:
    1. 匹配起始分隔符(opening delimiter)。
    2. 匹配正文(main text,即结束分隔符之前的所有文本)。
    3. 匹配结束分隔符。
  • 匹配开始和结束分隔符很容易,但匹配正文的时不能超越结束分隔符:
    • 匹配非引号内容:「[^"]
    • 匹配转义的反斜线需要使用环视:「(?<=\\)"
    • 综上得出的表达式为「"([^"]|(?<=\\)")*"」,此时可以匹配 2\"x3\"

文本:"/-|-\\" or "[^-^]"
期望:"/-|-\\"
RegEx:"([^"]|(?<=\\)")*"
结果:"/-|-\\" or "

  • 第一个闭引号之前存在一个反斜线,该反斜线本身是被转义的,其后的引号是表示引用文本的结束。逆序环视无法识别这个被转义的反斜线。
  • 匹配的位于开始分隔符和结東分隔符之间的文本可以包括转义的字符「\\.」,也可以包括非引号的任何字符「[^"]」。
  • 综上得出的表达式为「"(\\.|[^"])*"
  • 匹配优先和忽略优先都期望获得匹配,如果找不到结束的引号,它就会回溯,从而降低性能。
  • 如果回溯会导致不期望,与多选结构有关的匹配结果,可能是因为任何成功的匹配都不过是多选分支的排列顺序造成的偶然结果,
  • 如果有占有优先量词或者是固化分组,那么这个正则表达式可以被持续优化以提升性能(特别是对于 NFA)

去除文本首尾的空白字符

  1. 去除文本首部的空白字符「s/^\s+//
    去除文本末尾的空白字符「s/\s+$/
  2. 去除文本首尾空白字符的表达式:「s/\s*(.*?)\s*$/$1/s
    该表达式因为忽略优先约束的点号每次应用时都要检查「\s*$」导致大量回溯,严重影响效率。
  3. 去除文本首尾空白字符的表达式:「s/^\s*((?:.*\S)?)\s*$/$1/s」后面的「\S」强迫回溯直到找到一个非空字符,把剩下的空白字符留给最后的「\s*$」,捕获括号之外的内容。

HTML 相关范例

匹配 HTML Tag

RegEx:<("[^"]*"|'[^']*'|[^'">])*>
释义:
匹配 HTML Tag

  • 引用字符串可能为空(例如 alt=""), 所以最开始的两个多选分支的引号中使用「*」而非「+」。
  • NFA 引擎下,多选分支之间不存在重复,所以最后的「>」无法匹配是产生的回溯是不需要的,可使用非捕获型括号改写表达式以提高效率。

文本:...<a href="http://www.oreilly.com">O'Reilly Media</a>...
期望:http://www.oreilly.comO'Reilly Media
RegEx:\b HRFF\s* = \s*(?:"([^"]*)"|'([^']*)'|([^'">\S]+))
释义:
匹配 HTML Link

校验 HTTP URL

将 URL 地址分解为主机名(hostname)和路径(path)两部分。

^http://        # 匹配协议
([^/:]+) # 捕获主机名
(:(\d+))? # 匹配端口号(可能没有)
(/.*)?$ # 捕获路径

提取 URL

从纯文本中提取 URL 的正则表达式框架如下:
提取纯文本中的URL

几个保持数据协调性的原则

手动保持正则引擎的协调,才能忽略不需要的文本。有时为了提高表达式的效率,应该选择跳过不需要的文本,而非使用正向思维直接匹配目标文本。

  1. 根据期望保持匹配的协调性
    合理使用忽略优先量词,在后面的表达式失败之前,优先忽略容易引起大范围匹配成功的匹配操作。跳过我们希望跳过的文本而进行匹配。
  2. 不匹配时也应当保证协调性
  3. 使用「\G」保证协调
    \G」用于匹配上一次匹配结束的位置。