1、會計學1編譯編譯(biny)原理期末復習原理期末復習第一頁，共53頁。2題型：題型：填空填空 20分，分，10個空個空選擇選擇 20分，分，10小題小題(xio t)判斷判斷 10分，分，10小題小題(xio t)簡答題簡答題 20分，分，4小題小題(xio t)分析題分析題 30分，分，3小題小題(xio t)第1頁/共53頁第二頁，共53頁。3第2頁/共53頁第三頁，共53頁。第3頁/共53頁第四頁，共53頁。 = =。第4頁/共53頁第五頁，共53頁。nD. R1D. R1和和R2R2代表不同正則集代表不同正則集n(6)(6)設(shè)有設(shè)有A=a,abc A=a,abc 則則A3= A3= 。

2、第5頁/共53頁第六頁，共53頁。第6頁/共53頁第七頁，共53頁。第7頁/共53頁第八頁，共53頁。9如圖所示自動機如圖所示自動機M，請問下，請問下列哪個列哪個(n ge)字符串不是字符串不是M所能識別的所能識別的( D )。A. bbaaB. abbaC. ababD. Aabb第8頁/共53頁第九頁，共53頁。103.判斷判斷(pndun)句子、畫分析樹、文法符號集句子、畫分析樹、文法符號集、終結(jié)符集、非終結(jié)符集、終結(jié)符集、非終結(jié)符集1) 設(shè)有文法：設(shè)有文法： SaSbS|bSaS|c(1)判斷判斷(pndun)符號串符號串a(chǎn)babba是否為文法是否為文法G(S)的句子，如果是畫出其分析

3、樹。的句子，如果是畫出其分析樹。(2)給出給出G(S)的元語言符號集、文法符號集、終結(jié)的元語言符號集、文法符號集、終結(jié)符集、非終結(jié)符集符集、非終結(jié)符集第9頁/共53頁第十頁，共53頁。113.判斷句子、畫分析樹、文法判斷句子、畫分析樹、文法(wnf)符號集、終符號集、終結(jié)符集、非終結(jié)符集結(jié)符集、非終結(jié)符集1) 設(shè)有文法設(shè)有文法(wnf)： SaSbS|bSaS|c(1)判斷符號串判斷符號串a(chǎn)babba是否為文法是否為文法(wnf)G(S)的的句子，如果是畫出其分析樹。句子，如果是畫出其分析樹。(2)給出給出G(S)的元語言符號集、文法的元語言符號集、文法(wnf)符號符號集、終結(jié)符集、非終結(jié)符

4、集集、終結(jié)符集、非終結(jié)符集第10頁/共53頁第十一頁，共53頁。12練習：練習：設(shè)有文法設(shè)有文法G(S)為為SABx|xSxAxy|yAy|mnBxyA|m(1)判斷判斷(pndun)符號串符號串ymnyxyxy是否為文是否為文法法G(S)的句子，如果是畫出其分析樹。的句子，如果是畫出其分析樹。(2)給出給出G(S)的元語言符號集、文法符號集、終的元語言符號集、文法符號集、終結(jié)符集、非終結(jié)符集結(jié)符集、非終結(jié)符集第11頁/共53頁第十二頁，共53頁。135.5.有限有限(yuxin)(yuxin)自動機的表示自動機的表示狀態(tài)函數(shù)狀態(tài)函數(shù) 、狀態(tài)圖、狀態(tài)矩陣、狀態(tài)圖、狀態(tài)矩陣例：例：設(shè)有確定的有限

5、設(shè)有確定的有限(yuxin)(yuxin)自動機自動機M:M:（0,1,2,3,a,b,0,1,2,3,a,b,，0 0，33）（0 0，a a）=1 =1 （0 0，b b）=2=2（1 1，a a）=3 =3 （1 1，b b）=2=2（2 2，a a）=1 =1 （2 2，b b）=3=3（3 3，a a）=3 =3 （3 3，b b）=3=3畫出其狀態(tài)轉(zhuǎn)換圖和狀態(tài)轉(zhuǎn)換矩陣畫出其狀態(tài)轉(zhuǎn)換圖和狀態(tài)轉(zhuǎn)換矩陣第12頁/共53頁第十三頁，共53頁。14練習：設(shè)有確定練習：設(shè)有確定(qudng)的有限自動機的有限自動機M:（S,U,V,Q,0,1,f，S，Q）f（S，0）=U f（S，b）=Qf（

6、U，0）=Q f（U，1）=Vf（V，0）=S f（V，1）=Qf（Q，1）=V畫出其狀態(tài)轉(zhuǎn)換圖畫出其狀態(tài)轉(zhuǎn)換圖第13頁/共53頁第十四頁，共53頁。155. NFA轉(zhuǎn)換轉(zhuǎn)換(zhunhun)為為DFA(1) 給定(i dn)非確定的有限自動機M如下圖所示將將M確定化，并畫出確定化后的狀態(tài)確定化，并畫出確定化后的狀態(tài)(zhungti)轉(zhuǎn)換圖（要求：寫出步驟）轉(zhuǎn)換圖（要求：寫出步驟）第14頁/共53頁第十五頁，共53頁。165. NFA轉(zhuǎn)換轉(zhuǎn)換(zhunhun)為為DFA練習練習(linx)(linx)： 給定非確定的有限自動機給定非確定的有限自動機M M如下圖所示如下圖所示4f35621i a

7、aaabbbb將將M M確定確定(qudng)(qudng)化，并畫出確定化，并畫出確定(qudng)(qudng)化化后的狀態(tài)轉(zhuǎn)換圖（要求：寫出步驟）后的狀態(tài)轉(zhuǎn)換圖（要求：寫出步驟）第15頁/共53頁第十六頁，共53頁。17給定非確定的有限給定非確定的有限(yuxin)(yuxin)自動機自動機M M如下圖所示如下圖所示將將M M確定確定(qudng)(qudng)化，并畫出確定化，并畫出確定(qudng)(qudng)化后的狀化后的狀態(tài)轉(zhuǎn)換圖（要求：寫出步驟）態(tài)轉(zhuǎn)換圖（要求：寫出步驟）第16頁/共53頁第十七頁，共53頁。186 6 消除無關(guān)消除無關(guān)(wgun)(wgun)狀態(tài)狀態(tài)消除上圖

8、所示的消除上圖所示的DFADFA的無關(guān)狀態(tài)（要求的無關(guān)狀態(tài)（要求(yoqi)(yoqi)寫出寫出步驟）步驟）152463789679abaaabbba第17頁/共53頁第十八頁，共53頁。197 7 有限自動機和正規(guī)有限自動機和正規(guī)(zhnggu)(zhnggu)式的轉(zhuǎn)換式的轉(zhuǎn)換例例練習練習(linx)(linx)第18頁/共53頁第十九頁，共53頁。第19頁/共53頁第二十頁，共53頁。nC. Sxx|yxx D. C. Sxx|yxx D. SSy|xSSy|x第20頁/共53頁第二十一頁，共53頁。第21頁/共53頁第二十二頁，共53頁。例：例：E-E+T|T E-E+T|T T-TF|

9、F T-TF|F F-FF-F* *|a|b |a|b 求非終結(jié)符的求非終結(jié)符的FIRSTFIRST集和集和FOLLOWFOLLOW集集第22頁/共53頁第二十三頁，共53頁。練習練習(linx)(linx)：文法文法GSGS為：為： SAB|bC SAB|bC Ab|aA Ab|aA B aD |bD B aD |bD CAD|b CAD|b DaS|c DaS|c求非終結(jié)符的求非終結(jié)符的FIRSTFIRST集和集和FOLLOWFOLLOW集集第23頁/共53頁第二十四頁，共53頁。3. 3. 消除直接左遞歸消除直接左遞歸例例消除下列消除下列(xili)(xili)文法的直接左遞歸文法的直接

10、左遞歸E-E+TE-E+TT-TT-T* *F|FF|FF-(E)|id|F(id)F-(E)|id|F(id)答案：答案：E-EE-EE-+TE|E-+TE|T-FTT-FTT-T-* *FT|FT|F-(E)F|idFF-(E)F|idFF-(id)F| F-(id)F| 第24頁/共53頁第二十五頁，共53頁。4.LL(1)分析分析例：例：已知文法已知文法G(E)為：為：E-TEE-+TE| T -FTT-*FT| F-(E)|i其預測其預測(yc)分析表為：分析表為：分析分析i*i+i*i是否為該文法的句子，寫出分析過是否為該文法的句子，寫出分析過程程 第25頁/共53頁第二十六頁，共

11、53頁。27第26頁/共53頁第二十七頁，共53頁。步驟步驟分析棧分析棧余留輸入串余留輸入串所用產(chǎn)生式所用產(chǎn)生式1#Ei*i+i*i#23456789第27頁/共53頁第二十八頁，共53頁。4.LL(1)分析分析例：例：已知文法已知文法(wnf)G(E)為：為：E-TEE-+TE| T -FTT-*FT| F-(E)|i其預測分析表為：其預測分析表為：分析分析i+i+i*i是否為該文法是否為該文法(wnf)的句子，寫出分析過程的句子，寫出分析過程 第28頁/共53頁第二十九頁，共53頁。第29頁/共53頁第三十頁，共53頁。文法文法GMGM及其及其LRLR分析分析(fnx)(fnx)表如下，請

12、表如下，請給出對串給出對串dbba#dbba#的分析的分析(fnx)(fnx)過程。過程。GM: 1) M VbAGM: 1) M VbA2) V d2) V d3) V 3) V 4) A a4) A a5) A Aba5) A Aba6) A 6) A 第30頁/共53頁第三十一頁，共53頁。32nameACTIONGOTObdaMAV0r3 S3 1 21 acc 2S4 3r2 4r6 S5r6 6 5r4 r4 6S7 r1 7 S8 8r5 r5 第31頁/共53頁第三十二頁，共53頁。33對串對串dbba#的分析過程的分析過程(guchng)如下表如下表步步驟驟狀態(tài)棧狀態(tài)棧文法符

13、號文法符號棧棧剩余輸剩余輸入符號入符號動作動作12345678900302024024602467024678024601#d#V#Vb#VbA#VbAb#VbAba#VbA#Mdbba#bba#bba#ba#ba#a#移進移進用用V d歸約歸約移進移進用用A 歸約歸約移進移進移進移進用用A Aba 歸約歸約用用M VbA 歸約歸約接受接受第32頁/共53頁第三十三頁，共53頁。34練習：文法練習：文法GSGS及其及其LRLR分析分析(fnx)(fnx)表如表如下，請給出對輸入串下，請給出對輸入串da;aoa#da;aoa#的分析的分析(fnx)(fnx)過過程。程。GS: GS: 0) SS

14、0) SS1) SdSoS1) SdSoS2) S dS2) S dS3) S S;S 3) S S;S 4) S a 4) S a 第33頁/共53頁第三十四頁，共53頁。35nameACTIONGOTOdo;a#S0S2S3 S3 11 S4 acc 2S2 S3 53 r4r4 r4 4S2 S3 65 S7S4 r2 6 r3r3 r3 7S2 S3 88 r1S4 r1 第34頁/共53頁第三十五頁，共53頁。36輸入串輸入串da;aoa#的分析過程的分析過程(guchng)如下表：如下表：步驟狀態(tài)棧文法符號棧剩余輸入符號動作123456789101112 0020230250254

15、02543025460250257025730257801#d#da#dS#dS;#dS;a#dS;S#dS#dSo#dSoa#dSoS#Sda;aoa#a;aoa#;aoa#;aoa#aoa#oa #oa #oa #a #移進移進用S a 歸約移進移進用S a 歸約用S S;S 歸約移進移進用S a 歸約用SdSoS 歸約接受第35頁/共53頁第三十六頁，共53頁。v2 FIRSTVT 和和LASTVT式式PR ，n則則a FIRSTVT(P)。第36頁/共53頁第三十七頁，共53頁。38v構(gòu)造集合構(gòu)造集合LASTVT(P)的算法。的算法。v按其定義按其定義(dngy)，可用下面兩條規(guī)則來構(gòu)

16、造，可用下面兩條規(guī)則來構(gòu)造集合集合LASTVT(P)：v1. 若有產(chǎn)生式若有產(chǎn)生式P a或或P aQ，則，則a LASTVT(P)；v2. 若若a LASTVT(Q)，且有產(chǎn)生式，且有產(chǎn)生式P Q ，則，則a LASTVT(P)。,|)(NTVQVaaQPaPaPLASTVT而或(二)LASTVT第37頁/共53頁第三十八頁，共53頁。39設(shè)有文法設(shè)有文法G(E)G(E)如下：如下：EE+T | TEE+T | TTTTT* *F | FF | FFPF | PFPF | PP(E) | iP(E) | i(1)(1)計算該文法的計算該文法的FIRSTVTFIRSTVT和和LASTVTLAST

17、VT(2)(2)計算該文法的有限關(guān)系計算該文法的有限關(guān)系(gun x)(gun x)并產(chǎn)生優(yōu)先并產(chǎn)生優(yōu)先關(guān)系關(guān)系(gun x)(gun x)表表第38頁/共53頁第三十九頁，共53頁。40v(1) vFIRSTVT(E)=+, *, , i, ( vFIRSTVT(T)= *, , i, ( vFIRSTVT(F)= , i, ( vFIRSTVT(P)= i, ( LASTVT(E)=+, *, , i, ) LASTVT(T)= *, , i, ) LASTVT(F)= *, i, ) LASTVT(P)= i, ) 第39頁/共53頁第四十頁，共53頁。41第40頁/共53頁第四十一頁，

18、共53頁。42練習(linx)：(1)計算計算(j sun)該文法的該文法的FIRSTVT和和LASTVT(2)計算計算(j sun)該文法的有限關(guān)系并產(chǎn)生優(yōu)先關(guān)系表該文法的有限關(guān)系并產(chǎn)生優(yōu)先關(guān)系表第41頁/共53頁第四十二頁，共53頁。v主要題型：所有主要題型：所有(suyu)題型題型v中間代碼表示中間代碼表示寫出表達式寫出表達式a:=b*c+b*d-e 的后綴的后綴(huzhu)表示表示、三元序列、四元序列。、三元序列、四元序列。練習：練習：寫出表達式寫出表達式A+B*(C-D)*N的后綴的后綴(huzhu)表示表示、三元序列、四元序列。、三元序列、四元序列。第42頁/共53頁第四十三頁，共53頁。主要主要(zhyo)(zhyo)題型：題型： 填空、選擇、判斷填空、選擇、判斷第43頁/共53頁第四十四頁，共53頁。主要主要(zhyo)(zhyo)題型：題型： 填空、選擇、判斷、分析填空、選擇、判斷、分析第44頁/共53頁第四十五頁，共53頁。46基本塊和控制流圖基本塊和控制流圖將下面程序劃分將下面程序劃分(hu fn)(hu fn)成基本塊并作成基本塊并作出其程序控制流圖出其程序控制流圖第45頁/共53頁第四十六頁，共53頁。47（1） Read(A,B)（2） F=1（3） C=A*A（4）