《UNIX/Linux 系統管理技術手冊（第四版）》——2.3 正規表達式

本節書摘來自異步社群《unix/linux 系統管理技術手冊（第四版）》一書中的第2章，第2.3節，作者：【美】evi nemeth , garth snyder , trent r.hein , ben whaley著，更多章節内容可以通路雲栖社群“異步社群”公衆号檢視

unix/linux 系統管理技術手冊（第四版）

盡管有些語言比其他語言對正規表達式更關注，但大多數現代語言都支援正規表達式。諸如grep和vi這樣的unix指令也使用正規表達式。正規表達式如此常見，以至于通常都把其名稱縮寫為“regex”。有幾本書全篇就講如何發掘正規表達式的威力，而且無數博士論文的主題也都是正規表達式。

在解釋諸如wc -l*.pl這樣的指令行時，shell會做檔案名比對和擴充，但這并不是正規表達式比對的一種形式。它是一種稱之為“shell通配”的不同體系，并且它采用了一種不同的、更為簡單的文法。

正規表達式非常強大，但是它們不能支援所有可能的文法。其最著名的弱點就是：不能識别嵌套的限定符。例如，當允許用圓括号組織算術表達式的時候，就不可能寫出一個正規表達式，它能夠辨識出這樣的算術表達式是否有效。

正規表達式在perl語言中達到了其威力和完美的巅峰。實際上，perl的模式比對功能如此精緻，以至于把它們稱為正規表達式的一種實作，都顯得不夠準确。perl的模式能夠比對嵌套的限定符，能夠識别回文，還能夠比對由若幹個a後跟相同數量的b所組成的任意字元串——所有這些都超出了正規表達式能夠支援的範圍。當然，perl也能處理普通的正規表達式。

perl的模式比對語言保持為業界的标準，它已經被其他語言和工具廣泛采納。philip hazel寫的pcre 庫（perl-compatible regular expression，相容perl的正規表達式）讓開發人員能夠相當容易地把這種語言加入到他們自己的項目中。

正規表達式自身并不是一種腳本程式設計語言，但是它們作用很大，以至于隻要讨論腳本程式設計就要專門介紹它們的特色功能；是以也就有了本節内容1。本節我們讨論它們的基本形式，但帶有一些perl的改進。

2.3.1 比對過程

當代碼要判斷一個正規表達式的值時，它會嘗試用一個給定的文本字元串去比對一個給定的模式。要比對的“文本字元串”可以很長，其中可以包括換行符。用一個正規表達式去比對整個檔案或者html文檔的内容，往往是非常友善的。

整個搜尋模式必須和一段連續的搜尋文本比對，比對程式才宣布比對成功。不過，這個模式可以在任意位置進行比對。成功比對一次之後，取值程式就傳回比對出來的文本，以及該模式裡所有特别限定的部分所比對的結果清單。

2.3.2 普通字元

一般而言，在正規表達式中的字元就比對它們自己。是以下面這個模式

就比對字元串“i am the walrus”，并且隻比對這個字元串。因為它能夠比對搜尋文本中的任意位置，是以這個模式也能比對成功字元串“i am the egg man. i am the walrus. koo koo ka-choo!”不過，實際比對的地方僅限于“i am the walrus”這部分。比對是區分大小寫的。

2.3.3 特殊字元

表2.4給出了在正規表達式中常見的一些特殊符号的含義。它們都是基本字元——還有許許多多其他字元。

a.也就是說，一個空格、一個換頁、一個制表符、一個換行符或者一個回車|

許多特殊結構，像+和|，都會影響它們左邊或者右邊“東西”的比對。一般而言，這個“東西”可以是一個字元、用括号括起來的子模式，或者用方括号括起來的字元類。不過，對于 | 這個字元來說，前面所說的“東西”的範圍可以向左右無限制地擴充。如果想要限制這個豎線的作用域，那麼可以把這個豎線和左右兩邊的東西，都一起放到它們自己的一對圓括号裡。例如，

就比對“i am the walrus.”或者“i am the egg man.”。這個例子也示範了特殊字元（在這裡是點）的轉義。下面的模式

(i am the (walrus|egg man). ?){1,2}

比對下面所有的句子：

i am the walrus.

i am the egg man.

i am the walrus. i am the egg man.

i am the egg man. i am the walrus.

它偏偏也比對“i am the egg man. i am the egg man.”這一句（但那句話有什麼意義呢？）。更重要的是，它還比對“i am the walrus. i am the egg man. i am the walrus.”這句話，即使重複數明确限制為至多兩次。那是因為這個模式不需要比對整個搜尋文本。本例中的正規表達式比對兩個句子之後就終止了，并宣告比對成功。它根本不關心還有一次重複。

有一種常見的錯誤，把正規表達式的元字元*（零次或者多次的量詞）和shell的通配符搞混。正規表達式中的星号需要有東西去修飾；否則，它并不會按照預期去起作用。如果任何字元序列（包括根本沒有字元）都是能夠接受的比對結果，那麼就用.。

2.3.4 正規表達式的例子

在美國，郵政編碼是5個數字，或者5個數字後面加一個短劃線和另外4個數字。要比對一個正常的郵政編碼，就必須比對一個有5位數字的數。下面的正規表達式剛好符合要求：

^和$比對搜尋文本的開頭和結尾，但是沒有實際對應文本中的字元；它們是“零寬界定符（zero-width assertion）”。這兩個字元確定了一點，隻有正好5個數字才能比對這個正規表達式——對于在一個更長字元串裡面包含的5個數字，這個正規表達式不會去比對它們。d這個轉義符比對一個數字，量詞{5}表明必須正好比對5個數字。

為了既能比對5位數字的郵政編碼，也能比對那種擴充形式（即郵政編碼+4位數字），就要加上一個可有可無的短劃線，以及另外4位數字：

圓括号把短劃線和多出來的數字放到一起，這樣一來，它們就被當做一個整體上可有可無的單元。例如，這個正規表達式不會比對5位數字後跟一個短劃線。如果出現了短劃線，那麼也必須出現4位數字的擴充，否則就不會比對。

下面的表達式是示範正規表達式比對的一個經典例子：

它比對了利比亞上司人卡紮菲名字的大多數不同拼法，包括：

muammar al-kaddafi （bbc）

moammar gadhafi（美聯社）

muammar al-qadhafi （卡達半島電視台）

mu’ammar al-qadhafi （美國國務院）

能看出這些名字是怎樣比對該模式的嗎？

這個正規表達式也展示出：達到人們能夠閱讀清楚的上限有多快。許多正規表達式體系（包括perl中的體系）都支援一個x選項，它忽略模式裡的空白，并支援注釋，進而使得模式能夠被隔開，分成多行顯示。于是使用者就可以用空白把邏輯組劃分開，搞清楚其中的關系，就像用一種過程式語言那樣。例如：

這樣做有點兒幫助，但是仍然很容易折磨以後閱讀代碼的人。是以要做得友善些：如果可以，就用層次比對或者多個小的比對，而不用一個較大的正規表達式覆寫所有可能的情況。

2.3.5 捕獲

一次比對成功之後，每一對圓括号都變成了一個“捕獲組”，它們記錄下了該正規表達式比對的實際文本。這些結果的使用方式則取決于具體實作和上下文環境。在perl中，可以把比對結果當做一個清單或者一系列被編了号的變量來通路。

因為圓括号可以嵌套，怎樣知道哪個比對哪個呢？這很簡單——比對的次序和左括号的次序一樣。捕獲的數量和左括号的數量一樣多，不管每個用括号括起來的捕獲組在實際比對中扮演什麼角色（或者不扮演什麼角色）。當括号括起來的捕獲組沒有用到的時候（例如，當用mu(')?ammar比對“muammar”的時候），它對應的捕獲組就為空。

如果一個捕獲組比對了不止一次，那麼隻傳回最後一次比對的内容。例如，用下面這個模式

比對文本

的話，就會得到兩個結果，一個結果對應一對括号。

注意，這兩個捕獲組實際都比對了兩次。不過，實際隻傳回每對括号最後一次比對的文本。

2.3.6 貪心、懶惰和災難性的回溯

正規表達式從左到右進行比對。模式的每個成分都要比對盡可能長的字元串，然後再讓位給下一個成分，這種特性稱為“貪心”。

如果正規表達式比對器達到了一種不能完成一次比對的狀态，那麼它就從候選的比對結果那裡退回一點兒，讓一個貪心的原子成分少比對一點兒自己的文本。例如，考慮用正規表達式a*aa比對輸入的文本“aaaaaa”。

首先，正規表達式比對器把整個輸入都配置設定給這個正規表達式中的a部分，因為a是貪心的。在沒有可比對的a之後，比對器就繼續嘗試比對正規表達式接下來的部分。不過情況不妙，接下來的部分是個a，再沒有輸入文本能比對一個a的了；這就到了回溯的時候。正規表達式的a*部分不得不少比對一個它已經比對過的a。

現在比對器能夠比對aa了，但它仍然不能比對這個模式裡的最後那個a。是以它又得回溯，讓a再次騰出一個a。現在該模式裡的第二個和第三個a都有比對的a了，比對也就完成了。

這個簡單的例子展示出一些要點。首先，在處理整個檔案時，貪心的比對方式加上回溯會讓明顯很簡單的模式（如>）開銷很大2。正規表達式中.的部分一開始就比對了從第一個

使用者還可以使用懶惰（和貪心正好相反）通配符：用?來代替，用+?來代替+。這兩個版本的通配符比對盡可能少的輸入字元。如果不能比對更少的話，它們就多比對一些字元。在許多情況下，這兩個運算符比貪心的版本更有效，而且更接近使用者想要的結果。

不過要注意，它們得到的比對結果和貪心運算符的不一樣；差異不僅僅是這一種實作。對于我們給的html那個例子，懶惰模式是?>。但即便在這裡，?最終都會擴大到包括不想要的>，因為之後接下來的标簽可能不是一個。這又可能不是使用者想要的結果。

有多個通配部分的模式會導緻正規表達式比對器的處理量呈指數增長，如果文本的各個部分能夠比對幾個通配表達式，而搜尋文本實際上并不比對該模式的話，處理量都會尤其大。這種情況可沒有聽上去的那麼少見，特别是對html做模式比對的時候。想比對某些标簽後面跟着其他标簽，其間可能還被更多的标簽隔開，這是頻繁遇到的情形，但這種模式可能會要求正規表達式比對器嘗試許多可能的組合。

正規表達式專家jan goyvaerts把這種現象稱為“災難性的回溯”，他在自己的部落格裡寫下了有關這種現象的内容；參考regular-expressions.info/catastrophic.html了解詳情以及一些好的解決方案。

其中幾個能用到的辦法是：

如果可以一行一行地進行模式比對，而不是一次整個檔案進行模式比對，那麼性能差的風險就會小好多；

即使正規表達式的寫法預設采用了貪心運算符，但是可能不應該用它們，用懶惰運算符吧；

出現.*的地方本身全都值得懷疑，應該仔細檢查。