編譯原理PPT總結(jié)

1、下:編譯原理PPT總結(jié)1.正規(guī)文法到正規(guī)式的轉(zhuǎn)換 ：(i)將正規(guī)文法中的每個(gè)非終結(jié)符表 示成關(guān)于它的一個(gè)正規(guī)式方程，獲得一個(gè)聯(lián)立方程組。(2)依照求解規(guī)則：若 X = a X | 3 (或 X = a X + 3 ) 則解為X = a * 3 ；若 X = Xa | 3 (或 X = X a + 3 ) 則解為X = 3 a *以及正規(guī)式的分配律、交換律和結(jié)合律 求關(guān)于文法開始符號(hào)的正規(guī)式方程組的解。例1設(shè)有正規(guī)文法G：Z 0AA0A | 0BB1A | 試給出該文法生成語(yǔ)言的正規(guī)式。分析首先給出相應(yīng)的正規(guī)式方程組(方程組中用 午”代替正規(guī)式中的“| ”)如下： TOC o 1-5 h z Z

2、=0A(1)A = 0A + 0B(2)B=1A+ s(3)將(3)代入(2)中的B得A=0A+01A+0(4)又(4)利用分配律得A=(0+01)A+0(5)X(5)使用求解規(guī)則得A=(0+01)*0(6)將(6)代入式中的A,得Z = 0 (0 + 01)* 0即正規(guī)文法GZ所生成語(yǔ)言白正規(guī)式是：R = 0 (0 | 01)* 0例2設(shè)有正規(guī)文法G :A aB|bBB aC | a | bC aB試給出該文法生成語(yǔ)言的正規(guī)式。分析首先給出相應(yīng)的正規(guī)式方程組(方程組中用 午”代替正規(guī)式中的“| ”)如 TOC o 1-5 h z A = aB + bB(1)B = aC + a + b (2

3、)C = aB(3)將(3)代入(2)中的C得B=aaB + a + b (4)(4)使用求解規(guī)則得B=(aa)*(a+b)(5)(5)代入(1)中的B得A = (a + b)(aa)*(a + b)即正規(guī)文法 GA所生成語(yǔ)言的正規(guī)式是：R = (a | b)(aa)*(a | b)2.正規(guī)式到正規(guī)文法的轉(zhuǎn)換：(1)令 VT= 2(2)對(duì)任何正規(guī)式R選擇一個(gè)非終結(jié)符Z生成規(guī)則Z R并令S=Z。(3)若a和b都是正規(guī)式，對(duì)形如 A ab 的規(guī)則轉(zhuǎn)換成 A aB和B b兩規(guī)則，其 中B是新增的非終結(jié)符。(4)對(duì)已轉(zhuǎn)換的文法中，形如A a*b的 規(guī)則，進(jìn)一步轉(zhuǎn)換成A aA | b。(5)不斷利用規(guī)則

4、(3)和(4)進(jìn)行變換，直到 每條規(guī)則最多含有一個(gè)終結(jié)符為止。例1 將R=(a | b)(aa)*(a | b)轉(zhuǎn)換成相應(yīng)的 正規(guī)文法。解：令A(yù)是文法開始符號(hào)，根據(jù)規(guī)則(2) 變換為：A (a | b)(aa)*(a | b)根據(jù)規(guī)則(3)變換為：A (a | b)BB (aa)*(a | b)對(duì)B根據(jù)規(guī)則(4)變換為A aB|bBB aaB | a | b 根據(jù)規(guī)則(3)變換為A aB|bBB aC | a | bC aB.確定有限自動(dòng)機(jī)(DFA)的定義：確定的有限自動(dòng)機(jī) DFA M是一個(gè)五元 式M = (S, 8 , s0 , F )S是一個(gè)非空有限集，它的每個(gè)元素稱為一個(gè)狀態(tài)是一個(gè)有窮字

5、母表，它的每個(gè)元素稱為一個(gè)輸入符號(hào)，所以也稱為輸入符號(hào) 字母表8是狀態(tài)轉(zhuǎn)換函數(shù)，是在S X 一 S上的單值映射。8 (s,a) =s意味著：當(dāng)先行狀態(tài)為s、輸入字符為a時(shí)，將轉(zhuǎn)到下一 狀態(tài)s。我們稱s為s的一個(gè)后繼狀態(tài)。s0CS,是唯一的一個(gè)初態(tài)F S,是一個(gè)終態(tài)集(可空)，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。例如有 DFA M= (0,1,2,3,a,b , 8 ,0,3) 其中8定義為：5 (0,a)=1S ( 0,b)=2S ( 1,a)=3S ( 1,b)=2S (2,a)=1S (2,b)=3S (3, a) =3 S (3, b) =3其它表示形式：狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖NFA和DFA

6、的不同在于：1)8的值域是S的子集2)開始狀態(tài)有不止一個(gè)3)在NFA中每個(gè)結(jié)點(diǎn)可射出若干條弧與別 的結(jié)點(diǎn)相連接，每條弧用匯中的一個(gè)正規(guī) 式做標(biāo)記。例如 NFA M =(0,1,2,3,4,a,b, 8，0，1,2)其中：S (0,a)=0,3S (1,a)=1S (2,a)=2S (3,a)=1( (0,b)=0,4S(1,b)=1S (2,b)=2S (3,b)= 6S (4,b)=2S (4,a)= 6狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖:ab00,30, 411122231462例1 試構(gòu)造識(shí)別語(yǔ)言R = (a | b)*abb的NFA N,使 L(N)=L(R)。例2試構(gòu)造識(shí)別標(biāo)識(shí)符的NFA,描述

7、標(biāo)識(shí)符的正規(guī)式首先將R表示成如下拓廣轉(zhuǎn)換圖X，H，d)4丫)從左到右分裂R首先將R表示成如下拓廣轉(zhuǎn)換圖(2)片消納+只剩Y反愛使用卜曲的替換理射消上w中的所相結(jié)點(diǎn).虺步陽(yáng)正屈代束時(shí)七為：on結(jié)就1WY之間抽上的標(biāo)記.即為所求正初L從NFA M構(gòu)造正規(guī)式r舉例:例3試構(gòu)造正規(guī)式R=。的NFA苜先利用正規(guī)式的等價(jià)性化簡(jiǎn)正規(guī)式V (1,),=!* A R=Of |Q1=O(1*| 1)=01*首先將R走示成如F拓廣轉(zhuǎn)換圖OXX結(jié)點(diǎn)所有上的初態(tài)結(jié)點(diǎn)所有晡然志魴點(diǎn)-結(jié)點(diǎn)那么,中只有個(gè)初態(tài)X,一個(gè)終態(tài)Taa(alb)*hh山(5)合并0和Y間弧alb消去結(jié)點(diǎn)0(aelbb) (alb)*alb(aJb)

8、* (na hi).(a! b)，故構(gòu)造出來(lái)的正規(guī)式r (alb)*(率dbb)品1份*5. 由NFA確定DFA :若規(guī)定NFA的初杰集中只有唯一一個(gè)兀素，即 NFA的初態(tài)唯一，且狀態(tài)轉(zhuǎn)換函數(shù)單值，則讀 hFA即為DFADFA是NFA的特例對(duì)每一個(gè)NFA N一定存在一個(gè)DFA M,使得 L(M)=L(N)即對(duì)每個(gè)NFA即存在著與之等價(jià)的DFA M注意：與某一NFA等價(jià)的DTA不唯一NFA確定化.DFA子集法將NFA確定化為DFA的原因：使用NFA判定某個(gè)輸入符號(hào)串的時(shí)候，可能出現(xiàn)不確定的情況：不知道下面選擇那個(gè)狀態(tài)。如果選擇不好， 該輸入符號(hào)串可能不能到達(dá)終止?fàn)顟B(tài)。但是，我們不能 說(shuō)該輸入符號(hào)

9、串不能被該 NFA接受如果通過嘗試的方法，不斷試探來(lái)確定輸入符號(hào)串是 否可被接受，那么判定的效率將降低。解決的方法是將 NFA轉(zhuǎn)換為等價(jià)的DFAlLa 飆，5, 1(S. 3. 1低 4, 1)1 5.3, 11& 2r3, 1,6, Y) 4,12 % 1)區(qū)1)5, 2T 4, 1, & Y3 - 2. 3, h I (5. 2,3,1+Y15Y.6 J4 2,%1.615. 3. 6, lF Y4%6*LY5 (5,4.6, l.Y)3, L Y115. 2.64 L V)6 (5, 3r6, 1,Y5. 2,6, 3, 1, Y,5. 6, f(A,0)=A,Bf(B,0)= f 狀態(tài)

10、子集重命名后的狀態(tài)轉(zhuǎn)換矩陣ab01211312214333546A64635確定化后的狀態(tài)轉(zhuǎn)換圖例2符下面的NT AN確定化.di首先確定其初態(tài).命名為0狀態(tài)0 = E -CLOSURE(XhX_Q1d岡11)12Y億Y2.Y億Y2,Y)P：Y02首先確定其初態(tài)，命名為。狀態(tài)0 = E 工LOSURE(X尸XQ，010X12Y1o口 Y)區(qū)o6構(gòu)造下述文法 GZ的有窮臼動(dòng)機(jī)。例1Z-0AA-0A | 0BB - 1A | 解：f(Z,0)=Af(Z,1)= f(z,f(A,0)=A,Bf(A,1)= f(A,f(B,0)=f(B,1)=A f(B,e尸)=尸D0zA01 B2其狀態(tài)圖如圖(a)

11、或(b)所示。顯然,自動(dòng)機(jī)M是非確定的。 它識(shí)別的語(yǔ)言就是文法GZ 所描述的語(yǔ)言即L(GZ)=L(M)=0(0|0iy0o00 of例L構(gòu)造下文(b)文法GA的自動(dòng)機(jī).Af Al |B1B-BO|O0如下圖所示01B顯然，該自動(dòng)機(jī)是確定的。它識(shí)別的語(yǔ)言 就是文法GA所描述的語(yǔ)言。即 L(GfAl)=L(M)=OO*ll*例1設(shè)有窮自動(dòng)機(jī)乂=(5八,趾,0,11，依) 其中 f(S,a)=A f(S,b)=Af (A.a)=A f (A.b 尸 A f(A,O)=A f(A,l)=A M的狀態(tài)轉(zhuǎn)換圖如圖所示。 根據(jù)上述轉(zhuǎn)換規(guī)則，與M 等價(jià)的正規(guī)文法G為：G=(S,A,a,b,O/,P,S)其中P

12、: S;aA|bA Ar：aA|bA|0A| 1A| 或P： Sr*aA I bA A-aA |bA| 0A | 1A|a|b|a|b|O|l自動(dòng)機(jī)M所識(shí)別的語(yǔ)言L(M)=L(G)=(a|bXO|l Wb),例2 設(shè)DFAM=(A,B,C,O,1,例A,B) 其中：6 (A?0)=BS (B,1)=C5 (Cr0)=BG=(A,B,C,(M,P, A)其中P為A-OB | 0B-1C C-OBIOA-OB B-1C| COB0AC1根據(jù)轉(zhuǎn)換規(guī)則所求右線性文法為G=(A,B,C,0,P, A)其中P為Af 0B | 0B-ICC-OB | 0A-OB或 B-1CCf 0B該自動(dòng)機(jī)所識(shí)別的語(yǔ)言為0

13、(10)*例1將下圖所示的NFAN確定化。01 b 3 Ph0a13abABCDEa1：X：- 1 *FTT- e.F 9(E)&F今i首先確定其初態(tài)，命名為0狀態(tài)0 = -Cl OSUREX和2是可區(qū)別的雖然同為非終態(tài)，但13 2.=1且由1是可區(qū)別的4, 5,和6是等價(jià)的 (3, 4, 5, 6 srr - ,sr| 例3：有如下兩個(gè)產(chǎn)生式：VIF語(yǔ)句,- if E then S1 else S2;(IF語(yǔ)句a 今 if Ethen S1;提取左因子后：IF語(yǔ)句- if E then SI B;R 今 else S2 | t ;求非終結(jié)符 A的Follow集的算法.如果A是開始符號(hào)，#C

14、Follow(A).若有產(chǎn)生式B a Aa 3 ,aC VT ,則把a(bǔ)加入到Follow(A)中；.若有產(chǎn)生式B a AX 3 , X C VN ,則把First(X 3 )中非元素加入 Follow(A)中；.若 B a A 或 B a A 3 , 3 = e ,則把 Follow(B)加入到 Follow(A)中；.連續(xù)使用上述規(guī)則，直到Follow(A)不再增大。 七靠干數(shù)的 Foil05/follow(E) = #, )followfE) = followE) = # )Jfollow(T) - (flr娜H層) u=#,),+follow(r)_follow(T) = 禮)r +fo

15、lloF)=(first(T)- )Ufollow(T) =*,#,),+bbAE$-3|謁 gS| t LTL1 f LEFimtS)= (- a斌FimtS9=Cat E J)Fint(D= (, a)Follow(L)= )Eimcn=，,&的延 C尸a()#S$-*aS5 (L)S1STSfS+TS1-2S fLL-srLTl;VLf SUL J 練習(xí)1:文法GV:V - N|NEE - V|V+E制；判斯下述攵凌是否是LL(1)次注,S - a AS解: (D該文法不含左遞歸 EixatXS4AS)=a EixaiiSb)=EixrlA分bA) = (b)EiiKi(A1,) = (

16、e5和A的侯選式的first集都不相交，滿足條件2(3)由于垂 C.FirtfA- )Ml/IA) =EXj心卜瓜b)EqILdwIA) EirsMA - bA) ) 金也不滿足條件3,則不是LL1D文法S - xAyA - abb利甑禽魚的執(zhí)法是否為幺次 族，老不是，斑行改造解答：EimlArtab)二：First (A-a) = a;不滿足條件2,故不是LL(1)文法 ,改造方法：(消除回溯一提取公因子) S+xAy ; A-a(b|。= S-xAy ; AlaA; A 3b| e例：對(duì)于文法G(E)E-7Er Er-+TEJ 1 & T- FTr T-FT | 需 F *(E)| j 構(gòu)

17、造每個(gè)非終結(jié)符的FIRST和FOLLOW集合： FIRST(E) =(, iFOLLOW(E! =),#FIRST(E)- is iFIRSTVT和LASTVT集合的定義關(guān)于文法G中的每個(gè)非終結(jié)符 P:FIRSTVT(P尸a| P +a，或者 P +Qa，a C VT 且 Q C VN含義：由P往下推導(dǎo)所有可能出現(xiàn)的首個(gè)終結(jié)符例如：有 F一(E)|i ,則(，iCFIRSTVT(F)有 EfE+T,貝U E E+T, + FIRSTVT(E) LASTVT(P)=a|P+ a,或者 P + aQ,a C VT 且 Q VN含義：由P往下推導(dǎo)所有可能出現(xiàn)的最后一個(gè)終結(jié)符例如：有 F一(E)|i，

18、則),i C LASTVT(F)有 EfE+T,貝U E E+T, + LASTVT(E)連續(xù)使用下面兩條規(guī)則，直到 FIRSTVT(P)不再擴(kuò)大為止 若有 Pfa或 PfQa，貝U aCFIRSTVT(P)若 aC FIRSTVT(Q),且有 P-Q，貝U aC FIRSTVT(P) 即 FIRSTVT(Q)力口入 FIRSTVT(P)連續(xù)使用下面兩條規(guī)則，直到 LASTVT(P)不再擴(kuò)大為止 若有 Pfa 或 PfaQ MaC LASTVT(P)若 aC LASTVT(Q),且有 P-Q ,貝U aC LASTVT(P) 即把 LASTVT(Q)中力口入 LASTVT(P)中文法G為：Ef

19、 E+T|TFf P t F|PPf |iFIRSTVT (E)-WFTRSTVT(P)(, i)FIRSTVT(F)= 3 (, iFIRSTVT,(,FIRSTVT (E)+, *, f ,LASTVT (E9 = #LASTVT (?) = ), i1)(，iBEGIN LASTVT (F)= f , ) r 1LASTVT(T) = *, t , ), iLASTVT(E)=+, *, t t )t i)確定算符的優(yōu)先關(guān)系，構(gòu)造文法的算符優(yōu)先表 若有 A一ab或 A一aPb，貝U a=b 若有 A faP,對(duì) bC FIRSTVT(P),貝U abLR分析表課堂練習(xí)句子btib分析BE

20、GIN狀態(tài)2)043)024)0236)0236 7)025 8)01符號(hào)輸入動(dòng)作flb 那 排知bfibftwbfl#厘au邦如B*3狀 態(tài)ACTION動(dòng)作GOTO轉(zhuǎn)換abttSB08 3s41acc2s353_s1o4TTr35r 16r2 1r2r2文法(1)S-*BB(2)fr*aB(3)B，b1.可歸前綴是指AC2.A規(guī)范句型的A 。(可歸)前綴 B活前綴含有句柄的活前綴 D句柄若a為終結(jié)符，則A- a .ap為A項(xiàng)目。移進(jìn) B待約 C規(guī)約 D接受3. LR分析器核心部分是一張分析表，該表由 組成。(D)A ACTION 表 B GOTO 表 C LL(1)分 析表 D ACTION表和GOTO 表4.算符優(yōu)先分析法每次都是對(duì) 進(jìn)行規(guī)約。(B)A短語(yǔ) B最左素短語(yǔ) C素短語(yǔ) D 句柄 5自下而上語(yǔ)法分析的基本思想是：從待輸入的符號(hào)串出發(fā)，利用文法的產(chǎn)生式步步向上 規(guī)約，試圖直至規(guī)約到文法的 開始符號(hào)。6最右推導(dǎo)也被稱為規(guī)范推導(dǎo).其所得到的 句型稱為規(guī)范句型。7規(guī)范歸約每次歸約的是當(dāng)前句型的 句柄， 算符優(yōu)先文法每次歸約的是當(dāng)前句型的最左素短語(yǔ)。8、LR (0)分析法的名字中，L”的含義是以左到右掃描輸入串,R”的含義是 構(gòu)造一個(gè)最 右推導(dǎo)的逆過程,0含義是 每步頂