1、第第2 2章章 詞法分析詞法分析 第第2章章 詞法分析詞法分析 2.1 詞法分析器設(shè)計(jì)方法詞法分析器設(shè)計(jì)方法 2.2 一個簡單的詞法分析器示例一個簡單的詞法分析器示例 2.3 正規(guī)表達(dá)式與有限自動機(jī)簡介正規(guī)表達(dá)式與有限自動機(jī)簡介 2.4 正規(guī)表達(dá)式到有限自動機(jī)的構(gòu)造正規(guī)表達(dá)式到有限自動機(jī)的構(gòu)造 2.5 詞法分析器的自動生成詞法分析器的自動生成 第第2 2章章 詞法分析詞法分析 2.3 正規(guī)表達(dá)式與有限自動機(jī)簡介正規(guī)表達(dá)式與有限自動機(jī)簡介 2.3.1 正規(guī)表達(dá)式與正規(guī)集正規(guī)表達(dá)式與正規(guī)集 正規(guī)表達(dá)式是一種形式化的表示法，表示單詞符號的正規(guī)表達(dá)式是一種形式化的表示法，表示單詞符號的結(jié)構(gòu)結(jié)構(gòu)，從而精

2、確地定義單詞符號集。正規(guī)表達(dá)式簡稱，從而精確地定義單詞符號集。正規(guī)表達(dá)式簡稱為正規(guī)式，它表示的集合即為正規(guī)集。為正規(guī)式，它表示的集合即為正規(guī)集。 letter (letter digit)*-標(biāo)識符的正規(guī)式，標(biāo)識符的正規(guī)式， 標(biāo)識符集標(biāo)識符集-正規(guī)式所表示的正規(guī)集。正規(guī)式所表示的正規(guī)集。第第2 2章章 詞法分析詞法分析 對于給定的對于給定的字母表字母表，正規(guī)式和正規(guī)集的遞歸定義如下：，正規(guī)式和正規(guī)集的遞歸定義如下：(1)和和都是都是上的正規(guī)式，所表示的正規(guī)集分別為上的正規(guī)式，所表示的正規(guī)集分別為和和。(2) 對任一個對任一個a，a是是上的一個正規(guī)式，它所表示的正規(guī)集上的一個正規(guī)式，它所表示的正

3、規(guī)集為為a。 (3) 如果如果R和和S是是上的正規(guī)式，它們所表示的正規(guī)集分別為上的正規(guī)式，它們所表示的正規(guī)集分別為L(R)和和L(S)，則：，則： R S是是上的正規(guī)式，它所表示的正規(guī)集為上的正規(guī)式，它所表示的正規(guī)集為L(R)L(S)； R.S是是上的正規(guī)式，它所表示的正規(guī)集為上的正規(guī)式，它所表示的正規(guī)集為L(R) L(S)； (R)*是是上的正規(guī)式，它所表示的正規(guī)集為上的正規(guī)式，它所表示的正規(guī)集為(L(R)*； R也是也是上的正規(guī)式，它所表示的正規(guī)集為上的正規(guī)式，它所表示的正規(guī)集為L(R)。(4) 僅由有限次使用規(guī)則僅由有限次使用規(guī)則(1)(3)得到的表示式是得到的表示式是上的正規(guī)式，上的正

4、規(guī)式，它所表示的集合是它所表示的集合是上的正規(guī)集。上的正規(guī)集。第第2 2章章 詞法分析詞法分析 說明：說明： 規(guī)則規(guī)則(1)、(2)為基礎(chǔ)規(guī)則，規(guī)則為基礎(chǔ)規(guī)則，規(guī)則(3)為歸納規(guī)則，規(guī)則為歸納規(guī)則，規(guī)則(4)是是界限規(guī)則或終止規(guī)則。界限規(guī)則或終止規(guī)則。 上的一個字是指由上的一個字是指由中的字符所構(gòu)成的一個有窮序列；中的字符所構(gòu)成的一個有窮序列； 不包含任何字符的序列稱為不包含任何字符的序列稱為空字空字，用，用表示。表示。 *表示表示上所有字的全體，則空字上所有字的全體，則空字也在其中。也在其中。 表示不含任何元素的表示不含任何元素的空集空集 例如，若例如，若=a，b，則，則*=，a，b，aa，

5、ab，ba，bb，aaa，。第第2 2章章 詞法分析詞法分析 正規(guī)式間的運(yùn)算符正規(guī)式間的運(yùn)算符 “ ”表示或表示或 “ ”表示連接（通常可省略）表示連接（通常可省略） “*”表示閉包，使用括號可以改變運(yùn)算的次序。表示閉包，使用括號可以改變運(yùn)算的次序。*的正規(guī)式的正規(guī)式R和和S的連接可以形式化地定義為的連接可以形式化地定義為 RS= R&S 即集合即集合RS中的字是由中的字是由R和和S中的字連接而成的，且中的字連接而成的，且R自身的自身的n次連接記為次連接記為 n 個 Rn=RRR 第第2 2章章 詞法分析詞法分析 R0= R*=R0R1R2R3，則稱，則稱R*是是R的的閉包閉包 R+=

6、RR*，并稱，并稱R+是是R的的正閉包正閉包。對于對于上的正規(guī)式上的正規(guī)式R和和S，如果它所表示的正規(guī)集，如果它所表示的正規(guī)集L(R)=L(S)，則稱則稱R和和S等價(jià)等價(jià)并記為并記為R=S。正規(guī)式具有下列性質(zhì)：正規(guī)式具有下列性質(zhì)： (1) 交換律：交換律：R S = S R。 (2) 結(jié)合律：結(jié)合律：R (S T) = (R S) T； R(ST) = (RS)T。 (3) 分配律：分配律：R (S T) = RS RT； (R S)T = RT ST。 (4) 同一律：同一律：R = R = R。第第2 2章章 詞法分析詞法分析 例例2.1 令令=a,b，設(shè)，設(shè)R=(ab)*a、 S= a(

7、ba)*是是上的正規(guī)上的正規(guī)式，試求其表示的正規(guī)集。式，試求其表示的正規(guī)集。 解答解答第第2 2章章 詞法分析詞法分析 2.3.2 有限自動機(jī)有限自動機(jī) 有限自動機(jī)（有限自動機(jī)（FA）是更一般化的狀態(tài)轉(zhuǎn)換圖）是更一般化的狀態(tài)轉(zhuǎn)換圖 確定有限自動機(jī)確定有限自動機(jī)DFA 非確定有限自動機(jī)非確定有限自動機(jī)NFA 1確定有限自動機(jī)（確定有限自動機(jī)（DFA） 一個確定的有限自動機(jī)一個確定的有限自動機(jī)Md（記為（記為DFA Md）是一個）是一個五元組五元組M d=（S, f, s0, Z），其中：），其中： (1) S是一個是一個有限狀態(tài)集有限狀態(tài)集，它的每一個元素稱為一個狀態(tài)；，它的每一個元素稱為一個狀

8、態(tài)； (2) 是一個是一個有窮輸入字母表有窮輸入字母表，它的每一個元素稱為一個輸入，它的每一個元素稱為一個輸入字符；字符； 第第2 2章章 詞法分析詞法分析 (3) f是一個從是一個從S到到S的單值映射，即的單值映射，即f (si , a)=sj且有且有si、sjS和和a； (4) s0S，是，是惟一的一個初態(tài)惟一的一個初態(tài)； (5) Z ( S，是一個，是一個終態(tài)集終態(tài)集。 DFA Md有三種表示形式：五元組形式、狀態(tài)轉(zhuǎn)換圖、狀態(tài)有三種表示形式：五元組形式、狀態(tài)轉(zhuǎn)換圖、狀態(tài)轉(zhuǎn)換矩陣轉(zhuǎn)換矩陣?yán)?.4 假定假定DFA Md=(s0，s1，s2，a，b，f，s0，s2)，且有：，且有： f(s0

9、，a)= s1 f(s0，b)= s2 f(s1，a)= s1 f(s1，b)= s2 f(s2，a)= s2 f(s2，b)= s1第第2 2章章 詞法分析詞法分析 DFA的狀態(tài)轉(zhuǎn)換圖與狀態(tài)轉(zhuǎn)換矩陣表示的狀態(tài)轉(zhuǎn)換圖與狀態(tài)轉(zhuǎn)換矩陣表示 （1）假定）假定DFA有有m個狀態(tài)、個狀態(tài)、n個輸入字符（或字），個輸入字符（或字），則這個狀態(tài)轉(zhuǎn)換圖含有則這個狀態(tài)轉(zhuǎn)換圖含有m個狀態(tài)，每個狀態(tài)最多有個狀態(tài)，每個狀態(tài)最多有n條條輸出邊與其它狀態(tài)相連接，每一條輸出邊用輸出邊與其它狀態(tài)相連接，每一條輸出邊用（或（或*）中的一個不同的輸入字符（或一個輸入字）作標(biāo)記，中的一個不同的輸入字符（或一個輸入字）作標(biāo)記，整個圖

10、含有惟一一個初態(tài)（或多個初態(tài)）和若干個終整個圖含有惟一一個初態(tài)（或多個初態(tài)）和若干個終態(tài)。態(tài)。 （2）DFA也可以用狀態(tài)轉(zhuǎn)換矩陣表示。狀態(tài)轉(zhuǎn)換矩陣也可以用狀態(tài)轉(zhuǎn)換矩陣表示。狀態(tài)轉(zhuǎn)換矩陣的行表示狀態(tài)，列表示輸入符號，矩陣元素表示的行表示狀態(tài)，列表示輸入符號，矩陣元素表示f(si，a)的值。的值。第第2 2章章 詞法分析詞法分析 s12 s2s0aabbab第第2 2章章 詞法分析詞法分析 表2.2 狀態(tài)轉(zhuǎn)換矩陣 字符 狀態(tài)abs0s1s2s1s1s2s2s2s1第第2 2章章 詞法分析詞法分析 2非確定有限自動機(jī)非確定有限自動機(jī)(NFA) 一個非確定有限自動機(jī)一個非確定有限自動機(jī)Mn（記為（記為

11、NFA Mn）是一個）是一個五元組五元組Mn=(S,f,Q,Z)，其中：，其中： (1) S、Z的意義與的意義與DFA相同；相同； (2) f是一個從是一個從S*到到S的子集映射；的子集映射； (3) Q ( S，是一個非空初態(tài)集。，是一個非空初態(tài)集。 第第2 2章章 詞法分析詞法分析 例例2.5 假定假定 NFA Mn=(s0，s1，s2，a，b，f，s0，s2，s1)，且有：且有： f(s0，a)= s2 f(s0，b)= s0 ,s1 f(s1，a)= f(s1，b)= s2 f(s2，a)= f(s2，b)= s1 第第2 2章章 詞法分析詞法分析 2 s1s0s2bbbba第第2 2

12、章章 詞法分析詞法分析 表2.3 狀態(tài)轉(zhuǎn)換矩陣 字符 狀態(tài)abs0s2s0，s1s1s2s2s1第第2 2章章 詞法分析詞法分析 2.4 正規(guī)表達(dá)式到有限自動機(jī)的構(gòu)造正規(guī)表達(dá)式到有限自動機(jī)的構(gòu)造 2.4.1 由正規(guī)表達(dá)式構(gòu)造等價(jià)的由正規(guī)表達(dá)式構(gòu)造等價(jià)的NFA M 由正規(guī)表達(dá)式構(gòu)造等價(jià)的由正規(guī)表達(dá)式構(gòu)造等價(jià)的NFA M的方法如下：的方法如下：(1) 將正規(guī)表達(dá)式將正規(guī)表達(dá)式R表示成如圖表示成如圖210所示的拓廣轉(zhuǎn)換圖。所示的拓廣轉(zhuǎn)換圖。(2) 對正規(guī)表達(dá)式采用如圖對正規(guī)表達(dá)式采用如圖2-11所示的三條轉(zhuǎn)換規(guī)則來構(gòu)所示的三條轉(zhuǎn)換規(guī)則來構(gòu) NFA M。 第第2 2章章 詞法分析詞法分析 圖2-10

13、拓廣轉(zhuǎn)換圖X2 YR第第2 2章章 詞法分析詞法分析 圖2-11 轉(zhuǎn)換規(guī)則 sisjr1 | r2sisjr1r2sisjr1*123sisjr1r2sisjskr1r2sisjskr1第第2 2章章 詞法分析詞法分析 例例2.6 對給定正規(guī)表達(dá)式對給定正規(guī)表達(dá)式 (a b)*(aa bb)(a b)*構(gòu)造其構(gòu)造其NFA M。 第第2 2章章 詞法分析詞法分析 2.4.2 NFA M的確定化的確定化我們采用我們采用子集法子集法來對來對NFA M確定化。確定化。 首 先 定 義首 先 定 義 FA M 的 一 個 狀 態(tài) 子 集的 一 個 狀 態(tài) 子 集 I 的的 _ 閉 包閉 包 ， 即， 即

14、_CLOSURE(I)，則：，則： (1) 若若siI，則，則si_CLOSURE(I)； (2) 若若siI，則對從，則對從si出發(fā)經(jīng)過出發(fā)經(jīng)過通路所能到達(dá)的任何狀通路所能到達(dá)的任何狀態(tài)態(tài)sj，都有，都有sj_CLOSURE(I)。 其次對其次對FA M的一個狀態(tài)子集的一個狀態(tài)子集I，若，若a是是中的一個字符，定中的一個字符，定義義 Ia=_CLOSURE(J)其中，其中，J是所有那些可以從是所有那些可以從I中的某一狀態(tài)出發(fā)經(jīng)過有向邊中的某一狀態(tài)出發(fā)經(jīng)過有向邊a而而能到達(dá)的狀態(tài)集能到達(dá)的狀態(tài)集第第2 2章章 詞法分析詞法分析 例例 2 . 7 已 知 一 狀 態(tài) 轉(zhuǎn) 換 圖 如 下 圖 所

15、示 ， 且 假 定已 知 一 狀 態(tài) 轉(zhuǎn) 換 圖 如 下 圖 所 示 ， 且 假 定I=_1=1，2，試求從狀態(tài)，試求從狀態(tài)I出發(fā)經(jīng)過一條有向邊出發(fā)經(jīng)過一條有向邊a而能而能到達(dá)的狀態(tài)集到達(dá)的狀態(tài)集J和和_CLOSURE(J)。1524aa6378a第第2 2章章 詞法分析詞法分析 解答解答 從狀態(tài)從狀態(tài)I中的狀態(tài)中的狀態(tài)1或狀態(tài)或狀態(tài)2出發(fā)經(jīng)過一條出發(fā)經(jīng)過一條a弧而能到達(dá)的狀態(tài)集弧而能到達(dá)的狀態(tài)集J為為 5，3，4 若若siJ，則由，則由si出發(fā)經(jīng)過任意條出發(fā)經(jīng)過任意條有向邊而能到達(dá)有向邊而能到達(dá)的任何狀態(tài)的任何狀態(tài)sj_CLOSURE(J)，因此，因此_CLOSURE(J)為為 5，6，2，

16、3，8，4，7第第2 2章章 詞法分析詞法分析 用子集法對用子集法對NFA確定化的方法如下：確定化的方法如下： (1) 構(gòu)造一張轉(zhuǎn)換表，其第一列為狀態(tài)子集構(gòu)造一張轉(zhuǎn)換表，其第一列為狀態(tài)子集I，對不同的，對不同的a (a)在表中單設(shè)一列在表中單設(shè)一列Ia。 (2) 表的第一行第一列其狀態(tài)子集表的第一行第一列其狀態(tài)子集I為為_CLOSURE(s0)；其中，；其中，s0為初始狀態(tài)。為初始狀態(tài)。 (3) 根據(jù)第一列中的根據(jù)第一列中的I為每一個為每一個a求其求其Ia并記入對應(yīng)的并記入對應(yīng)的Ia列中，列中，如果此如果此Ia不同于第一列已存在的所有狀態(tài)子集不同于第一列已存在的所有狀態(tài)子集I，則將其順序，則將

17、其順序列入空行中的第一列。列入空行中的第一列。 (4) 重復(fù)步驟（重復(fù)步驟（3）直至對每個）直至對每個I及及a均已求得均已求得Ia，并且無新的，并且無新的狀態(tài)子集狀態(tài)子集Ia加入第一列時(shí)為止；此過程可在有限步后終止。加入第一列時(shí)為止；此過程可在有限步后終止。第第2 2章章 詞法分析詞法分析 (5) 重新命名第一列的每一狀態(tài)子集，則轉(zhuǎn)換表便成為重新命名第一列的每一狀態(tài)子集，則轉(zhuǎn)換表便成為新的狀態(tài)轉(zhuǎn)換矩陣，其狀態(tài)轉(zhuǎn)換函數(shù)新的狀態(tài)轉(zhuǎn)換矩陣，其狀態(tài)轉(zhuǎn)換函數(shù)f是是S到到S的單的單值映射，即為與值映射，即為與NFA M等價(jià)的等價(jià)的DFA M。 例例2.8 正規(guī)表達(dá)式（正規(guī)表達(dá)式（a b）*(aa bb)(

18、a b)*的的NFA M如圖如圖214所示，試將其確定化為所示，試將其確定化為DFA M。 解答解答 用子集法將圖用子集法將圖2-14所示的所示的NFA M確定化為確定化為表表2.4。 對表對表2.4中的所有子集重新命名，得到表中的所有子集重新命名，得到表2.5的狀態(tài)的狀態(tài)轉(zhuǎn)換矩陣及對應(yīng)的狀態(tài)轉(zhuǎn)換圖轉(zhuǎn)換矩陣及對應(yīng)的狀態(tài)轉(zhuǎn)換圖(見圖見圖2-15)。第第2 2章章 詞法分析詞法分析 34251X6abababab2 Y圖214 例2.8的NFA M第第2 2章章 詞法分析詞法分析 表2.4 例2.8的轉(zhuǎn)換表 IIaIbX,1,21,2,31,2,41,2,31,2,3,5,6,Y1,2,41,2,

19、41,2,31,2,4,5,6,Y1,2,3,5,6,Y1,2,3,5,6,Y1,2,4,6,Y1,2,4,5,6,Y1,2,3,6,Y1,2,4,5,6,Y1,2,4,6,Y1,2,3,6,Y1,2,4,5,6,Y1,2,3,6,Y1,2,3,5,6,Y1,2,4,6,Y第第2 2章章 詞法分析詞法分析 2 32 52 42 6120abbaabaabbaabb圖215 例2.8未化簡的DFA M第第2 2章章 詞法分析詞法分析 表2.5 例2.8的狀態(tài)轉(zhuǎn)換矩陣 Sab012132214335464564635第第2 2章章 詞法分析詞法分析 2.4.3 DFA M的化簡的化簡 對對NFA確

20、定化后所得到的確定化后所得到的DFA可能含有多余的狀可能含有多余的狀態(tài)，因此還應(yīng)對其進(jìn)行化簡。所謂態(tài)，因此還應(yīng)對其進(jìn)行化簡。所謂DFA M的化簡，是的化簡，是指 尋 找 一 個 狀 態(tài) 數(shù) 比指 尋 找 一 個 狀 態(tài) 數(shù) 比 M 少 的少 的 D FA M ， 使 得， 使 得L(M)=L(M)。化簡了的。化簡了的DFA M 滿足下述兩個條件：滿足下述兩個條件： (1) 沒有多余狀態(tài)；沒有多余狀態(tài)； (2) 在其狀態(tài)集中，沒有兩個相互等價(jià)的狀態(tài)存在。在其狀態(tài)集中，沒有兩個相互等價(jià)的狀態(tài)存在。 第第2 2章章 詞法分析詞法分析 所謂兩個狀態(tài)相互等價(jià)是指：對一給定的所謂兩個狀態(tài)相互等價(jià)是指：對一

21、給定的DFA M，若存在狀態(tài)若存在狀態(tài)s1、s2S且且s1s2，如果從，如果從s1出發(fā)能識別字符出發(fā)能識別字符串串而停于終態(tài)，從而停于終態(tài)，從s2出發(fā)也同樣能夠識別這個出發(fā)也同樣能夠識別這個而停而停于終態(tài)；反之，若從于終態(tài)；反之，若從s2出發(fā)能識別出發(fā)能識別而停于終態(tài)，則從而停于終態(tài)，則從s1出發(fā)也能識別這個出發(fā)也能識別這個而停于終態(tài)，則稱而停于終態(tài)，則稱s1和和s2是等價(jià)是等價(jià)的，否則就是可區(qū)分的。的，否則就是可區(qū)分的。 一個一個DFA M的狀態(tài)最小化過程是將的狀態(tài)最小化過程是將M的狀態(tài)集分的狀態(tài)集分割成一些不相交的子集，使得任何不同的兩個子集其割成一些不相交的子集，使得任何不同的兩個子集其

22、狀態(tài)都是可區(qū)分的，而同一子集中的任何兩個狀態(tài)都狀態(tài)都是可區(qū)分的，而同一子集中的任何兩個狀態(tài)都是等價(jià)的。是等價(jià)的。 第第2 2章章 詞法分析詞法分析 DFA M的化簡方法如下：的化簡方法如下： (1) 首先將首先將DFA M的狀態(tài)集的狀態(tài)集S中的終態(tài)與非終態(tài)分開，中的終態(tài)與非終態(tài)分開，形成兩個子集，即得到基本劃分。形成兩個子集，即得到基本劃分。 (2) 對當(dāng)前已劃分出的對當(dāng)前已劃分出的I(1)、I(2)、I(m) 子集（屬于不子集（屬于不同子集的狀態(tài)是可區(qū)分的），看每一個同子集的狀態(tài)是可區(qū)分的），看每一個I是否能進(jìn)一步劃是否能進(jìn)一步劃分；也即對某個分；也即對某個I(i)=s1,s2,sk，若存在

23、一個輸入字符，若存在一個輸入字符a（a）使得）使得Ia(i)不全包含在當(dāng)前劃分的某一子集不全包含在當(dāng)前劃分的某一子集I(j)中中（即跨越到兩個子集），就將（即跨越到兩個子集），就將I(i)一分為二（見圖一分為二（見圖216）。）。第第2 2章章 詞法分析詞法分析 圖216 是否劃分示意(a) 無需劃分；(b) 需要劃分(a)(b)s3s4s3s4s1s2s1s2s5aaaa第第2 2章章 詞法分析詞法分析 (3) 重復(fù)步驟重復(fù)步驟(2)，直到子集個數(shù)不再增加為止，直到子集個數(shù)不再增加為止（即每個子集已是不可再分的了）。所謂不能劃分，（即每個子集已是不可再分的了）。所謂不能劃分，是指該子集或者僅

24、有一個狀態(tài)，或者雖有多個狀態(tài)但是指該子集或者僅有一個狀態(tài)，或者雖有多個狀態(tài)但這些狀態(tài)均不可區(qū)分（即等價(jià)）。這些狀態(tài)均不可區(qū)分（即等價(jià)）。 那么，如何進(jìn)行劃分呢？假定當(dāng)前子集那么，如何進(jìn)行劃分呢？假定當(dāng)前子集I(i)=s1,s2,，且狀態(tài)，且狀態(tài)s1和和s2經(jīng)過有向邊經(jīng)過有向邊a分別到達(dá)狀態(tài)分別到達(dá)狀態(tài)t1和和t2，而，而t1和和t2又分屬于當(dāng)前已劃分出的兩個不同子集又分屬于當(dāng)前已劃分出的兩個不同子集I(j)和和I(k)，則此時(shí)應(yīng)將，則此時(shí)應(yīng)將I(i)分為兩部分，使得一部分含有分為兩部分，使得一部分含有s1： I(i1)=s sI(i)且且s經(jīng)有向邊經(jīng)有向邊a到達(dá)到達(dá)t1第第2 2章章 詞法分析詞法分析 而另一部分含有而另一部分含有s2： I(i2)=I(i) I(i1) 由于由于t1和和t2是可區(qū)分的，即存在一個字符串是可區(qū)分的，即存在一個字符串，t1將將讀出讀出而停于終態(tài)，而而停于終態(tài)，而t2或讀不出或讀不出或者可以讀出或者可