2014編譯原理期末復(fù)習(xí)資料完整版

1、1.2.給出語言a n b n a mb m | n,m 0的一個上下文無關(guān)文法。 解：GS : S ABA aAb |B- aBb|給出語言1 n 0 m 1 m0 n| n,m 0的一個上下文無關(guān)文法。3.解： GS : S- 1S0 | AA 0A1 | P48第6題(5)、(6).畫語法樹6、已知文法G:表達(dá)式 := 項 I 表達(dá)式+項項:= 因子 I 項*因子因子 :=( 表達(dá)式)(5) i+(i+i)(6)解：(5)語法樹：I ii+i*i(6)語法樹:4.(6分)U表達(dá)式A龍因表達(dá)式P48第13題直接短語等一個上下文無關(guān)文法生成句子abbaa的推導(dǎo)樹如下:13、b ba(3)求直

2、接短語解：直接短語有：a bP102例題6.1及其分析.(后加畫語法樹)例6.1設(shè)文法GS為：S aAcBeA bA AbB d對輸入串a(chǎn)bbcde#進(jìn)行分析，檢查該符號串是否是GS的句子。解：設(shè)一個先進(jìn)后出的符號符，并把句子左括號“#”號放入棧底，其分析過程如下:步驟符號棧輸入付號串動作(1)#abbcde#移進(jìn)(2)#abbcde#移進(jìn)(3)#abbcde#歸約(A b)(4)#aAbcde#移進(jìn)(5)#aAbcde#歸約(A Ab)(6)#aAcde#移進(jìn)(7)#aAcde#移進(jìn)(8)#aAcde#歸約(B d)(9)#aAcBe#移進(jìn)(10)#aAcBe#歸約(S aAcBe)(11)

3、#S#接受語法樹如下:(b)計算分析題(60%)DFAf最簡1、正規(guī)式7 NFAfP72 第 1 題(1 )、(4);第一題1、構(gòu)造下列正規(guī)式相應(yīng)的DFADFA.（1）1（0|1）*101 解：先構(gòu)造NFA用子集法將NFA確定化01SAAAABABACABACAABZABZACAB除S, A外，重新命名其他狀態(tài)，令 AB為B、AC為C、ABZ為D，因為D含有Z （NFA的終態(tài)），所以 D為終態(tài)，因此有：01SAAABBCBCADDCB得到DFA如下所示:0C b(ab)*|bb)*ab 解：先構(gòu)造NFA1DP72 第 4 題（a）4、把下圖確定化和最小化a解：確定化：用子集法將NFA確定化最小

4、化：初始分劃得終態(tài)組A,B，非終態(tài)組Cn 0: A,B , C，對終態(tài)組進(jìn)行審查，判斷代替A,B、C，因此有：A和B是等價的，故這是最后的劃分。重新命名，以abAACCA即DFA最小化如下:7、給文法GS: St aA|bQA t aA|bB|bBt bD|aQ Qt aQ|bD|bDt bB|aAEt aB|bFFt bD|aE|bDFA。NFA :構(gòu)造相應(yīng)的最小的 解：先構(gòu)造abSAQAABZBZQDBQDQQDZDZABDAB將S、A、BZ、B、Q、DZ、D重新命名，分別用0、1、2、3、4、5、6表示。因為2、5中含有Z,所以它們?yōu)榻K態(tài)。因此有：ab014112246346445513

5、初始分劃得：終態(tài)組2,5,非終態(tài)組 0,1,3,46n 0: 2,5 , 0,1,3,4,6對 0,1,3,4,6進(jìn)行審查：1,4輸入b到達(dá) 2,5,而0,3,6輸入b到達(dá) 3,4,6,故得到新分劃 1,4, 0,3,60經(jīng)過b到達(dá) 2, 3,6經(jīng)過b到達(dá) 3,6,故得到新分劃 0, 3,6,1,4 , 2,5 , 3,6,D分別代替0 , 1,4 , 2,5 , 3,6,其中A為始態(tài)，C為終態(tài)，可得到最小 DFAn 1: 2,5 , 1,4 , 0,3,6 對 0,3,6進(jìn)行審查： n 3：得到最后劃分0, 重新命名，以A, B, C, 如下：=(,i(E) =+, (T) =(,i(T)

6、=*, =(,i2、自頂向下方法(一)設(shè)文法G(E):E7 E + T | TT7 T*F|FF7 i | ( E )判斷是否為LL(1)文法.構(gòu)造文法的預(yù)測分析表.解：詳見P93-96例題。(1)由于文法中含有左遞歸，所以必須先消除左遞歸，使文法變?yōu)?E7T EE 7 +TE| T7 FTT 7 *FT| 1 i 1( E)FIRST 集合如下:FIRSTFIRSTFIRSTFIRSTFOLLOW集合如下:FIRSTFOLLOVy E) =),#FOLLOVy E) =),#FOLLOy T) =+,),#FOLLOVy T) =+,),#SELECT集合如下： (EtTE ) =(,i (

7、Ef +TE) =+ (EJ| s ) =),# (TtFT) =(,i (Tt *FT ) =* (Tt| s ) = +,),# (Ft i ) =i (Ft ( E )=(FOLLOVy F) =+,*,),# 各產(chǎn)生式的SELECTSELECTSELECTSELECTSELECTSELECTSELECTi+*()#EtT EtT EEt +TET sT sTt FTt FTTT st *FTT sT sFt it ( E )SELECT由上可知有相同左部產(chǎn)生式的SELECT集合的交集為空，故文法是LL(1)文法。(2)構(gòu)造文法的預(yù)測分析表如下：(二)P101 6.(4)改寫下面文法為L

8、L(1)文法，井對每個 LL(1)文法構(gòu)造相應(yīng)的預(yù)測分析表。Sfi|(E)EfE+S|ES|S解：首先為各非終結(jié)符構(gòu)造集與FOWOW熱 但因為產(chǎn)生式-+Sl-SlJ存在左遞歸. 故第一步先消除之.寫為：EtSE此時產(chǎn)生式已無左遞歸.可以開始寫出EWW集與FOLLOW弟了.F/lS7XS)=(i.(=剛W7WfZmF)=+, -t e)FOLLOW(S)=+,- #F0Z3W( (由此可以寫出預(yù)測分析表”rIC)+ -#sC)SEE FhJ-$F3、自底向上方法已知文法G(E):0 S t e1Et E + T23Tt T * F45Ft ( E )(1)證明該文法是SLR(1)文法Et tTt

9、 FFt i輸入串出錯的位置。(2)若已給出下面的SLR(1)分析表，試分析句子(i + ( * i )#狀態(tài)ACTIONGOTOi+*()#ETF0S5S41231sacc2r 2S223r44r 444SS4823566r 666S5S4937S5S4108S6S1191Sr 111033r 331155r 553、解：(1):先分析LR(0)項目:la：EE-* E4-T Ei TTT*F Ti F Ff (E)Ff * iIll SJE- EfE +TJI捫 Tf F(TI4； F-*( E i E+T Ei TTf-T*FTfF Ff CE Fi+Ifii Ef E+ * TTi T

10、*FTi F(E)切 F-*CE Ef E +TIll； Ff CE I薩 EfE+丁- _Tf T *FI護(hù) Tf T F */?! TfT* * F F+(E Ffi由上可見:IIS- E, Ef E.+T12E T# T-* T,+ F19L E+T, T-*K*FI 1 ,I 2 ,I 9 因為：對對對存在移進(jìn)一歸約沖突.分析FOLLOW 集:I1I2I9FOLLOW( S )= # n + =FOLLOW(E)= +, #, ) n * = FOLLOW(E)= +, #, ) n * =所以是SLR(1)文法。(2):STE PSX(i + ( * i ) #actio ngoto

11、10#(i + ( * i ) #S4204# (i + ( * i ) #S53045# (i+ ( * i ) #r 634043# (F+ ( * i ) #r425042# (T+ ( * i ) #r 286048# (E+ ( * i ) #S670486# (E+(* i ) #S4804864# (E+ (* i ) #errorthen while x*y3 do x:=x相應(yīng)的三地址代碼.-a*b else4、(一)給出語句 if a+b b+c*d while b+c*d10 do b:=b-(x*y+5)(1)t1=a+b(12)goto (6)(2)t2=c*d(13

12、)goto (23)(3)t3=b+t2(14)t7=c*d(4)if t1t3 goto (6)(15)t8=b+t7(5)goto (14)(16)if t810 goto (18)(6)t4=x*y(17)goto (23)if t43 goto (9)(18)t9=x*y(8)goto (13)(19)t10=t9+5(9)t5=a*b(20)t11=b-t10(10)t6=x-t5(21)b=t11(11)x=t6(22)goto (14)(23)(二)Whilea 0 V b 0 then a：= a- 1else b：= b + 1End;翻譯成四元式序列解：.(10 分)a,

13、0,(j ,(j，(j , a , 0,(j,(- , a, 1,(:= , T2 ,(j,(+ , b , 1,T3)(:= , T3 , , b)(j, , ,1)(15)5)3),5)15)T1),X)9)12)T2),a),1)5、（一）設(shè)有基本塊（10分）T1：=2T2：=10/ T1T3：=S- RT4：=S+ RA:B:T5：=A=S+ RT6：B:(1)=T3 * T 5=16畫出DAG圖；假設(shè)基本塊出口時只有A, B還被引用，請寫出優(yōu)化后的四元序列。5( 一)、解：(1)DAG:(3分)(2) 優(yōu)化后的四元式T3：=S RT4：=S+ RA:=5*T4B:=T3+ T4(二)P255-257 DAG 圖例試構(gòu)造以下基本塊 G的DAG(1)(8)(9)T0：= 3.14Ti：= 2* ToT2：A:B:T3：T4：T5：T6：=R+r=2* To=R+r=T3 * T 4=R-r=T5 *T6(1)解:B:if B=10 goto (1)畫出DAG圖；假設(shè)基本塊出口時只有 A, B還被引用，請