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

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

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

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

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

5、： U= (a b)， V = b a又如：又如： U= b(ab) , V =(ba) b再如：再如： U= (a b) , V =(a b ) 正則表達(dá)式的性質(zhì)正則表達(dá)式的性質(zhì)設(shè)設(shè)U、V和和W都是正則表達(dá)式，則如下關(guān)系普遍成立：都是正則表達(dá)式，則如下關(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 “或或”的抽取律的抽取律正則文法和正則表達(dá)式正則文法和正則表

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

7、(VN,VT,P,S),存在一個(gè)存在一個(gè) =VT上的正則表達(dá)式上的正則表達(dá)式r : L(r)=L(G)AxB, By A=xy AxA y A=x yAx y A=x y正則文法和正則表達(dá)式舉例正則文法和正則表達(dá)式舉例例例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正則表達(dá)式和正則文法舉例正則表達(dá)式和正則文法舉例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) 有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)有窮自動(dòng)機(jī)（也稱有限自動(dòng)機(jī)）作為一種識(shí)別裝置，有窮自動(dòng)機(jī)（也稱有限自動(dòng)機(jī)）作為一種識(shí)別裝置，它能準(zhǔn)確地識(shí)別正則集合，即識(shí)別正則文法所定義的它能準(zhǔn)確地識(shí)別正則集合，即識(shí)別正則文法所定義的語(yǔ)言與正則表達(dá)式所表示的集合，引入有窮自動(dòng)機(jī)這語(yǔ)言與正則表達(dá)式所表示的集合，引入有窮自動(dòng)機(jī)這個(gè)理論，正是為詞法分析程序的自動(dòng)構(gòu)造尋找特殊的個(gè)理論，正是為詞法分析程序的自動(dòng)構(gòu)造尋找特殊的方法和工具。方法和工具。有窮自動(dòng)機(jī)分為兩類：確定的有窮自動(dòng)機(jī)（有窮自動(dòng)機(jī)分為兩類：確定的有窮自動(dòng)機(jī)（

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

10、每個(gè)元素稱為一個(gè)狀態(tài)。是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符符是一個(gè)從是一個(gè)從S至至S的的單值映射單值映射。(s,a)=s意味著：當(dāng)意味著：當(dāng)現(xiàn)行狀態(tài)為現(xiàn)行狀態(tài)為s、輸入字符為、輸入字符為a時(shí)，將轉(zhuǎn)換到下一個(gè)狀態(tài)時(shí)，將轉(zhuǎn)換到下一個(gè)狀態(tài)s。我們稱我們稱s為為s的一個(gè)后繼狀態(tài)。的一個(gè)后繼狀態(tài)。s0S，是唯一的初態(tài)。，是唯一的初態(tài)。F S，是一個(gè)終態(tài)集（可空），是一個(gè)終態(tài)集（可空） 確定的有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī)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確定的有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī)DFA接受的字符串接受的字符串對(duì)于對(duì)于*中的任何字符串中的任何字符串t，若存在一條從初態(tài)結(jié)到某一終態(tài)結(jié)的，若存在一條從初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條路上所有弧的標(biāo)記符連接成的字符串等于道路，且這條路上所有弧的標(biāo)記符連接成的字符串等于t，則稱，則稱t可為可為DFA M所接收，所接收，若若M的初態(tài)結(jié)同時(shí)又是終態(tài)結(jié)，則的初態(tài)結(jié)同時(shí)又是終態(tài)結(jié)，則空字空字可為可為M所識(shí)別。所識(shí)別。*上的符號(hào)串上的符號(hào)串t被被M接受接受若若t *， (S，t)=P，其中

12、，其中S為為 M的開始狀態(tài)，的開始狀態(tài)，P Z，Z為終態(tài)為終態(tài)集。則稱集。則稱t為為DFA M所接受（識(shí)別）。所接受（識(shí)別）。*上的符號(hào)串上的符號(hào)串t，（我們將它表示成，（我們將它表示成t1tx的形式，其中的形式，其中t1，tx *）在）在DFA M上上運(yùn)行的定義為：的定義為： (Q, t1tx)= (Q, t1),tx) 其中其中QS確定的有窮自動(dòng)機(jī)確定的有窮自動(dòng)機(jī)例：證明例：證明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非確定的有窮自動(dòng)機(jī)非確定的有窮自動(dòng)機(jī)一個(gè)非確定的有窮自動(dòng)機(jī)一個(gè)非確定的有窮自動(dòng)機(jī)(NFA)M是一個(gè)五元式：是一個(gè)五元式：M=(S, , , S0, F)其中其中S是一個(gè)有限集，它的每個(gè)元素稱為一個(gè)狀態(tài)。是一個(gè)有限集，它的每個(gè)元素稱為一個(gè)狀態(tài)。是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符符是一個(gè)從是一個(gè)從S*至至S子集的單值映射。即：子集的單值映射。即：: S*

14、2SS0 S，是一個(gè)，是一個(gè)非空的初態(tài)集非空的初態(tài)集F S，是一個(gè)終態(tài)集（可空），是一個(gè)終態(tài)集（可空） 非確定的有窮自動(dòng)機(jī)例子非確定的有窮自動(dòng)機(jī)例子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簡(jiǎn)化為01SPS,Z0P.Z0ZPP1非確定的有窮自動(dòng)機(jī)非確定的有窮自動(dòng)機(jī)對(duì)于對(duì)于*中任何字中任何字，若存在一條從某一初態(tài)結(jié)點(diǎn)到某，若存在一條從某一初態(tài)結(jié)點(diǎn)到某一個(gè)終態(tài)結(jié)點(diǎn)的通路，且這條通路上所有弧的標(biāo)記字一個(gè)終態(tài)結(jié)點(diǎn)的通路，且這條通路上所有弧的標(biāo)記字依序連接成的字依序連

15、接成的字（忽略那些標(biāo)記為（忽略那些標(biāo)記為的弧）的?。┑扔诘扔?，則，則稱稱可為可為NFA M所識(shí)別（讀出或接受）。所識(shí)別（讀出或接受）。若若M的某些結(jié)點(diǎn)既是初態(tài)結(jié)點(diǎn)又是終態(tài)結(jié)點(diǎn)，或存在的某些結(jié)點(diǎn)既是初態(tài)結(jié)點(diǎn)又是終態(tài)結(jié)點(diǎn)，或存在一條從某一初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的一條從某一初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的通路，那么通路，那么空字空字可為可為M所識(shí)別。所識(shí)別。 NFANFA的確定化的確定化NFANFA的確定化的確定化顯然，顯然，DFA是是NFA的特例，但是對(duì)于每個(gè)的特例，但是對(duì)于每個(gè)NFA M都存都存在一個(gè)在一個(gè)DFA M，使，使L(M)=L(M)。 定義對(duì)狀態(tài)集合定義對(duì)狀態(tài)集合I的幾個(gè)有關(guān)運(yùn)算：的幾個(gè)有關(guān)運(yù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)任意條 弧而能到弧而能到達(dá)的狀態(tài)的集合。達(dá)的狀態(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)過(guò)一條的某一狀態(tài)經(jīng)過(guò)一條a弧而到達(dá)的狀態(tài)的全體。弧而到達(dá)的狀態(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的化簡(jiǎn)）的化簡(jiǎn)） 一個(gè)有窮自動(dòng)機(jī)一個(gè)有窮自動(dòng)機(jī)通過(guò)消除多余狀態(tài)和合并等價(jià)狀態(tài)而轉(zhuǎn)換成一個(gè)最小通過(guò)消除多余狀態(tài)和合并等價(jià)狀態(tài)而轉(zhuǎn)換成一個(gè)最小的與之等價(jià)的有窮自動(dòng)機(jī)。的與之等價(jià)的有窮自動(dòng)機(jī)。最小狀態(tài)最小狀態(tài)DFA沒有多余狀態(tài)沒有多余狀態(tài)(死狀態(tài)死狀態(tài))沒有兩個(gè)狀態(tài)是互相等價(jià)（不可區(qū)別）沒有兩個(gè)狀態(tài)是互相等價(jià)（不可區(qū)別）兩個(gè)狀態(tài)兩個(gè)狀態(tài)s和和t可區(qū)別：不滿足可區(qū)別：不滿足兼容性（一致性）兼容性（一致性）同是終態(tài)或同是非終態(tài)同是終態(tài)或同是非終態(tài)傳

20、播性（蔓延性）傳播性（蔓延性）從狀態(tài)從狀態(tài)s出發(fā)讀入某個(gè)出發(fā)讀入某個(gè)a a和和從狀態(tài)從狀態(tài)t出發(fā)出發(fā)讀入某個(gè)讀入某個(gè)a到達(dá)的狀態(tài)等價(jià)。到達(dá)的狀態(tài)等價(jià)。DFADFA的最小化的最小化算法的核心算法的核心把把M的狀態(tài)集的狀態(tài)集K分成不相交的子集。分成不相交的子集。結(jié)論結(jié)論接受接受L的最小狀態(tài)有窮自動(dòng)機(jī)不計(jì)同構(gòu)是唯一的。的最小狀態(tài)有窮自動(dòng)機(jī)不計(jì)同構(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.對(duì)對(duì)施施用傳播性原則用傳播性原則 構(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的最小化的最小化初始劃分：一個(gè)由終態(tài)組成，一初始劃分：一個(gè)由終態(tài)組成，一個(gè)由非終態(tài)組成個(gè)由非終態(tài)組成P0=(1,2,3,4,5,6,7

22、)P0=(1,2,3,4,5,6,7)觀察第一個(gè)子集，在讀入觀察第一個(gè)子集，在讀入a a之后劃分之后劃分為為P1=(1,2,3,4,5,6,7)P1=(1,2,3,4,5,6,7)觀察第二個(gè)子集，在讀入觀察第二個(gè)子集，在讀入a a之后劃分之后劃分為為P1=(1,2,3,4,5,6,7)P1=(1,2,3,4,5,6,7)觀察第四個(gè)子集，在讀入觀察第四個(gè)子集，在讀入a a之后劃分之后劃分為為P1=(1,2,3,4,5,6,7)P1=(1,2,3,4,5,6,7)正則文法與有限自動(dòng)機(jī)的等價(jià)性正則文法與有限自動(dòng)機(jī)的等價(jià)性對(duì)于正則文法對(duì)于正則文法G和有限自動(dòng)機(jī)和有限自動(dòng)機(jī)M，如果，如果L(G)=L(M

23、)，則稱則稱G和和M是等價(jià)的。關(guān)于正則文法和有限自動(dòng)機(jī)的是等價(jià)的。關(guān)于正則文法和有限自動(dòng)機(jī)的等價(jià)問題，有以下結(jié)論：等價(jià)問題，有以下結(jié)論：對(duì)每一個(gè)右線性正則文法對(duì)每一個(gè)右線性正則文法G或左線性正則文法或左線性正則文法G，都存，都存在一個(gè)正則自動(dòng)機(jī)在一個(gè)正則自動(dòng)機(jī)(FA)M，使得，使得L(M)=L(G)。對(duì)每一個(gè)對(duì)每一個(gè)FA M，都存在一個(gè)右線性正則文法，都存在一個(gè)右線性正則文法GR和左線和左線性正則文法性正則文法GL，使得，使得L(M)=L(GR)=( GL)。 正則文法與有限自動(dòng)機(jī)的等價(jià)性正則文法與有限自動(dòng)機(jī)的等價(jià)性正則文法正則文法GR=GR=其中其中P P由以下產(chǎn)生式構(gòu)成由以下產(chǎn)生式構(gòu)成A0|0B|1DA0|0B|1DB0D|1CB0D|1CC0|0B|1DC0|0B|1DD0D|1DD0