本文為《程序員》07年3月號《七種武器》專題所做。有興趣的讀者可以到 這里  來投一票，表達(dá)您對于程序員基本功的看法。

在程序員日常工作中，數(shù)據(jù)處理占據(jù)了相當(dāng)?shù)谋戎?。而在所有的?shù)據(jù)之中，文本又占據(jù)了相當(dāng)?shù)谋戎?。文本能夠被人理解，具有良好的透明性，利于系統(tǒng)的開發(fā)、測試和維護。然而，易于被人理解的文本數(shù)據(jù)，機器處理起來就不一定都那么容易。文本數(shù)據(jù)復(fù)雜多變，特定性強，甚至是千奇百怪。因此，文本處理程序可謂生存環(huán)境惡劣。一般來說，文本處理程序都是特定于應(yīng)用的，一個項目有一個項目的要求，彼此之間很難抽出共同點，代碼很難復(fù)用，往往是“一次編碼，一次運行，到處補丁”。其程序結(jié)構(gòu)散亂丑陋，談不上有什么“藝術(shù)性”，基本上與“模式”、“架構(gòu)”什么的無緣。在這里，從容雅致、溫文爾雅派不上用場，要想生存就必須以暴制暴。
事實上，幾十年的實踐證明，除了正則表達(dá)式和更高級的parser技術(shù)，在這樣一場街頭斗毆中別無利器。而其中，尤以正則表達(dá)式最為常用。所以，對于今天的程序員來說，熟練使用正則表達(dá)式著實應(yīng)該是一種必不可少的基本功。然而現(xiàn)實情況卻是，知道的人很多，善于應(yīng)用的人卻很少，而能夠洞悉其原理，理智而高效地應(yīng)用它的人則少之又少。大多數(shù)開發(fā)者被它的外表嚇倒，不敢也不耐煩深入了解其原理。事實上，正則表達(dá)式背后的原理并不復(fù)雜，只要耐心學(xué)習(xí)，積極實踐，理解正則表達(dá)式并不困難。下面列舉的一些條款，來自我本人學(xué)習(xí)和時間經(jīng)驗的不完全總結(jié)。由于水平和篇幅所限，只能浮光掠影，不足和謬誤之處，希望得到有識之士的指教。

1. 了解正則表達(dá)式的歷史
正則表達(dá)式萌芽于1940年代的神經(jīng)生理學(xué)研究，由著名數(shù)學(xué)家Stephen Kleene第一個正式描述。具體地說，Kleene歸納了前述的神經(jīng)生理學(xué)研究，在一篇題為《正則集代數(shù)》的論文中定義了“正則集”，并在其上定義了一個代數(shù)系統(tǒng)，并且引入了一種記號系統(tǒng)來描述正則集，這種記號系統(tǒng)被他稱為“正則表達(dá)式”。在理論數(shù)學(xué)的圈子里被研究了幾十年之后，1968年，后來發(fā)明了UNIX系統(tǒng)的Ken Thompson第一個把正則表達(dá)式用于計算機領(lǐng)域，開發(fā)了qed和grep兩個實用文本處理工具，取得了巨大成功。在此后十幾年里，一大批一流計算機科學(xué)家和黑客對正則表達(dá)式進行了密集的研究和實踐。在1980年代早期，UNIX運動的兩個中心貝爾實驗室和加州大學(xué)伯克利分校分別圍繞grep工具對正則表達(dá)式引擎進行了研究和實現(xiàn)。與之同時，編譯器“龍書”的作者Alfred Aho開發(fā)了Egrep工具，大大擴展和增強了正則表達(dá)式的功能。此后，他又與《C程序設(shè)計語言》的作者Brian Kernighan等三人一起發(fā)明了流行的awk文本編輯語言。到了1986年，正則表達(dá)式迎來了一次飛躍。先是C語言頂級黑客Henry Spencer以源代碼形式發(fā)布了一個用C語言寫成的正則表達(dá)式程序庫（當(dāng)時還不叫open source），從而把正則表達(dá)式的奧妙帶入尋常百姓家，然后是技術(shù)怪杰Larry Wall橫空出世，發(fā)布了Perl語言的第一個版本。自那以后，Perl一直是正則表達(dá)式的旗手，可以說，今天正則表達(dá)式的標(biāo)準(zhǔn)和地位是由Perl塑造的。Perl 5.x發(fā)布以后，正則表達(dá)式進入了穩(wěn)定成熟期，其強大能力已經(jīng)征服了幾乎所有主流語言平臺，成為每個專業(yè)開發(fā)者都必須掌握的基本工具。

2. 掌握一門正則表達(dá)式語言
使用正則表達(dá)式有兩種方法，一種是通過程序庫，另一種是通過內(nèi)置了正則表達(dá)式引擎的語言本身。前者的代表是Java、.NET、C/C++、Python，后者的代表則是Perl、Ruby、JavaScript和一些新興語言，如Groovy等。如果學(xué)習(xí)正則表達(dá)式的目標(biāo)僅僅是應(yīng)付日常應(yīng)用，則通過程序庫使用就可以。但只有掌握一門正則表達(dá)式語言，才能夠?qū)⒄齽t表達(dá)式變成編程的直覺本能，達(dá)到較高的水準(zhǔn)。不但如此，正則表達(dá)式語言也能夠在實踐中提供更高的開發(fā)和執(zhí)行效率。因此，有心者應(yīng)當(dāng)掌握一門正則表達(dá)式語言。

3. 理解DFA和NFA
正則表達(dá)式引擎分成兩類，一類稱為DFA（確定性有窮自動機），另一類稱為NFA（非確定性有窮自動機）。兩類引擎要順利工作，都必須有一個正則式和一個文本串，一個捏在手里，一個吃下去。DFA捏著文本串去比較正則式，看到一個子正則式，就把可能的匹配串全標(biāo)注出來，然后再看正則式的下一個部分，根據(jù)新的匹配結(jié)果更新標(biāo)注。而NFA是捏著正則式去比文本，吃掉一個字符，就把它跟正則式比較，匹配就記下來：“某年某月某日在某處匹配上了！”，然后接著往下干。一旦不匹配，就把剛吃的這個字符吐出來，一個個的吐，直到回到上一次匹配的地方。
DFA與NFA機制上的不同帶來5個影響：
1. DFA對于文本串里的每一個字符只需掃描一次，比較快，但特性較少；NFA要翻來覆去吃字符、吐字符，速度慢，但是特性豐富，所以反而應(yīng)用廣泛，當(dāng)今主要的正則表達(dá)式引擎，如Perl、Ruby、Python的re模塊、Java和.NET的regex庫，都是NFA的。
2. 只有NFA才支持lazy和backreference等特性；
3. NFA急于邀功請賞，所以最左子正則式優(yōu)先匹配成功，因此偶爾會錯過最佳匹配結(jié)果；DFA則是“最長的左子正則式優(yōu)先匹配成功”。
4. NFA缺省采用greedy量詞（見item 4）；
5. NFA可能會陷入遞歸調(diào)用的陷阱而表現(xiàn)得性能極差。

我這里舉一個例子來說明第3個影響。

例如用正則式/perl|perlman/來匹配文本 ‘perlman book’。如果是NFA，則以正則式為導(dǎo)向，手里捏著正則式，眼睛看著文本，一個字符一個字符的吃，吃完 ‘perl’ 以后，跟第一個子正則式/perl/已經(jīng)匹配上了，于是記錄在案，往下再看，吃進一個 ‘m’，這下糟了，跟子式/perl/不匹配了，于是把m吐出來，向上匯報說成功匹配 ‘perl’，不再關(guān)心其他，也不嘗試后面那個子正則式/perlman/，自然也就看不到那個更好的答案了。

如果是DFA，它是以文本為導(dǎo)向，手里捏著文本，眼睛看著正則式，一口一口的吃。吃到/p/，就在手里的 ‘p’ 上打一個鉤，記上一筆，說這個字符已經(jīng)匹配上了，然后往下吃。當(dāng)看到 /perl/ 之后，DFA不會停，會嘗試再吃一口。這時候，第一個子正則式已經(jīng)山窮水盡了，沒得吃了，于是就甩掉它，去吃第二個子正則式的/m/。這一吃好了，因為又匹配上了，于是接著往下吃。直到把正則式吃完，心滿意足往上報告說成功匹配了 ‘perlman’。

由此可知，要讓NFA正確工作，應(yīng)該使用 /perlman|perl/ 模式。

通過以上例子，可以理解為什么NFA是最左子式匹配，而DFA是最長左子式匹配。實際上，如果仔細(xì)分析，關(guān)于NFA和DFA的不同之處，都可以找出道理。而明白這些道理，對于有效應(yīng)用正則表達(dá)式是非常有意義的。
4. 理解greedy和lazy量詞
由于日常遇到的正則表達(dá)式引擎全都是NFA，所以缺省都采用greedy量詞。Greedy量詞的意思不難理解，就是對于/.*/、/\w+/這樣的“重復(fù)n”次的模式，以貪婪方式進行，盡可能匹配更多字符，直到不得以罷手為止。

舉一個例子，以 /<.*>/ 模式匹配 ‘<book> <title> Perl Hacks </title> </book>\t’文本，匹配結(jié)果不是 ‘<book>’，而是 ‘<book> <title> Perl Hacks </title> </book>’。原因就在于NFA引擎以貪婪方式執(zhí)行“重復(fù)n次”的命令。讓我們來仔細(xì)分析一下這個過程。

條款3指出，NFA的模型是以正則式為導(dǎo)向，拿著正則式吃文本。在上面的例子里，當(dāng)它拿著/.*/這個正則式去吃文本的時候，缺省情況下它就這么一路吃下去，即使碰到 ‘>’字符也不罷手——既然 /./ 是匹配任意字符， ‘>’ 當(dāng)然也可以匹配！所以就盡管吃下去，直到吃完遇到結(jié)尾（包括\t字符）也不覺得有什么不對。這個時候它突然發(fā)現(xiàn)，在正則表達(dá)式最后還有一個 />/，于是慌了神，知道吃多了，于是就開始一個字符一個字符的往回吐，直到吐出倒數(shù)第二個字符 ‘>’，完成了與正則式的匹配，才長舒一口氣，向上匯報，匹配字符串從第一個字符 ‘<’ 開始，到倒數(shù)第二個字符 ‘>’結(jié)束，即‘<book> <title> Perl Hacks </title> </book>’。

Greedy量詞的行為有時確實是用戶所需要的，有時則不是。比如在這個例子里，用戶可能實際上想得到的是 ‘book’ 串。怎么辦呢？這時候lazy量詞就派上用場了。把模式改為/<.*?>/就可以得到 ‘book’。這個加在 ‘*’號后面的 ‘?’ 把greedy量詞行為變成lazy量詞行為，從而由盡量多吃變?yōu)楸M量少吃，只要吃到一個 ‘>’立刻停止。

問號在正則表達(dá)式里用途最廣泛，這里是很重要的一個用途。

5. 理解backtracking
在條款4的基礎(chǔ)上解釋backtracking就很容易了。當(dāng)NFA發(fā)現(xiàn)自己吃多了，一個一個往回吐，邊吐邊找匹配，這個過程叫做backtracking。由于存在這個過程，在NFA匹配過程中，特別是在編寫不合理的正則式匹配過程中，文本被反復(fù)掃描，效率損失是不小的。明白這個道理，對于寫出高效的正則表達(dá)式很有幫助。
 

Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1520033