摘要：如果經過一系列輸入，最終如果能達到狀態，則輸入內容一定滿足正則表達式。正則表達式可以轉換為，已經有成熟的算法實現這一轉換。不過有時候轉換為可能導致狀態空間的指數增長，因此直接用識別正則表達式。

原文地址

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

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

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

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

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

這些搜索主要用到了兩種技術：

正則表達式

數據庫索引

這里我們先介紹一下正則表達式。

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

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

正則表達式有以下優點：

容易理解

能高效實現

具有堅實的理論基礎

正則表達式的語法十分簡單，雖然各種編程語言在正則表達式的語法上有細節上的區別，不過主要部分如下：

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

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

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

？表示字符出現0次或者1次

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

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

^ 匹配字符串的開始，$ 匹配字符串的結尾。

回到我們前面的例子中，我們用正則表達式[ab]*abb來匹配由a、b組成的，以abb結尾的字符串。這里[ab]*abb即可以這樣解讀：a或者b重復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"]

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

合法性檢查

文本的自動更正和編輯

信息提取

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

圖中一共有4個狀態S0, S1, S2, S3，在每個狀態基礎上輸入字符a或者b就會進入下一個狀態。如果經過一系列輸入，最終如果能達到狀態S3，則輸入內容一定滿足正則表達式[a|b]*abb。

為了更清晰表述問題，將上圖轉換為狀態轉換表，第一列為當前狀態，第二列為輸入a后當前狀態的跳轉，第三列為輸入b后當前狀態的跳轉。其中S0為起始狀態，S3為接受狀態，從起始狀態起經過一系列輸入到達接受狀態，那么輸入內容即滿足[a|b]*abb。

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

K是一個有窮集，它的每個元素稱為一個狀態；

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

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

S∈K是唯一的一個初態；

Z?K是一個狀態集，為可接受狀態或者結束狀態。

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

下面用字典實現[a|b]*abb的確定有限自動機，然后判斷輸入字符串是否滿足正則表達式。

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識別語言簡單直接，便于用程序實現，但是DFA較難從正則表達式直接轉換。如果我們能找到一種表達方式，用以連接正則表達式和DFA，那么就可以讓計算機識別正則表達式了。事實上，確實有這么一種表達方式，可以作為正則表達式和DFA的橋梁，而且很類似DFA，那就是非確定有限自動機(NFA)。

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

看上去很直觀，很有[a|b]*abb的神韻。它轉換為狀態轉換表如下：

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

K是一個有窮集，它的每個元素稱為一個狀態；

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

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

S∈K是唯一的一個初態；

Z?K是一個狀態集，為可接受狀態或者結束狀態。

數學上已經證明：

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

正則表達式可以轉換為NFA，已經有成熟的算法實現這一轉換。

NFA可以轉換為DFA，也有完美的實現。

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

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

開始之前，先來看下python中正則表達的一些規定。

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

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

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

(...) 會產生一個分組，在后面需要時可以用數組下標引用。

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

(?!...) 當...不出現時匹配，這叫做后向界定符

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

python中常用到的正則表達式函數主要有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出現的地方分割字符串。

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

re.MatchObject默認有一個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，當且僅當后面沒有緊跟著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：匹配郵箱地址。目前沒有可以完美表達郵箱地址的正則表達式，可以看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：給函數添加裝飾器。

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..."
----
"""

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

BeautifulSoup 是一個流行的第三方庫

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

參考
Wiki: Regular expression
正則表達式和有限狀態機
Python Regular Expressions
Python check for valid email address?
Python正則表達式的七個使用范例
高級正則表達式技術
編譯原理: 有窮自動機