梳理正則表達式發展史

作者：kamly，騰訊 CDC 應用開發工程師

前言

正則表達式在我們日常的軟件開發過程中被廣泛使用，例如編寫 Nginx 配置文件、在 Linux 與 macOS 下查找文件，然而不同軟件不同操作系統對於正則的應用有着不一樣的行爲，主要原因是正則表達式演進過程中，出現 POSIX 與 PCRE 派系之分。

一、歷史

先了解一下正則表達式的演進史。

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 年代洗禮，正則表達式形成了兩大派系：POSIX 與 PCRE：

正則表達式演進史

二、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

隨着 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 （非貪婪）等。

總結

正因爲 PCRE 與 POSIX 相比， PCRE 使用起來更加易用簡潔（不需要轉義，有更簡潔字符組），功能更加豐富（非捕獲組，環顧斷言，非貪婪）。如果沒有特殊原因，應儘可能使用 PCRE 派系，讓正則匹配的結果更符合我們預期。

pcre, posix bre, posix ere

篇幅原因，僅提供部分需要關注的對比，具體看【附錄 - PCRE、GNU BRE、GNU ERE 對比】。如果讀者對貪婪和非貪婪模式感興趣，可以瞭解一下正則表達式的執行引擎，或許會讓你對正則表達式產生新的看法。

三、實戰

瞭解完 PCRE 派系和 POSIX 派系後，我們來做個簡單的測試。文本內容如下，我們目標是需要匹配其中的數字：

12345
abcde

實驗環境爲 Linux 與 macOS 下的 grep ，分別使用:

實驗結果如下圖：

實驗結論

在 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. 其他發行版

參考資料

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/_jMpoi818qc3kwy-3Apkbw

猜你喜歡