天津大學編譯原理講義 - Part3詞法分析2

1、Part3Part3詞法分析詞法分析授課：胡靜授課：胡靜內(nèi)容提要內(nèi)容提要詞法分析器的作用詞法分析器的作用詞法分析程序的設(shè)計與實現(xiàn)詞法分析程序的設(shè)計與實現(xiàn)狀態(tài)圖狀態(tài)圖詞法分析程序的自動生成詞法分析程序的自動生成有窮自動機有窮自動機正則表達式與有限自動機正則表達式與有限自動機問題的提出問題的提出如果只向前看一個字符，不能夠確定我們將要讀入的是哪種如果只向前看一個字符，不能夠確定我們將要讀入的是哪種類型的類型的token如果如果token的開頭是的開頭是“i”，那么它一定是標識符么？，那么它一定是標識符么？如果如果token的開頭是的開頭是“2”，那么它一定是一個整型的常數(shù)么？，那么它一定是一個整型

2、的常數(shù)么？如果我們通過上面的類似如果我們通過上面的類似“插入插入”式的方法來寫識別式的方法來寫識別token的程的程序，這樣的程序不容易寫正確，而且也不容易維護序，這樣的程序不容易寫正確，而且也不容易維護因此需要一個更加有原理性的方法：詞法分析器的生成器，因此需要一個更加有原理性的方法：詞法分析器的生成器，可以自動產(chǎn)生有效的詞法分析器。（例如可以自動產(chǎn)生有效的詞法分析器。（例如lex，flex，Jlex）一般說來，沒有限制的向前看是必要的一般說來，沒有限制的向前看是必要的一些問題一些問題如何明確的描述如何明確的描述tokens2.e0 20.e-01 2.0000“” “x” “” “”如何將

3、文本分割成如何將文本分割成tokensif (x = 0) a = x1;if (x = 0) a = x1;如何描述如何描述tokenstokens我們可以使用我們可以使用正則表達式正則表達式來描述程序設(shè)計語言中的來描述程序設(shè)計語言中的tokens。正則表達式的定義如下：。正則表達式的定義如下：正則集合（語言）正則集合（語言）正則表達式的例子正則表達式的例子令令 =a，b， 正則表達式正則表達式正則集合集正則集合集aaa ba,babab(a b)(a b)aa,ab,ba,bba ,a,a, 任意個任意個a的串的串(a b) ,a,b,aa,ab 所有由所有由a 和和b組成的串組成的串(a

4、 b) (aa bb)(a b) 上所有含有兩個相繼的上所有含有兩個相繼的a或兩個或兩個相繼的相繼的b組成的串組成的串正則表達式的例子正則表達式的例子 =a，b，r=a(a b) 定義的正則集合定義的正則集合: a,aa,ab,abb, =d， ，e，+，-,則則 上的正則表達式上的正則表達式 d ( dd )(e(+ - )dd )表示的是無符號數(shù)的集表示的是無符號數(shù)的集合。其中合。其中d為為09的數(shù)字。的數(shù)字。若兩個正則表達式所表示的正則集合相同，則認為二若兩個正則表達式所表示的正則集合相同，則認為二者等價。兩個等價的正則表達式者等價。兩個等價的正則表達式U和和V記為記為U=V。例如：例如

5、： U= (a b)， V = b a又如：又如： U= b(ab) , V =(ba) b再如：再如： U= (a b) , V =(a b ) 正則表達式的性質(zhì)正則表達式的性質(zhì)設(shè)設(shè)U、V和和W都是正則表達式，則如下關(guān)系普遍成立：都是正則表達式，則如下關(guān)系普遍成立：U|V = V|U（交換律）（交換律）U|(V|W) = (U|V)|W （結(jié)合律）（結(jié)合律）U(VW) = (UV)W（結(jié)合律）、（結(jié)合律）、U(V|W) = UV | UW （分配律）（分配律）(V|W)U = VU |WU；U = U =Ur r=rr =r rr “或或”的抽取律的抽取律正則文法和正則表達式正則文法和正則表

6、達式對對 上的正則表達式上的正則表達式U ,存在一個正則文法存在一個正則文法G=(VN,VT,P,S):L(G)=L(r)初始，初始， VT= , S VN ，生成生成正則正則產(chǎn)生式產(chǎn)生式SU (R.1) 對形如對形如 Ar1r2的的正則正則產(chǎn)生式：產(chǎn)生式：Ar1B Br2 B VN(R.2)對形如對形如Ar r1的的正則正則產(chǎn)生式：產(chǎn)生式：ArB Ar1BrB Br1 B VN (R.3)對形如對形如Ar1 r2的的正則正則產(chǎn)生式產(chǎn)生式:Ar1 A r2 不斷應(yīng)用不斷應(yīng)用R做變換，直到每個產(chǎn)生式右端只含一個做變換，直到每個產(chǎn)生式右端只含一個VN正則文法和正則表達式正則文法和正則表達式對對G=

7、(VN,VT,P,S),存在一個存在一個 =VT上的正則表達式上的正則表達式r : L(r)=L(G)AxB, By A=xy AxA y A=x yAx y A=x y正則文法和正則表達式舉例正則文法和正則表達式舉例例例1：r=a(a d) VT=a,d Sa(a d) R.1SaA A(a d) R.2A(a d)BAB(a d)B BR.3 Gs:SaA A VT=a,d AaBVN=S,A,B AdB BaB BdBBP正則表達式和正則文法舉例正則表達式和正則文法舉例Gs:SaA AaA AdA Sa Aa Ad SaA a AaA a dA d A(a d)A (a d) A(a d

8、) (a d)S=a(a d) (a d) a =a(a d) (a d) =a(a d)+)R=a(a d) 有窮自動機有窮自動機有窮自動機（也稱有限自動機）作為一種識別裝置，有窮自動機（也稱有限自動機）作為一種識別裝置，它能準確地識別正則集合，即識別正則文法所定義的它能準確地識別正則集合，即識別正則文法所定義的語言與正則表達式所表示的集合，引入有窮自動機這語言與正則表達式所表示的集合，引入有窮自動機這個理論，正是為詞法分析程序的自動構(gòu)造尋找特殊的個理論，正是為詞法分析程序的自動構(gòu)造尋找特殊的方法和工具。方法和工具。有窮自動機分為兩類：確定的有窮自動機（有窮自動機分為兩類：確定的有窮自動機（

9、DFA）和）和不確定的有窮自動機（不確定的有窮自動機（NFA）。）。其中其中“不確定不確定”的含義是：對于某個輸入符號，在同的含義是：對于某個輸入符號，在同一狀態(tài)上存在不止一種轉(zhuǎn)換。一狀態(tài)上存在不止一種轉(zhuǎn)換。確定的和不確定的有窮自動機都能而且僅能識別正則確定的和不確定的有窮自動機都能而且僅能識別正則集合，即它們能夠識別正則表達式所表示的語言。集合，即它們能夠識別正則表達式所表示的語言。確定的有窮自動機確定的有窮自動機一個確定的有窮自動機一個確定的有窮自動機(DFA)M是一個五元式：是一個五元式：M=(S, , , s0, F)其中其中S是一個有限集，它的每個元素稱為一個狀態(tài)。是一個有限集，它的

10、每個元素稱為一個狀態(tài)。是一個有窮字母表，它的每個元素稱為一個輸入字是一個有窮字母表，它的每個元素稱為一個輸入字符符是一個從是一個從S至至S的的單值映射單值映射。(s,a)=s意味著：當意味著：當現(xiàn)行狀態(tài)為現(xiàn)行狀態(tài)為s、輸入字符為、輸入字符為a時，將轉(zhuǎn)換到下一個狀態(tài)時，將轉(zhuǎn)換到下一個狀態(tài)s。我們稱我們稱s為為s的一個后繼狀態(tài)。的一個后繼狀態(tài)。s0S，是唯一的初態(tài)。，是唯一的初態(tài)。F S，是一個終態(tài)集（可空），是一個終態(tài)集（可空） 確定的有窮自動機確定的有窮自動機DFA M=（S，U，V，Q，a，b，S，Q）其中）其中f定義為：定義為：（S，a）=U（V，a）=U（S，b）=V（V，b）=Q（U，

11、a）=Q（Q，a）=Q（U，b）=V（Q，b）=QabSUVUQVVUQQQQ字符字符狀態(tài)狀態(tài)bSUVQaaaba，bb確定的有窮自動機確定的有窮自動機DFA接受的字符串接受的字符串對于對于*中的任何字符串中的任何字符串t，若存在一條從初態(tài)結(jié)到某一終態(tài)結(jié)的，若存在一條從初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條路上所有弧的標記符連接成的字符串等于道路，且這條路上所有弧的標記符連接成的字符串等于t，則稱，則稱t可為可為DFA M所接收，所接收，若若M的初態(tài)結(jié)同時又是終態(tài)結(jié)，則的初態(tài)結(jié)同時又是終態(tài)結(jié)，則空字空字可為可為M所識別。所識別。*上的符號串上的符號串t被被M接受接受若若t *， (S，t)=P，其中

12、，其中S為為 M的開始狀態(tài)，的開始狀態(tài)，P Z，Z為終態(tài)為終態(tài)集。則稱集。則稱t為為DFA M所接受（識別）。所接受（識別）。*上的符號串上的符號串t，（我們將它表示成，（我們將它表示成t1tx的形式，其中的形式，其中t1，tx *）在）在DFA M上上運行的定義為：的定義為： (Q, t1tx)= (Q, t1),tx) 其中其中QS確定的有窮自動機確定的有窮自動機例：證明例：證明t=baab被例中的被例中的DFA所接受。所接受。 (S,baab)= ( (S,b),aab)= (V,aab)= ( (V,a),ab)= (U,ab)= (f(U,a),b)= (Q,b)=QQ屬于終態(tài)。屬于

13、終態(tài)。DFA M=（S，U，V，Q，a，b，S，Q）其中）其中定義為：定義為：（S，a）=U（V，a）=U（S，b）=V（V，b）=Q（U，a）=Q（Q，a）=Q（U，b）=V（Q，b）=Q非確定的有窮自動機非確定的有窮自動機一個非確定的有窮自動機一個非確定的有窮自動機(NFA)M是一個五元式：是一個五元式：M=(S, , , S0, F)其中其中S是一個有限集，它的每個元素稱為一個狀態(tài)。是一個有限集，它的每個元素稱為一個狀態(tài)。是一個有窮字母表，它的每個元素稱為一個輸入字是一個有窮字母表，它的每個元素稱為一個輸入字符符是一個從是一個從S*至至S子集的單值映射。即：子集的單值映射。即：: S*

14、2SS0 S，是一個，是一個非空的初態(tài)集非空的初態(tài)集F S，是一個終態(tài)集（可空），是一個終態(tài)集（可空） 非確定的有窮自動機例子非確定的有窮自動機例子NFA N=（S,P,Z,0,1,S,P,Z）其中）其中(S,0)=P(S,1)=S，Z(P,1)=Z(Z,0)=P(Z,1)=PSPZ00,111101SPS,Z0PZ0ZPP1簡化為01SPS,Z0P.Z0ZPP1非確定的有窮自動機非確定的有窮自動機對于對于*中任何字中任何字，若存在一條從某一初態(tài)結(jié)點到某，若存在一條從某一初態(tài)結(jié)點到某一個終態(tài)結(jié)點的通路，且這條通路上所有弧的標記字一個終態(tài)結(jié)點的通路，且這條通路上所有弧的標記字依序連接成的字依序連

15、接成的字（忽略那些標記為（忽略那些標記為的?。┑幕。┑扔诘扔?，則，則稱稱可為可為NFA M所識別（讀出或接受）。所識別（讀出或接受）。若若M的某些結(jié)點既是初態(tài)結(jié)點又是終態(tài)結(jié)點，或存在的某些結(jié)點既是初態(tài)結(jié)點又是終態(tài)結(jié)點，或存在一條從某一初態(tài)結(jié)點到某一終態(tài)結(jié)點的一條從某一初態(tài)結(jié)點到某一終態(tài)結(jié)點的通路，那么通路，那么空字空字可為可為M所識別。所識別。 NFANFA的確定化的確定化NFANFA的確定化的確定化顯然，顯然，DFA是是NFA的特例，但是對于每個的特例，但是對于每個NFA M都都存在一個存在一個DFA M，使，使L(M)=L(M)。 定義對狀態(tài)集合定義對狀態(tài)集合I的幾個有關(guān)運算：的幾個有關(guān)運

16、算：1 狀態(tài)集合狀態(tài)集合I的的 -閉包，表示為閉包，表示為 -closure(I)，定義為一，定義為一狀態(tài)集，是狀態(tài)集狀態(tài)集，是狀態(tài)集I中的任何狀態(tài)中的任何狀態(tài)s經(jīng)任意條經(jīng)任意條 弧而能到弧而能到達的狀態(tài)的集合。達的狀態(tài)的集合。狀態(tài)集合狀態(tài)集合I的任何狀態(tài)的任何狀態(tài)s都屬于都屬于 -closure(I)。2 狀態(tài)集合狀態(tài)集合I的的a弧轉(zhuǎn)換，表示為弧轉(zhuǎn)換，表示為move(I,a)定義為狀態(tài)定義為狀態(tài)集合集合J，其中，其中J是所有那些可從是所有那些可從I的某一狀態(tài)經(jīng)過一條的某一狀態(tài)經(jīng)過一條a弧而到達的狀態(tài)的全體?；《竭_的狀態(tài)的全體。定義定義Ia = -closure(move(I,a) - -閉

17、包的例子閉包的例子I=1, -closure(I)=1,2；I=5, -closure(I)=5,6,2；move(1,2,a)=5,3,4I=1,2, Ia= -closure(5,3,4)=2,3,4,5,6,7,8；12534687aa aNFANFA確定化的例子確定化的例子4f35621iaaaabbbbi,1,2i,1,21,2,31,2,31,2,31,2,31,2,41,2,41,2,3,5,6,f1,2,3,5,6,f1,2,41,2,41,2,31,2,3I Ib bI Ia a1,2,41,2,4SAB1,2,3,5,6,f1,2,3,5,6,fABCCA1,2,4,5,6

18、,f1,2,4,5,6,fD1,2,4,5,6,f1,2,4,5,6,fD1,2,3,5,6,f1,2,3,5,6,f1,2,4,6,f1,2,4,6,f1,2,3,6,f1,2,3,6,f1,2,4,5,6,f1,2,4,5,6,fCE1,2,4,6,f1,2,4,6,fEF1,2,3,6,f1,2,3,6,fFD1,2,3,6,f1,2,3,6,fF1,2,4,5,6,f1,2,4,5,6,fD1,2,3,5,6,f1,2,3,5,6,fC1,2,4,6,f1,2,4,6,fEBNFANFA的確定化的確定化aCDBAEFSbaaaaabbbbbabFS SA AA AB BC CB BA

19、Ab ba aB BC CD DD DC CE EF FD DE EF FF FD DC CE EDFADFA的最小化的最小化DFA的最小化（的最小化（DFA的化簡）的化簡） 一個有窮自動機一個有窮自動機通過消除多余狀態(tài)和合并等價狀態(tài)而轉(zhuǎn)換成一個最小通過消除多余狀態(tài)和合并等價狀態(tài)而轉(zhuǎn)換成一個最小的與之等價的有窮自動機。的與之等價的有窮自動機。最小狀態(tài)最小狀態(tài)DFA沒有多余狀態(tài)沒有多余狀態(tài)(死狀態(tài)死狀態(tài))沒有兩個狀態(tài)是互相等價（不可區(qū)別）沒有兩個狀態(tài)是互相等價（不可區(qū)別）兩個狀態(tài)兩個狀態(tài)s和和t可區(qū)別：不滿足可區(qū)別：不滿足兼容性（一致性）兼容性（一致性）同是終態(tài)或同是非終態(tài)同是終態(tài)或同是非終態(tài)傳

20、播性（蔓延性）傳播性（蔓延性）從狀態(tài)從狀態(tài)s出發(fā)讀入某個出發(fā)讀入某個a a和和從狀態(tài)從狀態(tài)t出發(fā)出發(fā)讀入某個讀入某個a到達的狀態(tài)等價。到達的狀態(tài)等價。DFADFA的最小化的最小化算法的核心算法的核心把把M的狀態(tài)集的狀態(tài)集K分成不相交的子集。分成不相交的子集。結(jié)論結(jié)論接受接受L的最小狀態(tài)有窮自動機不計同構(gòu)是唯一的。的最小狀態(tài)有窮自動機不計同構(gòu)是唯一的。DFA M =（K,f, k0, kt),最小狀態(tài)最小狀態(tài)DFA M1.構(gòu)造狀態(tài)的初始劃分構(gòu)造狀態(tài)的初始劃分：終態(tài)終態(tài)kt 和非終態(tài)和非終態(tài)K- kt兩組兩組2.對對施施用傳播性原則用傳播性原則 構(gòu)造新劃分構(gòu)造新劃分new 3. 如如new =,則

21、令則令 final= 并繼續(xù)步驟并繼續(xù)步驟4，否則否則:=new重復(fù)重復(fù)2 4.為為final中的每一組選一代表，這些代表構(gòu)成中的每一組選一代表，這些代表構(gòu)成M的狀態(tài)。若的狀態(tài)。若k是是一代表且一代表且f(k,a)=t,令令r是是t組的組的代表，則代表，則M中有一轉(zhuǎn)換中有一轉(zhuǎn)換f(k,a)=r M 的開始狀態(tài)是含有的開始狀態(tài)是含有K0的那組的代表的那組的代表 M的終態(tài)是含有的終態(tài)是含有Kt的那組的的那組的代表代表 5.去掉去掉M中的死狀態(tài)中的死狀態(tài).DFADFA的最小化的最小化初始劃分：一個由終態(tài)組成，一初始劃分：一個由終態(tài)組成，一個由非終態(tài)組成個由非終態(tài)組成P0=(1,2,3,4,5,6,7

22、)P0=(1,2,3,4,5,6,7)觀察第一個子集，在讀入觀察第一個子集，在讀入a a之后劃分之后劃分為為P1=(1,2,3,4,5,6,7)P1=(1,2,3,4,5,6,7)觀察第二個子集，在讀入觀察第二個子集，在讀入a a之后劃分之后劃分為為P1=(1,2,3,4,5,6,7)P1=(1,2,3,4,5,6,7)觀察第四個子集，在讀入觀察第四個子集，在讀入a a之后劃分之后劃分為為P1=(1,2,3,4,5,6,7)P1=(1,2,3,4,5,6,7)正則文法與有限自動機的等價性正則文法與有限自動機的等價性對于正則文法對于正則文法G和有限自動機和有限自動機M，如果，如果L(G)=L(M)，則稱則稱G和和M是等價的。關(guān)于正則文法和有限自動機的是等價的。關(guān)于正則文法和有限自動機的等價問題，有以下結(jié)論：等價問題，有以下結(jié)論：對每一個右線性正則文法對每一個右線性正則文法G或左線性正則文法或左線性正則文法G，都存，都存在一個正則自動機在一個正則自動機(FA)M，使得，使得L(M)=L(G)。對每一個對每一個FA M，都存在一個右線性正則文法，都存在一個右線性正則文法GR和左和左線性正則文