陳梓瀚 vczh@163.com http://www./vczh/

1、問題概述

隨著計算機語言的結(jié)構(gòu)越來越復(fù)雜，為了開發(fā)優(yōu)秀的編譯器，人們已經(jīng)漸漸感到將詞 法分析獨立出來做研究的重要性。不過詞法分析器的作用卻不限于此。回想一下我們的老師剛剛開始向我們講述程序設(shè)計的時候，總是會出一道題目：給出一個填入 了四則運算式子的字符串，寫程序計算該式子的結(jié)果。除此之外，我們有時候建立了比較復(fù)雜的配置文件，譬如XML的時候，分析器首先也要對該文件進行詞法分 析，把整個字符串?dāng)喑闪艘粋€一個比較短小的記號(指的是具有某種屬性的字符串)，之后才進行結(jié)構(gòu)上的分析。再者，在實現(xiàn)某種控制臺應(yīng)用程序的時候，程序需 要分析用戶打進屏幕的命令。如果該命令足夠復(fù)雜的話，我們也首先要對這個命令進行詞法分析，之后得到的結(jié)果會大大方便進行接下去的工作。

當(dāng)然，這些問題大部分已經(jīng)得到了解決，而且歷史上也有人做出了各種各樣專門的或 者通用的工具(Lex、正則表達式引擎等)來解決這一類問題。我們在使用這種工具的時候，為了更加高效地書寫配置，或者我們在某種特殊情況下需要自己制作 類似的工具，就需要了解詞法分析背后的原理。本文將給出一個構(gòu)造通用詞法分析工具所需要的原理。由于實現(xiàn)的代碼過長，本文將不附帶實現(xiàn)。

究竟什么是“把一個字符串?dāng)喑梢恍┯浱?#8221;呢？我們先從四則運算式子入手。一個四 則運算式子是一個字符數(shù)列，可是我們關(guān)心的對象實際上是操作符、括號和數(shù)字。于是此法分析的作用就是把一個字符串?dāng)嚅_成我們關(guān)心的帶有屬性的記號。舉個例 子：(11+22)*(33+44)是一個合法的四則運算式子，如果輸入是(左括號,”(“) (數(shù)字,”11”) (一級操作符,”+”) (數(shù)字,”22”) (右括號,”)”) (二級操作符,”*”) (左括號,”(“) (數(shù)字,”33”) (一級操作符,”+”) (數(shù)字,”44”) (右括號,”)”)的話，我們在檢查結(jié)構(gòu)的時候只需要關(guān)心這個記號的屬性(也就是左括號、右括號、數(shù)字、操作符等)就行了，具體計算的時候才需要關(guān)心這個 記號實際上的內(nèi)容。如果式子里邊有空格的話，我們也僅僅需要把空格當(dāng)成是一種記號類型，在詞法分析得出結(jié)果之后，將具有空格屬性的記號丟棄掉就可以了，接 下去的步驟不需變化。

但需要注意的是，詞法分析得到的結(jié)果是沒有層次結(jié)構(gòu)的，所有的記號都是等價的對象。我們在計算表達式的時候把+和*看成了不同層次的操作符，類似的結(jié)構(gòu)是具有嵌套的層次的。詞法分析不能得出嵌套層次結(jié)構(gòu)的信息，最多只能得到關(guān)于重復(fù)結(jié)構(gòu)的信息。

2、正則表達式

我們現(xiàn)在需要尋找一種可以描述記號類型的工具，在此之前我們首先研究一下常見的記號的結(jié)構(gòu)。為了表示出具有某種共性的字符串的集合，我們需要書寫出一些能代表字符串集合的規(guī)則。這個集合中的所有成員都將被認為是一種特定類型的記號。

首先，規(guī)則可以把一個特定的字符或者是空字符串認為是一種類型的記號的全部。上文所說到的四則運算式子的例子，“左括號”這種類型的記號就僅僅對應(yīng)著字符”(“，其他的字符或者字符串都不可能是“左括號”這個類型的記號。

其次，規(guī)則可以進行串聯(lián)。串聯(lián)的意思是這樣 的，我們可以讓一個字符串的前綴符合某一個指定的規(guī)則，剩下的部分的前綴符合第二個規(guī)則，剩下的部分的前綴符合第三個規(guī)則等等，一直到最后一個部分的全部 要符合最后一個規(guī)則。如果我們把”function”這個字符串作為一個記號類型來處理的話，我們可以把”function”這個字符串替換成8個串聯(lián)的 規(guī)則：”f”,”u”,”n”,”c”,”t”,”i”,”o”,”n”。首先，字符串”function”的前綴”f”符合規(guī)則”f”，剩下的部 分”unction”的前綴”u”符合規(guī)則”u”，等等，一直到最后一個部分”n”的全部符合規(guī)則”n”。

第三，規(guī)則可以進行并聯(lián)。并聯(lián)的意思就是， 如果一個字符串符合一系列規(guī)則中的其中一個的話，我們就說這個字符串符合這一些規(guī)則的并聯(lián)。于是這些規(guī)則的并聯(lián)就構(gòu)成了一個新的規(guī)則。一個典型的例子就是 判斷一個字符串是否關(guān)鍵字。關(guān)鍵字可以是”if”，可以是”else”，可以是”while”等等。當(dāng)然，一個關(guān)鍵字是不可能同時符合這些規(guī)則的，不過只 要一個字符串符合這些規(guī)則的其中一個的話，我們就說這個字符串是關(guān)鍵字。于是，關(guān)鍵字這個規(guī)則就是”if”、”else”、”while”等規(guī)則的并聯(lián)。

第四，一個規(guī)則可以是可選的。可選的規(guī)則實 際上是屬于并聯(lián)的一種特殊形式。加入我們需要規(guī)則”abc”和”abcde”并聯(lián)，我們會發(fā)現(xiàn)這兩個規(guī)則有著相同的前綴”abc”，而且這個前綴恰好就是 其中的一個規(guī)則。于是我們可以把規(guī)則改寫成”abc”與””和”de”的并聯(lián)的串聯(lián)。但是規(guī)則””指定的規(guī)則是空串，因此這個規(guī)則與”de”的并聯(lián)就可以 看成是一個可選的規(guī)則”de”。

第五，規(guī)則可以被重復(fù)。有限次的重復(fù)可以使 用串聯(lián)表示，但是如果我們不想限制重復(fù)的次數(shù)的話，串聯(lián)就沒法表示這個規(guī)則了，于是我們引入了“重復(fù)”。一個典型的例子就是程序設(shè)計語言的標識符。標識符 可以是一個變量的名字或者是其他東西。一門語言通常沒有規(guī)定變量名的最大長度。因此為了表示這個規(guī)則，就需要將52個字母進行并聯(lián)，然后對這個規(guī)則進行重 復(fù)。

上述的5種構(gòu)造規(guī)則的方法中，后面的4個方法被用于把規(guī)則組合成為更大的規(guī)則。為了給出這種規(guī)則的形式化表示，我們引入了一種范式。這種范式有以下語法：

1：字符用雙引號包圍起來，空串使用ε代替。

2：兩個規(guī)則頭尾連接代表規(guī)則的串聯(lián)。

3：兩個規(guī)則使用 | 隔開代表規(guī)則的并聯(lián)。

4：規(guī)則使用[]包圍代表該規(guī)則是可選的，規(guī)則使用{}包圍代表該規(guī)則是重復(fù)的。

5：規(guī)則使用()包圍代表該規(guī)則是一個整體，通常用于改變操作符 | 的優(yōu)先級。

舉個例子，一個實數(shù)的規(guī)則書寫如下：

{“0”|”1”|”2”|”3”|”4”|”5”|”6”|”7”|”8”|”9”}”.”[{“0”|”1”|”2”|”3”|”4”|”5”|”6”|”7”|”8”|”9”}]。

但是，我們?nèi)绾伪硎?#8220;不是數(shù)字的其他字符呢”？字符的數(shù)量是有限的，因此我們可 以使用規(guī)則的并聯(lián)來表示。但是所有的字符實在是太多（ASCII字符集有127個字符，UTF-16字符集有65535個字符），因此后來人們想出了各種 各樣的簡化規(guī)則書寫的辦法。比較著名的有BNF范式。BNF范式經(jīng)常被用于理論研究，但是更加實用的是正則表達式。

正則表達式的字符不需要用雙引號括起來，但是如果需要表示一些被定義了的字符 (如 “|” )的話，就使用轉(zhuǎn)義字符的方法表示(如 “\|”)。其次，X?代表[X]，X+代表{X}，X*代表[{X}]。字符集合可以用區(qū)間來表示，[0-9]可以表示 “0”|”1”|”2”|”3”|”4”|”5”|”6”|”7”|”8”|”9”，[^0-9]則表示“除了數(shù)字以外的其他字符”。正則表達式還有各種 各樣的其他規(guī)則來簡化我們的書寫，不過由于本文并不是“精通正則表達式”，因此我們只保留若干比較本質(zhì)的操作來進行詞法分析原理的描述。

正則表達式的表達能力極強，小數(shù)的規(guī)則可以使用[0-9]+.[0-9]來表示，C語言的注釋可以表示為/\*([^\*]|\*+[^\*/])*\*+/來表示。

3、有窮狀態(tài)自動機

人閱讀正則表達式會比較簡單，但是機器閱讀正則表達式就是一件非常困難的事情 了。而且，直接使用正則表達式進行匹配配的話，不僅工作量大，而且速度緩慢。因此我們還需要另外一種專門為機器設(shè)計的表達方式。本文在以后的章節(jié)中會給出 一種算法把正則表達式轉(zhuǎn)換為機器可以閱讀的形式，就是這一章節(jié)所描述的有窮狀態(tài)自動機。

有窮狀態(tài)自動機這個名字聽起來比較可怕，不過實際上這種自動機并沒有想象中的那 么復(fù)雜。狀態(tài)機的這種概念被廣泛的應(yīng)用在各種各樣的領(lǐng)域中。軟件工程的統(tǒng)一建模語言(UML)有狀態(tài)圖，數(shù)字邏輯中也有狀態(tài)轉(zhuǎn)移圖。不過這些各種各樣的圖 在本質(zhì)上都跟狀態(tài)機沒有什么區(qū)別。我將會通過一個例子來講述狀態(tài)的實際意義。

假設(shè)我們現(xiàn)在需要檢查一個字符串中a的數(shù)量和b的數(shù)量是否都是偶數(shù)。當(dāng)然我們可 以用一個正則表達式來描述它。不過對于這個問題來說，用正則表達式來描述遠遠不如構(gòu)造狀態(tài)機方便。我們可以設(shè)計出一個狀態(tài)的集合，然后指定集合中的某一個 元素為“起始狀態(tài)”。其實狀態(tài)就是在工作還沒開始的時候，分析器所處的狀態(tài)。分析器在每一次進行一項新的工作的時候，都要把狀態(tài)重置為起始狀態(tài)。分析器每 讀入一個字符就修改一次狀態(tài)，修改的方法我們也可以指定。分析器在讀完所有的字符以后，必然停留在一個確定的狀態(tài)中。如果這個狀態(tài)跟我們所期望的狀態(tài)一致 的話，我們就說這個分析器接受了這個字符串，否則我們就說這個分析器拒絕了這個字符串。

如何通過設(shè)計狀態(tài)及其轉(zhuǎn)移方法來實現(xiàn)一個分析器呢？當(dāng)然，如果一個字符串僅僅包 含a或者b的話，那么分析器的狀態(tài)只有四種：“奇數(shù)a奇數(shù)b”、“奇數(shù)a偶數(shù)b”、“偶數(shù)a奇數(shù)b”、“偶數(shù)a偶數(shù) b”。我們把這些狀態(tài)依次命名為aa、aB、Ab、AB。大寫代表偶數(shù)，小寫代表奇數(shù)。當(dāng)工作還沒開始的時候，分析器已經(jīng)讀入的字符串是空串，那么理所當(dāng) 然的起始狀態(tài)應(yīng)當(dāng)是AB。當(dāng)分析器讀完所有字符的時候，我們期望讀入的字符串的a和b的數(shù)量都是偶數(shù)，那么結(jié)束的狀態(tài)也應(yīng)該是AB。于是我們給出這樣的一 個狀態(tài)圖：

圖3.1

檢查一個字符串是否由偶數(shù)個a和偶數(shù)個b組成的狀態(tài)圖

在這個狀態(tài)圖里，有一個短小的箭頭指向了AB，代表AB這個狀態(tài)是初始狀態(tài)。 AB狀態(tài)有粗的邊緣，代表AB這個狀態(tài)是結(jié)束的可接受狀態(tài)。一個狀態(tài)圖的結(jié)束狀態(tài)可以是一個或者多個。在這個例子里，起始狀態(tài)和結(jié)束狀態(tài)剛好是同一個狀 態(tài)。標有字符”a”的箭頭從AB指向aB，代表如果分析器處于狀態(tài)AB并且讀入的字符是a的話，就轉(zhuǎn)移到狀態(tài)aB上。

我們把這個狀態(tài)圖應(yīng)用在兩個字符串上，分別是”abaabbba”和”aababbaba”。其中，第一個字符串是可以接受的，第二個字符串是不可接受的(因為有5個a和4個b)。

分析第一個字符串的時候，狀態(tài)機所經(jīng)過的狀態(tài)是：

AB[a]aB[b]ab[a]Ab[a]ab[b]aB[b]ab[b]aB[a]AB

分析第二個字符串的時候，狀態(tài)機所經(jīng)過的狀態(tài)是：

AB[a]aB[a]AB[b]Ab[a]ab[b]aB[b]ab[a]Ab[b]AB[a]aB

第一個字符串”abaabbba”讓狀態(tài)機在狀態(tài)AB上停了下來，于是這個字符串是可以接受的。第二個字符串”aababbaba”讓狀態(tài)機在狀態(tài)aB上停了下來，于是這個字符串是不可以接受的。

在機器內(nèi)部表示這個狀態(tài)圖的話，我們可以使用一種比較簡單的方法。這種方法僅僅把狀態(tài)與狀態(tài)之間的箭頭、起始狀態(tài)和結(jié)束狀態(tài)集合記錄下來。對應(yīng)于這個狀態(tài)圖的話，我們就可以把這個狀態(tài)圖表示成以下形式：

起始狀態(tài)：AB

結(jié)束狀態(tài)集合：AB

(AB,a,aB)

(AB,b,Ab)

(aB,a,AB)

(aB,b,ab)

(Ab,a,ab)

(Ab,b,AB)

(ab,a,Ab)

(ab,b,aB)

用一個狀態(tài)圖來表示狀態(tài)機的時候有時候會遇到確定性與非確定性的問題。所謂的確 定性就是指對于任何一個狀態(tài)，輸入一個字符都可以跳轉(zhuǎn)到另一個確定的狀態(tài)中去。確定性和非確定性的區(qū)別有一個直觀的描述：狀態(tài)圖的任何一個狀態(tài)都可以有不 定數(shù)量的邊指向另一個狀態(tài)，如果在這些邊里面，存在兩條邊，它們所承載的字符如果相同，那么這個狀態(tài)輸入這個就字符可以跳轉(zhuǎn)到另外兩個狀態(tài)中去，于是該狀 態(tài)機就是不確定的。如圖所示：

圖3.2

正則表達式ba*b的一個確定的狀態(tài)機表示

圖3.3

正則表達式ba*b的一個非確定的狀態(tài)機表示

圖3.3中的狀態(tài)機的起始狀態(tài)讀入字符b后可以跳轉(zhuǎn)到中間的兩個狀態(tài)里，因此這個狀態(tài)機是非確定的。相反，圖3.2中的狀態(tài)機，雖然功能跟圖3.3的狀態(tài)機一致，但卻是確定的。我們還可以使用一種特殊的邊來進行狀態(tài)的轉(zhuǎn)換。我們用ε邊來表示一個狀態(tài)可以不讀入字符就跳轉(zhuǎn)到另一個狀態(tài)上。下圖給出了一個跟圖3.3功能一致的包含ε邊的非確定的狀態(tài)機：

圖3.4

正則表達式ba*b的一個帶有ε邊的非確定的狀態(tài)機

在教科書中，通常把確定的有窮狀態(tài)自動機(有窮狀態(tài)自動機也就是本文討論的這種狀態(tài)機)稱為DFA，把非確定的有窮狀態(tài)自動機稱為NFA，把帶有ε邊的非確定的狀態(tài)機稱為ε-NFA。下文中也將采用這幾個術(shù)語來指示各種類型的有窮狀態(tài)自動機。

在剛剛接觸到ε邊的時候，一個通常的疑問就是這種邊存在的理由。事實上如果是人 直接畫狀態(tài)機的話，有時候也可以直接畫出一個確定的狀態(tài)機，復(fù)雜一點的話也可以畫出一個非確定的狀態(tài)機，在有些極端的情況下我們需要使用ε邊來更加簡潔的 表示我們的意圖。不過ε邊存在的最大的理由就是：我們可以通過使用ε邊來給出一個簡潔的算法把一個正則表達式轉(zhuǎn)換成ε-NFA。

4、從正則表達式到ε-NFA

通過第二節(jié)所描述的內(nèi)容，我們知道一個正則表達式的基本元素就是字符集。通過對 規(guī)則的串聯(lián)、并聯(lián)、重復(fù)、可選等操作，我們可以構(gòu)造除更復(fù)雜的正則表達式。如果從正則表達式構(gòu)造狀態(tài)機的時候也可以用這幾種操作對狀態(tài)圖進行組合的話，那 么方法將會變得很簡單。接下來我們將一一對這5個構(gòu)造正則表達式的方法進行討論。使用下文描述的算法構(gòu)造出來的所有ε-NFA都有且只有一個結(jié)束狀態(tài)。

1：字符集

字符集是正則表達式最基本的元素，因此反映到狀態(tài)圖上，字符集也會是構(gòu)成狀態(tài)圖的基本元素。對于字符集C，如果有一個規(guī)則只接受C的話，這個規(guī)則對應(yīng)的狀態(tài)圖將會被構(gòu)造成以下形式：

圖4.1

這個狀態(tài)圖的初始狀態(tài)是Start，結(jié)束狀態(tài)是End。Start狀態(tài)讀入字符集C跳轉(zhuǎn)到End狀態(tài)，不接受其他字符集。

2：串聯(lián)

如果我們使用A⊙B表示規(guī)則A和規(guī)則B的串聯(lián)，我們可以很容易的知道串聯(lián)這個操 作具有結(jié)合性，也就是說(A⊙B)⊙C=A⊙(B⊙C)。因此對于n個規(guī)則的串聯(lián)，我們只需要先將前n-1個規(guī)則進行串連，然后把得到的規(guī)則看成一個整 體，跟最后一個規(guī)則進行串聯(lián)，那么就得到了所有規(guī)則的串聯(lián)。如果我們知道如何將兩個規(guī)則串聯(lián)起來的話，也就等于知道了如何把n個規(guī)則進行串聯(lián)。

為了將兩個串聯(lián)的規(guī)則轉(zhuǎn)換成一個狀態(tài)圖，我們只需要先將這兩個規(guī)則轉(zhuǎn)換成狀態(tài) 圖，然后讓第一個狀態(tài)的結(jié)束狀態(tài)跳轉(zhuǎn)到第二個狀態(tài)圖的起始狀態(tài)。這種跳轉(zhuǎn)必須是不讀入字符的跳轉(zhuǎn)，也就是令這兩個狀態(tài)等價。因此，第一個狀態(tài)圖跳轉(zhuǎn)到了結(jié) 束狀態(tài)的時候，就可以當(dāng)成第二個狀態(tài)圖的起始狀態(tài)，繼續(xù)第二個規(guī)則的檢查。因此我們使用了ε邊連接兩個狀態(tài)圖：

圖4.2

3：并聯(lián)

并聯(lián)的方法跟串聯(lián)類似。為了可以在起始狀態(tài)讀入一個字符的時候就知道這個字符可 能走的是并聯(lián)的哪一些分支并進行跳轉(zhuǎn)，我們需要先把所有分支的狀態(tài)圖構(gòu)造出來，然后把起始狀態(tài)連接到所有分支的起始狀態(tài)上。而且，在某個分支成功接受了一 段字符串之后，為了讓那個狀態(tài)圖的結(jié)束狀態(tài)反映在整個狀態(tài)圖的結(jié)束狀態(tài)上，我們也把所有分支的結(jié)束狀態(tài)都連接到大規(guī)則的結(jié)束狀態(tài)上。如下所示：

圖4.3

4：重復(fù)

對于一個重復(fù)，我們可以設(shè)立兩個狀態(tài)。第一個狀態(tài)是起始狀態(tài)，第二個狀態(tài)是結(jié)束狀態(tài)。當(dāng)狀態(tài)走到結(jié)束狀態(tài)的時候，如果遇到一個可以讓規(guī)則接受的字符串，則再次回到結(jié)束狀態(tài)。這樣的話就可以用一個狀態(tài)圖來表示重復(fù)了。于是對于重復(fù)，我們可以構(gòu)造狀態(tài)圖如下所示：

圖4.4

5：可選

為可選操作建立狀態(tài)圖比較簡單。為了完成可選操作，我們需要在接受一個字符的時 候，如果字符串的前綴被當(dāng)前規(guī)則接受則走當(dāng)前規(guī)則的狀態(tài)圖，如果可選規(guī)則的后續(xù)規(guī)則接受了字符串則走后續(xù)規(guī)則的狀態(tài)圖，如果都接受的話就兩個圖都要走。為 了達到這個目的，我們把規(guī)則的狀態(tài)圖的起始狀態(tài)和結(jié)束狀態(tài)連接起來，得到了如下狀態(tài)圖：

圖4.5

如果重復(fù)使用的是0次以上重復(fù)，也就是原來的重復(fù)加上可選的結(jié)果，那么可以簡單地把圖4.4的Start狀態(tài)去掉，讓End狀態(tài)同時擁有起始狀態(tài)和結(jié)束狀態(tài)兩個角色，[Start]和[End]則保持原狀。

至此，我們已經(jīng)將5種構(gòu)造狀態(tài)圖的辦法都對應(yīng)到了5種構(gòu)造規(guī)則的辦法上了。對于 任意的一個正則表達式，我們僅需要把這個表達式還原成那5種構(gòu)造的嵌套，然后把每一步構(gòu)造都對應(yīng)到一個狀態(tài)圖的構(gòu)造上，就可以將一個正則表達式轉(zhuǎn)換成一個 ε-NFA了。舉個例子，我們使用正則表達式來表達“一個字符串僅包含偶數(shù)個a和偶數(shù)個b”，然后把它轉(zhuǎn)換成ε-NFA。

我們先對這個問題進行分析。如果一個字符串僅包含偶數(shù)個a和偶數(shù)個b的話，那么 這個字符串一定是偶數(shù)長度的。于是我們可以把這個字符串分割成兩個兩個的字符段。而且這些字符段只有四種：aa、bb、ab和ba。對于aa和bb來說， 無論出現(xiàn)多少次都不會影響字符串中a和b的數(shù)量的奇偶性(理由：在一個模2加法系統(tǒng)里，0是不變項，也就是說對于任何屬于模2加法的數(shù)X有X+0 = 0+X = X)。對于ab和ba的話，如果一個字符串的開始和結(jié)束是ab或者ba，中間的部分是aa或者bb的任意組合，這個字符串也是具有偶數(shù)個a和偶數(shù)個b的。 我們現(xiàn)在得到了兩種構(gòu)造偶數(shù)個a和偶數(shù)個b的字符串的方法。把串聯(lián)、并聯(lián)、可選、重復(fù)等操作應(yīng)用在這些字符串上，仍然會得到具有偶數(shù)個a和偶數(shù)個b的字符 串。于是我們可以把正則表達式書寫成以下形式：

((aa|bb)|((ab|ba)(aa|bb)*(ab|ba)))*

根據(jù)上文提到的方法，我們可以把這個正則表達式轉(zhuǎn)換成以下狀態(tài)機：

圖4.6

至此，我們已經(jīng)得到了把一個正則表達式轉(zhuǎn)換為ε-NFA的方法了。但是只得到ε-NFA還是不行的，因為ε-NFA的不確定性太大了，直接根據(jù)ε-NFA跑的話，每一次都會得到大量的臨時狀態(tài)集合，會極大地降低效率。因此，我們還需要一個辦法消除一個狀態(tài)機的非確定性。

5、消除非確定性

消除ε邊算法

我們見到的有窮狀態(tài)自動機一共有三種：ε-NFA、NFA和DFA?，F(xiàn)在我們需 要將ε-NFA轉(zhuǎn)換為DFA。一個DFA中不可能出現(xiàn)ε邊，所以我們首先要消除ε邊。消除ε邊算法基于一個很簡單的想法：如果狀態(tài)A通過ε邊到達狀態(tài)B的 話，那么狀態(tài)A無需讀入字符就可以直達狀態(tài)B。如果狀態(tài)B需要讀入字符x才可以到達狀態(tài)C的話，那么狀態(tài)A讀入x也可以到達狀態(tài)C。因為從A到C的路徑是 A B C，其中A到B不需要讀入字符。

于是我們會得到一個很自然的想法：消除從狀態(tài)A出發(fā)的ε邊，只需要尋找所有從A 開始僅通過ε邊就可以到達的狀態(tài)，并把從這些狀態(tài)觸出發(fā)的非ε邊復(fù)制到A上即可。剩下的工作就是刪除所有的ε邊和一些因為消除ε邊而變得不可到達的狀態(tài)。 為了更加形象地描述消除ε邊算法，我們從正則表達式(ab|cd)*構(gòu)造一個ε-NFA，并在此狀態(tài)機上應(yīng)用消除ε邊算法。

正則表達式(ab|cd)*的狀態(tài)圖如下所示：

圖5.1

1：找到所有有效狀態(tài)。

有效狀態(tài)就是在完成了消除ε邊算法之后仍然存在的狀態(tài)。我們可以在開始整個算法 之前就預(yù)先計算出所有有效狀態(tài)。有效狀態(tài)的特點是存在非ε邊的輸入。同時，起始狀態(tài)也是一個有效狀態(tài)。結(jié)束狀態(tài)不一定是有效狀態(tài)，但是如果存在一個有效狀 態(tài)可以僅通過ε邊到達結(jié)束狀態(tài)的話，那么這個狀態(tài)應(yīng)該被標記為結(jié)束狀態(tài)。因此對一個ε-NFA應(yīng)用消除ε邊算法產(chǎn)生的NFA可能出現(xiàn)多個結(jié)束狀態(tài)。不過起 始狀態(tài)仍然只有一個。

我們可以把“存在非ε邊的輸入或者起始狀態(tài)”這個判斷方法應(yīng)用在圖5.1每一個狀態(tài)上，計算出圖5.1中所有的有效狀態(tài)。結(jié)果如下圖所示。

圖5.2

所有非有效狀態(tài)的標簽都被刪除

如果一個狀態(tài)同時具有ε邊和非ε邊輸入的話，那么這個狀態(tài)仍然是有效狀態(tài)。因為所有的有效狀態(tài)在下一步的操作中，都會得到新的輸出和新的輸入。

2：添加所有必要的邊

接下來我們要對所有的有效狀態(tài)都應(yīng)用一個算法。這個算法分成兩步。第一步是尋找 一個狀態(tài)的ε閉包，第二步是把這個狀態(tài)的ε閉包看成一個整體，把所有從這個閉包中輸出的邊全部復(fù)制到當(dāng)前狀態(tài)上。從標記有效狀態(tài)的結(jié)果我們得到了圖5.1 狀態(tài)圖的有效狀態(tài)集合是{S/E 3 5 7 9}。我們依次對這些狀態(tài)應(yīng)用上述算法。第一步，計算S/E狀態(tài)的ε閉包。所謂一個狀態(tài)的ε閉包就是從這個狀態(tài)出發(fā)，僅通過ε邊就可以到達的所有狀態(tài)的集合。下圖中標記出了狀態(tài)S/E的ε閉包：

圖5.3

現(xiàn)在，我們把狀態(tài)S/E從狀態(tài)S/E的ε閉包中排除出去。因為從狀態(tài)A輸出的非 ε邊都屬于從狀態(tài)A的ε閉包中輸出的非ε邊，復(fù)制這些邊是沒有任何價值的。接下來就是找到從狀態(tài)S/E的ε閉包中輸出的非ε邊。在圖5.3我們可以很容易 地發(fā)現(xiàn)，從狀態(tài)1和狀態(tài)6(見圖5.1的狀態(tài)標簽)分別輸出到狀態(tài)3和狀態(tài)7的標記了a或者b的邊，就是我們所要尋找的邊。接下來我們把這些邊復(fù)制到狀態(tài) S/E上，邊的目標狀態(tài)仍然保持不變，可以得到下圖：

圖5.4

至此，這個算法在S/E上的應(yīng)用就結(jié)束了，接下來我們分別對剩下的有效狀態(tài){3 5 7 9}分別應(yīng)用此算法，可以得到下圖：

圖5.5

紅色的邊為新增加的邊

3：刪除所有ε邊和無效狀態(tài)

這一步操作是消除ε邊算法的最后步驟。我們只需要刪除所有的ε邊和無效狀態(tài)就完成了整個消除ε邊算法。現(xiàn)在我們對圖5.5的狀態(tài)機應(yīng)用第三步，得到如下狀態(tài)圖：

圖5.6

不過并不是只有新增的邊才不被刪除。根據(jù)定義，所有從有效狀態(tài)出發(fā)的非ε邊都是不能刪除的邊。

我們通過把消除ε邊算法應(yīng)用在圖5.1的狀態(tài)機上，得到了圖5.6這個DFA。但是并不是所有的消除ε邊算法都可以直接從ε-NFA直接得到DFA，這個其實跟正則表達式本身有關(guān)。至于什么正則表達式可以達到這個效果這里就不深究了。但是因為有可能產(chǎn)生NFA，所以我們還需要一個算法把NFA轉(zhuǎn)換成DFA。

從NFA到DFA

NFA是非確定性的狀態(tài)機，DFA是確定性的狀態(tài)機。確定性和非確定性的最大區(qū) 別就是：從一個狀態(tài)讀入一個字符，確定性的狀態(tài)機得到一個狀態(tài)，而非確定性的狀態(tài)機得到一個狀態(tài)的集合。如果我們把NFA的起始狀態(tài)S看成一個集合{S} 的話，對于一個狀態(tài)集合S’，給定一個輸入，就可以用NFA計算出對應(yīng)的狀態(tài)集合T’。因此我們在構(gòu)造DFA的時候，只需要把起始狀態(tài)對應(yīng)到S’，并且找 到所有可能在NFA同時出現(xiàn)的狀態(tài)集合，把這些集合都轉(zhuǎn)換成DFA的一個狀態(tài)，那么任務(wù)就完成了。因為NFA的狀態(tài)是有限的，所以NFA所有狀態(tài)的集合的 冪集的元素個數(shù)也是有限的，因此使用這個方法構(gòu)造DFA是完全可能的。

為了形象地表達出這個算法的過程，我們將構(gòu)造一個正則表達式，然后給出該正則表達式轉(zhuǎn)換成NFA的結(jié)果，并把構(gòu)造DFA的算法應(yīng)用在NFA上。假設(shè)一個字符串只有a、b和c三種字符，判斷一個字符串是不是以abc開始并且以cba結(jié)束正則表達式如下：

abc(a|b|c)*cba

通過上文的算法，可以得出如下圖所示的NFA：

圖5.7

現(xiàn)在我們開始構(gòu)造DFA，具體算法如下：

1：把{S}放進隊列L和集合D中。其中S是NFA的起始狀態(tài)。隊列L放置的是未被處理的已經(jīng)創(chuàng)建了的DFA狀態(tài)，集合D放置的是已經(jīng)存在的DFA狀態(tài)。根據(jù)上文的討論，DFA的每一個狀態(tài)都對應(yīng)著NFA的一些狀態(tài)。

2：從隊列L中取出一個狀態(tài)，計算從這個狀態(tài)輸出的所有邊所接受的字符集的并 集，然后對該集合中的每一個字符尋找接受這個字符的邊，把這些邊的目標狀態(tài)的并集T計算出來。如果T∈D則代表當(dāng)前字符指向了一個已知的DFA狀態(tài)。否則 則代表當(dāng)前字符指向了一個未創(chuàng)建的DFA狀態(tài)，這個時候就把T放進L和D中。在這個步驟里有兩層循環(huán)：第一層是遍歷所有接受的字符的并集，第二層是對每一個可以接受的字符遍歷所有輸出的邊計算目標DFA狀態(tài)所包含的NFA狀態(tài)的集合。

3：如果L非空則跳到2。

現(xiàn)在我們開始對圖5.7的狀態(tài)機應(yīng)用DFA構(gòu)造算法。

首先執(zhí)行第一步，我們得到：

圖5.8

從上到下分別是隊列L、集合D和DFA的當(dāng)前狀態(tài)。就這樣一直執(zhí)行該算法直到狀態(tài)3進入集合D，我們得到：

圖5.9

現(xiàn)在從隊列L中取出{3}，經(jīng)過分析得到狀態(tài)集合{3}接受的字符集合為{a b c}。{3}讀入a到達{4}，讀入b到達{5}，讀入c到達{6 7}。因為{4}、{5}和{6 7}都不屬于D，所以把它們都放入隊列L和集合D：

圖5.10

從隊列中取出4進行計算，我們得到：

圖5.11

顯然，對于狀態(tài){4}的處理并沒有發(fā)現(xiàn)新的DFA狀態(tài)。于是處理{5}和{6 7}，我們可以得到：

圖5.12

在處理狀態(tài){5}的時候沒有發(fā)現(xiàn)新的DFA狀態(tài)，處理{6 7}在輸入{a c}之后的跳轉(zhuǎn)也沒有發(fā)現(xiàn)新的DFA狀態(tài)，但是我們發(fā)現(xiàn)了{6 7}輸入b卻得到了新的DFA狀態(tài){5 8}。把算法執(zhí)行完，我們得到一個DFA：

圖5.13

至此，對圖5.7的狀態(tài)機應(yīng)用DFA構(gòu)造算法的流程就結(jié)束了，我們得到了圖5.13的DFA，其功能與圖5.7的NFA等價。在DFA中，起始狀態(tài)是0，結(jié)束狀態(tài)是4E。凡是包含了NFA的結(jié)束狀態(tài)的DFA狀態(tài)都必須是結(jié)束狀態(tài)。

6、使用正則表達式構(gòu)造詞法分析器

判斷一個字符串是否屬于某規(guī)則的算法介紹到這里就結(jié)束了?；氐轿覀円婚_始的問題上，我們需要使用一些規(guī)則來吧一個長的字符串?dāng)嚅_成記號，然后計算出每一個記號對應(yīng)的規(guī)則。在解決這個問題之前，我們先考察一下能夠成功地被詞法分析器接受的字符串應(yīng)該是什么樣子的。

假設(shè)我們現(xiàn)在有規(guī)則A、B、C和D，分別對應(yīng)于四種記號類型，那么被詞法分析器 接受的字符串就是A、B、C和D的任意組合，也就是(A|B|C|D)*。如果規(guī)定了輸入的字符串不能為空的話，那么被詞法分析器接受的字符串就是 (A|B|C|D)+。但是單純地使用(A|B|C|D)+作為一個規(guī)則去應(yīng)用在輸入的字符串的話，我們只能夠判斷字符串是否是詞法分析器能夠接受的字符 串。因此我們需要對這個方法進行修改。

首先按照上文的方法，把每一個記號類型對應(yīng)的規(guī)則的正則表達式轉(zhuǎn)換成DFA，然后使用并聯(lián)的方法將他們組合起來，但是并不使用“重復(fù)”。但是這次我們要做一點修改，我們要把新的DFA的每一個狀態(tài)對應(yīng)的規(guī)則的DFA狀態(tài)集合記住。

這里給出一個例子，我們假設(shè)需要一個簡單語言的詞法分析器，規(guī)則如下：

I：[a-zA-Z_][a-zA-Z_0-9]*

N：[0-9]+

R：[0-9]+.[0-9]+

O：[=>+-*/|&]

按照規(guī)則構(gòu)造出四個DFA并將它們組合起來：

圖6.1

我們構(gòu)造出了I|N|R|O的DFA，并且標識出了哪些狀態(tài)包含了原DFA的結(jié) 束狀態(tài)。這樣做的一個好處是，當(dāng)我們把一個字符串放進這樣的一個DFA之后，我們就一直等待整個字符串被接受，或者失敗。如果字符串被接受的話，我們就把 當(dāng)前的結(jié)束狀態(tài)記下來。如果失敗的話，我們就把這個狀態(tài)機在分析字符串的時候經(jīng)過的最后一個結(jié)束狀態(tài)記下來。這個時候，結(jié)束狀態(tài)所代表的原DFA結(jié)束狀態(tài) 的相應(yīng)記號類型就是我們所需要的信息了。如果得不到任何結(jié)束狀態(tài)的話，輸入的字符串就是不背詞法分析其接受的。

舉個例子，使用上述狀態(tài)機分析”123.ABC”。

首先從狀態(tài)0開始，依次經(jīng)過狀態(tài)N N N 2，然后宣告失敗。最后一個N(結(jié)束狀態(tài))以及當(dāng)時被接受的字符串”123”被識別，結(jié)果為(N，”123”)。然后從”.ABC”開始，輸入第一個記號 就失敗了，于是”.”被識別為不可接受字串。最后輸入”ABC”，依次經(jīng)過狀態(tài)0 1 I I，然后字符串結(jié)束并且被接受，于是輸出(I，”ABC”)。

為什么我們在構(gòu)造狀態(tài)機的時候不使用“重復(fù)”呢？因為在每一個記號被識別出的時候，我們都要做一些額外的工作。如果我們使用“重復(fù)”來構(gòu)造詞法分析器的狀態(tài)機，我們將無從知道一個記號被識別出來的確切時間。

算法到這里基本上就結(jié)束了，不過還存在一些小問題需要在細節(jié)上解決。一般來說我們給出的一些構(gòu)成詞法分析器的規(guī)則很少有沖突，不過偶爾會出現(xiàn)兩個規(guī)則所代表的字符串集合存在交集的情況。有了DFA這個工具，我們可以很輕易地識別出規(guī)則沖突。

假如我們的詞法分析器有A和B兩個狀態(tài)，那么我們構(gòu)造詞法分析器A|B的時候， 將會得到一些包含DFA(A)和DFA(B)的結(jié)束狀態(tài)的新狀態(tài)。我們只需要檢查這些狀態(tài)是否具有以下特征，就可以判斷A和B的關(guān)系。我們假設(shè) DFA(A)為規(guī)則A的狀態(tài)機，DFA(B)為規(guī)則B的狀態(tài)機，DFA(L)為詞法分析器A|B的狀態(tài)機：

1：如果DFA(L)存在一個或多個狀態(tài)同時包含了DFA(A)和DFA(B)的結(jié)束狀態(tài)，那么A和B所代表的字符串存在交集。

2：如果DFA(L)不存在同時包含了DFA(A)和DFA(B)的結(jié)束狀態(tài)的狀態(tài)，那么A和B所代表的字符串不存在交集。

3：如果DFA(L)的某些狀態(tài)包含了DFA(A)的結(jié)束狀態(tài)，并且這些狀態(tài)都無一例外地包含了DFA(B)的結(jié)束狀態(tài)的話，那么A是B的子集。

4：如果DFA(L)的某些狀態(tài)包含了DFA(A)的結(jié)束狀態(tài)，但是這些狀態(tài)并沒有無一例外地包含DFA(B)的結(jié)束狀態(tài)的話，那么A不是B的子集。

在圖6.1的詞法分析器中，我們可以很清楚地看出I、N、R和O四個規(guī)則兩兩之間都不存在交集。我們可以嘗試構(gòu)造一個沖突的規(guī)則，并看一看詞法分析器的DFA是什么樣子的：

假設(shè)詞法分析器包含以下規(guī)則：

A：”if”

B：[a-z]+

對A|B構(gòu)造DFA，我們將會得到如下狀態(tài)機：

圖6.2

通過圖6.2我們可以看出，這個狀態(tài)圖滿足了上述的條件3：包含了狀態(tài)A的結(jié)束狀態(tài)的狀態(tài)都包含了B的結(jié)束狀態(tài)，因此A是B的子集。顯然”if”是[a-z]+的一個子集。在處理這種有沖突的規(guī)則的時候，既可以報錯，也可以根據(jù)指定的優(yōu)先級進行挑選。

7、尾聲

使用DFA的方法完成的可配置詞法分析器的性能是相當(dāng)好的。筆者前不久曾經(jīng)做過 實驗，首先使用本文提到的算法開發(fā)一個這樣的詞法分析器，然后在一份C++代碼(這份代碼經(jīng)過多次復(fù)制而成件，一共有3.12M)中抽取所有數(shù)字、標識符 和注釋，吞吐速度高達46萬記號/秒（筆者的臺式電腦配置是奔騰4的超線程2.99GHz處理器，1G內(nèi)存），其中抽取出來的記號一共有22萬個。在分析 的過程中，只有10%的時間花在了DFA上，90%的時間花在了處理結(jié)果的工作上。DFA本身造成的消耗是很小的。不過詞法分析的性能在很大程度上跟 DFA的實現(xiàn)有很大關(guān)系。三個月前筆者也實現(xiàn)過一個同類的程序，但是吞吐速度僅有1.1萬記號/秒。

一般來說，比較高性能的DFA的實現(xiàn)是一張二維的表。行代表字符，列代表DFA 的狀態(tài)，單元格代表該狀態(tài)經(jīng)輸入某個字符之后進行轉(zhuǎn)移的目標狀態(tài)。此外還有一張表用來記錄哪些狀態(tài)對應(yīng)哪些規(guī)則的結(jié)束狀態(tài)。筆者的詞法分析器是基于 UTF-16編碼的字符串，一張表一共有65535行顯然是不現(xiàn)實的，因此還有另一張表把字符轉(zhuǎn)換成字符類。字符類是這樣定義的：假設(shè)現(xiàn)在已經(jīng)存在了 65535行的一張大表，如果在某個字符區(qū)間所對應(yīng)的子表內(nèi)，任意一列的單元格的數(shù)據(jù)都一樣的話，那么這個區(qū)間內(nèi)的所有字符就可以被視為是等價的，這些字 符就屬于同一個字符類。于是僅需要另外一張65535個單元的表用來把一個字符映射到字符類。這種做法可以大大的壓縮DFA所需要的空間。在筆者的程序 里，識別字符類的算法被融入了DFA的構(gòu)造算法中