正則表達式是一種描述詞素的重要表示方法。雖然正則表達式并不能表達出所有可能的模式（例如“由等數量的 a 和 b 組成的字符串”），但是它可以非常高效的描述處理詞法單元時要用到的模式類型。

一、正則表達式的定義
正則表達式可以由較小的正則表達式按照規則遞歸地構建。每個正則表達式 r  表示一個語言 L(r) ，而語言可以認為是一個字符串的集合。正則表達式有以下兩個基本要素：

1.ϵ  是一個正則表達式， L(ϵ)=ϵ ，即該語言只包含空串（長度為 0 的字符串）。
2.如果 a  是一個字符，那么 a  是一個正則表達式，并且 L(a)={a} ，即該語言只包含一個長度為 1  的字符串 a 。
由小的正則表達式構造較大的正則表達式的步驟有以下四個部分。假定 r  和 s  都是正則表達式，分別表示語言 L(r)  和 L(s) ，那么：

1.(r)|(s)  是一個正則表達式，表示語言 L(r)∪L(s) ，即屬于 L(r)  的字符串和屬于 L(s)  的字符串的集合（ L(r)∪L(s)={s|s∈L(r) or s∈L(s)} ）。
2.(r)(s)  是一個正則表達式，表示語言 L(r)L(s) ，即從 L(r)  中任取一個字符串，再從 L(s)  中任取一個字符串，然后將它們連接后得到的所有字符串的集合（ L(r)L(s)={st|s∈L(r) and t∈L(s)} ）。
3.(r)∗  是一個正則表達式，表示語言 L(r)∗ ，即將 L(r)  連接 0  次或多次后得到的語言。
4.(r)  是一個正則表達式，表示語言 L(r) 。
上面這些規則都是由 Kleene 在 20 世紀 50 年代提出的，在之后有出現了很多針對正則表達式的擴展，他們被用來增強正則表達式表述字符串模式的能力。這里采用是類似 Flex 的正則表達式擴展，風格則類似于 .Net 內置的正則表達式：

利用上面的表格中列出擴展正則表達式，就可以比較方便的定義需要的模式了。不過有些需要注意的地方：

1. 這里的定義不支持 POSIX Style 的字符類，例如 [:alnum:] 之類的，與 Flex 不同。
2. $ 匹配行尾，即可以匹配 /n 也可以匹配 /r/n，也與 Flex 不同。
3. 字符集的相減是 C# 風格的 [a-z-[b-f]]，而不是 Flex 那樣的 [a-c]{-}[b-z]。
4. 向前看中的 $ 只表示 '$'，而不再匹配行尾，例如 a/b$ 僅當 "a" 后面是 "b$" 時才匹配 "a"。

二、正則表達式的表示

雖然上面定義了正則表達式的規則，但它們表示起來卻很簡單，我使用 Cyjb.Compiler.RegularExpressions 命名空間下的 8 個類來表示任意的正則表達式，其類圖如下所示：

圖 1 正則表達式類圖

其中，Regex 類是正則表達式的基類，CharClassExp 表示字符類（單個字符），LiteralExp 表示原義文本（多個字符組成的字符串），RepeatExp 表示正則表達式重復（可以重復上限至下限之間的任意次數），AlternationExp 表示正則表達式的并（r|s），ConcatenationExp 表示正則表達式的連接（rs），AnchorExp 表示行首限定、行尾限定和向前看，EndOfFileExp 表示文件的結尾（<<EOF>>）。

將 CharClassExp、LiteralExp、RepeatExp、AlternationExp、ConcatenationExp 這些類進行嵌套，就可以表示大部分正則表達式了；AnchorExp 單獨拿出來是因為它只能作為最外層的正則表達式，而不能位于其它正則表達式內部；EndOfFileExp 則是專門用于 <<EOF>> 的。這里并未考慮上下文，因為上下文的處理并不在正則表達式這里，而是在之后的“終結符符定義”部分。

正則表達式的表示比較簡單，但為了更加易用，有必要提供從字符串（例如 "abc[0-9]+"）轉換為相應的正則表達式的轉換方法。RegexCharClass 類是System.Text.RegularExpressions.RegexCharClass 類的包裝，用于表示一個字符類，我對其中的某些函數進行了修改，以符合我這里的正則表達式定義。RegexOptions 類和 RegexParser 類則是用于正則表達式解析的類，具體的解析算法太過復雜，就不多加解釋。

三、正則表達式

正則表達式構造好后，就需要使用它去匹配詞素。一個詞法分析器可能需要定義很多正則表達式，還可能包括上下文以及行首限定符，處理起來還是比較復雜的。為了簡便起見，我會首先討論怎么用一條正則表達式去匹配字符串，在之后的文章中再討論如何用組合多條正則表達式去匹配詞素。

使用正則表達式匹配字符串，一般都會用到有窮自動機（finite automata）的表示方法。有窮自動機是識別器（recognizer），只能對每個可能的輸入回答“是”或“否”，表示時候與此自動機相匹配?；蛘哒f，不斷的讀入字符，直到有窮自動機回答“是”，此刻就正確的匹配了一個字符串。

有窮自動機分為兩類：

不確定的有窮自動機（Nondeterministic Finite Automata，NFA）對其邊上的標號沒有任何限制。一個符號標記離開同一狀態的多條邊，并且空串 $/epsilon$ 也可以作為標號。確定的有窮自動機（Deterministic Finite Automata，DFA）對于每個狀態及自動機輸入字母表中的每個符號有且只有一條離開該狀態、以該符號為標號的邊。

NFA 和 DFA 可以識別的語言集合是相同的（后面會說到 NFA 如何轉換為等價的 DFA），并且這些語言的集合正好是能夠用正則表達式描述的語言集合（正則表達式可以轉換為等價的 NFA）。因此，采用有窮自動機來識別正則表達式描述的語言，也是很自然的。

3.1 不確定的有窮自動機 NFA

一個不確定的有窮自動機（NFA）由以下幾個部分組成：

一個有窮的狀態集合 $S$。一個輸入符號集合 $/Sigma$，即輸入字母表（input alphabet）。我們假設空串 $/epsilon$ 不是 $/Sigma$ 中的元素。一個轉換函數（transition function），它為每個狀態和 $/Sigma /cup /{ /epsilon /}$ 的每個符號都給出了相應的后繼狀態（next state）的集合。$S$ 中的一個狀態 $s_0$ 被指定為開始狀態，或者說初始狀態。$S$ 的一個子集 $F$ 被指定為接受狀態（或者說終止狀態）的集合。

下圖就是一個能識別正則表達式 (a|b)*baa 的語言的 NFA，邊上的字母就是該邊的標號。

圖 2 NFA 實例

NFA 的匹配過程很直觀，從起始狀態開始，每讀入一個符號，NFA 就可以沿著這個符號對應的邊前進到下一個狀態（$/epsilon$ 邊不用讀入符號也可以前進，當然也可以不前進），就這樣不斷讀入符號，直到所有符號都讀入進來，如果最后到達的是接受狀態，那么匹配成功，否則匹配失敗。

在狀態 1 上，有兩條標號為 b 的邊，一條指向狀態 1，一條指向狀態 2，這就使自動機產生了不確定性――當到達狀態 1 時，如果讀入的字符是 'b'，那么并不能確定應該轉移到狀態 1 還是 2，此時就需要使用集合保存所有可能的狀態，把它們都嘗試一遍才可以。

接下來嘗試用這個 NFA 去匹配字符串 "ababaa"。

步驟當前節點讀入字符轉移到節點1{0, 1}a{1}2{1}b{1, 2}3{1, 2}a{1, 3}4{1, 3}b{1, 2}5{1, 2}a{1, 3}6{1, 3}a{1, 4}

此時字符串已經全部讀入，最后到達了狀態 1 和 4，其中狀態 4 是一個接受狀態，因此 NFA 返回結果“是”。

使用 NFA 進行模式匹配的時間復雜度是 $O(k(n + m))$，其中 $k$ 為要匹配的字符串的長度，$n$ 為 NFA 中的狀態數，$m$ 為 NFA 中的轉移數。可見，NFA 的效率與輸入字符串的長度和 NFA 的大小成正比，效率并不高。

3.2 確定的有窮自動機 DFA

確定的有窮自動機（DFA）是 NFA 的一個特例，其中：

沒有輸入 $/epsilon$ 之上的轉換動作。對每個狀態 $s$ 和每個輸入符號 $a$，有且只有一條標號為 $a$ 的邊離開。

因此，NFA 抽象的表示了用來識別某個語言中串的算法，而相應的 DFA 則是具體的識別串的算法。

下圖是同樣識別正則表達式 (a|b)*baa 的語言的 DFA，看起來比 NFA 的要復雜不少。

圖 3 DFA 實例

DFA 的匹配過程則更加簡單，因為沒有了 $/epsilon$ 轉換和不確定的轉換，只要從起始狀態開始，每讀入一個符號，就直接沿著這個符號對應的邊前進到下一個狀態（這個狀態是唯一的），就這樣不斷讀入符號，直到所有符號都讀入進來，如果最后到達的是接受狀態，那么匹配成功，否則匹配失敗。

接下來嘗試用這個 DFA 去匹配字符串 "ababaa"。

步驟當前節點讀入字符轉移到節點10a020b131a242b151a262a3

此時字符串已經全部讀入，最后到達了狀態 3，是一個接受狀態，因此 DFA 返回結果“是”。

使用 DFA 進行模式匹配的時間復雜度是 $O(k)$，其中 $k$ 為要匹配的字符串的長度，可見，DFA 的效率只與輸入字符串的長度有關，效率非常高。

3.3 為什么使用 DFA

上面介紹的 NFA 和 DFA 識別語言的能力是相同的，但在詞法分析中實際使用的都是 DFA，是有下面幾種原因。

NFA 的匹配效率比不過 DFA 的，詞法分析器顯然運行的越快越好。雖然 DFA 的構造則要花費很長時間，一般是 $O(r^3)$，最壞情況下可能會是 $O(r^22^r)$，但在詞法分析器這一特定領域中，DFA 只需要構造一次，就可以多次使用，而且 Flex 可以在生成源代碼的時候就構造好 DFA，耗點時間也沒有關系。DFA 在最壞情況下可能會使狀態個數呈指數增長，《編譯原理》上給出了一個例子 $(a|b)*a(a|b)^{n-1}$，識別這個正則表達式的 NFA 具有 $n+1$ 個狀態，而 DFA 卻至少有 $2^n$ 個狀態，不過這么特殊的情況在編程語言中基本不會見到，不用擔心這一點。

不過 NFA 還是有用的，因為 DFA 要利用 NFA，通過子集構造法得到；將正則表達式轉換為 NFA，也有助于理解如何處理多條正則表達式和處理向前看。下一篇文章就開始介紹 NFA 的表示以及如何將正則表達式轉換為 NFA。