有了上一節(jié)中得到的正則表達(dá)式，那么就可以用來構(gòu)造 NFA 了。NFA 可以很容易的從正則表達(dá)式轉(zhuǎn)換而來，也有助于理解正則表達(dá)式表示的模式。

一、NFA 的表示方法

在這里，一個(gè) NFA 至少具有兩個(gè)狀態(tài)：首狀態(tài)和尾狀態(tài)，如圖 1 所示，正則表達(dá)式 $t$ 對應(yīng)的 NFA 是 N(t)，它的首狀態(tài)是 $H$，尾狀態(tài)是 $T$。圖中僅僅畫出了首尾兩個(gè)狀態(tài)，其它的狀態(tài)和狀態(tài)間的轉(zhuǎn)移都沒有表示出來，這是因?yàn)樵谙旅娼榻B的遞歸算法中，僅需要知道 NFA 的首尾狀態(tài)，其它的信息并不需要關(guān)心。

圖 1 NFA 的表示

我使用下面的 Nfa 類來表示一個(gè) NFA，只包含首狀態(tài)、尾狀態(tài)和一個(gè)添加新狀態(tài)的方法。

NFA 的狀態(tài)中，必要的屬性只有三個(gè)：符號索引、狀態(tài)轉(zhuǎn)移和狀態(tài)類型。只有接受狀態(tài)的符號索引才有意義，它表示當(dāng)前的接受狀態(tài)對應(yīng)的是哪個(gè)正則表達(dá)式，對于其它狀態(tài)，都會(huì)被設(shè)為 -1。

狀態(tài)轉(zhuǎn)移表示如何從當(dāng)前狀態(tài)轉(zhuǎn)移到下一狀態(tài)，雖然 NFA 的定義中，每個(gè)節(jié)點(diǎn)都可能包含多個(gè) ϵ  轉(zhuǎn)移和多個(gè)字符轉(zhuǎn)移（就是邊上標(biāo)有字符的轉(zhuǎn)移）。但在這里，字符轉(zhuǎn)移至多有一個(gè)，這是由之后給出的 NFA 構(gòu)造算法的特點(diǎn)所決定的。

狀態(tài)類型則是為了支持向前看符號而定義的，它可能是 Normal、TrailingHead 和 Trailing 三個(gè)枚舉值之一，這個(gè)屬性將在處理向前看符號的部分詳細(xì)說明。

下面是 NfaState 類的定義：

我在 NfaState 類中額外定義的兩個(gè)屬性 Nfa 和 Index 單純是為了方便狀態(tài)的使用。$\epsilon$ 轉(zhuǎn)移直接被定義為一個(gè)列表，而字符轉(zhuǎn)移則被定義為兩個(gè)屬性：CharClassTarget 和 CharClassTransition，CharClassTarget 表示目標(biāo)狀態(tài)，CharClassTransition 表示字符類，字符類會(huì)在下面詳細(xì)解釋。

NfaState 類中還定義了三個(gè) Add 方法，分別是用來添加單個(gè)字符的轉(zhuǎn)移、字符類的轉(zhuǎn)移和 $\epsilon$ 轉(zhuǎn)移的。

二、從正則表達(dá)式構(gòu)造 NFA

這里使用的遞歸算法是 McMaughton-Yamada-Thompson 算法（或者叫做 Thompson 構(gòu)造法），它比 Glushkov 構(gòu)造法更加簡單易懂。

2.1 基本規(guī)則

對于正則表達(dá)式 $\epsilon$，構(gòu)造如圖 2(a) 的 NFA。對于包含單個(gè)字符 $a$ 的正則表達(dá)式 $\bf{a}$，構(gòu)造如圖 2(b) 的 NFA。

圖 2 基本規(guī)則

上面的第一個(gè)基本規(guī)則在這里其實(shí)是用不到的，因?yàn)樵谡齽t表達(dá)式的定義中，并沒有定義 $\epsilon$。第二個(gè)規(guī)則則在表示字符類的正則表達(dá)式 CharClassExp 類中使用，代碼如下：

2.2 歸納規(guī)則
有了上面的兩個(gè)基本規(guī)則，下面介紹的歸納規(guī)則就可以構(gòu)造出更復(fù)雜的 NFA。

假設(shè)正則表達(dá)式 s  和 t  的 NFA 分別為 N(s)  和 N(t) 。

1. 對于 r=s|t ，構(gòu)造如圖 3 的 NFA，添加一個(gè)新的首狀態(tài) H  和新的尾狀態(tài) T ，然后從 H  到 N(s)  和 N(t)  的首狀態(tài)各有一個(gè) ϵ  轉(zhuǎn)移，從 H  到 N(s)  和 N(t)  的尾狀態(tài)各有一個(gè) ϵ  轉(zhuǎn)移到新的尾狀態(tài) T 。很顯然，到了 H  后，可以選擇是匹配 N(s)  或者是 N(t) ，并最終一定到達(dá) T 。

圖 3 歸納規(guī)則 AlternationExp

這里必須要注意的是，$N(s)$ 和 $N(t)$ 中的狀態(tài)不能夠相互影響，也不能存在任何轉(zhuǎn)移，否則可能會(huì)導(dǎo)致識別的結(jié)果不是預(yù)期的。

AlternationExp 類中的代碼如下：

2. 對于 $r=st$，構(gòu)造如圖 4 的 NFA，將 $N(s)$ 的首狀態(tài)作為 $N(r)$ 的首狀態(tài)，$N(t)$ 的尾狀態(tài)作為 $N(r)$ 的尾狀態(tài)，并在 $N(s)$ 的尾狀態(tài)和 $N(t)$ 的首狀態(tài)間添加一條 $\epsilon$ 轉(zhuǎn)移。

圖 4 歸納規(guī)則 ConcatenationExp

ConcatenationExp 類中的代碼如下：

LiteralExp 也可以看成是多個(gè) CharClassExp 連接而成，所以可以多次應(yīng)用這個(gè)規(guī)則來構(gòu)造相應(yīng)的 NFA。

3. 對于 $r=s*$，構(gòu)造如圖 5 的 NFA，添加一個(gè)新的首狀態(tài) $H$ 和新的尾狀態(tài) $T$，然后添加四條 $\epsilon$ 轉(zhuǎn)移。不過這里的正則表達(dá)式定義中，并沒有顯式定義 $r*$，因此下面給出 RepeatExp 對應(yīng)的規(guī)則。

圖 5 歸納規(guī)則 s*

4. 對于 $r=s\{m,n\}$，構(gòu)造如圖 6 的 NFA，添加一個(gè)新的首狀態(tài) $H$ 和新的尾狀態(tài) $T$，然后創(chuàng)建 $n$ 個(gè) $N(s)$ 并連接起來，并從第 $m - 1$ 個(gè) $N(s)$ 開始，都添加一條尾狀態(tài)到 $T$ 的 $\epsilon$ 轉(zhuǎn)移（如果 $m=0$，就添加從 $H$ 到 $T$ 的 $\epsilon$ 轉(zhuǎn)移）。這樣就保證了至少會(huì)經(jīng)過 $m$ 個(gè) $N(s)$，至多會(huì)經(jīng)過 $n$ 個(gè) $N(s)$。

圖 6 歸納規(guī)則 RepeatExp

不過如果 $n = \infty$，就需要構(gòu)造如圖 7 的 NFA，這時(shí)只需要?jiǎng)?chuàng)建 $m$ 個(gè) $N(s)$，并在最后一個(gè) $N(s)$ 的首尾狀態(tài)之間添加一個(gè)類似于 $s*$ 的 $\epsilon$ 轉(zhuǎn)移，就可以實(shí)現(xiàn)無上限的匹配了。如果此時(shí)再有 $m=0$，情況就與 $s*$ 相同了。

圖 7 歸納規(guī)則 RepeatExp $n = \infty$

綜合上面的兩個(gè)規(guī)則，得到了 RepeatExp 類的構(gòu)造方法：

5. 對于 $r=s/t$ 這種向前看符號，情況要特殊一些，這里僅僅是將 $N(s)$ 和 $N(t)$ 連接起來（同規(guī)則 2）。因?yàn)槠ヅ湎蚯翱捶枙r(shí)，如果 $t$ 匹配成功，那么需要進(jìn)行回溯，來找到 $s$ 的結(jié)尾（這才是真正匹配的內(nèi)容），所以需要將 $N(s)$ 的尾狀態(tài)標(biāo)記為 TrailingHead 類型，并將 $N(T)$ 的尾狀態(tài)標(biāo)記為 Trailing 類型。標(biāo)記之后的處理，會(huì)在下節(jié)轉(zhuǎn)換為 DFA 時(shí)說明。

2.3 正則表達(dá)式構(gòu)造 NFA 的示例

這里給出一個(gè)例子，來直觀的看到一個(gè)正則表達(dá)式 (a|b)*baa 是如何構(gòu)造出對應(yīng)的 NFA 的，下面詳細(xì)的列出了每一個(gè)步驟。

圖 8 正則表達(dá)式 (a|b)*baa 構(gòu)造 NFA 示例

最后得到的 NFA 就如上圖所示，總共需要 14 個(gè)狀態(tài)，在 NFA 中可以很明顯的區(qū)分出正則表達(dá)式的每個(gè)部分。這里構(gòu)造的 NFA 并不是最簡的，因此與上一節(jié)《C# 詞法分析器（三）正則表達(dá)式》中的 NFA 不同。不過 NFA 只是為了構(gòu)造 DFA 的必要存在，不用費(fèi)工夫化簡它。

三、劃分字符類

現(xiàn)在雖然得到了 NFA，但這個(gè) NFA 還是有些細(xì)節(jié)問題需要處理。例如，對于正則表達(dá)式 [a-z]z，構(gòu)造得到的 NFA 應(yīng)該是什么樣的？因?yàn)橐粭l轉(zhuǎn)移只能對應(yīng)一個(gè)字符，所以一個(gè)可能的情形如圖 9 所示。

圖 9 [a-z]z 構(gòu)造的 NFA

前兩個(gè)狀態(tài)間總共需要 26 個(gè)轉(zhuǎn)移，后兩個(gè)狀態(tài)間需要 1 個(gè)轉(zhuǎn)移。如果正則表達(dá)式的字符范圍再廣些呢，比如 Unicode 范圍？添加 6 萬多條轉(zhuǎn)移，顯然無論是時(shí)間還是空間都是不能承受的。所以，就需要利用字符類來減少需要的轉(zhuǎn)移個(gè)數(shù)。

字符類指的是字符的等價(jià)類，意思是一個(gè)字符類對應(yīng)的所有字符，它們的狀態(tài)轉(zhuǎn)移完全是相同的?；蛘哒f，對自動(dòng)機(jī)來說，完全沒有必要區(qū)分一個(gè)字符類中的字符——因?yàn)樗鼈兛偸侵赶蛳嗤臓顟B(tài)。

就像上面的正則表達(dá)式 [a-z]z 來說，字符 a-y 完全沒有必要區(qū)分，因?yàn)樗鼈兛偸侵赶蛳嗤臓顟B(tài)。而字符 z 需要單獨(dú)拿出來作為一個(gè)字符類，因?yàn)樵跔顟B(tài) 1 和 2 之間的轉(zhuǎn)移使得字符 z 和其它字符區(qū)分開來了。因此，現(xiàn)在就得到了兩個(gè)字符類，第一個(gè)字符類對應(yīng)字符 a-y，第二個(gè)字符類對應(yīng)字符 z，現(xiàn)在得到的 NFA 如圖 10 所示。

圖 10 [a-z]z 使用字符類構(gòu)造的 NFA

使用字符類之后，需要的轉(zhuǎn)移個(gè)數(shù)一下就降到了 3 個(gè)，所以在處理比較大的字母表時(shí)，字符類是必須的，它即能加快處理速度，又能降低內(nèi)存消耗。

而字符類的劃分，就是將 Unicode 字符劃分到不同的字符類中的過程。我目前采用的算法是一個(gè)在線算法，即每當(dāng)添加一個(gè)新的轉(zhuǎn)移時(shí)，就會(huì)檢查當(dāng)前的字符類，判斷是否需要對現(xiàn)有字符類進(jìn)行劃分，同時(shí)得到轉(zhuǎn)移對應(yīng)的字符類。字符類的表示是使用一個(gè) ISet<int>，因?yàn)橐粋€(gè)轉(zhuǎn)移可能對應(yīng)于多個(gè)字符類。

初始：字符類只有一個(gè)，表示整個(gè) Unicode 范圍
輸入：新添加的轉(zhuǎn)移 $t$
輸出：新添加的轉(zhuǎn)移對應(yīng)的字符類 $cc_t$
for each (每個(gè)現(xiàn)有的字符類 $CC$) {
　　$cc_1 = \left\{ c|c \in t\& c \in CC \right\}$
　　if ($cc_1= \emptyset$) { continue; }
　　$cc_2 = \left\{ c|c \in CC\& c \notin t \right\}$
　　將 $CC$ 劃分為 $cc_1$ 和 $cc_2$
　　$cc_t = cc_1 \cup cc_t$
　　$t = \left\{ c|c \in t\& c \notin CC \right\}$
　　if ($t = \emptyset$) { break; }
}

這里需要注意的是，每當(dāng)一個(gè)現(xiàn)有的字符類 $CC$ 被劃分為兩個(gè)子字符類 $cc_1$ 和 $cc_2$，之前的所有包含 $CC$ 的轉(zhuǎn)移對應(yīng)的字符類都需要更新為 $cc_1$ 和 $cc_2$，以包含新添加的子字符類。

我在 CharClass 類中實(shí)現(xiàn)了該算法，其中充分利用了 CharSet 類集合操作效率高的特點(diǎn)。

四、多條正則表達(dá)式、限定符和上下文

通過上面的算法，已經(jīng)可以實(shí)現(xiàn)將單個(gè)正則表達(dá)式轉(zhuǎn)換為相應(yīng)的 NFA 了，如果有多條正則表達(dá)式，也非常簡單，只要如圖 11 那樣添加一個(gè)新的首節(jié)點(diǎn)，和多條到每個(gè)正則表達(dá)式的首狀態(tài)的 $\epsilon$ 轉(zhuǎn)移。最后得到的 NFA 具有一個(gè)起始狀態(tài)和 $n$ 個(gè)接受狀態(tài)。

圖 11 多條正則表達(dá)式的 NFA

對于行尾限定符，可以直接看成預(yù)定義的向前看符號，r\$ 可以看成 r/\n 或 r/\r?\n（這樣可以支持 Windows 換行和 Unix 換行），事實(shí)上也是這么做的。

對于行首限定符，僅當(dāng)在行首時(shí)才會(huì)匹配這條正則表達(dá)式，可以考慮把這樣的正則表達(dá)式單獨(dú)拿出來——當(dāng)從行首開始匹配時(shí)，就使用行首限定的正則表達(dá)式進(jìn)行匹配；從其它位置開始匹配時(shí)，就使用其它的正則表達(dá)式進(jìn)行匹配。

當(dāng)然，即使是從行首開始匹配，非行首限定的正則表達(dá)式也是可以匹配的，所以就將所有正則表達(dá)式分為兩個(gè)集合，一個(gè)包含所有的正則表達(dá)式，用于從行首匹配是使用；另一個(gè)只包含非行首限定的正則表達(dá)式，用于從其它位置開始匹配時(shí)使用。然后，再為這兩個(gè)集合分別構(gòu)造出相應(yīng)的 NFA。

對于我的詞法分析器，還會(huì)支持上下文?？梢詾槊總€(gè)正則表達(dá)式指定一個(gè)或多個(gè)上下文，這個(gè)正則表達(dá)式就會(huì)只在給定的上下文環(huán)境中生效。利用上下文機(jī)制，就可以更精細(xì)的控制字符串的匹配情況，還可能構(gòu)造出更強(qiáng)大的詞法分析器，例如可以在匹配字符串的同時(shí)處理字符串內(nèi)的轉(zhuǎn)義字符。

上下文的實(shí)現(xiàn)與上面行首限定符的思想相同，就是為將每個(gè)上下文對應(yīng)的正則表達(dá)式分為一組，并分別構(gòu)造 NFA。如果某個(gè)正則表達(dá)式屬于多個(gè)上下文，就會(huì)將它復(fù)制并分到多個(gè)組中。

假設(shè)現(xiàn)在定義了 $N$ 個(gè)上下文，那么加上行首限定符，總共需要將正則表達(dá)式分為 $2N$ 個(gè)集合，并為每個(gè)集合分別構(gòu)造 NFA。這樣不可避免的會(huì)有一些內(nèi)存浪費(fèi)，但字符串匹配速度會(huì)非常快，而且可以通過壓縮的辦法一定程度上減少內(nèi)存的浪費(fèi)。如果通過為每個(gè)狀態(tài)維護(hù)特定的信息來實(shí)現(xiàn)上下文和行首限定符的話，雖然 NFA 變小了，但存儲(chǔ)每個(gè)狀態(tài)的信息也會(huì)消耗額外的內(nèi)存，在匹配時(shí)還會(huì)出現(xiàn)很多回溯的情況（回溯是性能殺手），效果可能并不好。

雖然需要構(gòu)造 $2N$ 個(gè) NFA，但其實(shí)只需要構(gòu)造一個(gè)具有 $2N$ 個(gè)起始狀態(tài)的 NFA 即可，每個(gè)起始狀態(tài)對應(yīng)于一個(gè)上下文的（非）行首限定正則表達(dá)式集合，這樣做是為了保證這 $2N$ 個(gè) NFA 使用的字符類是同一個(gè)，否則后面處理起來會(huì)非常麻煩。

現(xiàn)在，正則表達(dá)式對應(yīng)的 NFA 就構(gòu)造好了，下一篇文章中，我就會(huì)介紹如何將 NFA 轉(zhuǎn)換為等價(jià)的 DFA。

最新評論