梳理正则表达式发展史

作者:kamly,腾讯 CDC 应用开发工程师

前言

正则表达式在我们日常的软件开发过程中被广泛使用,例如编写 Nginx 配置文件、在 Linux 与 macOS 下查找文件,然而不同软件不同操作系统对于正则的应用有着不一样的行为,主要原因是正则表达式演进过程中,出现 POSIXPCRE 派系之分。

一、历史

先了解一下正则表达式的演进史。

20 世纪 40 年代,两位神经生理学家 Warren McCulloch 和 Walter Pitts,研究出了一种用数学方式来描述神经网络的方法,可以将神经系统中的神经元描述成小而简单的自动控制元。

50 年代,一位叫 Stephen Kleene 的数学家在 McCulloch 和 Pitts 早期工作的基础上,发表了《神经网络事件表示法和有穷自动机》 论文。这篇论文描述了一种叫做 "正则集合(Regular Sets)" 的数学符号,引入了正则表达式的概念。

60 年代,Unix 之父 Ken Thompson 发表了 《正则表达式搜索算法》 论文。并且根据这篇论文的算法,将正则引入到编辑器 qed ,以及之后的编辑器 ed 中,然后又移植到了我们熟悉的文本搜索工具 grep 中。

70 年代,由于 grep 支持的功能不多,因此 Alfred Aho 编写了 egrep 程序(其中 e 表示加强版的意思)。在 grep 、 egrep 发展的同时, awk 、 lex 、 sed 等异军也开始凸起,每个程序所支持的正则表达式都有差别。

80 年代,POSIX (Portable Operating System Interface) 标准公诸于世,它制定了不同的操作系统都需要遵守的一套规则,其中就包括正则表达式的规则。遵循 POSIX 规则的正则表达式,称为 POSIX 派系的正则表达式。Unix 系统或类 Unix 系统上的大部分工具,如 grep 、sed 、awk 等都属于 POSIX 派系。同样在 80 年代,Larry Wall 发布了 Perl 编程语言,其中引入的正则表达式功能是颗耀眼明珠。

90 年代,随着 Perl 语言的发展,它的正则表达式功能越来越强悍。为了把 Perl 语言中正则的功能移植到其他语言中, PCRE (Perl Compatible Regular Expressions)派系的正则表达式也诞生了。现代编程语言如 Python , Ruby , PHP , C / C++ , Java 等正则表达式,大部分都属于 PCRE 派系。

总的来说,经历 20 世纪 80 至 90 年代洗礼,正则表达式形成了两大派系:POSIXPCRE

正则表达式演进史

二、POSIX 与 PCRE

POSIX 派系 与 PCRE 派系具体有什么不一样?我们应该何时选择哪个派系?

POSIX 派系

POSIX 派系是遵循 POSIX 规则的正则表达式,其中代表软件有:grep ,sed 和 awk 等。

BRE 和 ERE 标准

POSIX 派系分为两种标准:

  1. BRE 标准(Basic Regular Expression 基本正则表达式)
  2. ERE 标准(Extended Regular Expression 扩展正则表达式)

在 GNU 版本下,两者具体差别如下:

BRE 和 ERE 对比

是不是很难找到两者的差别点呢?仔细留意一下,第 3,4,5,7 行的内容。我们能发现,如果使用 BRE 标准,需要对 [], (), | 符号进行转义。作者看来 ERE 实际上是 BRE 的一个扩展标准,开发者使用 ERE 能书写更简单的正则表达式,不需要对某些字符进行特殊转义。

POSIX 字符组

POSIX 派系有自己的字符组,叫 POSIX 字符组,具体解释如下所示:

POSIX字符组

篇幅原因,仅提供部分需要关注的对比,具体看【附录-POSIX 字符组详细内容】。

PCRE 派系

现代编程语言大部分都属于 PCRE 派系,如 Python , PHP 和 Java 等。

PCRE 与 Perl
  • Perl1 提供了正则表达式操作符——是通用脚本语言的首创;
  • Perl2 补充 /i 量词,能够进行不区分大小写匹配等;
  • Perl3 支持 /e 量词,能够增强替换运算符的能力;{min,max} 区间量词等;
  • Perl5 添加 非捕获的括号,忽略优先的量词,顺序环视功能等。

随着 Perl 每次迭代,新增的特性使正则表达式本身逐渐成为一门强大的编程语言,并为其提供了进一步发展空间,也因为派系的整合, PCRE 库横空出世,它是一套兼容 Perl 正则表达式库,全面仿制 Perl 的正则表达式的语法和语义。其他开发人员可以把 PCRE 库整合到自己的工具和语言中,为使用者提供丰富的正则功能。

特性
  1. 更易用 相对于 POSIX 派系的 BRE 标准,不需要使用 \ 进行转义。 例如:在多选分支结构直接使用 | 即可(1|2 表达 1 或者 2)
  2. 更简洁 在兼容 POSIX 字符组的基础上还支持更简洁的写法。 例如:\w 等价于 [[:word:]]\d 等价于 [[:digit:]]
  3. 更多功能 例如:Look-around (环顾断言), Non-capturing Group (非捕获组), non-greedy (非贪婪)等。

总结

正因为 PCREPOSIX 相比, PCRE 使用起来更加易用简洁(不需要转义,有更简洁字符组),功能更加丰富(非捕获组,环顾断言,非贪婪)。如果没有特殊原因,应尽可能使用 PCRE 派系,让正则匹配的结果更符合我们预期。

pcre, posix bre, posix ere

篇幅原因,仅提供部分需要关注的对比,具体看【附录-PCRE、GNU BRE、GNU ERE 对比】。如果读者对贪婪和非贪婪模式感兴趣,可以了解一下正则表达式的执行引擎,或许会让你对正则表达式产生新的看法。

三、实战

了解完 PCRE 派系和 POSIX 派系后,我们来做个简单的测试。文本内容如下,我们目标是需要匹配其中的数字:

12345
abcde

实验环境为 Linux 与 macOS 下的 grep ,分别使用:

  • 不带参数,为 POSIX BRE 模式;
  • 带参数 -E,为 POSIX ERE 模式;
  • 带参数 -P,为 PCRE 模式( macOS 不支持)。

实验结果如下图:

实验结论

在 Linux 环境下

通过 man grep ,可以了解到 Linux 下的 grep 默认是 POSIX BRE 模式:

-G, --basic-regexp
            Interpret PATTERN as a basic regular expression (BRE, see below).  This is the default.

加上 -E 则是 POSIX ERE 模式:

-E, --extended-regexp
              Interpret PATTERN as an extended regular expression (ERE, see below).

加上 -P 则是 PCRE 模式:

 -P, --perl-regexp
              Interpret the pattern as a Perl-compatible regular expression (PCRE).  This is experimental and grep -P may warn of unimplemented features.
在 macOS 环境下

从实验结果来看, grep '\d' demo.txt' 命令在 Linux 与 macOS 输出是不一样的,这是因为 macOS 自带的 grep 是 BSD 版本,而 Linux 下的 grep 则是 GNU 版本。

macOS 基于 BSD,预置 BSD 工具链,众多命令行工具与 Linux 下 GNU 工具的行为不一致,例如常见的 gzip , find 和 sed ,以及本文重点提及的 grep。

读者如果希望自己的 macOS 电脑能完美运行 GNU/Linux 上的 Shell 脚本,可以使用 homebrew 来逐一替换,例如本文提及的 grep 可以通过 brew install grep

总结

正则表达式以及相关生态在发展了数十年的情况下,应用场景已经非常广泛。读者在使用软件工具的时候,应需要了解该工具支持正则表达式何种派系,避免执行脚本迁移不同环境后运行结果不符合预期。

例如:

  1. 确认版本类型(GNU , BSD)。建议统一使用 GNU 中 grep 程序,避免在不同环境下运行结果不符合预期的现状
  2. 确认每个模式下的选项(BRE , ERE , PCRE)。尽可能选择 PCRE 模式,因为 PCRE 模式更符合我们的使用习惯。

此外,除了关心正则表达式的标准之外,强烈推荐读者细读正则表达式的执行引擎,或许能帮助你写出更性能更好的正则表达式,避免因为正则表达式的地狱回溯导致的应用程序的 OOM。

附录

POSIX 字符组详细内容

POSIX字符组详细内容

PCRE、GNU BRE、GNU ERE 对比

PCRE、GNU BRE、GNU ERE 对比

GNU

GNU简介

BSD

BSD 是加州大学伯克利分校对 Unix 系统进行的扩展与重新发行。目前的 BSD 生态系统围绕三大主要操作系统:

  1. FreeBSD、OpenBSD、NetBSD
  2. DragonFly BSD
  3. 其他发行版

参考资料

招人正则匹配中,欢迎扫码命中

腾讯程序员视频号最新视频

文章分享自微信公众号:
腾讯技术工程

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!

如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 正则表达式-梳理

    先贴上两个地址,正则表达式的生成工具,第三个是正则表达式的生成图文解析,并测试正确与否

    用户3055976
  • 梳理 50 年人机交互界面发展史,得出这个规律,开发框架的选择不再迷茫

    框架的英文是 Framework,与之经常并提的另一个词汇是 Library。两者的区别有哪些?

    LIYI
  • JavaScript发展史

    HTML5学堂:JavaScript是HTML5中的一个基本组成部分。我们对HTML5的基本发展进行了基本了解之后,还需要对JavaScript有一定的了解,特...

    HTML5学堂
  • Linux发展史

    第1章 Linux发展史 1.1 什么是操作系统 操作系统是人与计算机硬件的一个中介。 1.2 操作系统组成 操作系统类似与鸡蛋 蛋壳--------->系统中...

    惨绿少年
  • MPEG发展史

    原文链接:https://www.linkedin.com/pulse/mpeg-metamorphoses-leonardo-chiariglione/

    用户1324186
  • Shopify发展史

    Shopify的创始人是个滑雪爱好者,对当时存在的一些电商平台不满意最而自己建站,希望通过自己的网站售卖滑雪用品。

    春哥大魔王
  • Linux发展史

    lonelyvaf
  • RPC 发展史

    本文主要介绍RPC基础概念以及发展历程,目的是为了让读者对RPC 的发展以及发展过程中遇到的问题有比较清晰的了解。

    goodspeed
  • 梳理

    kmokidd
  • 中国黑客发展史

    用户1127987
  • 图说AI发展史

    1943年,可以认为是AI肇始,自此人类打开了一个盒子,对于从中放出来的巨兽,尚未定论。但,它来了。

    老齐
  • 深度学习发展史

    作为机器学习最重要的一个分支,深度学习近年来发展迅猛,在国内外都引起了广泛的关注。然而深度学习的火热也不是一时兴起的,而是经历了一段漫长的发展史。接下来我们了解...

    磐创AI
  • web的发展史

    web2.0时代 ajax异步数据传输(ajax98年出现的,真正广泛接触是在05年的时候,05年的时候出现了一大批基于ajax应用出现了,类似于谷歌地图,16...

    河湾欢儿
  • MySQL DDL发展史

    - 注意: 在online ddl前,inplace的方法主要在第三步大大缩短了时间,只重构了索引,没有重新copy所有数据

    划水教练
  • JAVA日志发展史

    2001年以前,Java是没有日志库的,打印日志全凭System.out和System.err

    用户9282069
  • DevOps 的发展史

    当我们在搜索引擎搜索 DevOps 的时候,会出现很多其他的名词,例如,Agile(敏捷开发),Scrum,Lean,Kanban 等等。无形之中增加了我们的学...

    公众号: 云原生生态圈
  • vue梳理

    念念不忘
  • Spring boot(0)一JAVA Web发展史和spring boo发展史

    CGI(Common Gateway Interface)公共网关接口,一种在web服务端使用的脚本技术,使用C或Perl语言编写,用于接收web用户请求并处理...

    黄规速

扫码关注云+社区

领取腾讯云代金券