第三章 詞法分析

第三章詞法分析詞法分析概述正則表達(dá)式與有窮狀態(tài)自動(dòng)機(jī)詞法分析程序的實(shí)現(xiàn)詞法分析程序的自動(dòng)生成1第一節(jié)詞法分析程序詞法分析是編譯過(guò)程中的第一個(gè)階段，其任務(wù)是：從左到右逐個(gè)字符地對(duì)源程序進(jìn)行掃描，產(chǎn)生一個(gè)個(gè)單詞符號(hào)。源程序（字符串形式）中間程序（單詞符號(hào)串形式）問(wèn)題：1、什么是單詞符號(hào)？2、單詞符號(hào)該如何表示？3、如何識(shí)別出單詞？21、單詞符號(hào)單詞符號(hào)是程序語(yǔ)言的基本語(yǔ)法單位，一般分為下面5種：關(guān)鍵字（基本字）：（個(gè)數(shù)確定，可全體編為一類(lèi)，也可一字一類(lèi))標(biāo)識(shí)符：（個(gè)數(shù)不確定，作為一類(lèi)）常數(shù)：各種類(lèi)型的常數(shù)。(個(gè)數(shù)不確定，按類(lèi)型分類(lèi))運(yùn)算符：如+、-、*、/、<等。(個(gè)數(shù)確定，一符一類(lèi))界符：如，、；、（、）、:等。(個(gè)數(shù)確定,一符一類(lèi))注意：一種語(yǔ)言的單詞如何分類(lèi)、怎樣編碼，主要取決于技術(shù)上的方便。32、單詞的表示形式詞法分析程序輸出的單詞符號(hào)通常用二元式表示：（單詞種別，單詞自身的值）單詞種別：表示單詞種類(lèi)，常用整數(shù)編碼，它是語(yǔ)法分析需要的單詞自身的值：是編譯中其他階段所需要的信息如果一個(gè)種別只含一個(gè)單詞符號(hào)，那么該單詞符號(hào)的種別編碼就完全代表它自身的值。如果一個(gè)種別含有多個(gè)單詞符號(hào)，那么還應(yīng)給出該單詞符號(hào)的自身值：標(biāo)識(shí)符自身值是標(biāo)識(shí)符自身的字符串；常數(shù)自身值是常數(shù)的二進(jìn)制數(shù)值。4單詞符號(hào)種別begin1if2then3while4do5end6identifier10digit11+13……5例如：程序段if(a>1)b=10;假定基本字、運(yùn)算符、界符都是一符一種。

它所輸出的單詞符號(hào)是：(2,)基本字if(29,)左括號(hào)((10,’a’)標(biāo)識(shí)符a(23,)大于號(hào)>(11,’1’的二進(jìn)制)常數(shù)1

(30,)

右括號(hào))(10,’b’)標(biāo)識(shí)符b(17,)賦值號(hào)=(11,’10’的二進(jìn)制)常數(shù)10(26,)分號(hào)；63、單詞的識(shí)別在詞法分析中，可以用狀態(tài)轉(zhuǎn)換圖來(lái)識(shí)別單詞。例如狀態(tài)轉(zhuǎn)換圖是有限的有向圖，結(jié)點(diǎn)表示狀態(tài)，用圓圈表示；結(jié)點(diǎn)之間可以用有向邊連接，有向邊上可標(biāo)記字符。7詞法分析程序的設(shè)計(jì)對(duì)于狀態(tài)圖中每一個(gè)狀態(tài)構(gòu)造一段代碼，代碼功能為：（1）從輸入串中讀入一個(gè)字符；（2）判明讀入的字符與由此狀態(tài)出發(fā)的哪條弧上的標(biāo)記相匹配，則轉(zhuǎn)至相匹配的那條弧所指向的狀態(tài)。（3）均不匹配時(shí)便失敗。8第二節(jié)正則表達(dá)式正則表達(dá)式是一種適合描述符號(hào)的表示法，可由它定義正規(guī)集。正規(guī)集即為正規(guī)式所描述的串的集合。一般用L()表示。采用正則表達(dá)式的原因：詞法規(guī)則簡(jiǎn)單，容易被理解；從它容易構(gòu)造高效識(shí)別程序；可由正則表達(dá)式構(gòu)造詞法分析程序；可用于其他各種信息流的處理。91、正則表達(dá)式的定義設(shè)為字母表，則的正則表達(dá)式按照下列規(guī)則遞歸地定義：(1)都是上的正規(guī)式，表示為L(zhǎng)()={}；(2)是上的正規(guī)式，表示為L(zhǎng)()={}；(3)對(duì)于任何a，a是上的一個(gè)正規(guī)式，表示為L(zhǎng)(a)={a}；(4)（遞歸定義）若r和s都是上的正規(guī)式，則(r)是上的正規(guī)式，表示集合L((r))=L(r)；rs是上的正規(guī)式，表示集合L(r|s)=L(r)∪L(s)；rs是上的正規(guī)式，表示集合L(rs)=L(r)L(s)；r*是上的正規(guī)式，表示集合L(r*)=(L(r))*。10例：令={a，b}，上的正規(guī)式和相應(yīng)的正規(guī)集的例子有：正規(guī)式 正規(guī)集a {a}ab {a,b}ab {ab}(ab)(ab) {aa,ab,ba,bb}a {,a,a,……任意個(gè)a的串}11

(ab)表示正規(guī)集{,a,b,aa,ab……所有由a和b組成的串}(ab)(aabb)(ab)

表示正規(guī)集{上所有含有兩個(gè)相繼的a或兩個(gè)相繼的b組成的串}12例：若={a，b}，則字符串集合S={anban|n≠0}可以用正規(guī)式描述嗎？132、程序設(shè)計(jì)語(yǔ)言中的正規(guī)式實(shí)例令Σ={letter,digit}，則Σ上的正規(guī)式r=letter(letter|digit)*可以用來(lái)表示標(biāo)識(shí)符。令Σ={d,.,e,+,-}，則Σ上的正規(guī)式r=d*(.dd*|ε)(e(+|-|ε)dd*|ε)可以用來(lái)表示無(wú)符號(hào)浮點(diǎn)數(shù)。其中d表示digit,即0-9數(shù)字。143、正則表達(dá)式的等價(jià)如果正則表達(dá)式r與s表示的正則集相同，即值相等，則稱(chēng)它們是等價(jià)的。記為

r=s例：b{ab}={ba}b{a|b}={{a}}15例：判斷下述正規(guī)式之間是否等價(jià)。1）(a|b)*與a*|b*2）(ab)*與a*b*3）(a|b)*與(a*b*)*答：1）、2）不等價(jià)，3）等價(jià)164、正則表達(dá)式的性質(zhì)設(shè)e、e1、e2、e3均為正則表達(dá)式，則e|=|e=ee=e=(零正則表達(dá)式)e=e=e(單位正則表達(dá)式)e1|e2=e2|e1(交換律)e1|(e2|e3)=(e1|e2)|e3e1(e2e3)=(e1e2)e3(結(jié)合律)e1(e2|e3)=e1e2|e1e3

(e1|e2)e3=e1e3|e2e3(分配律)17舉例1、在字母表Σ={a,b,c}中，考慮僅包括一個(gè)b的所有串的集合。2、給出字母表Σ={a,b,c}上的一個(gè)正則表達(dá)式，((b|c)*a(b|c)*a)*(b|c)*簡(jiǎn)要描述它所生成的語(yǔ)言。3、試為Pascal語(yǔ)言的注釋部分編寫(xiě)正則表達(dá)式。

18狀態(tài)轉(zhuǎn)換圖確定有窮狀態(tài)自動(dòng)機(jī)（DFA）非確定有窮狀態(tài)自動(dòng)機(jī)（NFA）把NFA變?yōu)镈FADFA的化簡(jiǎn)第三節(jié)有窮狀態(tài)自動(dòng)機(jī)（FA）19有窮自動(dòng)機(jī)是依據(jù)某些輸入而改變狀態(tài)的機(jī)器或程序?？梢杂脿顟B(tài)轉(zhuǎn)換圖來(lái)表示。有窮自動(dòng)機(jī)是有向圖這種通用結(jié)構(gòu)的一個(gè)實(shí)例，在動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)和高級(jí)搜索方面有許多應(yīng)用。序201、狀態(tài)轉(zhuǎn)換圖有向圖，結(jié)點(diǎn)表示狀態(tài)，用圓圈表示；結(jié)點(diǎn)之間可以用有向邊連接，有向邊上標(biāo)記影響狀態(tài)改變的可能輸入的字符；21狀態(tài)轉(zhuǎn)換圖舉例例1：字符串必須以空格開(kāi)始和結(jié)束，中間可以有0個(gè)或任意多個(gè)由a~z組成的字符串。22例2：Pascal語(yǔ)言中關(guān)系運(yùn)算符識(shí)別的狀態(tài)轉(zhuǎn)換圖。

051624837return(relop,LE)return(relop,NE)return(relop,LT)return(relop,GE)return(relop,GT)return(relop,EQ)開(kāi)始<=>=>=**otherother23123開(kāi)始letterotherletter或digitreturn(id)例3：標(biāo)識(shí)符識(shí)別的狀態(tài)轉(zhuǎn)換圖。24思考：無(wú)符號(hào)浮點(diǎn)數(shù)的狀態(tài)轉(zhuǎn)換圖。252、確定的有窮狀態(tài)自動(dòng)機(jī)一個(gè)確定的有窮自動(dòng)機(jī)（DFA）D是一個(gè)五元組D=（K，Σ，M，S，F(xiàn)），其中

K：有窮非空的狀態(tài)集合；Σ：有窮非空的輸入符號(hào)字母表；M：轉(zhuǎn)換函數(shù)，是在K×Σ→K上的映像，即，如M（ki，a）=kj，（ki∈K，kj∈K）就意味著，當(dāng)前狀態(tài)為ki，輸入符為a時(shí)，將轉(zhuǎn)換為下一個(gè)狀態(tài)kj，我們把kj稱(chēng)作ki的一個(gè)后繼狀態(tài)；

S:S∈K是唯一的一個(gè)初態(tài)；F:FK是非空的終態(tài)集合。26從狀態(tài)轉(zhuǎn)換圖構(gòu)造DFADFAD=（{S，Z，A，B}，{a，b}，M，S，{Z}），其中M定義為：M（S，a）=AM（S，b）=BM（A，a）=ZM（A，b）=BM（B，a）=AM（B，b）=Z M（Z，a）=Z abSABabZbaa例1：從下面狀態(tài)圖構(gòu)造DFA。27例2：構(gòu)造一個(gè)識(shí)別語(yǔ)言(a|b)*ab的有窮自動(dòng)機(jī)。從正則表達(dá)式構(gòu)造有窮自動(dòng)機(jī)12開(kāi)始a0abb輸入符號(hào)ab0{0,1}{0}1{2}2狀態(tài)28例設(shè)ＤＦＡＭ＝（｛０,１,２,３｝，｛ａ,ｂ｝，f，０，｛３｝）其中f（０，ａ）＝１，f（１，ａ）＝3f（２，ａ）＝１，f（３，ａ）＝３f（０，ｂ）＝２，f（１，ｂ）＝２f（２，ｂ）＝３，f（３，ｂ）＝３29轉(zhuǎn)換矩陣3b012aaaabbb3狀態(tài)轉(zhuǎn)換圖易存儲(chǔ)30

從狀態(tài)轉(zhuǎn)換圖看，從初態(tài)出發(fā)，沿任一條路徑到達(dá)接受狀態(tài)，這條路徑上的弧上的標(biāo)記符號(hào)連接起來(lái)構(gòu)成的符號(hào)串被接受(識(shí)別)。DFAM所能識(shí)別的字的全體即L(M)。字集V是正規(guī)的ifV=L（M）012aaaabbb3b31非確定有窮狀態(tài)自動(dòng)機(jī)一個(gè)非確定的有窮自動(dòng)機(jī)（NFA）D是一個(gè)五元組：N=（K，Σ，M，S，F(xiàn)）其中K：有窮非空的狀態(tài)集合；Σ：有窮非空的輸入字母表；M：轉(zhuǎn)換函數(shù)，是在K×Σ到K的子集所組成集合的映像，M(R,T)={Q1,Q2,….Qn}S:SK是非空的初態(tài)集合；F:FK是非空的終態(tài)集合.32DFA與NFA的區(qū)別DFANFA開(kāi)始狀態(tài)唯一一個(gè)或多個(gè)映像單個(gè)狀態(tài)狀態(tài)集合33舉例與右圖所示對(duì)應(yīng)的有一個(gè)NFA，N=({S,A,B,Z},{a,b},M,{S},{Z})其中M：M(S,a)={A}M(S,b)={B}M(A,a)={Z}M(A,b)={B}M(B,a)={A,B}M(B,b)={Z}M(Z,a)={A,Z}abaaaabSABabZbSABabZaabSABabZ34對(duì)于輸入字符串babbabb，運(yùn)行該NFA步驟當(dāng)前狀態(tài)輸入的其余部分可能的后繼選擇1SbabbabbBB2BabbabbA,BA3AbbabbBB4BbabbZZ5ZabbA,ZA6AbbBB7BbZZ35練習(xí)：某操作系統(tǒng)下合法的文件名為device:name.extention其中第一部分（device:）和第三部分（.extention）可缺省，若device、name和extention都是字母串，長(zhǎng)度不限，但至少為１，畫(huà)出識(shí)別這種文件名的DFA。36第四節(jié)

由正則式構(gòu)造有窮自動(dòng)機(jī)A為有窮狀態(tài)自動(dòng)機(jī)，e為正則表達(dá)式，則存在L(A)=|e|，即正則表達(dá)式與有窮自動(dòng)機(jī)之間具有等價(jià)性。任何兩個(gè)有窮自動(dòng)機(jī)M和M’，若它們識(shí)別的語(yǔ)言相同(L(M)=L(M’))，則稱(chēng)M和M’等價(jià)。37一、由正則表達(dá)式構(gòu)造等價(jià)的NFAM1、由正則表達(dá)式R表示成如圖所示的拓廣轉(zhuǎn)換圖。XYR2、對(duì)正則式采用如下規(guī)則構(gòu)造對(duì)應(yīng)的NFAM。SiSjr1|r2SiSjr1r2SiSjr1r2SiSjSkr1r2SiSjr*SiSjSkεεr3、逐步運(yùn)用上述3個(gè)規(guī)則不斷在1、圖中增加新結(jié)點(diǎn)進(jìn)行分解，直到每條有向邊上僅標(biāo)識(shí)有Σ中的一個(gè)字母或ε為止，則NFAM構(gòu)造完成。38舉例對(duì)給定正規(guī)式b*(d|ad)(b|ab)+，構(gòu)造其N(xiāo)FAM。εεεεbbbbbaaadd39定義1：集合I的ε-閉包：令I(lǐng)是一個(gè)狀態(tài)集的子集，定義ε-closure（I）為：1）若s∈I，則s∈ε-closure（I）；2）若s∈I，則從s出發(fā)經(jīng)過(guò)任意條ε弧能夠到達(dá)的任何狀態(tài)都屬于ε-closure（I）。狀態(tài)集ε-closure（I）稱(chēng)為I的ε-閉包為了使得NFA確定化，我們首先給出兩個(gè)定義：56432aεaaε1例：如圖所示的狀態(tài)圖：令I(lǐng)={1}，求ε-closure（I）=？根據(jù)定義：ε-closure（I）={1，3}40將NFAN=（Q，，f，S，Z）確定化為DFAM的方法（子集法）（舉例說(shuō)明）（1）置DFAM中的狀態(tài)集Q‘,Z’為集（2）給出M的初態(tài)S’=E-CLOSER({S}),并把S’置為未標(biāo)記狀態(tài)后加入到Q’中。（未標(biāo)記狀態(tài)為新?tīng)顟B(tài)）(3)如果Q’中存在未標(biāo)記的狀態(tài)T={q1,q2…qn},qi∈Q則進(jìn)行如下變換：1）對(duì)于每個(gè)a∈,置J=f({q1,q2…qn},a)=f(q1,a)f(q2,a)…f(qn,a)U=E-CLOSER(I)如果U不在Q’中，則將U置為無(wú)標(biāo)記的狀態(tài)添加到Q’中，且把狀態(tài)轉(zhuǎn)移f’(T,a)=U添加到M中，如果U至少含有一個(gè)元素是N的終態(tài)，則把U置為M的終態(tài)，即把U添加到Z’中。2）對(duì)T置標(biāo)記（表示T不再是新加入Q’中的狀態(tài)）。（4）重復(fù)進(jìn)行步驟（3）,直到Q’中不再含有未標(biāo)記的狀態(tài)為止。（5）重新命名Q’中的狀態(tài)，最后獲得等價(jià)的DFAM.41——J是從狀態(tài)子集I中的每個(gè)狀態(tài)出發(fā)，經(jīng)過(guò)標(biāo)記為a的弧而達(dá)到的狀態(tài)集合.——Ia是狀態(tài)子集,其元素為J中的狀態(tài)，加上從J中每一個(gè)狀態(tài)出發(fā)通過(guò)ε弧到達(dá)的狀態(tài)定義2:令I(lǐng)是NFAM’的狀態(tài)集的一個(gè)子集,a∈Σ定義:Ia=ε-closure(J)其中J=∪δ(s,a)S∈I56432aεaaε1例：令I(lǐng)={1}，求Ia=?Ia=ε-closure(J)=ε-closure(δ(1，a)）=ε-closure({2，4}）={2，4，6}42例：有NFAM，求DFAM’。a1234startabaccεI=ε-closure({1})={1,4}Ia=ε-closure(δ(1,a)∪δ(4,a))=ε-closure({2,3}∪φ）=ε-closure({2,3})={2,3}Ib=ε-closure(δ(1,b)∪δ(4,b))=ε-closure(φ）=φIc=ε-closure(δ(1,c)∪δ(4,c))=φI={2,3},Ia={2},Ib={4},Ic={3,4}…IIaIbIc

{1,4}{2,3}φφ{(diào)2,3}{2}{4}{3,4}{2}{2}{4}φ{(diào)4}φφφ{(diào)3,4}φφ{(diào)3,4}初態(tài)43startIIaIbIc

{1,4}{2,3}φφ{(diào)2,3}{2}{4}{3,4}{2}{2}{4}φ{(diào)4}φφφ{(diào)3,4}φφ{(diào)3,4}符號(hào)狀態(tài)abc02341221________3344DFAM’狀態(tài)轉(zhuǎn)換矩陣將求得的狀態(tài)轉(zhuǎn)換矩陣重新編號(hào)01423{1,4}{2,3}{4}{2}acabbc{3,4}44結(jié)論：NFAM通過(guò)“子集法”可以確定化為DFAM″，它們接收語(yǔ)言的能力是等價(jià)的，通常不區(qū)分（確定化時(shí)除外），合稱(chēng)為有限自動(dòng)機(jī)(finiteautomata)（FA）。

45“對(duì)于任一個(gè)DFA，存在一個(gè)唯一的狀態(tài)最少的等價(jià)的DFA”一個(gè)有窮自動(dòng)機(jī)是化簡(jiǎn)的

它沒(méi)有多余狀態(tài)并且它的狀態(tài)中沒(méi)有兩個(gè)是互相等價(jià)的。一個(gè)有窮自動(dòng)機(jī)可以通過(guò)消除多余狀態(tài)和合并等價(jià)狀態(tài)而轉(zhuǎn)換成一個(gè)最小的與之等價(jià)的有窮自動(dòng)機(jī)。3.4.5DFA的化簡(jiǎn)(最小化)46定義：(1)有窮自動(dòng)機(jī)的多余狀態(tài)：從該自動(dòng)機(jī)的開(kāi)始狀態(tài)出發(fā)，任何輸入串也不能到達(dá)那個(gè)狀態(tài)。01s0s1s2s3s5s7s1s5s1s2s2s5s5s1s1s3s0s1例:s0為初始狀態(tài)畫(huà)狀態(tài)圖可以看出s4,s6,s8為不可達(dá)狀態(tài)應(yīng)該消除01s0s1s2s3s4s5s6s7s8s1s5s7s2s2s5s5s7s5s6s1s3s8s0s0s1s3s647等價(jià)狀態(tài)狀態(tài)s和t的等價(jià)條件是:對(duì)于所有輸入符號(hào)c，Ic(s)=Ic(t)，即狀態(tài)s、t對(duì)于c具有相同的后繼，則稱(chēng)s，t是等價(jià)的。（任何有后繼的狀態(tài)和任何無(wú)后繼的狀態(tài)一定不等價(jià)）一個(gè)DFAM的狀態(tài)最少化過(guò)程：將M的狀態(tài)集分割成一些不相交的子集，任何不同的兩子集中的狀態(tài)都是可區(qū)別的，同一子集中的任何兩狀態(tài)都是等價(jià)的；最后，在每個(gè)子集中選一個(gè)狀態(tài)作代表，消去其他狀態(tài)，得到最少狀態(tài)的等價(jià)DFAM’。48“分割法”：把一個(gè)DFA(不含多余狀態(tài))的狀態(tài)分割成一些不相關(guān)的子集，使得任何不同的兩個(gè)子集狀態(tài)都是可區(qū)別的，而同一個(gè)子集中的任何狀態(tài)都是等價(jià)的.例1:最小化5724361srartaaaaaaabbbbbbb狀態(tài)集的劃分將所有DFA的終態(tài)與其它狀態(tài)劃分成兩個(gè)子集G1,G2;分別從兩個(gè)子集G1,G2中尋找等價(jià)狀態(tài)進(jìn)行化簡(jiǎn)。49解:(一)區(qū)分終態(tài)與非終態(tài)12345663731546737414212ab567374142ab123463731546123區(qū)號(hào)區(qū)號(hào)5724361srartaaaaaaabbbbbbb將所有DFA的終態(tài)與其它狀態(tài)劃分成兩個(gè)子集50123456637315467374142ab12431243123456637315467374142ab5區(qū)號(hào)區(qū)號(hào)12345ab5214355231155243aaaaabbbbb567374142ab123463731546123區(qū)號(hào)將區(qū)號(hào)代替狀態(tài)號(hào)得:51練習(xí)：有正則式(a|b)*(aa|bb)(a|b)*，試為其構(gòu)造最簡(jiǎn)的DFA。521、NFA的確定化X13ba2y6ba45aabb采用子集構(gòu)造法對(duì)NFA進(jìn)行確定化。53

狀態(tài)Sdabd:Sd1aSd2d:Sd1bSd2Sd0={x,3,1}{3,4,1}{3,5,1}{3,4,1}{3,2,4,1,6,y}{3,5,1}{3,5,1}{3,4,1}{3,2,5,1,6,y}{3,2,4,1,6,y}{3,2,4,6,1,y}{3,5,6,1,y}{3,2,5,1,6,y}{3,4,6,1,y}{3,2,5,6,1,y}54

狀態(tài)Sdabd:Sd1aSd2d:Sd1bSd2{3,5,6,1,y}{3,6,4,1,y}{3,2,6,5,1,y}{3,4,6,1,y}{3,2,6,4,1,y}{3,6,5,1,y}55{x,3,1}{3,4,1}{3,5,1}{3,2,4,1,6,y}{3,2,5,1,6,y}{3,5,6,1,y}{3,4,6,1,y}abaabababbabab560123456abaabababbabab57