第三章 詞法分析

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

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

(30,)

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

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

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

r=s例：b{ab}={ba}b{a|b}={{a}}15例：判斷下述正規(guī)式之間是否等價。1）(a|b)*與a*|b*2）(ab)*與a*b*3）(a|b)*與(a*b*)*答：1）、2）不等價，3）等價164、正則表達式的性質(zhì)設e、e1、e2、e3均為正則表達式，則e|=|e=ee=e=(零正則表達式)e=e=e(單位正則表達式)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}中，考慮僅包括一個b的所有串的集合。2、給出字母表Σ={a,b,c}上的一個正則表達式，((b|c)*a(b|c)*a)*(b|c)*簡要描述它所生成的語言。3、試為Pascal語言的注釋部分編寫正則表達式。

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

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

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

S:S∈K是唯一的一個初態(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)造一個識別語言(a|b)*ab的有窮自動機。從正則表達式構(gòu)造有窮自動機12開始a0abb輸入符號ab0{0,1}{0}1{2}2狀態(tài)28例設ＤＦＡＭ＝（｛０,１,２,３｝，｛ａ,ｂ｝，f，０，｛３｝）其中f（０，ａ）＝１，f（１，ａ）＝3f（２，ａ）＝１，f（３，ａ）＝３f（０，ｂ）＝２，f（１，ｂ）＝２f（２，ｂ）＝３，f（３，ｂ）＝３29轉(zhuǎn)換矩陣3b012aaaabbb3狀態(tài)轉(zhuǎn)換圖易存儲30

從狀態(tài)轉(zhuǎn)換圖看，從初態(tài)出發(fā)，沿任一條路徑到達接受狀態(tài)，這條路徑上的弧上的標記符號連接起來構(gòu)成的符號串被接受(識別)。DFAM所能識別的字的全體即L(M)。字集V是正規(guī)的ifV=L（M）012aaaabbb3b31非確定有窮狀態(tài)自動機一個非確定的有窮自動機（NFA）D是一個五元組：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開始狀態(tài)唯一一個或多個映像單個狀態(tài)狀態(tài)集合33舉例與右圖所示對應的有一個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對于輸入字符串babbabb，運行該NFA步驟當前狀態(tài)輸入的其余部分可能的后繼選擇1SbabbabbBB2BabbabbA,BA3AbbabbBB4BbabbZZ5ZabbA,ZA6AbbBB7BbZZ35練習：某操作系統(tǒng)下合法的文件名為device:name.extention其中第一部分（device:）和第三部分（.extention）可缺省，若device、name和extention都是字母串，長度不限，但至少為１，畫出識別這種文件名的DFA。36第四節(jié)

由正則式構(gòu)造有窮自動機A為有窮狀態(tài)自動機，e為正則表達式，則存在L(A)=|e|，即正則表達式與有窮自動機之間具有等價性。任何兩個有窮自動機M和M’，若它們識別的語言相同(L(M)=L(M’))，則稱M和M’等價。37一、由正則表達式構(gòu)造等價的NFAM1、由正則表達式R表示成如圖所示的拓廣轉(zhuǎn)換圖。XYR2、對正則式采用如下規(guī)則構(gòu)造對應的NFAM。SiSjr1|r2SiSjr1r2SiSjr1r2SiSjSkr1r2SiSjr*SiSjSkεεr3、逐步運用上述3個規(guī)則不斷在1、圖中增加新結(jié)點進行分解，直到每條有向邊上僅標識有Σ中的一個字母或ε為止，則NFAM構(gòu)造完成。38舉例對給定正規(guī)式b*(d|ad)(b|ab)+，構(gòu)造其NFAM。εεεεbbbbbaaadd39定義1：集合I的ε-閉包：令I是一個狀態(tài)集的子集，定義ε-closure（I）為：1）若s∈I，則s∈ε-closure（I）；2）若s∈I，則從s出發(fā)經(jīng)過任意條ε弧能夠到達的任何狀態(tài)都屬于ε-closure（I）。狀態(tài)集ε-closure（I）稱為I的ε-閉包為了使得NFA確定化，我們首先給出兩個定義：56432aεaaε1例：如圖所示的狀態(tài)圖：令I={1}，求ε-closure（I）=？根據(jù)定義：ε-closure（I）={1，3}40將NFAN=（Q，，f，S，Z）確定化為DFAM的方法（子集法）（舉例說明）（1）置DFAM中的狀態(tài)集Q‘,Z’為集（2）給出M的初態(tài)S’=E-CLOSER({S}),并把S’置為未標記狀態(tài)后加入到Q’中。（未標記狀態(tài)為新狀態(tài)）(3)如果Q’中存在未標記的狀態(tài)T={q1,q2…qn},qi∈Q則進行如下變換：1）對于每個a∈,置J=f({q1,q2…qn},a)=f(q1,a)f(q2,a)…f(qn,a)U=E-CLOSER(I)如果U不在Q’中，則將U置為無標記的狀態(tài)添加到Q’中，且把狀態(tài)轉(zhuǎn)移f’(T,a)=U添加到M中，如果U至少含有一個元素是N的終態(tài)，則把U置為M的終態(tài)，即把U添加到Z’中。2）對T置標記（表示T不再是新加入Q’中的狀態(tài)）。（4）重復進行步驟（3）,直到Q’中不再含有未標記的狀態(tài)為止。（5）重新命名Q’中的狀態(tài)，最后獲得等價的DFAM.41——J是從狀態(tài)子集I中的每個狀態(tài)出發(fā)，經(jīng)過標記為a的弧而達到的狀態(tài)集合.——Ia是狀態(tài)子集,其元素為J中的狀態(tài)，加上從J中每一個狀態(tài)出發(fā)通過ε弧到達的狀態(tài)定義2:令I是NFAM’的狀態(tài)集的一個子集,a∈Σ定義:Ia=ε-closure(J)其中J=∪δ(s,a)S∈I56432aεaaε1例：令I={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}符號狀態(tài)abc02341221________3344DFAM’狀態(tài)轉(zhuǎn)換矩陣將求得的狀態(tài)轉(zhuǎn)換矩陣重新編號01423{1,4}{2,3}{4}{2}acabbc{3,4}44結(jié)論：NFAM通過“子集法”可以確定化為DFAM″，它們接收語言的能力是等價的，通常不區(qū)分（確定化時除外），合稱為有限自動機(finiteautomata)（FA）。

45“對于任一個DFA，存在一個唯一的狀態(tài)最少的等價的DFA”一個有窮自動機是化簡的

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