基本正则表达式(BRE)和扩展正则表达式(ERE)

Sunday, December 8, 2019

最初的正则表达式出现于理论计算机科学自动控制 理论和形式化语言 理论中。在这些领域中有对计算(自动控制)的模型和对形式化语言 描述与分类的研究。

1940年,沃伦·麦卡洛克Walter Pitts神经系统 中的神经元描述成小而简单的自动控制元。

1950年代,数学家斯蒂芬·科尔·克莱尼 利用称之为「正则集合」的数学符号来描述此模型。肯·汤普逊 将此符号系统引入编辑器QED ,随后是Unix 上的编辑器ed ,并最终引入grep 。自此以后,正則表达式被广泛地应用于各种Unix或类Unix 系统的工具中。正则表达式的POSIX规范,分为基本型正则表达式(Basic Regular Expression,BRE)和扩展型正则表达式(Extended Regular Express,ERE)两大流派。在兼容POSIX的UNIX系统上,grep和egrep之类的工具都遵循POSIX规范,一些数据库系统中的正则表达式也符合POSIX规范。grep、vi、sed都属于BRE,是历史最早的正则表达式,因此元字符必须转譯之后才具有特殊含义。egrep、awk则属于ERE,元字符不用转譯 。 —— 维基百科

BRE 和 ERE 是 POSIX 标准中定义的两种不同风格的正则表达式, 也是比较早的正则表达式,只支持一些比较基础功能,没有贪婪匹配( .* )和非贪婪匹配( .*? )的区别(具体效果要看具体的实现,GNU的实现中均表现为贪婪匹配,另外一些实现中 .*? 可能导致语法错误),更不支持正、逆向巡视等后来的高级语法。

BRE语法

. 匹配单个任意字符, 匹配 . 本身使用 \.

* 前面的字符或模式重复任意次($$ x\geq0 $$),匹配 * 本身使用 \*

\{m\} 前面的字符或模式重复m次($$x=m$$)

\{m,n\} 前面的字符或模式重复m到n次($$m\leq x \leq n$$)

\{m,\} 前面的字符或模式重复m次及以上($$x\geq m$$)

\(regexp\) 分组,将 \(\) 之间的内容视为一个整体,有两个作用

  1. 配合前面的 * \{m,n\} 等量词使用,例如: ab\{2\} 匹配“abb”, 而 \(ab\)\{2\} 匹配“abab”
  2. 向后引用(back references),使用 \1 ~ \9 来引用第1~9个分组匹配的内容,例如: \(ab*\)\1 可以匹配“abab”,也能匹配“abbbabbb”

^ 放在正则表达式开头则匹配行首,其他位置匹配 ^ 本身

$ 放在正则表达式末尾则匹配行尾,其他位置匹配 $ 本身

[list] 自定义字符集,可以匹配 [] 之间出现的任意字符,例如: a[bcd] 可以匹配”ab",“ac”或“ad”。且支持使用char1-char2这种省略写法,例如: [0-9]* 可以匹配”1234567890“ , [a-c]* 可以匹配“cabba”

[^list] 同上,但匹配所有没有出现在 [] 之间的其他字符

另外其他风格的正则表达式中有诸如 \d \w \s 等速记符号(shorthand)表示一些常用字符集,BER和ERE均不支持这种写法,取而代之的是POSIX标准中定义的字符集:

POSIXDescriptionASCIIShorthand
[:alnum:]数字和字母[a-zA-Z0-9]
[:alpha:]字母[a-zA-Z]
[:ascii:]ASCII字符[\x00-\x7F]
[:blank:]空格和 Tab[ \t]\h
[:cntrl:]控制字符[\x00-\x1F\x7F]
[:digit:]数字[0-9]\d
[:graph:]可视字符[\x21-\x7E]
[:lower:]小写字母[a-z]\l
[:print:]可打印字符[\x20-\x7E]
[:punct:]标点符号[!"#$%&'()*+, -./:;<=>?@[ \]^_‘{|}~]
[:space:]所有空白字符[ \t\r\n\v\f]\s
[:upper:]大写字母[A-Z]\u
[:word:]单词[A-Za-z0-9_]\w
[:xdigit:]十六进制数[A-Fa-f0-9]

注意:[] 也是该字符集名称的一部分,即在使用中和 [0-9] 等价的是 [[:digit:]] 而不是 [:digit:]

ERE语法

ERE和BRE的最显著的区别是ERE中所有元字符(metacharacters)均不需要使用 \ 进行转义,即用 {m,n} 替代 \{m,n\} , (regexp) 替代 \(regexp\) (当然分组向后引用依旧是 \1 ~ \9)。此外ERE还在BRE基础上增加了以下语法:

? 前面的字符或模式重复0或1次($$0 \leq x \leq 1$$)

+ 前面的字符或模式重复1次及以上($$x\geq 1$$)

regexp1|regexp2 匹配 regexp1regexp2

GNU扩展的BRE

实际上现代Linux发行版中使用的 grep sed awk 等工具均由GNU提供,GNU在实现时对BRE进行了扩展,增加了 \? \+ \| 使得BRE和ERE的区别仅剩元字符是否需要转义。个人认为BRE现在存在的主要意义还是向下兼容,避免修改已经投入使用的正则表达式。


参考:

shellRegExp

Bash中的模式匹配”glob patterns“和”extglob“

关于"sudo cd"的讨论