1、第 3 講,編譯原理,西北農(nóng)林科技大學(xué)本科教程,主講教師：趙建邦,第二章詞法分析2.3-2.5節(jié) 2.3 正規(guī)表達(dá)式與有限自動(dòng)機(jī)簡(jiǎn)介 2.4 正規(guī)表達(dá)式到優(yōu)先自動(dòng)機(jī)的構(gòu)造 2.5 詞法分析器的自動(dòng)生成 重點(diǎn)掌握 有限自動(dòng)機(jī)理論 有限自動(dòng)機(jī)的構(gòu)造、確定化和化簡(jiǎn),本講目標(biāo),第二章 詞法分析,2.1 詞法分析的設(shè)計(jì)方法 2.2 一個(gè)簡(jiǎn)單的詞法分析器 2.3 正規(guī)表達(dá)式與有限自動(dòng)機(jī)簡(jiǎn)介 2.4 正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造 2.5 詞法分析器的自動(dòng)生成,2.3.2：有限自動(dòng)機(jī)：可以自動(dòng)識(shí)別單詞的機(jī)器 有限自動(dòng)機(jī)（Finite Automation）： FA是一個(gè)狀態(tài)轉(zhuǎn)換圖，“有限”指的是狀態(tài)有限。當(dāng)前

2、狀態(tài)讀入一個(gè)字符后，和后繼狀態(tài)的轉(zhuǎn)換有以下三種情形： (1)后繼狀態(tài)為自身 (2)后繼狀態(tài)只有一個(gè) (3)后繼狀態(tài)有多個(gè) 如果每次轉(zhuǎn)換的后繼狀態(tài)是唯一的，則稱它為確定有限自動(dòng)機(jī)（Deterministic FA） 如果每次轉(zhuǎn)換的后繼狀態(tài)不是唯一的，則稱它為非確定有限自動(dòng)機(jī)（Nondeterministic FA）,2.3 正規(guī)表達(dá)式與優(yōu)先自動(dòng)機(jī)簡(jiǎn)介,2.3.2：有限自動(dòng)機(jī) 1、確定有限自動(dòng)機(jī)（DFA）： DFA是一個(gè)五元組，Md (S, , f, s0 , Z) ，其中： (1) S是一個(gè)有限狀態(tài)集合，它的每個(gè)元素稱為一個(gè)狀態(tài) (2) 是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符 f是一個(gè)從

3、S至S的單值映射，也叫狀態(tài)轉(zhuǎn)移函數(shù) s0S 是唯一的初態(tài) 是一個(gè)終態(tài)集,2.3 正規(guī)表達(dá)式與優(yōu)先自動(dòng)機(jī)簡(jiǎn)介,2.3.2：有限自動(dòng)機(jī) 1、確定有限自動(dòng)機(jī)（例2.4）： 假定DFA Md =(s0, s1, s2，a,b, f , s0 ,s2 )，狀態(tài)轉(zhuǎn)移函數(shù)： f(s0, a) = s1 f(s0, b) = s2 f(s1, a) = s1 f(s1, b) = s2 f(s2, a) = s2 f(s2, b) = s1,2.3 正規(guī)表達(dá)式與優(yōu)先自動(dòng)機(jī)簡(jiǎn)介,狀態(tài)轉(zhuǎn)換矩陣：,2.3.2：有限自動(dòng)機(jī) 2、非確定有限自動(dòng)機(jī)（NFA）： NFA是一個(gè)五元組，Md (S, , f, Q, Z) ，其

4、中： (1) S是一個(gè)有限狀態(tài)集合，它的每個(gè)元素稱為一個(gè)狀態(tài) (2) 是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符 (3) f是一個(gè)從S*至S的多值映射，也叫狀態(tài)轉(zhuǎn)移函數(shù) (4) QS 是非空初態(tài)集 (5) 是一個(gè)終態(tài)集 NFA相比于DFA的特征： 若干個(gè)初始狀態(tài) (2) f多值映射 (3) 允許接收字和空字符,2.3 正規(guī)表達(dá)式與優(yōu)先自動(dòng)機(jī)簡(jiǎn)介,2.3.2：有限自動(dòng)機(jī) 2、非確定有限自動(dòng)機(jī)（例2.5）： 假定NFA Mn =(s0, s1, s2,a,b, f , s0 ,s2,s2)，狀態(tài)轉(zhuǎn)移函數(shù)： f(s0, a) =s2 f(s0, b) =s0,s2 f(s1, a) = f(s1

5、, b) =s2 f(s2, a) = f(s2, b) = s1 ,2.3 正規(guī)表達(dá)式與優(yōu)先自動(dòng)機(jī)簡(jiǎn)介,狀態(tài)轉(zhuǎn)換矩陣：,2.3.2：有限自動(dòng)機(jī)（識(shí)別的語(yǔ)言） 對(duì)于一個(gè)自動(dòng)機(jī)FA 而言，如果存在一條從初始狀態(tài)到終止?fàn)顟B(tài)的通路，通路上有向邊所識(shí)別的字符依次連接所得到的字符串為, 則稱可以為FA 所接受或者為FA 所識(shí)別 FA 所能識(shí)別的字符串集為FA 所識(shí)別的語(yǔ)言，記為L(zhǎng)(M) FA的等價(jià)：對(duì)于任意兩個(gè)FA M和 FA M, 如果L(M)=L(M), 則稱M和M等價(jià) 對(duì)于任意一個(gè)NFA M，一定存在一個(gè)DFA M與其等價(jià),2.3 正規(guī)表達(dá)式與優(yōu)先自動(dòng)機(jī)簡(jiǎn)介,2.3 課堂例題,例2.5 接受與正規(guī)

6、式(a|b) *abb相同的語(yǔ)言的DFA與NFA:,DFA識(shí)別abb aabb abab 無(wú)論成功或者失敗只需要 運(yùn)行一次,NFA識(shí)別abb aabb abab 無(wú)論成功或者失敗可能需要 運(yùn)行若干次,第二章 詞法分析,2.1 詞法分析的設(shè)計(jì)方法 2.2 一個(gè)簡(jiǎn)單的詞法分析器 2.3 正規(guī)表達(dá)式與有限自動(dòng)機(jī)簡(jiǎn)介 2.4 正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造 2.5 詞法分析器的自動(dòng)生成,需要了解的等價(jià)性： 1.如果R是字母表上的一個(gè)正規(guī)式，則必然存在一個(gè)NFA M，使得L(M)=L(R); 2.對(duì)于任意一個(gè)NFA M，一定存在一個(gè)DFA M與其等價(jià) ,即L(M)=L(M); 從正規(guī)式開(kāi)始構(gòu)造DFA的過(guò)程

7、有以下幾個(gè)步驟： 1.由正規(guī)式構(gòu)造NFA; 2.由NFA構(gòu)造與之等價(jià)的DFA（確定化） 3.DFA的化簡(jiǎn),2.4 正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造（重點(diǎn)）,2.4.1：由正規(guī)式構(gòu)造等價(jià)的NFA 1、對(duì)于給定的正規(guī)式R，將其表示成 稱為“拓廣轉(zhuǎn)換圖”其中X為初始狀態(tài)，Y為終止?fàn)顟B(tài) 2、對(duì)正規(guī)式中的三種運(yùn)算，分別采用如下的對(duì)應(yīng)轉(zhuǎn)換規(guī)則,2.4 正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造,Y,X,R,2.4 正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造,例2.6 對(duì)給定正規(guī)表達(dá)式 b*(d|ad)(b|ab)+ 構(gòu)造其NFA M,X,按照正規(guī)式從左到右構(gòu)造NFA：,解答 先用R+=RR*改造正規(guī)表達(dá)式,b*(d|ad)(b|ab)+

8、 = b*(d|ad)(b|ab)(b|ab)*,2.4.2：NFA的確定化（相關(guān)概念） NFA的確定化：構(gòu)造一個(gè)和NFA等價(jià)的DFA 狀態(tài)集合I的_閉包 設(shè)I是FA M的狀態(tài)子集，則以下?tīng)顟B(tài)屬于_CLOSURE(I) ： (1) 若siI，則si _CLOSURE(I) ； (2) 若siI，則對(duì)從si出發(fā)經(jīng)過(guò)任意條通路所能到達(dá)的 狀態(tài)sj，都有sj _CLOSURE(I) 。 定義Ia = _CLOSURE(J) ，其中： I=s1, s2, sn，J = f(I,a) = f(s1,a)f(s2,a) f(sn,a),2.4 正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造,1,5,2,4,2.4 正規(guī)表達(dá)

9、式到有限自動(dòng)機(jī)的構(gòu)造,例2.7 已知一狀態(tài)轉(zhuǎn)換圖如下圖所示，且假定I=_CLOSURE(1)=1,2，試求從狀態(tài)集I出發(fā)經(jīng)過(guò)一條有向邊a能到達(dá)的狀態(tài)集J和_CLOSURE(J),6,3,7,8,a,a,a,解答 狀態(tài)集I經(jīng)過(guò)一條a弧得到J， J = 5,3,4 J中的每一個(gè)狀態(tài)經(jīng)過(guò)任意條通路得到_CLOSURE(J) =Ia= 5,6,2,3,8,4,7,2.4.2：NFA的確定化（子集法） (1) 構(gòu)造一張轉(zhuǎn)換表，第一列記為狀態(tài)子集I，對(duì)于不同的符號(hào) (a)，在表中單設(shè)一列Ia ； (2) 表的首行首列置為_(kāi)CLOSURE(s0)，其中s0為初始狀態(tài)； (3) 根據(jù)首行首列的I，為每個(gè)a求其

10、Ia 并記入對(duì)應(yīng)的Ia 列中， 如果此Ia 不同于第一列中已存在的所有狀態(tài)子集I，則將其 順序列入空行中的第一列； (4) 重復(fù)(3)直至對(duì)每個(gè)I及a均已求得Ia ，并且無(wú)新的狀態(tài)子集 Ia加入第一列時(shí)為止； (5) 重新命名第一列的每一個(gè)狀態(tài)子集，形成新的狀態(tài)轉(zhuǎn)換矩陣， 即為與NFA等價(jià)的DFA,2.4 正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造,2.4 正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造,例2.8 求正規(guī)表達(dá)式(a|b) *(aa|bb) (a|b) *對(duì)應(yīng)的DFA M,解答首先根據(jù)正規(guī)式構(gòu)造NFA M:,1.構(gòu)造狀態(tài)轉(zhuǎn)換表:,X,1,2,1,2,3,1,2,4,1,2,3,1,2,4,2.確定首行首列: _

11、CLOSURE(s0),3.依次計(jì)算Ia和Ib 并更新首列,2.4 正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造,X,1,2,1,2,3,1,2,4,1,2,3,1,2,4,1,2,3,5,6,Y,1,2,4,1,2,3,5,6,Y,1,2,3,1,2,4,5,6,Y,1,2,4,5,6,Y,1,2,3,5,6,Y,1,2,4,6,Y,1,2,4,6,Y,1,2,3,6,Y,1,2,3,6,Y,1,2,4,5,6,Y,1,2,3,6,Y,1,2,4,5,6,Y,1,2,3,5,6,Y,1,2,4,6,Y,4.重復(fù)(3) ,直至無(wú)新?tīng)顟B(tài)加入首列為止,5.新的狀態(tài)轉(zhuǎn)換矩陣,0,1,2,3,4,5,6,1,3,1,

12、3,6,6,3,2,2,4,5,4,4,5,0,1,2,3,4,5,6,1,3,1,3,6,6,3,2,2,4,5,4,4,5,得到新的狀態(tài)轉(zhuǎn)換圖DFA:,2.4 正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造,2.4.3：DFA的化簡(jiǎn) 狀態(tài)的等價(jià)： 假設(shè)s1和s2是M的兩個(gè)不同的狀態(tài)，如果從s1出發(fā)能識(shí)別字符串而停于終態(tài)，從s2出發(fā)也能識(shí)別而停于終態(tài)。 反之也是成立的。稱s1和s2等價(jià)，否則稱它們可區(qū)分 一個(gè)確定有限自動(dòng)機(jī)M的化簡(jiǎn)是指： 尋找一個(gè)狀態(tài)數(shù)比M少的DFA M，使得L(M)=L(M) 化簡(jiǎn)后的DFA滿足兩個(gè)條件： (1) 沒(méi)有多余狀態(tài) (2) 狀態(tài)集中不存在等價(jià)狀態(tài),2.4 正規(guī)表達(dá)式到有限自動(dòng)機(jī)的

13、構(gòu)造,2.4.3：DFA的化簡(jiǎn)（方法） (1) 首先將DFA的狀態(tài)集按照終態(tài)與非終態(tài)分為兩個(gè)子集，形成 初始劃分H (2) 對(duì)每個(gè)子集G進(jìn)行如下變換： 把G劃分為新的子集，使得G的兩個(gè)狀態(tài)s1和s2屬于同一子集,當(dāng)且僅當(dāng)對(duì)任何輸入符號(hào)a,狀態(tài)s1和s2的后繼狀態(tài)都屬于同一子集； 用G劃分出的所有子集替換G，形成新的劃分Hnew (3) 如果Hnew = H，執(zhí)行(4);否則令H = Hnew，重復(fù)執(zhí)行(2) (4) 劃分結(jié)束后，一個(gè)子集只對(duì)應(yīng)一個(gè)狀態(tài)，作為代表狀態(tài)，刪去 其它一切等價(jià)狀態(tài)，并將對(duì)應(yīng)的弧射向這個(gè)代表狀態(tài),2.4 正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造,2.4 正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造,

14、例2.8 求正規(guī)表達(dá)式(a|b) *(aa|bb) (a|b) *對(duì)應(yīng)的DFA M,解答 畫(huà)出例2.8未化簡(jiǎn)的DFA:,(1)初始劃分集合1=0,1,2 ，集合2=3,4,5,6,(2)考察0,1,2：0a,0b,1b,2a 在集合1；1a, 2b在集合2； 因此劃分為012； 考察3,4,5,6： 3a,4a,5a,6a在集合2；3b,4b,5b,6b在集合2； 因此不進(jìn)行劃分。,2.4 正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造,例2.8 求正規(guī)表達(dá)式(a|b) *(aa|bb) (a|b) *對(duì)應(yīng)的DFA M,解答,(3) 劃分的最終結(jié)果為 0 、1、2、3,4,5,6； 對(duì)其進(jìn)行重命名：0、1、2、3,(4) 得到新的狀態(tài)轉(zhuǎn)換矩陣和化簡(jiǎn)后的DFA，如下所示：,2.4 正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造,例2.8 求正規(guī)表達(dá)式(a|b) *(aa|bb) (a|b) *對(duì)應(yīng)的DFA M,NFA M:,化簡(jiǎn)前的DFA M:,化簡(jiǎn)后的DFA M:,2.4 正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造,例2.8 求正規(guī)表達(dá)式(a|b) *(aa|bb) (a|b) *對(duì)應(yīng)的DFA M,NFA M:,化簡(jiǎn)前的DFA M:,化簡(jiǎn)后的DFA M:,2.4 正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造,例2.12 某高級(jí)程序語(yǔ)言無(wú)符號(hào)數(shù)的正規(guī)表達(dá)式為 dig