編譯原理PPT總結

1、下:編譯原理PPT總結1.正規(guī)文法到正規(guī)式的轉換 ：(i)將正規(guī)文法中的每個非終結符表 示成關于它的一個正規(guī)式方程，獲得一個聯(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ī)式的分配律、交換律和結合律 求關于文法開始符號的正規(guī)式方程組的解。例1設有正規(guī)文法G：Z 0AA0A | 0BB1A | 試給出該文法生成語言的正規(guī)式。分析首先給出相應的正規(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所生成語言白正規(guī)式是：R = 0 (0 | 01)* 0例2設有正規(guī)文法G :A aB|bBB aC | a | bC aB試給出該文法生成語言的正規(guī)式。分析首先給出相應的正規(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所生成語言的正規(guī)式是：R = (a | b)(aa)*(a | b)2.正規(guī)式到正規(guī)文法的轉換：(1)令 VT= 2(2)對任何正規(guī)式R選擇一個非終結符Z生成規(guī)則Z R并令S=Z。(3)若a和b都是正規(guī)式，對形如 A ab 的規(guī)則轉換成 A aB和B b兩規(guī)則，其 中B是新增的非終結符。(4)對已轉換的文法中，形如A a*b的 規(guī)則，進一步轉換成A aA | b。(5)不斷利用規(guī)則

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

5、母表，它的每個元素稱為一個輸入符號，所以也稱為輸入符號 字母表8是狀態(tài)轉換函數(shù)，是在S X 一 S上的單值映射。8 (s,a) =s意味著：當先行狀態(tài)為s、輸入字符為a時，將轉到下一 狀態(tài)s。我們稱s為s的一個后繼狀態(tài)。s0CS,是唯一的一個初態(tài)F S,是一個終態(tài)集(可空)，終態(tài)也稱可接受狀態(tài)或結束狀態(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)轉換矩陣和狀態(tài)轉換圖NFA和DFA

6、的不同在于：1)8的值域是S的子集2)開始狀態(tài)有不止一個3)在NFA中每個結點可射出若干條弧與別 的結點相連接，每條弧用匯中的一個正規(guī) 式做標記。例如 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)轉換矩陣和狀態(tài)轉換圖:ab00,30, 411122231462例1 試構造識別語言R = (a | b)*abb的NFA N,使 L(N)=L(R)。例2試構造識別標識符的NFA,描述

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

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

9、串不能被該 NFA接受如果通過嘗試的方法，不斷試探來確定輸入符號串是 否可被接受，那么判定的效率將降低。解決的方法是將 NFA轉換為等價的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)轉換矩陣ab01211312214333546A64635確定化后的狀態(tài)轉換圖例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構造下述文法 GZ的有窮臼動機。例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)所示。顯然,自動機M是非確定的。 它識別的語言就是文法GZ 所描述的語言即L(GZ)=L(M)=0(0|0iy0o00 of例L構造下文(b)文法GA的自動機.Af Al |B1B-BO|O0如下圖所示01B顯然，該自動機是確定的。它識別的語言 就是文法GA所描述的語言。即 L(GfAl)=L(M)=OO*ll*例1設有窮自動機乂=(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)轉換圖如圖所示。 根據(jù)上述轉換規(guī)則，與M 等價的正規(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自動機M所識別的語言L(M)=L(G)=(a|bXO|l Wb),例2 設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ù)轉換規(guī)則所求右線性文法為G=(A,B,C,0,P, A)其中P為Af 0B | 0B-ICC-OB | 0A-OB或 B-1CCf 0B該自動機所識別的語言為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是等價的 (3, 4, 5, 6 srr - ,sr| 例3：有如下兩個產(chǎn)生式：VIF語句,- if E then S1 else S2;(IF語句a 今 if Ethen S1;提取左因子后：IF語句- if E then SI B;R 今 else S2 | t ;求非終結符 A的Follow集的算法.如果A是開始符號，#C

14、Follow(A).若有產(chǎn)生式B a Aa 3 ,aC VT ,則把a加入到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 練習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例：對于文法G(E)E-7Er Er-+TEJ 1 & T- FTr T-FT | 需 F *(E)| j 構

17、造每個非終結符的FIRST和FOLLOW集合： FIRST(E) =(, iFOLLOW(E! =),#FIRST(E)- is iFIRSTVT和LASTVT集合的定義關于文法G中的每個非終結符 P:FIRSTVT(P尸a| P +a，或者 P +Qa，a C VT 且 Q C VN含義：由P往下推導所有可能出現(xiàn)的首個終結符例如：有 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往下推導所有可能出現(xiàn)的最后一個終結符例如：有 F一(E)|i，

18、則),i C LASTVT(F)有 EfE+T,貝U E E+T, + LASTVT(E)連續(xù)使用下面兩條規(guī)則，直到 FIRSTVT(P)不再擴大為止 若有 Pfa或 PfQa，貝U aCFIRSTVT(P)若 aC FIRSTVT(Q),且有 P-Q，貝U aC FIRSTVT(P) 即 FIRSTVT(Q)力口入 FIRSTVT(P)連續(xù)使用下面兩條規(guī)則，直到 LASTVT(P)不再擴大為止 若有 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)先關系，構造文法的算符優(yōu)先表 若有 A一ab或 A一aPb，貝U a=b 若有 A faP,對 bC FIRSTVT(P),貝U abLR分析表課堂練習句子btib分析BE

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