摘要：如果經(jīng)過一系列輸入，最終如果能達(dá)到狀態(tài)，則輸入內(nèi)容一定滿足正則表達(dá)式。正則表達(dá)式可以轉(zhuǎn)換為，已經(jīng)有成熟的算法實(shí)現(xiàn)這一轉(zhuǎn)換。不過有時候轉(zhuǎn)換為可能導(dǎo)致狀態(tài)空間的指數(shù)增長，因此直接用識別正則表達(dá)式。

原文地址

先來看一個讓人震撼的小故事，故事來自知乎問題PC用戶的哪些行為讓你當(dāng)時就震驚了？

同學(xué)在一個化妝品公司上班，旁邊一個大媽（四十多歲）發(fā)給他一個exl表，讓他在里面幫忙找一個經(jīng)銷商的資料。  
表格里面大約有幾百個客戶資料，我同學(xué)直接篩選填入信息，然后沒找到，就轉(zhuǎn)頭告訴大媽，說這個表里沒有。  
大媽很嚴(yán)厲的批評了我同學(xué)，說年輕人干工作一定要沉的住氣，心浮氣躁可不行。這才幾分鐘啊，我才看了二十行，你怎么就找完了。  
同學(xué)過去一看，大媽在一行一行的精挑細(xì)選，頓時一身冷汗。把篩選辦法告知后，大媽不但不領(lǐng)情，還召集辦公司其他老職員，一起聲討我同學(xué)，我們平時都是這么找的，你肯定是偷工減料，我們找一個小時沒找完，你幾分鐘就找完了。

不知道是否確有此事，不過看起來好嚇人的樣子。仔細(xì)想想，大多數(shù)人都是用以往的經(jīng)驗(yàn)來分析遇見的新問題的。就上面的大媽而言，在接觸計(jì)算機(jī)之前的幾十年里，她面對的都是紙質(zhì)的客戶資料，此時，要查找某一客戶資料，只能一行一行看下去了。

現(xiàn)在，雖然有了計(jì)算機(jī)，但是只是簡單的把它看做一個比較大的紙質(zhì)資料庫罷了，并沒有認(rèn)識到計(jì)算機(jī)的強(qiáng)大之處。這里的強(qiáng)大主要就是說計(jì)算機(jī)在處理電子文檔時的強(qiáng)大的搜索功能了。

當(dāng)然，對于大部分年輕人來說，計(jì)算機(jī)中的搜索功能是再熟悉不過了。我們可以在word、excel、網(wǎng)頁中搜索特定內(nèi)容，可以在整個計(jì)算機(jī)文件系統(tǒng)中搜索文件名，甚至搜索文件中的內(nèi)容（Win下的everthing，Mac下的Spotlight）。

這些搜索主要用到了兩種技術(shù)：

正則表達(dá)式

數(shù)據(jù)庫索引

這里我們先介紹一下正則表達(dá)式。

簡單來說，正則表達(dá)式就是用來匹配特定內(nèi)容的字符串。舉個例子來講，如果我想找出由a、b組成的，以abb結(jié)尾的字符串，比如ababb，那么用正則表達(dá)式來表示就是[ab]*abb。

正則表達(dá)的理念是由數(shù)學(xué)家Stephen Kleene在1950年首次提出來的，開始時主要用于UNIX下文本編輯器ed和過濾器grep中。1968年開始廣泛應(yīng)用于文本編輯器中的模式匹配和編譯器中的詞法分析。1980年，一些復(fù)雜的正則表達(dá)語句開始出現(xiàn)在Perl中，使用了由Henry Spencer實(shí)現(xiàn)的正則表達(dá)解析器。而Henry Spencer后來寫了更高效的正則解析器Tcl，Tcl混合使用了NFA（非確定有限自動機(jī)）/DFA（確定有限自動機(jī)）來實(shí)現(xiàn)正則表達(dá)語法。

正則表達(dá)式有以下優(yōu)點(diǎn)：

容易理解

能高效實(shí)現(xiàn)

具有堅(jiān)實(shí)的理論基礎(chǔ)

正則表達(dá)式的語法十分簡單，雖然各種編程語言在正則表達(dá)式的語法上有細(xì)節(jié)上的區(qū)別，不過主要部分如下：

[a-z]表示所有小寫字母，[0-9]表示所有數(shù)字，[amk]表示a、m或k。

+表示字符重復(fù)1或者多次，*表示字符重復(fù)0或者多次。在使用+或者*時，正則表達(dá)式遵從maximal munch的原則，也就是說它匹配能夠匹配到的最大字符串。

a|z 表示匹配字符"a"或者"z"

？表示字符出現(xiàn)0次或者1次

是正則表達(dá)式中的escape符號，*表示的就是"*"這個字符，而不是它在正則表達(dá)式中的功能。

. 表示出了換行符之外的任何字符，而^表示出了緊接它的字符以外的任何字符

^ 匹配字符串的開始，$ 匹配字符串的結(jié)尾。

回到我們前面的例子中，我們用正則表達(dá)式[ab]*abb來匹配由a、b組成的，以abb結(jié)尾的字符串。這里[ab]*abb即可以這樣解讀：a或者b重復(fù)0或者多次，然后是abb的字符串。

下面用python在"aababbaxz abcabb abbbbabb"中搜索[ab]*abb：

import re
content = "aababbaxz abcabb abbbbabb"
pattern = re.compile("[a|b]*abb")
print pattern.findall(content)
# outputs: ["aababb", "abb", "abbbbabb"]

其實(shí)，正則表達(dá)式不只用于文本搜索和模糊匹配，還可以用于以下場景：

合法性檢查

文本的自動更正和編輯

信息提取

正則表達(dá)式便于我們理解使用，但是如何讓計(jì)算機(jī)識別用正則表達(dá)式描述的語言呢？仍然以前面的[a|b]*abb為例，計(jì)算機(jī)如何識別[a|b]*abb的意義呢？首先我們來看判斷輸入內(nèi)容是否匹配正則表達(dá)式的流程圖：

圖中一共有4個狀態(tài)S0, S1, S2, S3，在每個狀態(tài)基礎(chǔ)上輸入字符a或者b就會進(jìn)入下一個狀態(tài)。如果經(jīng)過一系列輸入，最終如果能達(dá)到狀態(tài)S3，則輸入內(nèi)容一定滿足正則表達(dá)式[a|b]*abb。

為了更清晰表述問題，將上圖轉(zhuǎn)換為狀態(tài)轉(zhuǎn)換表，第一列為當(dāng)前狀態(tài)，第二列為輸入a后當(dāng)前狀態(tài)的跳轉(zhuǎn)，第三列為輸入b后當(dāng)前狀態(tài)的跳轉(zhuǎn)。其中S0為起始狀態(tài)，S3為接受狀態(tài)，從起始狀態(tài)起經(jīng)過一系列輸入到達(dá)接受狀態(tài)，那么輸入內(nèi)容即滿足[a|b]*abb。

其實(shí)上圖就是一個DFA實(shí)例（確定有限自動機(jī)），下面給出DFA較為嚴(yán)格的定義。一個確定的有窮自動機(jī)(DFA) M 是一個五元組：M = (K, ∑, f, S, Z)，其中：

K是一個有窮集，它的每個元素稱為一個狀態(tài)；

∑是一個有窮字母表，它的每個元素稱為一個輸入符號，所以也稱∑為輸入符號表；

f是轉(zhuǎn)換函數(shù)，是在K×∑→K上的映射，如f(ki, a)→kj，ki∈K，kj∈K就意味著當(dāng)前狀態(tài)為ki，輸入符號為a時，將轉(zhuǎn)換為下一個狀態(tài)kj，我們將kj稱作ki的一個后繼狀態(tài)；

S∈K是唯一的一個初態(tài)；

Z?K是一個狀態(tài)集，為可接受狀態(tài)或者結(jié)束狀態(tài)。

DFA的確定性表現(xiàn)在轉(zhuǎn)換函數(shù)f:K×∑→K是一個單值函數(shù)，也就是說對任何狀態(tài)ki∈K和輸入符號a∈∑，f(k, a)唯一地確定了下一個狀態(tài)，因此DFA很容易用程序來模擬。

下面用字典實(shí)現(xiàn)[a|b]*abb的確定有限自動機(jī)，然后判斷輸入字符串是否滿足正則表達(dá)式。

DFA_func = {0: {"a": 1, "b": 0},
            1: {"a": 1, "b": 2},
            2: {"a": 1, "b": 3},
            3: {"a": 1, "b": 0}
            }
input_symbol = ["a", "b"]
current_state = 0
accept_state = 3

strings = ["ababaaabb",
           "ababcaabb",
           "abbab"]
for string in strings:
    for char in string:
        if char not in input_symbol:
            break
        else:
            current_state = DFA_func[current_state][char]

    if current_state == 3:
        print string, "---> Match!"
    else:
        print string, "--->No match!"
    current_state = 0
    """outputs:
    ababaaabb ---> Match!
    ababcaabb --->No match!
    abbab --->No match!
    """

上面的例子可以看出DFA識別語言簡單直接，便于用程序?qū)崿F(xiàn)，但是DFA較難從正則表達(dá)式直接轉(zhuǎn)換。如果我們能找到一種表達(dá)方式，用以連接正則表達(dá)式和DFA，那么就可以讓計(jì)算機(jī)識別正則表達(dá)式了。事實(shí)上，確實(shí)有這么一種表達(dá)方式，可以作為正則表達(dá)式和DFA的橋梁，而且很類似DFA，那就是非確定有限自動機(jī)(NFA)。

還是上面的例子，如果用NFA表示流程圖，就如下圖所示：

看上去很直觀，很有[a|b]*abb的神韻。它轉(zhuǎn)換為狀態(tài)轉(zhuǎn)換表如下：

NFA的定義與DFA區(qū)別不大，M = (K, ∑, f, S, Z)，其中：

K是一個有窮集，它的每個元素稱為一個狀態(tài)；

∑是一個有窮字母表，它的每個元素稱為一個輸入符號，ε表示輸入為空，且ε不存在于∑；

f是轉(zhuǎn)換函數(shù)，是在K×∑*→K上的映射，∑*說明存在遇到ε的情況，f(ki, a)是一個多值函數(shù)；

S∈K是唯一的一個初態(tài)；

Z?K是一個狀態(tài)集，為可接受狀態(tài)或者結(jié)束狀態(tài)。

數(shù)學(xué)上已經(jīng)證明：

DFA，NFA和正則表達(dá)式三者的描述能力是一樣的。

正則表達(dá)式可以轉(zhuǎn)換為NFA，已經(jīng)有成熟的算法實(shí)現(xiàn)這一轉(zhuǎn)換。

NFA可以轉(zhuǎn)換為DFA，也有完美的實(shí)現(xiàn)。

這里不做過多陳述，想了解詳情可以參考《編譯原理》一書。至此，計(jì)算機(jī)識別正則表達(dá)式的過程可以簡化為：正則表達(dá)式→NFA→DFA。不過有時候NFA轉(zhuǎn)換為DFA可能導(dǎo)致狀態(tài)空間的指數(shù)增長，因此直接用NFA識別正則表達(dá)式。

前面已經(jīng)使用python的re模塊，簡單展示了正則表達(dá)式[ab]*abb的匹配過程。下面將結(jié)合幾個常用的正則表達(dá)式例子，展示正則表達(dá)式的強(qiáng)大之處。

開始之前，先來看下python中正則表達(dá)的一些規(guī)定。

w 匹配單詞字符，即[a-zA-Z0-9_]，W 則恰好相反，匹配[^a-zA-Z0-9_];

s 匹配單個的空白字符：space, newline( ), return( ), tab( ), form(f)，即[ fv]，S 相反。

d 匹配數(shù)字[0-9]，D 恰好相反，匹配[^0-9]。

(...) 會產(chǎn)生一個分組，在后面需要時可以用數(shù)組下標(biāo)引用。

(?P...) 會產(chǎn)生命名組，需要時直接用名字引用。

(?!...) 當(dāng)...不出現(xiàn)時匹配，這叫做后向界定符

r"pattern" 此時pattern為原始字符串，其中的""不做特殊處理，r" " 匹配包含""和"n"兩個字符的字符串，而不是匹配新行。當(dāng)一個字符串是原始類型時，Python編譯器不會對其嘗試做任何的替換。關(guān)于原始字符串更多的內(nèi)容可以看stackflow上問題Python regex - r prefix

python中常用到的正則表達(dá)式函數(shù)主要有re.search, re.match, re.findall, re.sub, re.split。

re.findall: 返回所有匹配搜索模式的字符串組成的列表；

re.search: 搜索字符串直到找到匹配模式的字符串，然后返回一個re.MatchObject對象，否則返回None；

re.match: 如果從頭開始的一段字符匹配搜索模式，返回re.MatchObject對象，否則返回None。

re.sub(pattern, repl, string, count=0, flags=0): 返回repl替換pattern后的字符串。

re.split: 在pattern出現(xiàn)的地方分割字符串。

re.search和re.match均可指定開始搜索和結(jié)束搜索的位置，即re.search(string[, pos[, endpos]])和re.match(string[, pos[, endpos]])，此時從pos搜索到endpos。需要注意的是，match總是從起始位置匹配，而search則從起始位置掃描直到遇到匹配。

re.MatchObject默認(rèn)有一個boolean值True，match()和search()在沒有找到匹配時均返回None，因此可以用簡單的if語句判斷是否匹配。

match = re.search(pattern, string)
if match:
    process(match)

re.MatchObject對象主要有以下方法：group([group1, ...])和groups([default])。group返回一個或多個分組，groups返回包含所有分組的元組。

例子1：匹配Hello，當(dāng)且僅當(dāng)后面沒有緊跟著World。

strings = ["HelloWorld!",
           "Hello World!"]
import re
pattern = re.compile(r"Hello(?!World).*")
for string in strings:
    result = pattern.search(string)
    if result:
        print string, "> ", result.group()
    else:
        print string, "> ", "Not match"
"""
outputs:
HelloWorld! >  Not match
Hello World! >  Hello World!
"""

例子2：匹配郵箱地址。目前沒有可以完美表達(dá)郵箱地址的正則表達(dá)式，可以看stackflow上問題Using a regular expression to validate an email address 。這里我們用[w.-]+@[w-]+.[w.-]+來簡單地匹配郵箱地址。

content = """
          alice@google.com
          alice-bob@gmail.._com gmail
          alice.bob@apple.com apple
          alice.bob@gmailcom invalid gmail
          """
import re
address = re.compile(r"[w.-]+@[w-]+.[w.-]+")
print address.findall(content)
"""
outpus:
["alice@google.com", "alice-bob@gmail.._com", "alice.bob@apple.com"]
"""

例子3：給函數(shù)添加裝飾器。

original = """
def runaway():
    print "running away..."
"""
import re
pattern = re.compile(r"def (w+():)")
wrapped = pattern.sub(r"@get_car
def 1", original)
print original, "--->", wrapped, "----"
"""outputs
def runaway():
    print "running away..."
--->
@get_car
def runaway():
    print "running away..."
----
"""

看起來正則表達(dá)式似乎無所不能，但是并不是所有的場合都適合用正則表達(dá)式，許多情況下我們可以找到替代的工具。比如我們想解析一個html網(wǎng)頁，這時候應(yīng)該使用使用 HTML 解析器，stackflow上有一個答案告訴你此時為什么不要使用正則表達(dá)式。python有很多html解析器，比如：

BeautifulSoup 是一個流行的第三方庫

lxml 是一個功能齊全基于 c 的快速的庫

參考
Wiki: Regular expression
正則表達(dá)式和有限狀態(tài)機(jī)
Python Regular Expressions
Python check for valid email address?
Python正則表達(dá)式的七個使用范例
高級正則表達(dá)式技術(shù)
編譯原理: 有窮自動機(jī)