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

更新時(shí)間：2013年05月03日 09:57:59 作者：

本篇文章介紹了，C#詞法分析器之正則表達(dá)式的使用。需要的朋友參考下

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

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

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

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

正則表達(dá)式

描述

單個(gè)字符 x。

除了換行以外的任意單個(gè)字符。

[xyz]

一個(gè)字符類，表示 'x'，'y'，'z' 中的任意一個(gè)字符。

[a-z]

一個(gè)字符類，表示 'a' 到 'z' 之間的任意一個(gè)字符（包含 'a' 和 'z'）。

[^a-z]

一個(gè)字符類，表示除了 [a-z] 之外的任意一個(gè)字符。

[a-z-[b-f]]

一個(gè)字符類，表示 [a-z] 范圍減去 [b-f] 范圍的字符，等價(jià)于 [ag-z]。

將任意正則表達(dá)式 r 重復(fù) 0 次或多次。

將 r 重復(fù) 1 次或多次。

將 r 重復(fù) 0 次或 1 次，即“可選”的 r。

r{m,n}

將 r 重復(fù) m 次至 n 次（包含 m 和 n）。

r{m,}

將 r 重復(fù) m 次或多次（大于等于 m 次）。

r{m}

將 r 重復(fù)恰好 m 次。

{name}

展開(kāi)預(yù)先定義的正則表達(dá)式 “name”，可以通過(guò)預(yù)先定義一些正則表達(dá)式，以實(shí)現(xiàn)簡(jiǎn)化正則表達(dá)式。

"[xyz]\"foo"

原義字符串，表示字符串“[xyz]"foo”，用法與 C# 中定義字符串基本相同。

表示 X 字符轉(zhuǎn)義，如果 X 是 'a','b','t','r','v','f','n' 或 'e'，表示相應(yīng)的 ASCII 字符；如果 X 是 'w','W','s','S','d' 或 'D'，則表示相應(yīng)的字符類；否則表示字符 X。

\nnn

表示使用八進(jìn)制形式指定的字符，nnn 最多由三位數(shù)字組成。

\xnn

表示使用十六進(jìn)制形式指定的字符，nn 恰好由兩位數(shù)字組成。

\cX

表示 X 指定的 ASCII 控制字符。

\unnnn

表示使用十六進(jìn)制形式指定的 Unicode 字符，nnnn 恰好由四位數(shù)字組成。

\p{name}

表示 name 指定的 Unicode 通用類別或命名塊中的單個(gè)字符。

\P{name}

表示除了 name 指定的 Unicode 通用類別或命名塊之外的單個(gè)字符。

(r)

表示 r 本身。

(?r-s:pattern)

應(yīng)用或禁用子正則表達(dá)式中指定的選項(xiàng)。選項(xiàng)可以是字符 'i','s' 或 'x'。

'i' 表示不區(qū)分大小寫(xiě)；'-i' 表示區(qū)分大小寫(xiě)。
's' 表示允許 '.' 匹配換行符；'-s' 表示不允許 '.' 匹配換行符。
'x' 表示忽略模式中的空白和注釋，除非使用 '\' 字符轉(zhuǎn)義或者在字符類中，或者使用雙引號(hào)（""）括起來(lái)；'-x' 表示不忽略空白。

以下下兩列中的模式是等價(jià)的：

(?:foo)	(foo)
(?i:ab7)	([Aa][Bb]7)
(?-i:ab)	(ab)
(?s:.)	[\u0000-\uFFFF]
(?-s:.)	[^\n\r]
(?ix-s: a . b)	([Aa][^\n\r][Bb])
(?x:a b)	("ab")
(?x:a\ b)	("a b")
(?x:a" "b)	("a b")
(?x:a[ ]b)	("a b")
(?x:a (?#comment) c)	(abc)

(?#comment)

表示注釋，注釋中不允許出現(xiàn)右括號(hào) ')'。

r 與 s 的連接。

r|s

r 與 s 的并。

r/s

僅當(dāng) r 后面跟著 s 時(shí)，才匹配 r。這里 '/' 表示向前看，s 并不會(huì)被匹配。

行首限定符，僅當(dāng) r 在一行的開(kāi)頭時(shí)才匹配。

行尾限定符，僅當(dāng) r 在一行的結(jié)尾時(shí)才匹配。這里的行尾可以是 '\n'，也可以是 '\r\n'。

<s>r

僅當(dāng)當(dāng)前是上下文 s 時(shí)才匹配 r。

<s1,s2>r

僅當(dāng)當(dāng)前是上下文 s1 或 s2 時(shí)才匹配 r。

<*>r

在任意上下文中匹配 r。

<<EOF>>

表示在文件的結(jié)尾。

<s1,s2><<EOF>>

表示在上下文 s1 或 s2 時(shí)的文件的結(jié)尾。

這里與字符類和 Unicode 通用類別相關(guān)的知識(shí)請(qǐng)參考 C# 的正則表達(dá)式語(yǔ)言 - 快速參考中的“字符類”小節(jié)。大部分的正則表達(dá)式表示方法也與 C# 中的相同，有所不同的向前看（r/s）、上下文（<s>r）和文件結(jié)尾（<<EOF>>）會(huì)在之后的文章中解釋。

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

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

二、正則表達(dá)式的表示

雖然上面定義了正則表達(dá)式的規(guī)則，但它們表示起來(lái)卻很簡(jiǎn)單，我使用 Cyjb.Compiler.RegularExpressions 命名空間下的 8 個(gè)類來(lái)表示任意的正則表達(dá)式，其類圖如下所示：

圖 1 正則表達(dá)式類圖

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

將 CharClassExp、LiteralExp、RepeatExp、AlternationExp、ConcatenationExp 這些類進(jìn)行嵌套，就可以表示大部分正則表達(dá)式了；AnchorExp 單獨(dú)拿出來(lái)是因?yàn)樗荒茏鳛樽钔鈱拥恼齽t表達(dá)式，而不能位于其它正則表達(dá)式內(nèi)部；EndOfFileExp 則是專門(mén)用于 <<EOF>> 的。這里并未考慮上下文，因?yàn)樯舷挛牡奶幚聿⒉辉谡齽t表達(dá)式這里，而是在之后的“終結(jié)符符定義”部分。

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

三、正則表達(dá)式

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

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

有窮自動(dòng)機(jī)分為兩類：

不確定的有窮自動(dòng)機(jī)（Nondeterministic Finite Automata，NFA）對(duì)其邊上的標(biāo)號(hào)沒(méi)有任何限制。一個(gè)符號(hào)標(biāo)記離開(kāi)同一狀態(tài)的多條邊，并且空串 $\epsilon$ 也可以作為標(biāo)號(hào)。確定的有窮自動(dòng)機(jī)（Deterministic Finite Automata，DFA）對(duì)于每個(gè)狀態(tài)及自動(dòng)機(jī)輸入字母表中的每個(gè)符號(hào)有且只有一條離開(kāi)該狀態(tài)、以該符號(hào)為標(biāo)號(hào)的邊。

NFA 和 DFA 可以識(shí)別的語(yǔ)言集合是相同的（后面會(huì)說(shuō)到 NFA 如何轉(zhuǎn)換為等價(jià)的 DFA），并且這些語(yǔ)言的集合正好是能夠用正則表達(dá)式描述的語(yǔ)言集合（正則表達(dá)式可以轉(zhuǎn)換為等價(jià)的 NFA）。因此，采用有窮自動(dòng)機(jī)來(lái)識(shí)別正則表達(dá)式描述的語(yǔ)言，也是很自然的。

3.1 不確定的有窮自動(dòng)機(jī) NFA

一個(gè)不確定的有窮自動(dòng)機(jī)（NFA）由以下幾個(gè)部分組成：

一個(gè)有窮的狀態(tài)集合 $S$。一個(gè)輸入符號(hào)集合 $\Sigma$，即輸入字母表（input alphabet）。我們假設(shè)空串 $\epsilon$ 不是 $\Sigma$ 中的元素。一個(gè)轉(zhuǎn)換函數(shù)（transition function），它為每個(gè)狀態(tài)和 $\Sigma \cup \{ \epsilon \}$ 的每個(gè)符號(hào)都給出了相應(yīng)的后繼狀態(tài)（next state）的集合。$S$ 中的一個(gè)狀態(tài) $s_0$ 被指定為開(kāi)始狀態(tài)，或者說(shuō)初始狀態(tài)。$S$ 的一個(gè)子集 $F$ 被指定為接受狀態(tài)（或者說(shuō)終止?fàn)顟B(tài)）的集合。

下圖就是一個(gè)能識(shí)別正則表達(dá)式 (a|b)*baa 的語(yǔ)言的 NFA，邊上的字母就是該邊的標(biāo)號(hào)。

圖 2 NFA 實(shí)例

NFA 的匹配過(guò)程很直觀，從起始狀態(tài)開(kāi)始，每讀入一個(gè)符號(hào)，NFA 就可以沿著這個(gè)符號(hào)對(duì)應(yīng)的邊前進(jìn)到下一個(gè)狀態(tài)（$\epsilon$ 邊不用讀入符號(hào)也可以前進(jìn)，當(dāng)然也可以不前進(jìn)），就這樣不斷讀入符號(hào)，直到所有符號(hào)都讀入進(jìn)來(lái)，如果最后到達(dá)的是接受狀態(tài)，那么匹配成功，否則匹配失敗。

在狀態(tài) 1 上，有兩條標(biāo)號(hào)為 b 的邊，一條指向狀態(tài) 1，一條指向狀態(tài) 2，這就使自動(dòng)機(jī)產(chǎn)生了不確定性——當(dāng)?shù)竭_(dá)狀態(tài) 1 時(shí)，如果讀入的字符是 'b'，那么并不能確定應(yīng)該轉(zhuǎn)移到狀態(tài) 1 還是 2，此時(shí)就需要使用集合保存所有可能的狀態(tài)，把它們都嘗試一遍才可以。

接下來(lái)嘗試用這個(gè) NFA 去匹配字符串 "ababaa"。

步驟當(dāng)前節(jié)點(diǎn)讀入字符轉(zhuǎn)移到節(jié)點(diǎn)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}

此時(shí)字符串已經(jīng)全部讀入，最后到達(dá)了狀態(tài) 1 和 4，其中狀態(tài) 4 是一個(gè)接受狀態(tài)，因此 NFA 返回結(jié)果“是”。

使用 NFA 進(jìn)行模式匹配的時(shí)間復(fù)雜度是 $O(k(n + m))$，其中 $k$ 為要匹配的字符串的長(zhǎng)度，$n$ 為 NFA 中的狀態(tài)數(shù)，$m$ 為 NFA 中的轉(zhuǎn)移數(shù)?？梢?jiàn)，NFA 的效率與輸入字符串的長(zhǎng)度和 NFA 的大小成正比，效率并不高。

3.2 確定的有窮自動(dòng)機(jī) DFA

確定的有窮自動(dòng)機(jī)（DFA）是 NFA 的一個(gè)特例，其中：

沒(méi)有輸入 $\epsilon$ 之上的轉(zhuǎn)換動(dòng)作。對(duì)每個(gè)狀態(tài) $s$ 和每個(gè)輸入符號(hào) $a$，有且只有一條標(biāo)號(hào)為 $a$ 的邊離開(kāi)。

因此，NFA 抽象的表示了用來(lái)識(shí)別某個(gè)語(yǔ)言中串的算法，而相應(yīng)的 DFA 則是具體的識(shí)別串的算法。

下圖是同樣識(shí)別正則表達(dá)式 (a|b)*baa 的語(yǔ)言的 DFA，看起來(lái)比 NFA 的要復(fù)雜不少。

圖 3 DFA 實(shí)例

DFA 的匹配過(guò)程則更加簡(jiǎn)單，因?yàn)闆](méi)有了 $\epsilon$ 轉(zhuǎn)換和不確定的轉(zhuǎn)換，只要從起始狀態(tài)開(kāi)始，每讀入一個(gè)符號(hào)，就直接沿著這個(gè)符號(hào)對(duì)應(yīng)的邊前進(jìn)到下一個(gè)狀態(tài)（這個(gè)狀態(tài)是唯一的），就這樣不斷讀入符號(hào)，直到所有符號(hào)都讀入進(jìn)來(lái)，如果最后到達(dá)的是接受狀態(tài)，那么匹配成功，否則匹配失敗。

接下來(lái)嘗試用這個(gè) DFA 去匹配字符串 "ababaa"。

步驟當(dāng)前節(jié)點(diǎn)讀入字符轉(zhuǎn)移到節(jié)點(diǎn)10a020b131a242b151a262a3

此時(shí)字符串已經(jīng)全部讀入，最后到達(dá)了狀態(tài) 3，是一個(gè)接受狀態(tài)，因此 DFA 返回結(jié)果“是”。

使用 DFA 進(jìn)行模式匹配的時(shí)間復(fù)雜度是 $O(k)$，其中 $k$ 為要匹配的字符串的長(zhǎng)度，可見(jiàn)，DFA 的效率只與輸入字符串的長(zhǎng)度有關(guān)，效率非常高。

3.3 為什么使用 DFA

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

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

不過(guò) NFA 還是有用的，因?yàn)?DFA 要利用 NFA，通過(guò)子集構(gòu)造法得到；將正則表達(dá)式轉(zhuǎn)換為 NFA，也有助于理解如何處理多條正則表達(dá)式和處理向前看。下一篇文章就開(kāi)始介紹 NFA 的表示以及如何將正則表達(dá)式轉(zhuǎn)換為 NFA。

您可能感興趣的文章: