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

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

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

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

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

我這里舉一個(gè)例子來(lái)說(shuō)明第3個(gè)影響。

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

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

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

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

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

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

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

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

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

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