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

一、NFA 的表示方法

在這里，一個 NFA 至少具有兩個狀態(tài)：首狀態(tài)和尾狀態(tài)，如圖 1 所示，正則表達式 $t$ 對應的 NFA 是 N(t)，它的首狀態(tài)是 $H$，尾狀態(tài)是 $T$。圖中僅僅畫出了首尾兩個狀態(tài)，其它的狀態(tài)和狀態(tài)間的轉移都沒有表示出來，這是因為在下面介紹的遞歸算法中，僅需要知道 NFA 的首尾狀態(tài)，其它的信息并不需要關心。

圖 1 NFA 的表示

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

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

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

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

下面是 NfaState 類的定義：

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

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

二、從正則表達式構造 NFA

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

2.1 基本規(guī)則

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

圖 2 基本規(guī)則

上面的第一個基本規(guī)則在這里其實是用不到的，因為在正則表達式的定義中，并沒有定義 $\epsilon$。第二個規(guī)則則在表示字符類的正則表達式 CharClassExp 類中使用，代碼如下：

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

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

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

圖 3 歸納規(guī)則 AlternationExp

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

AlternationExp 類中的代碼如下：

2. 對于 $r=st$，構造如圖 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$ 轉移。

圖 4 歸納規(guī)則 ConcatenationExp

ConcatenationExp 類中的代碼如下：

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

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

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

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

圖 6 歸納規(guī)則 RepeatExp

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

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

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

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

2.3 正則表達式構造 NFA 的示例

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

圖 8 正則表達式 (a|b)*baa 構造 NFA 示例

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

三、劃分字符類

現(xiàn)在雖然得到了 NFA，但這個 NFA 還是有些細節(jié)問題需要處理。例如，對于正則表達式 [a-z]z，構造得到的 NFA 應該是什么樣的？因為一條轉移只能對應一個字符，所以一個可能的情形如圖 9 所示。

圖 9 [a-z]z 構造的 NFA

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

字符類指的是字符的等價類，意思是一個字符類對應的所有字符，它們的狀態(tài)轉移完全是相同的?；蛘哒f，對自動機來說，完全沒有必要區(qū)分一個字符類中的字符——因為它們總是指向相同的狀態(tài)。

就像上面的正則表達式 [a-z]z 來說，字符 a-y 完全沒有必要區(qū)分，因為它們總是指向相同的狀態(tài)。而字符 z 需要單獨拿出來作為一個字符類，因為在狀態(tài) 1 和 2 之間的轉移使得字符 z 和其它字符區(qū)分開來了。因此，現(xiàn)在就得到了兩個字符類，第一個字符類對應字符 a-y，第二個字符類對應字符 z，現(xiàn)在得到的 NFA 如圖 10 所示。

圖 10 [a-z]z 使用字符類構造的 NFA

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

而字符類的劃分，就是將 Unicode 字符劃分到不同的字符類中的過程。我目前采用的算法是一個在線算法，即每當添加一個新的轉移時，就會檢查當前的字符類，判斷是否需要對現(xiàn)有字符類進行劃分，同時得到轉移對應的字符類。字符類的表示是使用一個 ISet<int>，因為一個轉移可能對應于多個字符類。

初始：字符類只有一個，表示整個 Unicode 范圍
輸入：新添加的轉移 $t$
輸出：新添加的轉移對應的字符類 $cc_t$
for each (每個現(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; }
}

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

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

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

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

圖 11 多條正則表達式的 NFA

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

對于行首限定符，僅當在行首時才會匹配這條正則表達式，可以考慮把這樣的正則表達式單獨拿出來——當從行首開始匹配時，就使用行首限定的正則表達式進行匹配；從其它位置開始匹配時，就使用其它的正則表達式進行匹配。

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

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

上下文的實現(xiàn)與上面行首限定符的思想相同，就是為將每個上下文對應的正則表達式分為一組，并分別構造 NFA。如果某個正則表達式屬于多個上下文，就會將它復制并分到多個組中。

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

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

現(xiàn)在，正則表達式對應的 NFA 就構造好了，下一篇文章中，我就會介紹如何將 NFA 轉換為等價的 DFA。

最新評論