編譯3詞法分析_zss_3

1、編譯原理編譯原理(第三版第三版) 陳火旺等編著22022-3-183.3.4 正規(guī)文法與有限自動機的等價性正規(guī)文法與有限自動機的等價性n對于正規(guī)文法對于正規(guī)文法G和有限自動機和有限自動機M，如果，如果L(G)L(M)，則稱，則稱G和和M是是等價等價的。關(guān)于的。關(guān)于正規(guī)文法和有限自動機的等價性，有以正規(guī)文法和有限自動機的等價性，有以下結(jié)論：下結(jié)論：32022-3-18n定理：定理： 1.對每一個右線性正規(guī)文法對每一個右線性正規(guī)文法G或左線性正或左線性正規(guī)文法規(guī)文法G，都存在一個有限自動機，都存在一個有限自動機(FA) M，使得，使得L(M)L(G)。 2.對每一個對每一個FA M，都存在一個右線

2、性正規(guī)，都存在一個右線性正規(guī)文法文法GR和左線性正規(guī)文法和左線性正規(guī)文法GL，使得，使得L(M)L(GR)L(GL)。42022-3-18n證明：證明： 1. 1. 對每一個右線性正規(guī)文法對每一個右線性正規(guī)文法G或左線性正或左線性正規(guī)文法規(guī)文法G，都構(gòu)造一個有限自動機（，都構(gòu)造一個有限自動機（FA） M，使得，使得L(M)L(G)。(1) 設(shè)右線性正規(guī)文法設(shè)右線性正規(guī)文法G=。將。將VN中的每一非終結(jié)符號視為狀態(tài)符號，中的每一非終結(jié)符號視為狀態(tài)符號，并增加一個新的終結(jié)狀態(tài)符號并增加一個新的終結(jié)狀態(tài)符號f，f VN。 令令M=，其中狀態(tài)，其中狀態(tài)轉(zhuǎn)換函數(shù)轉(zhuǎn)換函數(shù) 由以下規(guī)則定義：由以下規(guī)則定義：

3、52022-3-18(a) 若對某個若對某個A VN及及a VT ，P中有中有產(chǎn)生式產(chǎn)生式Aa，則令，則令 (A,a)=f(b) 對任意的對任意的A VN及及a VT ，設(shè)，設(shè)P中中左端為左端為A，右端第一符號為，右端第一符號為a的所有產(chǎn)的所有產(chǎn)生式為：生式為：AaA1|aAk （不包括（不包括Aa），）， 則令則令 (A,a)=A1,Ak。 顯然顯然，上述，上述M是一個是一個NFA。62022-3-18對于右線性正規(guī)文法對于右線性正規(guī)文法G，在，在S w的最左推的最左推導過程中導過程中:利用利用AaB一次就相當于在一次就相當于在M中從狀態(tài)中從狀態(tài)A經(jīng)經(jīng)過標記為過標記為a的箭弧到達狀態(tài)的箭弧到

4、達狀態(tài)B（包括（包括a= 的情的情形）形）;在推導的最后，利用在推導的最后，利用Aa一次則相當于在一次則相當于在M中從狀態(tài)中從狀態(tài)A經(jīng)過標記為經(jīng)過標記為a的箭弧到達終結(jié)狀態(tài)的箭弧到達終結(jié)狀態(tài)f（包括（包括a= 的情形）。的情形）。綜上，在正規(guī)文法綜上，在正規(guī)文法G中，中，S w的的充要條件充要條件是：在是：在M中，從狀態(tài)中，從狀態(tài)S到狀態(tài)到狀態(tài)f有一條通路，有一條通路，其上所有箭弧的標記符號依次連接起來恰好其上所有箭弧的標記符號依次連接起來恰好等于等于w，這就是說，這就是說，w L(G)當且僅當當且僅當w L(M)，故，故L(G)L(M)。+ + +72022-3-18(2) 設(shè)左線性正規(guī)文法

5、設(shè)左線性正規(guī)文法G=。將。將VN中的每一符號視為狀態(tài)符號，并增加一個初中的每一符號視為狀態(tài)符號，并增加一個初始狀態(tài)符號始狀態(tài)符號q0，q0 VN。 令令M=，其中狀態(tài)轉(zhuǎn)，其中狀態(tài)轉(zhuǎn)換函數(shù)換函數(shù) 由以下規(guī)則定義：由以下規(guī)則定義：(a) 若對某個若對某個A VN及及a VT ，若，若P中有產(chǎn)中有產(chǎn)生式生式Aa，則令，則令 (q0,a)=A(b) 對任意的對任意的A VN及及a VT ，若，若P中所有中所有右端第一符號為右端第一符號為A，第二個符號為，第二個符號為a的產(chǎn)的產(chǎn)生式為：生式為：A1Aa, , AkAa， 則令則令 (A,a)=A1,Ak。與與(1)類似，可以證明類似，可以證明L(G)L(

6、M)。82022-3-18nGR(A) ：A0 | 0B | 1DB0D | 1CC0 | 0B | 1DD0D | 1Dn從從GR出發(fā)構(gòu)造出發(fā)構(gòu)造NFA M = ，M的狀態(tài)轉(zhuǎn)換圖的狀態(tài)轉(zhuǎn)換圖如右圖所示。如右圖所示。n顯然顯然 L(M) = L(GR)。例例: (理解理解“等價性等價性”)ABCD100,1110f00092022-3-183.3.4 正規(guī)文法與有限自動機的等價性（續(xù)）正規(guī)文法與有限自動機的等價性（續(xù)）n定理：定理： 1.對每一個右線性正規(guī)文法對每一個右線性正規(guī)文法G或左線性正或左線性正規(guī)文法規(guī)文法G，都存在一個有限自動機，都存在一個有限自動機(FA) M，使得，使得L(M)L

7、(G)。 2.對每一個對每一個FA M，都存在一個右線性正規(guī)，都存在一個右線性正規(guī)文法文法GR和左線性正規(guī)文法和左線性正規(guī)文法GL，使得，使得L(M)L(GR)L(GL)。102022-3-18證明證明2：對每一個：對每一個DFA M，都存在一個右線，都存在一個右線性正規(guī)文法性正規(guī)文法GR和左線性正規(guī)文法和左線性正規(guī)文法GL，使得，使得L(M)L(GR)L(GL)。 設(shè)設(shè)DFA M= (1) 若若s0 F，我們令，我們令GR=，其，其中中P是由以下規(guī)則定義的產(chǎn)生式集合：是由以下規(guī)則定義的產(chǎn)生式集合：對任何對任何a及及A,B S，若有，若有 (A,a)=B，則：，則： (a) 當當B F時，令時

8、，令AaB， (b) 當當B F時，令時，令Aa | aB。112022-3-18對任何對任何w*，不妨設(shè)，不妨設(shè)w=a1ak，其中，其中ai (i=1,k)。若。若s0 w，則存在一個最左推導：，則存在一個最左推導： s0a1A1a1a2A2a1aiAia1ai+1Ai+1a1ak因而，在因而，在M中有一條從中有一條從s0出發(fā)依次經(jīng)過出發(fā)依次經(jīng)過A1，Ak-1到達終態(tài)的通路，該通路上所有箭弧的到達終態(tài)的通路，該通路上所有箭弧的標記依次為標記依次為a1,ak。反之亦然。所以，。反之亦然。所以，w L(GR)當且僅當當且僅當w L(M)。+ +122022-3-18q 現(xiàn)在考慮現(xiàn)在考慮s0 F的

9、情形：的情形： 因為因為 (s0, )=s0，所以，所以L(M)。但。但 不屬于上面構(gòu)不屬于上面構(gòu)造的造的GR所產(chǎn)生的語言所產(chǎn)生的語言L(GR)。不難發(fā)現(xiàn)，。不難發(fā)現(xiàn)，L(GR)=L(M)- 。 所以，我們在上述所以，我們在上述GR中添加新的非終結(jié)符號中添加新的非終結(jié)符號s0 ，(s0S)和產(chǎn)生式和產(chǎn)生式s0s0| ，并用，并用s0 代替代替s0作開始作開始符號。這樣修正符號。這樣修正GR后得到的文法后得到的文法GR 仍是右線性正仍是右線性正規(guī)文法，并且規(guī)文法，并且L(GR )=L(M)。 (2) 類似于類似于(1)，從，從DFA M出發(fā)可構(gòu)造左線性正規(guī)出發(fā)可構(gòu)造左線性正規(guī)文法文法GL，使得，

10、使得L(GL)=L(M)。 最后，由最后，由DFA和和NFA之間的等價性，結(jié)論之間的等價性，結(jié)論2得證。得證。132022-3-18nL(M) = 0(10)*nGR = ，其中，其中P由下列產(chǎn)生由下列產(chǎn)生式組成：式組成：A0 | 0B | 1DB0D | 1CC0 | 0B | 1DD0D | 1DL(GR) = L(M) = 0(10)*例例3.4 設(shè)設(shè)DFA M = 。M的狀態(tài)轉(zhuǎn)換圖如下圖所示。的狀態(tài)轉(zhuǎn)換圖如下圖所示。ABCD100,11100142022-3-18n從從NFA M出發(fā)構(gòu)造左線性出發(fā)構(gòu)造左線性正規(guī)文法正規(guī)文法GL = ，其中，其中P 由由下列產(chǎn)生式組成：下列產(chǎn)生式組成：f

11、0 | C0CB1B0 | C0D1 | C1 | D0 | D1 | B0易證易證 L(GL) = L(M)。從從GR構(gòu)造構(gòu)造NFA M，參見，參見 (p53)。M的狀態(tài)轉(zhuǎn)換圖如圖的狀態(tài)轉(zhuǎn)換圖如圖3.9(b)所示。所示。ABCD100,1110f000152022-3-18FA正規(guī)集正規(guī)集正規(guī)式正規(guī)式DFANFA正規(guī)文法正規(guī)文法3.3.13.3.23.3.33.3.43.3.5162022-3-183.3.5 3.3.5 正規(guī)式與有限自動機的等價性正規(guī)式與有限自動機的等價性n定理：定理： 1. 對任何對任何FA M，都存在一個正規(guī)式，都存在一個正規(guī)式r，使，使得得L(r)=L(M)。 2.

12、對任何正規(guī)式對任何正規(guī)式r，都存在一個，都存在一個FA M，使，使得得L(M)=L(r)。2對轉(zhuǎn)換圖概念拓廣對轉(zhuǎn)換圖概念拓廣，令每條弧可用一個，令每條弧可用一個正規(guī)式作標記。正規(guī)式作標記。(對一類輸入符號對一類輸入符號)172022-3-18n證明：證明： 1 1 對對 上任一上任一NFA M，構(gòu)造一個，構(gòu)造一個 上的正規(guī)上的正規(guī)式式r，使得，使得L(r)=L(M)。首先，在首先，在M的轉(zhuǎn)換圖上加進兩個狀態(tài)的轉(zhuǎn)換圖上加進兩個狀態(tài)X和和Y，從從X用用 弧連接到弧連接到M的所有初態(tài)結(jié)點，從的所有初態(tài)結(jié)點，從M的所的所有終態(tài)結(jié)點用有終態(tài)結(jié)點用 弧連接到弧連接到Y(jié)，從而形成一個新，從而形成一個新的的N

13、FA，記為，記為M，它只有一個初態(tài)，它只有一個初態(tài)X和一個終和一個終態(tài)態(tài)Y，顯然，顯然L(M)=L(M)。然后，反復使用下面的一條規(guī)則，逐步消去所然后，反復使用下面的一條規(guī)則，逐步消去所有結(jié)點，直到只剩下有結(jié)點，直到只剩下X和和Y為止：為止：182022-3-18代之為代之為ijr1r2kikr1r2代之為代之為ijr1|r2ijr2r1代之為代之為ikr1r2*r2ijr1r3kr2192022-3-1812354U1V1U2V2W2W11254V1(U1|U2)*W1V1(U1|U2)*W2V2(U1|U2)*W2V2(U1|U2)*W1例：例：202022-3-18q最后，最后，X到到Y(jié)

14、的弧上標記的正規(guī)式即為的弧上標記的正規(guī)式即為所構(gòu)造的正規(guī)式所構(gòu)造的正規(guī)式rq顯然顯然L(r)=L(M)=L(M)212022-3-18n證明證明2: 對于對于 上的正規(guī)式上的正規(guī)式r，構(gòu)造一個，構(gòu)造一個NFA M，使，使L(M)=L(r)，并且，并且M只有一個終態(tài)，只有一個終態(tài)，而且沒有從該終態(tài)出發(fā)的箭弧而且沒有從該終態(tài)出發(fā)的箭弧。 下面使用關(guān)于下面使用關(guān)于r中運算符數(shù)目的歸納法證中運算符數(shù)目的歸納法證明上述結(jié)論。明上述結(jié)論。(1) 若若r具有零個運算符，則具有零個運算符，則r= 或或r= 或或r=a，其，其中中a。此時下圖所示的三個有限自動機顯然。此時下圖所示的三個有限自動機顯然符合上述要求

15、。符合上述要求。q0q0qfaq0qf222022-3-18(2) 假設(shè)結(jié)論對于少于假設(shè)結(jié)論對于少于k(k 1)個運算符的正個運算符的正規(guī)式成立。規(guī)式成立。 當當r中含有中含有k個運算符時，個運算符時，r有三種情形：有三種情形：l情形情形1：r=r1|r2，r1,r2中運算符個數(shù)少于中運算符個數(shù)少于k。從而，由歸納假設(shè)，對從而，由歸納假設(shè)，對ri存在存在Mi=，使得，使得L(Mi)=L(ri)，并且，并且Mi沒有從終沒有從終態(tài)出發(fā)的箭?。☉B(tài)出發(fā)的箭?。╥=1,2）。不妨設(shè)）。不妨設(shè)S1S2= ，在在S1 S2中加入兩個新狀態(tài)中加入兩個新狀態(tài)q0，f0。232022-3-18 令令M=，其中其中

16、 定義如下：定義如下：(a) (q0, )=q1,q2(b) (q,a)= 1(q,a), 當當q S1-f1, a1 (c) (q,a)= 2(q,a), 當當q S2-f2, a2 (d) (f1, )= (f2, )=f0。 M的狀態(tài)轉(zhuǎn)換如右圖所示。的狀態(tài)轉(zhuǎn)換如右圖所示。 L(M)=L(M1)L(M2) =L(r1)L(r2)=L(r) q0f0M1q1f1M2q2f2 242022-3-18l情形情形2：r=r1r2, 設(shè)設(shè)Mi同情形同情形1(i=1,2)。 令令M=，其中，其中 定義如下：定義如下：(a) (q,a)= 1(q,a), 當當q S1-f1, a1 (b) (q,a)=

17、 2(q,a), 當當q S2, a2 (c) (f1, )=q2 M的狀態(tài)轉(zhuǎn)換如右圖所示。的狀態(tài)轉(zhuǎn)換如右圖所示。 L(M)=L(M1)L(M2) =L(r1)L(r2)=L(r)。 M1q1f1M2q2f2252022-3-18l情形情形3：r=r1*。設(shè)。設(shè)M1同情形同情形1。令令M=，其中，其中q0, f0 S1， 定義如下：定義如下：(a) (q0, )= (f1, )=q1, f0(b) (q,a)= 1(q, a), 當當q S1-f1, a1 。M的狀態(tài)轉(zhuǎn)換如右圖所示。的狀態(tài)轉(zhuǎn)換如右圖所示。L(M) = L(M1)* = L(r1)* = L(r)至此，結(jié)論至此，結(jié)論2獲證。獲證

18、。 M1q1f1q0f0 262022-3-181) 1) 構(gòu)造構(gòu)造 上的上的NFA M 使得使得 L(V)=L(M)首先，把首先，把V表示成表示成XYV上述證明過程實質(zhì)上是一個將正規(guī)表達式上述證明過程實質(zhì)上是一個將正規(guī)表達式轉(zhuǎn)換為有限自動機的算法。轉(zhuǎn)換為有限自動機的算法。272022-3-18代之為代之為ijV1V2kikV1V2代之為代之為ijV1|V2ijV2V1代之為代之為ikV1*ij kV1然后，按下面的三條規(guī)則對然后，按下面的三條規(guī)則對V進行分裂進行分裂282022-3-18n逐步把這個圖轉(zhuǎn)變?yōu)槊織l弧只標記為逐步把這個圖轉(zhuǎn)變?yōu)槊織l弧只標記為 上的上的一個字符或一個字符或 ，最后得

19、到一個，最后得到一個NFA M，顯然，顯然L(M)=L(V)292022-3-18n(a|b)*(aa|bb)(a|b)*XY(a|b)*(aa|bb)(a|b)*XY 514236ab ababab302022-3-18IIaIbX,5,15,3,15,4,15,3,15,2,3,1,6,Y5,4,15,4,15,3,15,2,4,1,6,Y5,2,3,1,6,Y5,2,3,1,6,Y5,4,6,1,Y5,4,6,1,Y5,3,6,1,Y5,2,4,1,6,Y5,2,4,1,6,Y5,3,6,1,Y5,2,4,1,6,Y5,3,6,1,Y5,2,3,1,6,Y5,4,6,1,YXY 5142

20、36ab ababab312022-3-18Iab0121322153344655656340123546aabbbabaababab322022-3-18FA正規(guī)集正規(guī)集正規(guī)式正規(guī)式DFANFA正規(guī)文法正規(guī)文法3.3.13.3.23.3.33.3.43.3.5DFA3.3.6332022-3-183.3.6 3.3.6 確定有限自動機的化簡確定有限自動機的化簡n對對DFA M的化簡的化簡:尋找一個狀態(tài)數(shù)比尋找一個狀態(tài)數(shù)比M少少的的DFA M，使得，使得L(M)=L(M)n假設(shè)假設(shè)s和和t為為M的兩個狀態(tài)，稱的兩個狀態(tài)，稱s和和t等價等價:如果從狀態(tài)如果從狀態(tài)s出發(fā)能讀出某個字出發(fā)能讀出某個字

21、 而停止而停止于終態(tài)，那么同樣，從于終態(tài)，那么同樣，從t出發(fā)也能讀出出發(fā)也能讀出 而停止于終態(tài)；反之亦然。而停止于終態(tài)；反之亦然。n兩個狀態(tài)不等價，則稱它們是兩個狀態(tài)不等價，則稱它們是可區(qū)別可區(qū)別的。的。狀態(tài)等價狀態(tài)等價狀態(tài)可區(qū)別狀態(tài)可區(qū)別342022-3-18n對一個對一個DFA M最少化的基本思想最少化的基本思想: 把把M M的狀態(tài)集劃分為一些的狀態(tài)集劃分為一些不相交不相交的子的子集，使得任何兩個不同子集的狀態(tài)是集，使得任何兩個不同子集的狀態(tài)是可區(qū)別的，而同一子集的任何兩個狀態(tài)是的，而同一子集的任何兩個狀態(tài)是等價的。最后，從每個子集選出一個代的。最后，從每個子集選出一個代表，同時消去其他狀

22、態(tài)。表，同時消去其他狀態(tài)。352022-3-18n具體做法具體做法: 對對M的狀態(tài)集進行劃分的狀態(tài)集進行劃分首先，把首先，把S劃分為終態(tài)和非終態(tài)兩個子集，劃分為終態(tài)和非終態(tài)兩個子集，形成基本劃分形成基本劃分 。 假定到某個時候，假定到某個時候， 已含已含m個子集，記為個子集，記為 =I(1)，I(2)，I(m)，檢查，檢查 中的每個子中的每個子集看是否能進一步劃分集看是否能進一步劃分:n對某個對某個I(i)，令，令I(lǐng)(i)=s1,s2, ,sk，若存在，若存在一個輸入字符一個輸入字符a使得使得Ia(i) 不會包含在現(xiàn)行不會包含在現(xiàn)行 的某個子集的某個子集I(j)中，則至少應把中，則至少應把I(

23、i)分為兩分為兩個部分。個部分。362022-3-18n例如，假定狀態(tài)例如，假定狀態(tài)s1和和s2經(jīng)經(jīng)a弧分別到達弧分別到達t1和和t2，而，而t1和和t2屬于現(xiàn)行屬于現(xiàn)行 中的兩個不同子集，中的兩個不同子集，說明有一個字說明有一個字 ， t1讀出讀出 后到達終態(tài)，而后到達終態(tài)，而t2讀出讀出 后不能到達終態(tài)，或者反之，那后不能到達終態(tài)，或者反之，那么對于字么對于字a ， s1讀出讀出a 后到達終態(tài)，而后到達終態(tài)，而s2讀出讀出a 不能到達終態(tài)，或者反之，所以不能到達終態(tài)，或者反之，所以s1和和s2不等價。不等價。s1t1as2t2a i j372022-3-18n則將則將I(i)分成兩半，使得

24、一半含有分成兩半，使得一半含有s1 : I(i1)=s|s I(i)且且s經(jīng)經(jīng)a弧到達弧到達t, 且且t與與t1屬于現(xiàn)行屬于現(xiàn)行 中的同一子集中的同一子集 另一半含有另一半含有s2 : I(i2)=I(i)-I(i1)s1t1as2t2a i j382022-3-18n一般地，對某個一般地，對某個a和和I(i)，若，若Ia(i) 落入現(xiàn)行落入現(xiàn)行 中中 N個不同子集，則應把個不同子集，則應把I(i)劃分成劃分成N個不相交個不相交的組，使得每個組的組，使得每個組J的的Ja都落入的都落入的 同一子同一子集。這樣構(gòu)成新的劃分。集。這樣構(gòu)成新的劃分。n重復上述過程，直到重復上述過程，直到 所含子集數(shù)不再增長。所含子集數(shù)不再增長。n對于上述最后劃分對于上述最后劃分 中的每個子集，我們選中的每個子集，我們選取每個子集取每個子集I中的一個狀態(tài)代表其他狀態(tài)，中的一個狀態(tài)代表其他狀態(tài)，則可得到化簡后的則可得到化簡后的D