思維導(dǎo)圖.png

轉(zhuǎn)載請注明出處：http://www.itdecent.cn/p/5b3316b95fe6

本文出自 容華謝后的博客

往期回顧：

《一起學(xué)習(xí)正則表達(dá)式（一）那些讓人頭暈的元字符》

《一起學(xué)習(xí)正則表達(dá)式（二）量詞與貪婪》

《一起學(xué)習(xí)正則表達(dá)式（三）分組與引用》

《一起學(xué)習(xí)正則表達(dá)式（四）常見的4種匹配模式》

《一起學(xué)習(xí)正則表達(dá)式（五）斷言匹配》

《一起學(xué)習(xí)正則表達(dá)式（六）正則匹配原理》

0.寫在前面

在前面的文章中，我們學(xué)習(xí)了正則表達(dá)式的基礎(chǔ)元字符，貪婪匹配還有一些常用的匹配模式，學(xué)會了這些，工作中的大部分問題，我們都可以做到游刃有余的解決。

But，僅僅是這些還不夠，今天我們一起來學(xué)習(xí)下正則的匹配原理，知其所以還要知其所以然，學(xué)完本篇文章，相信各位可以寫出更加優(yōu)美的正則表達(dá)式。

1.有窮狀態(tài)自動機

如果看過《編譯原理》這本書，對有窮狀態(tài)自動機這個詞一定不陌生，有窮是指一個系統(tǒng)具有有窮個狀態(tài)，不同的狀態(tài)代表不同的意義。自動機是指系統(tǒng)可以根據(jù)相應(yīng)的條件，在不同的狀態(tài)下進行轉(zhuǎn)移，從一個初始狀態(tài)到達(dá)終止?fàn)顟B(tài)。

以正則表達(dá)式 ab|ac 為例：

ab|ac

1 是初始狀態(tài)，輸入 a 后就轉(zhuǎn)移到狀態(tài) 2 上，接著再輸入 b 可以轉(zhuǎn)移到狀態(tài) 3 上，或者輸入 c 可以轉(zhuǎn)移到狀態(tài) 4 上，圖中藍(lán)色的圓圈代表可接受的結(jié)束狀態(tài)，結(jié)束狀態(tài)可以是一個，也可以是多個。

有窮狀態(tài)自動機就是一個識別器，它對每個輸入的字符做識別和判斷，來確定下一步該走向哪里，有窮狀態(tài)狀態(tài)機分為兩種，分別是：

• 確定性有窮自動機（Deterministic Finite Automata，DFA）

• 非確定性有窮自動機（Nondeterministic Finite Automata，NFA）

2.DFA原理

DFA 是確定性有窮自動機的簡稱，因為是確定性的，所以 DFA 的特點是，每一個狀態(tài)都能夠基于下一個輸入的字符，進行確定的轉(zhuǎn)換，以 ab*c 為例：

ab*c

可以看到上圖中，在狀態(tài) 1 下，輸入 a 可以到達(dá)狀態(tài) 2，輸入 c 可以到達(dá)狀態(tài) 3，在狀態(tài) 2 下，輸入 b 還是在狀態(tài) 2，輸入 c 可以到達(dá)狀態(tài) 3，其中的每一步狀態(tài)轉(zhuǎn)移都是確定的。

3.NFA原理

NFA 是非確定性有窮自動機的簡稱，和 DFA 相反，在某些狀態(tài)的輸入下，不能做確定性的狀態(tài)轉(zhuǎn)換，分為兩種情況：

• 同一個輸入字符，可以轉(zhuǎn)換到不同的狀態(tài)

• 接受空字符 ε，也就是不讀入字符就跳轉(zhuǎn)到另一個狀態(tài)上

注：ε：epsilon，音標(biāo)/ep'silon/，中文讀音為“艾普西隆”

現(xiàn)在有這樣一個需求，匹配以字母 a 開頭，字母 b 結(jié)尾，中間是任意多（可以是 0 個）英文小寫字母的字符串，我們可以很快的寫出正則表達(dá)式 a[a-z]*b，看下狀態(tài)圖：

a[a-z]*b

當(dāng)要匹配的目標(biāo)字符串是 aabb 時，在狀態(tài) 1 下，輸入 a 到達(dá)狀態(tài) 2，在狀態(tài) 2 下，輸入第二個 a 還在狀態(tài) 2，這個時候輸入 b，既可以保持在狀態(tài) 2 下，還可以轉(zhuǎn)移到狀態(tài) 3，這個時候狀態(tài)是不確定的，只有輸入第二個 b 之后，才能知道上一步應(yīng)該向什么狀態(tài)轉(zhuǎn)移。

上面的狀態(tài)圖，還可以用 ε-NFA 來表示：

a[a-z]*b（ε-NFA）

ε 代表空字符，如果要匹配的目標(biāo)字符串是 ab，路徑就是：狀態(tài)1 —> a —> 狀態(tài)2 —> ε —> 狀態(tài)5 —> b —> 狀態(tài)6

4.DFA工作機制

DFA 引擎的工作方式是，先看文本再看正則，以文本為主導(dǎo)，舉個栗子：

目標(biāo)字符串：Toady is such a beautiful day

正則表達(dá)式：beau(x|tify|tiful)

想象一下，你手里拿著一張彩票（文本），在看電視中的開獎號碼（正則），看一眼第一個 T 不對，接著 o、a、d、y... 依次看下來，到了 b 終于對了一個，接著又對上了 e、a、u 三個字母，有戲：

text: Toady is such a beautiful day
                         ^
regex: beau(x|tify|tiful)
          ^

繼續(xù)往后看，彩票中 u 的后面是 t，看一眼開獎號碼的三個獎項，一等獎 x 不符合，二等獎和三等獎都是以 t 開頭的：

text: Toady is such a beautiful day
                          ^
regex: beau(x|tify|tiful)
            ^ ^    ^
            ??    ?

接著看彩票的 i、f、u、l 部分，發(fā)現(xiàn)中了三等獎，Congratulations！

text: Toady is such a beautiful day
                          ^
regex: beau(x|tify|tiful)
            ^ ^     ^
            ? ?    ?

可以發(fā)現(xiàn)，DFA 以文本為主導(dǎo)，目標(biāo)字符串只看一遍，不會發(fā)生回溯，相同的字符不會被測試多次。

5.NFA工作機制

NFA 引擎的工作方式和 DFA 相反，是先看正則再看文本，以正則為主導(dǎo)，還是用上面的栗子。

這次是先看開獎號碼（正則），再看你手里的彩票（文本），開獎號碼第一個字母是 b，在彩票中找到了 b，接著看開獎號碼后面的 e，看下彩票中 b 后面是 e，就這樣找到了 beau：

regex: beau(x|tify|tiful)
          ^
text: Toady is such a beautiful day
                         ^

接著再看彩票 beau 的后面是不是 x，發(fā)現(xiàn)不是，一等獎擦肩而過：

regex: beau(x|tify|tiful)
            ^
            ?
text: Toady is such a beautiful day
                          ^

繼續(xù)看二等獎，開獎號碼 t、i、f 都符合，到了 y 發(fā)現(xiàn)彩票里的是 u，二等獎擦肩而過：

regex: beau(x|tify|tiful)
                 ^
                 ?
text: Toady is such a beautiful day
                             ^

再看三等獎，重新從 t 開始比較（回溯，NFA 引擎會記住這里），發(fā)現(xiàn)都符合，又中獎了。

可以發(fā)現(xiàn)，NFA 以正則為主導(dǎo)，會發(fā)生回溯，目標(biāo)字符串的同一部分，有可能會被反復(fù)測試很多次，因此，在最壞的情況下，它的執(zhí)行速度可能會非常慢。

6.POSIX NFA

因為傳統(tǒng)的 NFA 引擎急于報告匹配結(jié)果，找到第一個匹配上的就返回了，所以可能會導(dǎo)致還有更長的匹配未被發(fā)現(xiàn)，比如我們用正則 北京|北京市 來匹配文本 北京市，看下效果：

NFA

可以看到匹配到的結(jié)果是 北京，而 北京市 也是我們想要的匹配結(jié)果，并沒有匹配上，這個時候 POSIX NFA 應(yīng)運而生，它會在找到可能的最長匹配之前進行回溯，也就是說它會匹配最長的目標(biāo)字符串，如果兩邊長度相同，則以左邊的為準(zhǔn)，所以POSIX NFA 引擎的速度要慢于傳統(tǒng)的 NFA 引擎。

看下DFA、傳統(tǒng) NFA 以及 POSIX NFA 引擎的特點：

7.寫在最后

最后在總結(jié)下上面講到的內(nèi)容：

思維導(dǎo)圖

到這里，正則表達(dá)式的匹配原理就講完了，如果有問題可以給我留言評論，謝謝。

正則表達(dá)式在線校驗工具：https://regex101.com/