C#詞法分析器之構造NFA詳解

2020-01-24 03:23:25

字體：大中小

來源：轉載

供稿：網友

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

一、NFA 的表示方法

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

圖 1 NFA 的表示

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

復制代碼代碼如下:

namespace Cyjb.Compiler.Lexer {
     class Nfa {
         // 獲取或設置 NFA 的首狀態。
         NfaState HeadState { get; set; }
         // 獲取或設置 NFA 的尾狀態。
         NfaState TailState { get; set; }
         // 在當前 NFA 中創建一個新狀態。
         NfaState NewState() {}
     }
 }

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

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

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

下面是 NfaState 類的定義：

復制代碼代碼如下:

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

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

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

二、從正則表達式構造 NFA

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

2.1 基本規則

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

圖 2 基本規則

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

復制代碼代碼如下:

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

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

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

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

圖 3 歸納規則 AlternationExp

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

AlternationExp 類中的代碼如下：

復制代碼代碼如下:

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$，構造如圖 4 的 NFA，將 $N(s)$ 的首狀態作為 $N(r)$ 的首狀態，$N(t)$ 的尾狀態作為 $N(r)$ 的尾狀態，并在 $N(s)$ 的尾狀態和 $N(t)$ 的首狀態間添加一條 $/epsilon$ 轉移。

圖 4 歸納規則 ConcatenationExp

ConcatenationExp 類中的代碼如下：

復制代碼代碼如下:

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 也可以看成是多個 CharClassExp 連接而成，所以可以多次應用這個規則來構造相應的 NFA。

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

圖 5 歸納規則 s*

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

圖 6 歸納規則 RepeatExp

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

圖 7 歸納規則 RepeatExp $n = /infty$

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

復制代碼代碼如下:

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) {
         // 至少要構造一次。
         times = 1;
     }
     for (int i = 0; i < times; i++) {
         innerExp.BuildNfa(nfa);
         lastHead.Add(nfa.HeadState);
         if (i >= minTimes) {
             // 添加到最終的尾狀態的轉移。
             lastHead.Add(tail);
         }
         lastHead = nfa.TailState;
     }
     // 為最后一個節點添加轉移。
     lastHead.Add(tail);
     // 無上限的情況。
     if (maxTimes == int.MaxValue) {
         // 在尾部添加一個無限循環。
         nfa.TailState.Add(nfa.HeadState);
     }
     nfa.HeadState = head;
     nfa.TailState = tail;
 }

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

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

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

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

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

三、劃分字符類

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

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

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

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

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

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

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

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

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

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

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

復制代碼代碼如下:

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) {
             // 當前字符類與 set 沒有重疊。
             continue;
         }
         // 得到當前字符類與 set 重疊的部分。
         setClone.ExceptWith(set);
         if (setClone.Count == cc.Count) {
             // 完全被當前字符類包含，直接添加。
             result.Add(i);
         } else {
             // 從當前的字符類中剔除被分割的部分。
             cc.ExceptWith(setClone);
             // 更新字符類。
             int newCC = charClassList.Count;
             result.Add(newCC);
             charClassList.Add(setClone);
             // 更新舊的字符類......
         }
         // 重新復制 set。
         setClone = new CharSet(set);
     }
     return result;
 }

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

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

圖 11 多條正則表達式的 NFA

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

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

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

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

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

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

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

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

上一篇：C#詞法分析器之轉換DFA詳解

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