第三章詞法分析

1、詞法分析的作用：詞法分析的作用：1.逐個(gè)讀入源程序字符并按照構(gòu)詞規(guī)則分成一系列單詞。單詞中包括保留字、標(biāo)識符、運(yùn)算符、標(biāo)點(diǎn)符號和常量等。2.詞法分析是編譯過程中的一個(gè)階段。前面我們講過，詞法分析采用正規(guī)文法來定義和識別詞法分析程序的功能詞法分析程序的功能1. 根據(jù)詞法規(guī)則把源程序字符流轉(zhuǎn)換為語義關(guān)聯(lián)的單詞符號的序列，同時(shí)進(jìn)行詞法檢查2. 對數(shù)字常數(shù)完成數(shù)字字符串到（二進(jìn)制）數(shù)值的轉(zhuǎn)換3. 刪去空格字符和注解源程序詞法分析程序語法分析程序Tokenget token.1.詞法分析單獨(dú)作為一遍2.詞法分析程序作為單獨(dú)的子程序S.P.(字符串)詞法分析詞法分析S.P.(符號串)語法分析語法分析第一遍

2、第一遍第二遍第二遍單詞串單詞串優(yōu)點(diǎn)優(yōu)點(diǎn): 結(jié)構(gòu)清晰、各遍功能單一結(jié)構(gòu)清晰、各遍功能單一缺點(diǎn)：效率低缺點(diǎn)：效率低詞法分析實(shí)現(xiàn)方案：詞法分析實(shí)現(xiàn)方案：基本上有兩種While ij do if ij then i:=i-j else j:=j-I while，i，j， do， if，i，j,then, i, := , i, - , j,else, j, :=, j, -, i詞法分析器 Pascal程序段程序段詞類和屬性 computer n. Calculating machine.一般程序語言單詞的分類： 1關(guān)鍵字(保留字或基本字)：begin,end 2標(biāo)識符：用來表示各種名字 3常量：256

3、，3 .14，true,abs 4 運(yùn)算符：如，、*、/ 等等 5分界符：如逗號，分號，冒號等單詞的詞類和屬性單詞的詞類和屬性詞法分析器的二元式輸出形式： （詞類編碼，單詞自身的屬性值）1. 詞類編碼提供給語法分析程序使用2. 單詞自身的屬性值提供給語義分析程序使用3. 具體的分類設(shè)計(jì)以方便語法分析程序使用為原則4. 單詞自身的屬性值提供的內(nèi)容，是由詞法分析和語義分析的任務(wù)劃分決定的單詞的詞類和屬性單詞的詞類和屬性 Pascal源程序經(jīng)詞法分析器的輸出 while， id，指向i的符號表入口的指針 relationalop , NE id，指向j的符號表入口的指針 do， if， id，指向i

4、的符號表入口的指針 id，指向j的符號表入口的指針While ij do程序段的單詞輸出例子：程序段的單詞輸出例子：u 程序設(shè)計(jì)語言的單詞都能用正規(guī)文法描述；u 例如，標(biāo)識符可定義為u 若把字母、數(shù)字視為終結(jié)符，則上述產(chǎn)生式為（左線性）正規(guī)文法u 若我們用d表示0-9間的數(shù)字，則C語言的的文法也是（右線性）正規(guī)文法（見P49）u 一般說來，凡能用正規(guī)文法描述的語言，均可由某種有限狀態(tài)算法進(jìn)行分析。 由有限個(gè)結(jié)點(diǎn)所組成的有向圖。u 每個(gè)結(jié)點(diǎn)代表在識別分析過程中掃描器所處的狀態(tài)，其中 含有一個(gè)初始狀態(tài)和若干個(gè)終態(tài)。在圖中，狀態(tài)用圓圈表示，終態(tài)用雙層圓圈表示。u 狀態(tài)之間可用有向邊連接，其上標(biāo)記一字

5、符a，表示從有向邊的射出狀態(tài)出發(fā)，識別一字符a后，將進(jìn)入箭頭所指狀態(tài)（結(jié)點(diǎn)）設(shè)G=(VN,VT,P,S)是一右線性文法,并設(shè)|VN|=K,則所要構(gòu)造的狀態(tài)轉(zhuǎn)換圖共有K+1個(gè)狀態(tài)(結(jié)點(diǎn)).用VN中的每個(gè)符號分別標(biāo)記其中的K個(gè)結(jié)點(diǎn),且令G的開始符S為初態(tài)結(jié)點(diǎn);余下的一個(gè)結(jié)點(diǎn)作為終態(tài)結(jié)點(diǎn),用F( VN)標(biāo)記.我們用如下規(guī)則來連接這K+1個(gè)結(jié)點(diǎn):(1)對于G中產(chǎn)生式AaB,從結(jié)點(diǎn)A引一有向邊到結(jié)點(diǎn)B,并用a標(biāo)記這一有向邊;(2)對于G中產(chǎn)生式Aa,從結(jié)點(diǎn)A引一有向邊到終態(tài)結(jié)點(diǎn)F,并用a標(biāo)記這一有向邊;(3)對于G中產(chǎn)生式A(若有的話),則將結(jié)點(diǎn)A設(shè)為終態(tài).例如,P49中定義的無符號數(shù)的文法對應(yīng)的狀態(tài)轉(zhuǎn)

6、換圖狀態(tài)轉(zhuǎn)換圖為(化簡后):0453126d.dddd.E+|-Edd對于已給的字符串對于已給的字符串w=a1a2an,ai VT,利用利用對對w 識別的步驟識別的步驟如下如下:(1)從初始狀態(tài)從初始狀態(tài)S出發(fā)出發(fā),自左至右逐個(gè)掃描自左至右逐個(gè)掃描w的各個(gè)字符的各個(gè)字符(當(dāng)前為當(dāng)前為a1),此時(shí)在結(jié)點(diǎn)此時(shí)在結(jié)點(diǎn)S所射出的諸矢線中所射出的諸矢線中,尋找標(biāo)記為尋找標(biāo)記為a1的矢線的矢線(若不存在若不存在,則表明則表明w有語法錯(cuò)誤有語法錯(cuò)誤),讀入讀入a1并沿矢線所指方向并沿矢線所指方向前進(jìn)前進(jìn),過渡到下一狀態(tài)過渡到下一狀態(tài)(設(shè)為設(shè)為A1).(2)設(shè)當(dāng)前處在設(shè)當(dāng)前處在Ai狀態(tài)狀態(tài),所掃描的字符為所掃

7、描的字符為ai+1,在結(jié)點(diǎn)在結(jié)點(diǎn)Ai所射出的諸所射出的諸矢線中矢線中,尋找標(biāo)記為尋找標(biāo)記為ai+1的矢線的矢線(若不存在若不存在,則表明則表明w有語法錯(cuò)有語法錯(cuò)誤誤),讀入讀入ai+1,并進(jìn)入狀態(tài)并進(jìn)入狀態(tài)Ai+1;(3)重復(fù)重復(fù)(2),直到直到w中所有字符被讀完且恰好進(jìn)入終態(tài)中所有字符被讀完且恰好進(jìn)入終態(tài)F時(shí)時(shí),宣告宣告整個(gè)識別結(jié)束整個(gè)識別結(jié)束,w可被接受可被接受.顯然顯然,若我們從若我們從初態(tài)初態(tài)出發(fā)出發(fā),分別沿分別沿一切可能一切可能的的路徑路徑到達(dá)到達(dá)終態(tài)結(jié)點(diǎn)終態(tài)結(jié)點(diǎn),并并將中徑中將中徑中矢線上所標(biāo)記的字符矢線上所標(biāo)記的字符依次連接起來依次連接起來,便得到便得到狀態(tài)轉(zhuǎn)換狀態(tài)轉(zhuǎn)換圖圖所能識

8、別的所能識別的全部符號串全部符號串,這些符號串組成的集合構(gòu)成了該這些符號串組成的集合構(gòu)成了該識別的語言識別的語言= 80;0134256eniL字母字母字母字母數(shù)字?jǐn)?shù)字?jǐn)?shù)字= =；0124563L ine= 80; 標(biāo)識符 , Line 分隔符 , = 常量, 80 分隔符, ； 數(shù)字?jǐn)?shù)字字母字母1 1= =0 0 03; ;1輸入輸出有限控制器通過動(dòng)畫演示給出詞法分析程序的完成其功能的過程，同時(shí)給出識別的結(jié)果狀態(tài)轉(zhuǎn)換圖與文法推導(dǎo)u 用狀態(tài)轉(zhuǎn)換圖識別符號串 的過程，就是為 建立一個(gè)推導(dǎo)的過程。u 在第一步（在初始狀態(tài) 下，掃描到而過渡到下一狀態(tài)A A1 1），由狀態(tài)轉(zhuǎn)換圖的構(gòu)造規(guī)則可知，中必有

9、產(chǎn)生式;對于識別過程的后續(xù)步驟，由狀態(tài)A Ai i識別后過渡到恰好對應(yīng)了使用產(chǎn)生式最后在狀態(tài)識別后到達(dá)終態(tài) ，對應(yīng)了使用產(chǎn)生式進(jìn)行推導(dǎo)： u u 設(shè)設(shè)是一是一,是相應(yīng)的是相應(yīng)的,則從前面的討論可則從前面的討論可以看出如下事實(shí)：以看出如下事實(shí)：(1)在利用在利用對符號串對符號串進(jìn)行識別時(shí)進(jìn)行識別時(shí),中每次狀態(tài)的轉(zhuǎn)換都模擬了中每次狀態(tài)的轉(zhuǎn)換都模擬了一步直接推導(dǎo)一步直接推導(dǎo),即識別方法即識別方法(或稱分析方法或稱分析方法) 是是“ ”的的;(2)因因右線性文法右線性文法只有形如只有形如的產(chǎn)生式，所以推導(dǎo)的的產(chǎn)生式，所以推導(dǎo)的每一步所得句型只含一個(gè)非終結(jié)符，所以推導(dǎo)的每一步所得句型只含一個(gè)非終結(jié)符，所

10、以推導(dǎo)的規(guī)范規(guī)范的，每步的，每步所得的句型也必為所得的句型也必為規(guī)范句型規(guī)范句型；(3)對于對于所識別的任一符號串所識別的任一符號串 ,必存在必存在G中的一個(gè)推導(dǎo)中的一個(gè)推導(dǎo) (即有即有反之反之,對于對于中任一句子中任一句子 ,必存在一條從初必存在一條從初態(tài)態(tài) 到終態(tài)到終態(tài) 的路徑的路徑,此路徑上各矢線的標(biāo)記依次拼接起來所組此路徑上各矢線的標(biāo)記依次拼接起來所組成的符號串恰為成的符號串恰為u 設(shè)是一左線性文法,構(gòu)造相應(yīng)的狀態(tài)轉(zhuǎn)換圖的方法是:u 首先用的符標(biāo)記M的結(jié)點(diǎn),其中,開始符 對應(yīng)的結(jié)點(diǎn)為終態(tài)結(jié)點(diǎn).另外,再引入一個(gè)新結(jié)點(diǎn)作為初態(tài).矢線的連接規(guī)則為:(1)對于中形如 的產(chǎn)生式,引矢線:且標(biāo)記為

11、 ;(2)對于G中形如 的產(chǎn)生式,引矢,且標(biāo)記為 .已給文法已給文法G=(S,U,0,1,SS1 |U1, UU0 | 0,S)u 由構(gòu)造狀態(tài)轉(zhuǎn)換圖的方法可知,從初態(tài)從初態(tài)到下一狀態(tài)到下一狀態(tài)A A的轉(zhuǎn)換的轉(zhuǎn)換, ,對應(yīng)了形如對應(yīng)了形如 的產(chǎn)生式的產(chǎn)生式,即將終結(jié)符 歸約成非終結(jié)符;u 類似地,從狀態(tài)B轉(zhuǎn)換到狀態(tài) ,對應(yīng)了形對應(yīng)了形如如的產(chǎn)生式的產(chǎn)生式,即將歸約為 ;u 如此下去,直到從某狀態(tài) 轉(zhuǎn)換到狀態(tài)(終態(tài)),對應(yīng)了形如對應(yīng)了形如的產(chǎn)生式的產(chǎn)生式,即將歸約為開始符 .此時(shí)歸約成功,也恰好進(jìn)入了終態(tài),即狀態(tài)轉(zhuǎn)換圖識別了(或接受)該符號串.u 前面識別的例子對應(yīng)的歸約過程見右圖狀態(tài)轉(zhuǎn)換圖實(shí)際上

12、是有限自動(dòng)機(jī)的圖形表示3.3.1 確定的有限自動(dòng)機(jī)DFA1.1.抽象地看抽象地看, ,狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖由五個(gè)部分組成由五個(gè)部分組成: :(1)(1)有限個(gè)狀態(tài)之集有限個(gè)狀態(tài)之集, ,記作記作KK; ;(2)(2)有限個(gè)輸入符號組成的字母表有限個(gè)輸入符號組成的字母表, ,記作記作 ; ;(3)(3)從從KK到到KK的的轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù) f: Kf: KK. f(p,a)=qK. f(p,a)=q表示若當(dāng)前狀態(tài)表示若當(dāng)前狀態(tài)為為p p, ,且輸入符號為且輸入符號為a a, ,則進(jìn)入下一個(gè)狀態(tài)為則進(jìn)入下一個(gè)狀態(tài)為q q; ;(4)(4)S S0 0 KK, ,初始初始( (開始開始) )狀態(tài)狀態(tài)

13、; ;(5)(5)若干個(gè)終態(tài)之集若干個(gè)終態(tài)之集: : Z( Z( K )K )由上述五個(gè)要素組成的五元式由上述五個(gè)要素組成的五元式 M=(K, M=(K, , f,S, f,S0 0,Z ),Z )稱為一個(gè)稱為一個(gè)確定確定的有限自動(dòng)機(jī)的有限自動(dòng)機(jī) ( (DFADFA: : D Deterministic eterministic F Finite inite A Automatautomata) )由此可見由此可見, ,一一DFADFA實(shí)際上是狀態(tài)轉(zhuǎn)換圖的形式描述實(shí)際上是狀態(tài)轉(zhuǎn)換圖的形式描述( (數(shù)學(xué)定義數(shù)學(xué)定義), ),狀狀態(tài)轉(zhuǎn)換圖是態(tài)轉(zhuǎn)換圖是DFADFA的幾何的幾何( (圖形圖形) )表示

14、表示. .2.為定義DFA所接受(或識別)的符號串集合,我們先將其轉(zhuǎn)換函數(shù)f 的定義域拓廣到K* :(1)f (s, )=s, s K;(2)f (s,aw)=f ( f(s,a),w), s K,a,w*;由上面的定義可知,對于x* ,f(s,x)=t 的含義是,當(dāng)M從狀態(tài)s出發(fā),依次掃描完x的各個(gè)符號后將進(jìn)入狀態(tài)t.即只要f有定義,f與f的效果是一致的.我們稱DFA M接受(或識別)某符號串x*,用狀態(tài)轉(zhuǎn)換圖來說,就是從初態(tài)S0出發(fā),經(jīng)一恰好標(biāo)有x 的路徑后可達(dá)到某終態(tài)S Z ;用f描述就是: S Z, f(S0,x)=S M的接受集 我們把一DFA M所接受的符號串的全體稱為M的接受集,

15、記為L(M),即 L(M)= x | f(S0,x) Z,x* u 我們之所以把前面定義的有限自動(dòng)機(jī)有限自動(dòng)機(jī)稱為確定的FA，是因?yàn)樵跔顟B(tài)轉(zhuǎn)換的每一步，根據(jù)FA當(dāng)前的狀態(tài)及掃描的輸入字符，便能唯一地唯一地確定FA的下一狀態(tài)。在轉(zhuǎn)換圖上看，若|=n，則任何結(jié)點(diǎn)所引出的矢線至多有n條，且矢線上的標(biāo)記均不同。u 例如，P52圖3-4所對應(yīng)的DFA為 M=(R,U,S,0,1,f,R,S) 其中，f的定義如下：f(R,0)=Uf(U,0)=Uf(U,1)=Sf(S,1)=Su 由DFA與狀態(tài)轉(zhuǎn)換圖的關(guān)系可知，構(gòu)造狀態(tài)轉(zhuǎn)換圖的算法，同樣適用于構(gòu)造DFA。u 實(shí)際上，我們可以證明， 正規(guī)文法G， DFA

16、M，使L(M)=L(G)，反之亦然。3.3.2非確定的有限自動(dòng)機(jī)u 若在一左線性文法中含有若在一左線性文法中含有多個(gè)右部相同的產(chǎn)生式，多個(gè)右部相同的產(chǎn)生式，如如 AUa BUa CUa XUa,u 或在一右線性文法中同時(shí)或在一右線性文法中同時(shí)含有形如含有形如 UaA UaB UaC UaX 的產(chǎn)生式，的產(chǎn)生式，u 在相應(yīng)的狀態(tài)轉(zhuǎn)換圖中，在相應(yīng)的狀態(tài)轉(zhuǎn)換圖中，就會出現(xiàn)這樣的結(jié)點(diǎn)就會出現(xiàn)這樣的結(jié)點(diǎn)U，它具有多條標(biāo)記為同一輸它具有多條標(biāo)記為同一輸入符號入符號a的矢線，如右圖的矢線，如右圖所示所示由上圖可知，在由上圖可知，在U狀態(tài)下，輸狀態(tài)下，輸入符號為入符號為a時(shí)，時(shí)，F(xiàn)A的下一狀態(tài)的下一狀態(tài)不唯一

17、，而是在狀態(tài)集不唯一，而是在狀態(tài)集A,B,C,X中任選其一。具有中任選其一。具有這種性質(zhì)的這種性質(zhì)的FA稱為非確定的稱為非確定的FA（NFA: Nondeterministic FA）u 在形式上，NFA M同樣可用五元式定義：M=(K,f,S0,Z)，其中，K, ,S0,Z的含義同DFA,轉(zhuǎn)換函數(shù)f的定義為 f: K(K),即將(Si,aj)映射到K的一個(gè)子集Sk1,Skm u 類似地，我們可把f的定義域拓廣到K* ：(1) f(S,)=S;(2)f(S,aw)=f(f(S,a),w) a,w*.再設(shè) f(S,a)= Sk1,Skm ,且定義mikmikkkkwSfwaSffawSfwSfw

18、SSSfiim11),(),(),(:),(),(21則有這樣，我們已把f的定義域擴(kuò)大到(K) *。根據(jù)類似的理由，我們將對f和f不加區(qū)分u 對于對于x x* *, ,若集合若集合f(Sf(S0 0,x),x)中含有中含有Z Z中的元素（終態(tài)），則說明，至少中的元素（終態(tài)），則說明，至少存在一條從初態(tài)存在一條從初態(tài)S S0 0到某一終態(tài)的路到某一終態(tài)的路徑，此路徑上的符號之連接恰為徑，此路徑上的符號之連接恰為x x，此時(shí)，我們稱此時(shí)，我們稱x x為為M M所接受所接受u 所有為所有為M M所接受的符號串之集稱為所接受的符號串之集稱為NFA MNFA M的接受集（或識別集），記的接受集（或識別集

19、），記作作 L(M).L(M).即即 L(M)L(M)=x | f(Sx | f(S0 0, , x )x ) Z Z , x, x u 例例3.13.1 給定給定M= (S,A,B,C, M= (S,A,B,C, a,b, f , S ,C),a,b, f , S ,C),其狀態(tài)轉(zhuǎn)換其狀態(tài)轉(zhuǎn)換圖見右。由圖可知圖見右。由圖可知M M是一是一NFANFA。u M M識別符號串識別符號串a(chǎn)babbababb的路徑為的路徑為 S(S(a a) )A(A(b b) )B(B(a a) )A(A(b b) )B(B(b b) )C C( (接受接受) )。( (參見書中參見書中P60P60的表的表) )

20、注意注意，NFANFA識別輸入符號串識別輸入符號串時(shí)有一個(gè)試探過程，為了能時(shí)有一個(gè)試探過程，為了能走到終態(tài)，往往要走許多彎走到終態(tài)，往往要走許多彎路（路（帶回溯帶回溯），這影響了），這影響了FAFA的效率。的效率。3.3.3 對于字母表對于字母表 上的任一上的任一NFA M，必存在與，必存在與M等價(jià)的等價(jià)的DFA M 令令I(lǐng)是一個(gè)狀態(tài)集的子集，定義是一個(gè)狀態(tài)集的子集，定義-closure（I）為：）為：1）若）若sI，則，則s-closure（I）；）；2）若）若sI，則從，則從s出發(fā)經(jīng)過任意條出發(fā)經(jīng)過任意條弧能夠到達(dá)的弧能夠到達(dá)的任何狀態(tài)都屬于任何狀態(tài)都屬于-closure（I）。）。 狀態(tài)

21、集狀態(tài)集-closure（I）稱為）稱為I的的-閉包閉包我們可以通過一例子來說明狀態(tài)子集的-閉包的構(gòu)造方法非確定有限自動(dòng)機(jī)的確定化集合I的-閉包的定義例：如圖所示的狀態(tài)圖：令I(lǐng)=1，求-closure（I）=？156432aaa根據(jù)定義：-closure（I）=1，3我們同樣可以通過一例子來說明上述定義,仍采用前面給定的狀態(tài)圖為例- J是從狀態(tài)子集I中的每個(gè)狀態(tài)出發(fā),經(jīng)過標(biāo)記為a的弧而達(dá)到的狀態(tài)集合.-Ia是狀態(tài)子集,其元素為J中的狀態(tài),加上從J中每一個(gè)狀態(tài)出發(fā)通過弧到達(dá)的狀態(tài)定義2: 令I(lǐng)是NFA M的狀態(tài)集的一個(gè)子集, a,定義: Ia=-closure(J) 其中其中J = f(s,a)

22、SI例：令I(lǐng)=1 Ia=-closure(J) =-closure(f(1，a) =-closure(2，4)=2，4，6156432aaaNFA確定化子集法u 設(shè)設(shè) M=(K,M=(K, ,f,S0,Z) ,f,S0,Z) 是是 上的上的NFANFA，現(xiàn)構(gòu)造，現(xiàn)構(gòu)造 上上DFA DFA M M=（K, , ,f,S0,Z).方法如下：方法如下：首先從S0出發(fā)，求出-closure(S0)，記為DFA的初態(tài)q0，依次推導(dǎo)直到?jīng)]有新狀態(tài)產(chǎn)生。步驟如下：u 1、令k=-closure(s0)(即為DFA的初態(tài))u 2、對于k中的任一尚未標(biāo)記的狀態(tài)qi=si1,si2sik,sik K,作u i)標(biāo)

23、記qi；u ii)對于每個(gè)a ，置u qj= -closure(f(qi,a),若qj不在k中，則作為一個(gè)未標(biāo)記的狀態(tài)添加到k中，繼續(xù)循環(huán)。例：有NFA M 先從狀態(tài)1開始，即I=1 a1234startabaccI=-closure(1)=1,4Ia=-closure(f(1,a)f(4,a)=-closure(2,3) = -closure (2,3)=2,3Ib= -closure(f(1,b)f(4,b)=-closure()=Ic= -closure(f(1,c)f(4,c)=從上一步中獲得新狀態(tài)2,3,再計(jì)算I=2,3的Ia,Ib,得到I=2,3, Ia=2,Ib=4,Ic=3,4

24、1234startabacc I Ia Ib Ic 1,4 2,3 2,3 2 4 3,4 2 2 4 4 3,4 3,4 將求得的狀態(tài)轉(zhuǎn)換矩陣重新編號DFA M狀態(tài)轉(zhuǎn)換矩陣： 符號狀態(tài)abc0 2 341221_3344DFA M的狀態(tài)圖：01423start1,42,342acabbc注意：包含原初始狀態(tài)注意：包含原初始狀態(tài)1的狀態(tài)子集為的狀態(tài)子集為DFA M的初態(tài)的初態(tài) 包含原終止?fàn)顟B(tài)包含原終止?fàn)顟B(tài)4的狀態(tài)子集為的狀態(tài)子集為DFA M的終態(tài)。的終態(tài)。3,4自動(dòng)機(jī)的簡化一個(gè)DFA M的化簡是指尋找一個(gè)狀態(tài)數(shù)比較少的DFA M,使L(M)=L(M)。DFA的最小化就是尋求最小狀態(tài)DFA1、最

25、小狀態(tài)、最小狀態(tài)DFA的含義的含義:u 沒有多余狀態(tài)(死狀態(tài))u 沒有兩個(gè)狀態(tài)是互相等價(jià)（不可區(qū)別）2、狀態(tài)、狀態(tài)S和和T等價(jià)的條件等價(jià)的條件 一致性條件 狀態(tài)S和T必須同時(shí)為可接受狀態(tài)或不可接受狀態(tài)。 蔓延性條件 對于所有輸入符號，狀態(tài)S和狀態(tài)T必須轉(zhuǎn)換到等價(jià)的狀態(tài)里。 3、 DFA的最小化的方法（分割法）的最小化的方法（分割法）方法：將DFA的狀態(tài)分割成一些互不相交的子集。“分割法”u DFA的最小化算法的核心u 把一個(gè)DFA的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個(gè)狀態(tài)都是等價(jià)的.u 算法：u A、將所有狀態(tài)分成兩個(gè)子集終態(tài)集和非終態(tài)集u

26、B、運(yùn)用狀態(tài)等價(jià)原則分別對兩個(gè)子集的狀態(tài)進(jìn)行分析和劃分，把互相等價(jià)的狀態(tài)構(gòu)成一個(gè)子組。u 兩個(gè)狀態(tài)s和t分在同一子組的充要條件是：對所有的輸入符號a，狀態(tài)s和t都轉(zhuǎn)換為同一組中的狀態(tài)。若發(fā)現(xiàn)不等價(jià)，繼續(xù)劃分，這樣FA的狀態(tài)被分成互不相交的若干子集。u C、從每個(gè)子組中選出一個(gè)狀態(tài)做代表，即可構(gòu)成簡化的FA例:最小化5724361srartaaaaaaabbbbbbb解:(一)區(qū)分終態(tài)與非終態(tài)12345663731546737414212ab123456637315467374142ab123區(qū)號區(qū)號當(dāng)輸入a時(shí)，6，7狀態(tài)在區(qū)號為2的子集內(nèi)，即可以將區(qū)號為1中的1，2化為一個(gè)子集12345663

27、7315467374142ab12431243123456637315467374142ab5區(qū)號區(qū)號將區(qū)號代替狀態(tài)號得:12345ab521435523115 5243aaaaabbbbb到目前為止,我們已了解了對于任意三型語言L(G),存在DFA M使L(M)=L(G),反之,任意的M,存在G,使L(G)=L(M).這稱為描述語言的等價(jià)性.本節(jié)將引入正規(guī)表達(dá)式正規(guī)表達(dá)式的概念,它們可用于描述三描述三型語言的特征型語言的特征,特別是對自動(dòng)生成詞法分析程序而言，它是非常有用的工具。所謂正規(guī)表達(dá)式正規(guī)表達(dá)式就是用特定的運(yùn)算符運(yùn)算符及運(yùn)算對象運(yùn)算對象按某種規(guī)則構(gòu)造的表達(dá)式，用于描述給定三型語用于描

28、述給定三型語言的所有句子。言的所有句子。3.4.1正規(guī)表達(dá)式及正規(guī)集的定義u 定義 設(shè)是一字母表,則上的正規(guī)表達(dá)式正規(guī)表達(dá)式(正則表達(dá)式,正規(guī)式)及其表示的正規(guī)集正規(guī)集可遞歸定義如下:(1) 是一正規(guī)式, 相應(yīng)的正規(guī)集為;(2) 是一正規(guī)式, 相應(yīng)的正規(guī)集為;(3) a,a 是一正規(guī)式, 相應(yīng)的正規(guī)集為a;(4) 設(shè)r,s是正規(guī)式, 且它們所表示的正規(guī)集為Lr,Ls,則1. (r) (s)是正規(guī)式, 相應(yīng)的正規(guī)集為LrLs;2. (r)|(s)是正規(guī)式, 相應(yīng)的正規(guī)集為Lr Ls;3. (r)*是正規(guī)式, 相應(yīng)的正規(guī)集為Lr*有限地使用上面的規(guī)則(4),所得的表達(dá)式均是正規(guī)式.定義中的括號主要

29、用于規(guī)定運(yùn)算順序.我們規(guī)定優(yōu)先級從高到低依次為 *, , |,則可以省略一些括號,例如(r) (s)*)|(r) 可簡寫為r s*|r.另外, 常?？墒÷圆粚? rs*|r正規(guī)式與正規(guī)集的例子符號串的長度大等于符號串長度為偶數(shù)的符號串結(jié)尾的任何以正規(guī)集正規(guī)式babababababbbaabaabaabbabbbabaaabaabababaababaaaaaaaaaaaaaaaiiii,2)|)(|)(|(,)|(,)|(,|,|,*00*給定正規(guī)式給定正規(guī)式, ,它唯一確定一它唯一確定一正規(guī)集正規(guī)集; ;反之反之不真不真. .即一個(gè)即一個(gè)正規(guī)集可由多正規(guī)集可由多個(gè)個(gè) 不同的正不同的正規(guī)式表示規(guī)

30、式表示. .若二正規(guī)式描若二正規(guī)式描述同一正規(guī)集述同一正規(guī)集, ,則稱二式則稱二式( (相等相等) )正規(guī)式間的基正規(guī)式間的基本等價(jià)關(guān)系見本等價(jià)關(guān)系見下頁下頁. .正規(guī)式公理正規(guī)式公理u A1. r|s=s|rA2. r|r=ru A3. r|=rA4. (r|s)|t=r|(s|t)u A5. (rs)t=r(st)A6. r(s|t)=rs|rtu A7. (s|t)r=sr|st A8. r=r=u A9. r=r=rA10. r*=(|r)*=|rr* 例子例子例：令=l,d，則上的正規(guī)式 r=l(ld)定義的正規(guī)集為:l,ll,ld,ldd,其中l(wèi)代表字母,d代表數(shù)字。 正規(guī)式即是“

31、字母(字母|數(shù)字) ” ,它表示的正規(guī)集中的每個(gè)元素的模式是“字母打頭的字母數(shù)字串”,這就是C和多數(shù)程序語言的標(biāo)識符詞法規(guī)則.例：令=d，e，+，-,則上的正規(guī)式d(dd )(e(+- )dd )表示的是無符號數(shù)的集合。其中d為09的數(shù)字。 程序設(shè)計(jì)語言的單詞都能用正規(guī)式程序設(shè)計(jì)語言的單詞都能用正規(guī)式 來定義來定義. .利用以下轉(zhuǎn)換規(guī)則利用以下轉(zhuǎn)換規(guī)則, ,直至只剩下一個(gè)開始符號定義直至只剩下一個(gè)開始符號定義的產(chǎn)生式的產(chǎn)生式, ,并且產(chǎn)生式的右部不含非終結(jié)符并且產(chǎn)生式的右部不含非終結(jié)符. .3.4.2 由正規(guī)文法構(gòu)造相應(yīng)的正規(guī)式由正規(guī)文法構(gòu)造相應(yīng)的正規(guī)式規(guī)則規(guī)則規(guī)則規(guī)則1規(guī)則規(guī)則2規(guī)則規(guī)則4文法產(chǎn)生式文法產(chǎn)生式正則式正則式AxB,ByAxA|yAx,AyA=xyA=x*yA=x|y規(guī)則規(guī)則3AAx|yA=yx*例:有文法Gs SaA|a, AaA|dA|a|d于是: S=aA|a A=(aA|dA)|(a|d)A=(a|d)A|(a|d)由規(guī)則二: A=(a|d)*(a|d) 代入:S=a(a|d)*(a|d)|a 于是: