C#詞法分析器之構(gòu)造NFA詳解

2020-01-24 03:23:25

字體：大中小

供稿：網(wǎng)友

有了上一節(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)的方法。

復(fù)制代碼代碼如下:

namespace Cyjb.Compiler.Lexer {
     class Nfa {
         // 獲取或設(shè)置 NFA 的首狀態(tài)。
         NfaState HeadState { get; set; }
         // 獲取或設(shè)置 NFA 的尾狀態(tài)。
         NfaState TailState { get; set; }
         // 在當(dāng)前 NFA 中創(chuàng)建一個(gè)新狀態(tài)。
         NfaState NewState() {}
     }
 }

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 類的定義：

復(fù)制代碼代碼如下:

namespace Cyjb.Compiler.Lexer {
     class NfaState {
         // 獲取包含當(dāng)前狀態(tài)的 NFA。
         Nfa Nfa;
         // 獲取當(dāng)前狀態(tài)的索引。
         int Index;
         // 獲取或設(shè)置當(dāng)前狀態(tài)的符號索引。
         int SymbolIndex;
         // 獲取或設(shè)置當(dāng)前狀態(tài)的類型。
         NfaStateType StateType;
         // 獲取字符類的轉(zhuǎn)移對應(yīng)的字符類列表。
         ISet<int> CharClassTransition;
         // 獲取字符類轉(zhuǎn)移的目標(biāo)狀態(tài)。
         NfaState CharClassTarget;
         // 獲取 ϵ 轉(zhuǎn)移的集合。
         IList<NfaState> EpsilonTransitions;
         // 添加一個(gè)到特定狀態(tài)的轉(zhuǎn)移。
         void Add(NfaState state, char ch);
         // 添加一個(gè)到特定狀態(tài)的轉(zhuǎn)移。
         void Add(NfaState state, string charClass);
         // 添加一個(gè)到特定狀態(tài)的ε轉(zhuǎn)移。
         void Add(NfaState state);
     }
 }

我在 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 類中使用，代碼如下：

復(fù)制代碼代碼如下:

void BuildNfa(Nfa nfa) {
     nfa.HeadState = nfa.NewState();
     nfa.TailState = nfa.NewState();
     // 添加一個(gè)字符類轉(zhuǎn)移。
     nfa.HeadState.Add(nfa.TailState, charClass);
 }

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)致識(shí)別的結(jié)果不是預(yù)期的。

AlternationExp 類中的代碼如下：

復(fù)制代碼代碼如下:

void BuildNfa(Nfa nfa) {
     NfaState head = nfa.NewState();
     NfaState tail = nfa.NewState();
     left.BuildNfa(nfa);
     head.Add(nfa.HeadState);
     nfa.TailState.Add(tail);
     right.BuildNfa(nfa);
     head.Add(nfa.HeadState);
     nfa.TailState.Add(tail);
     nfa.HeadState = head;
     nfa.TailState = tail;
 }

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 類中的代碼如下：

復(fù)制代碼代碼如下:

void BuildNfa(Nfa nfa) {
     left.BuildNfa(nfa);
     NfaState head = nfa.HeadState;
     NfaState tail = nfa.TailState;
     right.BuildNfa(nfa);
     tail.Add(nfa.HeadState);
     nfa.HeadState = head;
 }

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)造方法：

復(fù)制代碼代碼如下:

void BuildNfa(Nfa nfa) {
     NfaState head = nfa.NewState();
     NfaState tail = nfa.NewState();
     NfaState lastHead = head;
     // 如果沒有上限，則需要特殊處理。
     int times = maxTimes == int.MaxValue ? minTimes : maxTimes;
     if (times == 0) {
         // 至少要構(gòu)造一次。
         times = 1;
     }
     for (int i = 0; i < times; i++) {
         innerExp.BuildNfa(nfa);
         lastHead.Add(nfa.HeadState);
         if (i >= minTimes) {
             // 添加到最終的尾狀態(tài)的轉(zhuǎn)移。
             lastHead.Add(tail);
         }
         lastHead = nfa.TailState;
     }
     // 為最后一個(gè)節(jié)點(diǎn)添加轉(zhuǎn)移。
     lastHead.Add(tail);
     // 無上限的情況。
     if (maxTimes == int.MaxValue) {
         // 在尾部添加一個(gè)無限循環(huán)。
         nfa.TailState.Add(nfa.HeadState);
     }
     nfa.HeadState = head;
     nfa.TailState = tail;
 }

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)。

復(fù)制代碼代碼如下:

View Code 
 HashSet<int> GetCharClass(string charClass) {
     int cnt = charClassList.Count;
     HashSet<int> result = new HashSet<int>();
     CharSet set = GetCharClassSet(charClass);
     if (set.Count == 0) {
         // 不包含任何字符類。
         return result;
     }
     CharSet setClone = new CharSet(set);
     for (int i = 0; i < cnt && set.Count > 0; i++) {
         CharSet cc = charClassList[i];
         set.ExceptWith(cc);
         if (set.Count == setClone.Count) {
             // 當(dāng)前字符類與 set 沒有重疊。
             continue;
         }
         // 得到當(dāng)前字符類與 set 重疊的部分。
         setClone.ExceptWith(set);
         if (setClone.Count == cc.Count) {
             // 完全被當(dāng)前字符類包含，直接添加。
             result.Add(i);
         } else {
             // 從當(dāng)前的字符類中剔除被分割的部分。
             cc.ExceptWith(setClone);
             // 更新字符類。
             int newCC = charClassList.Count;
             result.Add(newCC);
             charClassList.Add(setClone);
             // 更新舊的字符類......
         }
         // 重新復(fù)制 set。
         setClone = new CharSet(set);
     }
     return result;
 }

四、多條正則表達(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。

上一篇：C#詞法分析器之轉(zhuǎn)換DFA詳解

下一篇：C#詞法分析器之正則表達(dá)式的使用