編譯課后習(xí)題答.pdf

習(xí)題解答 第2章 上下文無關(guān)文法 西北大學(xué)軟件工程研究所 龔曉慶第 139頁2010-06-22 6. 令文法G6為 N D|ND D 0|1|2|3|4|5|6|7|8|9 （1）G6的語言L(G6)是什么？ （2）給出句子0127、34和568的最左推導(dǎo)和最右推導(dǎo) 解答 （1）G6的語言是由09這10個(gè)數(shù)字組成的字符串（1）G6的語言是由09這10個(gè)數(shù)字組成的字符串 （2）最左推導(dǎo) N=ND =NDD =DDDD =0DDD =01DD =012D =0127N=ND =NDD =DDDD =0DDD =01DD =012D =0127 N =ND =DD =3D =4D N =ND =NDD =DDD =5DD =56D =568 5 56 568 最右推導(dǎo) N =ND =N7 =ND7 =N27 =ND27 =N127 =D127 =0127 N =ND =N4 =D4 =34 N =ND =N8 =ND8 =N68 =D68 =568 西北大學(xué)軟件工程研究所 龔曉慶第 239頁2010-06-22 7 寫個(gè)文法使其語言是奇數(shù)集且每個(gè)奇數(shù)不以0開頭7.寫一個(gè)文法，使其語言是奇數(shù)集，且每個(gè)奇數(shù)不以0開頭 解答 ?分析結(jié)構(gòu) ?D代表單個(gè)奇數(shù)，C代表非0數(shù)字，A代表所有數(shù)字，B代表任意數(shù)字D代表單個(gè)奇數(shù)，C代表非0數(shù)字，A代表所有數(shù)字，B代表任意數(shù)字 串 ?G(S)：S D | CD |CBDG(S)：S | C |C D 1|3|5|7|9 C 2|4|6|8|DC 2|4|6|8|D A 0|C B BA | A 西北大學(xué)軟件工程研究所 龔曉慶第 339頁2010-06-22 8.令文法為 E T | E+T | E-T T F | T*F |T/F F (E) | i E | (1)給出i+i*i、i*(i+i)的最左推導(dǎo)和最右推導(dǎo) (2)給出i+i+i、i+i*i、i-i-i的語法樹 解答 E ET+ 解答 （1）最左推導(dǎo) E=E+T =T+T =F+T =i+T =i+T*F ET + F F iT =i+F*F =i+i*F =i+i*i E =T =T*F =F*F =i*F =i*(E) =i*(E+T) F i iT F =i*(T+T)=i*(F+T) =i*(i+T) =i*(i+F) =i*(i+i) 最右推導(dǎo) i E E =E+T =E+T*F =E+T*i =E+F*i =E+i*i =T+i*i =F+i*i =i*i+i ET + TF*T E =T =T*F =T*(E) =T*(E+T) =T*(E+F) =T*(E+i) =T*(T+i) =T*(F+i) =T*(i*i) =F*(i*i) F F i =i*(i+i) （2）語法樹如圖 i i 西北大學(xué)軟件工程研究所 龔曉慶第 439頁2010-06-22 9. 證明下面的文法是二義的： S iSeS | iS | iS iSeS | iS | i 解答 考慮句子iiiei，存在如下兩個(gè)最右推導(dǎo)：考慮句子iiiei，存在如下兩個(gè)最右推導(dǎo)： S = iSeS =iSei =iiSei =iiiei S =iS = iiSeS = iiSei = iiieiS iS iiSeS iiSei iiiei 由此，該文法是二義的 10 把下面的文法改寫為無二義的10. 把下面的文法改寫為無二義的： S SS | (S) | ( ) ?思路：S SS 是產(chǎn)生二義性的根源將其變?yōu)榈葍r(jià)的遞歸結(jié)構(gòu)?思路：S SS 是產(chǎn)生二義性的根源，將其變?yōu)榈葍r(jià)的遞歸結(jié)構(gòu) 解答 將文法改造成G(S)：將文法改造成G(S)： S TS | T T (S) | ( )(S) | ( ) 西北大學(xué)軟件工程研究所 龔曉慶第 539頁2010-06-22 11. 給出下面語言的相應(yīng)文法 i L1 anbnci| n 1, i 0 L2 aibncn| n 1, i 0 L3 anbnambm| n ,m0 3 L4 1n0m1m0n| n ,m0 解答解答 L1的文法：SAC A aAb | abC cC | L2的文法：SAB A aA | B bBc | bc |L3的文法：SAB A aAb | B aBb | L4的文法：S 1S0 | A A 0A1 | 西北大學(xué)軟件工程研究所 龔曉慶第 639頁2010-06-22 習(xí)題解答 第3章 詞法分析 西北大學(xué)軟件工程研究所 龔曉慶第 739頁2010-06-22 7. 構(gòu)造下列正規(guī)式相應(yīng)的DFA構(gòu)造下列規(guī)式相應(yīng)的 1(0|1)*101 解答解答 ?第一步：根據(jù)正規(guī)式構(gòu)造NFA如圖 ?第二步：NFA確定化，得到狀態(tài)轉(zhuǎn)換矩陣和相應(yīng)DFA如圖 II0I1II0I1 01 111,2 1,21,31,2 1,311,2,4 1 2 41 31 21,2,41,31,2 西北大學(xué)軟件工程研究所 龔曉慶第 839頁2010-06-22 8. 給出下面正規(guī)表達(dá)式 串（1）以01結(jié)尾的二進(jìn)制數(shù)串 （2）能被5整除的十進(jìn)制整數(shù) （3）包含奇數(shù)個(gè)1或奇數(shù)個(gè)0的二進(jìn)制數(shù)串 解答 (0|1)*01( | ) (1|2|3|4|5|6|7|8|9) (0|1|2|3|4|5|6|7|8|9)*(0|5) | 0 | 5 0* 1( 0 | 10*1 )* | 1* 0 ( 1 | 01*0 )* (|)|(|) 9. 對下面的情況給出DFA及正規(guī)式 （1）0,1上含有子串010的所有串 （2） 0,1上不含子串010的所有串 解答 (0|1)* 010 (0|1)* 1* (0 | 111* )* 1* 西北大學(xué)軟件工程研究所 龔曉慶第 939頁2010-06-22 12. 將圖3.18的(a)和(b)分別確定化和最小化 解答 (a)確定化得到狀態(tài)轉(zhuǎn)換矩陣如表 (b)首先將狀態(tài)劃分為0,12,3,4,5； 有0,1a = 1 0,1b = 2,4 ( )確定化得到狀轉(zhuǎn)換矩陣如表 DFA如圖 2,3,4,5a = 1,3,0,5 2,3,4,5b = 2,3,4,5IIaIb 所以可以進(jìn)一步劃分為0,1 2,4 3,5; 有0,1a = 1 0,1b = 2,4 00,11 0,10,11 10 2,4a = 1,0 2,4b = 3,5 3,5a = 3,5 3,5b = 2,4 10 因此最后劃分結(jié)果為0,1 2,4 3,5; DFA如圖 西北大學(xué)軟件工程研究所 龔曉慶第 1039頁2010-06-22 14. 構(gòu)造一個(gè)DFA，它接受=0,1上所有滿足如下條件的字符串： 每個(gè)1都有0直接跟在右邊每個(gè)1都有0直接跟在右邊。 解答 構(gòu)造相應(yīng)的正規(guī)式為 (0|10)* 構(gòu)造NFA如右圖 確定化得到狀態(tài)轉(zhuǎn)換矩陣和DFA如下 最小化DFA II0I1 0,1,31,32 , , , 1,31,32 21 321,3 西北大學(xué)軟件工程研究所 龔曉慶第 1139頁2010-06-22 15. 給定右線性文法G， S 0S | 1S | 1A | 0B A 1C | 1 B 0C | 0 C 0C | 1C | 0 | 1 求出一個(gè)與G等價(jià)的左線性文法 解答 文法G對應(yīng)的FA如圖 根據(jù)FA，構(gòu)造左線性文法為 |F C0 | C1 | A1 | B0 A S1 | 1 B S0 | 0 C A1 | B0 |C0 |C1 S S0 | S1 | 0 | 1 西北大學(xué)軟件工程研究所 龔曉慶第 1239頁2010-06-22 習(xí)題解答 第4章 自上而下語法分析 西北大學(xué)軟件工程研究所 龔曉慶第 1339頁2010-06-22 1. 考慮下面的文法： TTTS a | | (T) T T,S | S 消去左遞歸。改寫后的文法是否為LL(1)的？給出預(yù)測分析表 解答解答 消除直接左遞歸，得到G(S) S a | | (T)T ST FIRSTFOLLOW Sa (# ， ) S a | | (T) T ST T ,ST | 計(jì)算每個(gè)非終結(jié)符的FIRST和FOLLOW集合 Ta () T， ) 計(jì)算每個(gè)非終結(jié)符的FIRST和FOLLOW集合 構(gòu)造預(yù)測分析表 因?yàn)楸碇袩o多重定義項(xiàng) 所以文法G是LL(1)的因?yàn)楸碇袩o多重定義項(xiàng),所以文法G 是LL(1)的 a， ，()# SS aS S (T) TT ST T ST T ST TTSTTT ,ST 西北大學(xué)軟件工程研究所 龔曉慶第 1439頁2010-06-22 2. 對下面的文法G TTTTTE TE E +E | T FT T T | F PF F *F | P (E) | a | b | (1)計(jì)算每個(gè)非終結(jié)符的FIRST和FOLLOW集合 FIRSTFOLLOW E( a b # ) E# ) (2)證明這個(gè)文法是LL(1)的 (3)構(gòu)造預(yù)測分析表 解答（1）非終結(jié)符的FIRST和FOLLOW集合 E+ # ) T( a b + ) # T( a b + ) # 解答（1）非終結(jié)符的FIRST和FOLLOW集合 （2）構(gòu)造預(yù)測分析表如下: 因?yàn)楸碇袩o多重定義項(xiàng)，所以文法是LL(1)的 () F( a b ( a b + ) # F* ( a b + ) # P( a b * ( a b + ) # 因?yàn)楸碇袩o多重定義項(xiàng)，所以文法是LL(1)的 （3）分析表如（2）所示 P( a b * ( a b + ) # ab()+*# ETETETETE E+E TFTFTFTFTTFTFTFTFT TTTTT FPFPFPFPF F*F Pab(E) 西北大學(xué)軟件工程研究所 龔曉慶第 1539頁2010-06-22 3. 下面文法中，哪些是LL(1)文法，說明理由 (1) S ABc A a |B b | (2) S Ab A a | B |B b | (3) S ABBA A a |B b | (4) S aSe | B B bBe |C C cCe | d 解答 文法不含左遞歸；first(S) = a,b,c followS = # first(A) = a, follow(A) = b,c first(B) = b , f ll(B) 可見滿足LL(1)文法的三個(gè)條件是LL(1)文法follow(B) = c；可見滿足LL(1)文法的三個(gè)條件，是LL(1)文法 文法不含左遞歸；first(S) = a,b followS = # first(A) = a b follow(A) = b first(B) = b follow(B) = a,b, follow(A) = b first(B) = b , follow(B) = b；考慮A的產(chǎn)生式， first(A) follow(A) = b ，所 以文法不是LL(1)的。 不是LL(1)文法，理由略 是LL(1)文法，理由略 西北大學(xué)軟件工程研究所 龔曉慶第 1639頁2010-06-22 4. 對下面文法 TTExpr Expr | (Expr) | Var ExprTail ExprTail Expr | Var id VarTail VarTail (Expr) | (1)構(gòu)造LL(1)分析表 (2)給出句子idid(id)的分析過程 解答 FIRSTFOLLOW (1)計(jì)算每個(gè)非終結(jié)符的FIRST和FOLLOW集 合 構(gòu)造分析表如 Expr，(，id#，) ExprTail，#，) Varid) # 構(gòu)造預(yù)測分析表如下 (2)分析過程略 Varid, ) ,# VarTail(，, ) ,# id()# ExprExprVar ExprTail(Expr) ExprTailExpr Varid VarTail VarTail(Expr)VarTail(Expr) 西北大學(xué)軟件工程研究所 龔曉慶第 1739頁2010-06-22 習(xí)題解答 第5章 自下而上語法分析 西北大學(xué)軟件工程研究所 龔曉慶第 1839頁2010-06-22 1.令文法G1為 E E+T | T T T*F | F F (E) | i令文法為|( ) | 證明E+T*F是它的一個(gè)句型，指出這個(gè)句型的所有短語、直接短語 和句柄。和句柄。 解答： E+T*F是文法G1的句型，因?yàn)榇嬖谌缦聢D所示的語法樹 短語T*F 和 E+T*F短語：T*F 和 E+T*F 直接短語：T*FE 句柄：T*F ET+ TF*TF 西北大學(xué)軟件工程研究所 龔曉慶第 1939頁2010-06-22 3. 考慮表格文法G2: S a|(T) T T,S|S （1）計(jì)算G2的FIRSTVT和LASTVT（1）計(jì)算G2的FIRSTVT和LASTVT （2）計(jì)算G2的優(yōu)先關(guān)系，G2是算符優(yōu)先文法嗎？ （3）計(jì)算G2的優(yōu)先函數(shù) （4）給出輸入串(a,(a,a)的算符優(yōu)先分析過程。 解答 （1）FIRSTVT(S) ( FIRSTVT(T) ( （1）FIRSTVT(S) = a ( FIRSTVT(T) = , a ( LASTVT(S) = a ) LASTVT(T) = , a ) （2）G2的優(yōu)先關(guān)系表如右 a(),# a 因?yàn)楸碇袩o多重定義項(xiàng) 所以G2是算符優(yōu)先文法 a ( , a()# #= a(),# f662642 g777232 a(), g f44244 g55523 西北大學(xué)軟件工程研究所 龔曉慶第 2039頁2010-06-22 5.考慮文法S AS | b A SA | a5.考慮文法S AS | b A SA | a (1)列出文法的所有LR(0)項(xiàng)目 (2) 構(gòu)造這個(gè)文法的LR(0)項(xiàng)集規(guī)范族及識(shí)別活前綴的DFA(2) 構(gòu)造這個(gè)文法的LR(0)項(xiàng)目集規(guī)范族及識(shí)別活前綴的DFA (3)這個(gè)文法是SLR的嗎？若是，構(gòu)造SLR分析表 (4)這個(gè)文法是LALR或LR(1)的嗎？ 解答解答 （1）0. SS 1. SS 2. S AS 3. S AS 4. S AS 5. S b6. S b 7. A SA 8. A SA 9. A SA 10. A a 11. A a （2）識(shí)別活前綴的DFA如下頁圖 該DFA的狀態(tài)構(gòu)成了LR(0)項(xiàng)目集規(guī)范族 西北大學(xué)軟件工程研究所 龔曉慶第 2139頁2010-06-22 解答（續(xù)） （3）該文法不是SLR文法： I3，I6，I7有移進(jìn)歸約 沖突 I3：FOLLOW(S)=# 不包I3：FOLLOW(S) #,不包 含a,b OO (S) #bI7: FOLLOW(S)=#, a, b; 移進(jìn)歸約沖突無法消解 I6：FOLLOW(A) = a,b;移 進(jìn)歸約沖突無法消解 所以文法不是SLR文法。 西北大學(xué)軟件工程研究所 龔曉慶第 2239頁2010-06-22 （4）構(gòu)造LR(1)項(xiàng)目集規(guī) 范族如圖范族如圖 對于狀態(tài)5，包含項(xiàng)目 ASA，a/b，所以 遇到a或b時(shí)，應(yīng)該用A SA歸約。 又因?yàn)闋顟B(tài)5包含項(xiàng)目又因?yàn)闋顟B(tài)5包含項(xiàng)目 Aa，a/b，所以 遇到a時(shí)應(yīng)該移進(jìn) 因此存在“移進(jìn)歸約” 沖突，文法不是LR(1) 的的； 因此也不是LALR的。 西北大學(xué)軟件工程研究所 龔曉慶第 2339頁2010-06-22 6. 構(gòu)造下面文法的LALR項(xiàng)目集和分析表 TTTTE E+T | T T TF | F F F* | (E) |a |b | 解答： 拓廣文法為G(E)，略。文法的LR(1)項(xiàng)目集為： I0= E E, # E E + T, #/+ E T, #/+ T TF, #/+/ (/a/b/ T F, #/+/ (/a/b/ F F*, #/+/(/a/b/* F ( E ), #/+/(/a/b/* F a, #/+/(/a/b/* F b, #/+/(/a/b/* F , #/+/(/a/b/* I1= GO(I0,E)=E E, # E E + T, #/+ I1 GO(I0,E) E E , # E E T, #/ I2= GO(I0,T)=E T , #/+ T TF, #/+/ (/a/b/ F F*, #/+/(/a/b/* F ( E ), #/+/(/a/b/* F a, #/+/(/a/b/* F b, #/+/(/a/b/* F , #/+/(/a/b/* I3= GO(I0,F)= T F, #/+/ (/a/b/ F F *, #/+/(/a/b/* I4= GO(I0,()= F ( E ), #/+/(/a/b/* E E + T, )/+ E T, )/+ T TF, )/+/ (/a/b/ T F, )/+/ (/a/b/ F F*, )/+/(/a/b/* F ( E ), )/+/(/a/b/*T TF, )/ / (/a/b/ T F, )/ / (/a/b/ F F , )/ /(/a/b/ / F ( E ), )/ /(/a/b/ / F a, )/+/(/a/b/* F b, )/+/(/a/b/* F , )/+/(/a/b/* I5= GO(I0,a)= F a, #/+/(/a/b/* I6= GO(I0,b)= F b, #/+/(/a/b/* I7= GO(I0,)= F , #/+/(/a/b/* 西北大學(xué)軟件工程研究所 龔曉慶第 2439頁2010-06-22 I8= GO(I1,+)=E E+ T, #/+ T TF, #/+/ (/a/b/ T F, #/+/ (/a/b/ F F*, #/+/(/a/b/* F ( E ), #/+/(/a/b/* F a, #/+/(/a/b/* F b, #/+/(/a/b/* F , #/+/(/a/b/* I9= GO(I2,F)=T TF, #/+/ (/a/b/ F F*, #/+/(/a/b/* GO(I9,*) = I10 GO(I2()= I4GO(I2a)= I5GO(I2b)= I6GO(I2)= I7GO(I2,() I4 GO(I2,a) I5 GO(I2,b) I6 GO(I2, ) I7 I10= GO(I3,*)= F F* , #/+/(/a/b/* I11= GO(I4,E)=F (E ), #/+/(/a/b/* E E + T, )/+ I12= GO(I4,T)=E T , )/+ T TF, )/+/ (/a/b/ F F*, )/+/(/a/b/* F ( E ), )/+/(/a/b/* F a, )/+/(/a/b/* F b, )/+/(/a/b/* F , )/+/(/a/b/* I2同心 I13= GO(I4,F)= T F, )/+/ (/a/b/ F F *, )/+/(/a/b/* I3同心I13 GO(I4,F) T F , )/ / (/a/b/ F F, )/ /(/a/b/ / I3同心 I14= GO(I4,()= F ( E ), )/+/(/a/b/* E E + T, )/+ E T, )/+ T TF, )/+/ (/a/b/ T F, )/+/ (/a/b/ F F*, )/+/(/a/b/* F ( E ), )/+/(/a/b/* F a, )/+/(/a/b/* F b, )/+/(/a/b/* F , )/+/(/a/b/* I4同心 I15= GO(I4,a)= F a, )/+/(/a/b/* I5同心 I16= GO(I4,b)= F b, )/+/(/a/b/* I6同心I16 GO(I4,b) F b , )/ /(/a/b/ / I6同心 I17= GO(I4,)= F , )/+/(/a/b/* I7同心 I18= GO(I8,T)=E E+T, #/+ T T F, #/+/ (/a/b/ F F*, #/+/(/a/b/* F ( E ), #/+/(/a/b/* F a #/+/(/a/b/* F b #/+/(/a/b/* F #/+/(/a/b/* #/+/(/a/b/ / F a, #/+/(/a/b/ / F b, #/+/(/a/b/ / F , #/+/(/a/b/ / GO(I8,F) = I3GO(I8,()= I4 GO(I8,a)= I5 GO(I8,b)= I6 GO(I8,)= I7 西北大學(xué)軟件工程研究所 龔曉慶第 2539頁2010-06-22 I19= GO(I11,)=F (E), #/+/(/a/b/* I20= GO(I11,+)=E E+ T, )/+ T TF, )/+/ (/a/b/ T F, )/+/ (/a/b/ F F*, )/+/(/a/b/* F ( E ), )/+/(/a/b/* F a, )/+/(/a/b/* F b, )/+/(/a/b/* F , )/+/(/a/b/* I8同心 I21= GO(I12F)=T TF )/+/ (/a/b/ F F*)/+/(/a/b/* I9同心GO(I21*) = I22I21 GO(I12,F) T TF , )/ / (/a/b/ F F , )/ /(/a/b/ / I9同心GO(I21, ) I22 GO(I12,()= I14 GO(I12,a)= I15 GO(I12,b)= I16 GO(I12,)= I17 I22= GO(I13,*)= F F* , )/+/(/a/b/* I10同心 I23= GO(I14,E)=F (E ), )/+/(/a/b/* E E + T, )/+ I11同心 GO(I23,+)= I20 GO(I14,T)= I12 GO(I14,F)= I13 GO(I14,()= I14 GO(I14,a)= I15 GO(I14,b)= I16 GO(I14,)= I17 GO(I18,F)= I9GO(I18,()= I4GO(I18,a)= I5GO(I18,b)= I6GO(I18,)= I7GO(I18,F) I9 GO(I18,() I4 GO(I18,a) I5 GO(I18,b) I6 GO(I18, ) I7 I24= GO(I20,T)=E E+T, )/+ T T F, )/+/ (/a/b/ F F*, )/+/(/a/b/* F ( E ), )/+/(/a/b/* F a, )/+/(/a/b/* F b, )/+/(/a/b/* F , )/+/(/a/b/* I18同心 GO(I20,F)= I13 GO(I20,()= I14 GO(I20,a)= I15 GO(I20,b)= I16 GO(I20,)= I17 I25= GO(I23,)=F (E), )/+/(/a/b/* I19 同心 GO(I24,F)= I21GO(I24,()= I14GO(I24,a)= I15GO(I24,b)= I16GO(I24,)= I17GO(I24,F) I21 GO(I24,() I14 GO(I24,a) I15 GO(I24,b) I16 GO(I24, ) I17 合并其中的合并其中的12組同心項(xiàng)目集后，得到組同心項(xiàng)目集后，得到LALR項(xiàng)目集（項(xiàng)目集（14個(gè)）個(gè)） 構(gòu)造構(gòu)造LALR分析表如下分析表如下構(gòu)造構(gòu)造LALR分析表如下分析表如下 西北大學(xué)軟件工程研究所 龔曉慶第 2639頁2010-06-22 ACTIONGOTO +*()ab#ETF 0s4s5s6s7123 1s8 acc 1s8 acc 2r2s4r2s5s6s7r29 3r4s10r4r4r4r4r4r43r4s10r4r4r4r4r4r4 4s4s5s6s71123 5r7r7r7r7r7r7r7r7 6r8r8r8r8r8r8r8r8 7r9r9r9r9r9r9r9r9 845671238s4s5s6s7123 9r310r3r3r3r3r3r3 10r5r5r5r5r5r5r5r510r5r5r5r5r5r5r5r5 11s8s10s13 12r1s4r1s5s6s7r19 13r6r6r6r6r6r6r6r6 西北大學(xué)軟件工程研究所 龔曉慶第 2739頁2010-06-22 7.證明下面文法是SLR(1)但不是LR(0)的。 SA A Ab | bBa BaAc | a |aAb 解答：文法的LR(0)項(xiàng)目集規(guī)范族如下： I0 = SA，A Ab， AbBa I1 = Go(I0,A) = SA，A Ab I2 = Go(I0,b) = AbBa， BaAc， B a， B aAb I3 =Go(I1,b) = A Ab I4 = Go(I2,B) = AbBa I5 = Go(I2,a) = BaAc， Ba ， Ba Ab， A Ab， AbBa I6 = Go(I4,a) = AbBa I7 = Go(I5 A) = BaAcBaA bA Ab Go(I5 b) = I2I7 = Go(I5,A) = BaA c ， BaA b ， A A b Go(I5,b) = I2 I8 = Go(I7,b) = BaAb ， A Ab I9 = Go(I7,c) = BaAc I1和I5中都存在移進(jìn)歸約沖突，I8中存在歸約歸約沖突 所以文法不是LR(0)的。 對I1，F(xiàn)OLLOW(S)=#，不包含b，沖突可解決； 對I5，F(xiàn)OLLOW(B)=a，不含b，沖突可解決； 對I8FOLLOW(A)=b c # FOLLOW(B)=a 二者不相交沖突可解決對I8， FOLLOW(A)=b,c,# FOLLOW(B)=a,二者不相交，沖突可解決 所以，文法是SLR(1)的。 西北大學(xué)軟件工程研究所 龔曉慶第 2839頁2010-06-22 8. 證明下面的文法是LL(1)的，但不是SLR(1)的 SAaAb | BbBa A B 解答因?yàn)?FIRST(AaAb) = a, FIRST(BbBa) =b 二者交集為空; FIRST(A)=FIRST(B) = ，F(xiàn)OLLOW(A)=FOLLOW(B) = a,b；A,B各自的 FIRST和FOLLOW集合不相交；所以該文法是LL(1)的。 構(gòu)造LR(0)項(xiàng)目集規(guī)范族如下： I0 = S S ，SAaAb， A ，SBbBa， B I1=Go(I0,S) = S S I2 = Go(I0 A) = SA aAbI2 = Go(I0,A) = SAaAb I3 Go(I0,B) = SBbBa I4 = Go(I2, a) = SAaAb， SAaAb， A I5 = Go(I3, b) = S BbBa ， S BbBa ， B I6 = Go(I4, A) SAaAb， SAaAb I7 Go(I5,B) = SBbBa， SB bBa 對I0：FOLLOW(A)=FOLLOW(B) = a b () I8 = Go(I6, b) SAaAb Go(I6,a) = I4 I9 Go(I7,a) = SBbBa Go(I7, b) = I5 對I0：FOLLOW(A)=FOLLOW(B) = a,b A 和B 的歸約歸約沖突無法消解，所以文法不是SLR的。 西北大學(xué)軟件工程研究所 龔曉慶第 2939頁2010-06-22 習(xí)題解答 第6章 屬性文法 西北大學(xué)軟件工程研究所 龔曉慶第 3039頁2010-06-22 7.下列文法由開始符號產(chǎn)生一個(gè)二進(jìn)制數(shù)，令綜合屬性val給出該數(shù) 的值： SL.L | L L LB | B B 0 | 1 試設(shè)計(jì)求S.val的屬性文法。 解答，屬性文法如下： 產(chǎn)產(chǎn)生式生式語義規(guī)則語義規(guī)則產(chǎn)產(chǎn)生式生式語義規(guī)則語義規(guī)則 SSprint (S.val) S L1L2S val := L1val + L2val / 2L2.lengthS L1.L2S.val := L1.val + L2.val / 2 g S L S.val := L.val L L BL val := L val*2 + B valL L1B L.val := L1.val 2 + B.val L.length := L1.length+1 L B L.val := B.val L.length := 1 B 0 B.val := 0 B 1 B.val := 1 西北大學(xué)軟件工程研究所 龔曉慶第 3139頁2010-06-22 補(bǔ)充題：已知文法G如下： SS h=4 S(L) | a L L,S|S (1)給出一個(gè)語法制導(dǎo)定義，輸出配對括號個(gè)數(shù) (2)給出句子(a,a),(a,(a,a)帶注釋的語法分析樹 S L()L.h=3 S.h 4 (3)寫一個(gè)翻譯方案，打印每個(gè)a的嵌套深度 解答 ，LS S.h=2L.h=1 解答 （1）引入屬性h，代表配對括號數(shù) 語法制導(dǎo)定義如下 L() L() S L h 0 S.h=1 S h 1 L.h=1 語法制導(dǎo)定義如下 產(chǎn)產(chǎn)生式語生式語義規(guī)則義規(guī)則 L() ，LS L() ，LS S L.h=0S.h=0 L.h=0 S h 0 L.h=0 L.h=0 S.h=1 產(chǎn)產(chǎn)義規(guī)則義規(guī)則 SSprint (S.h) S (L) S.h := L.h + 1 S a S a，LS S.h=0 S.h=0 L.h=0S.h=0 S aS.h := 0 L L1，S L.h := L1.h + S.h a aS S.h=0 L S L.h := S.h a 西北大學(xué)軟件工程研究所 龔曉慶第 3239頁2010-06-22 （3）為S、L引入屬性d，代表a的嵌套深度。翻譯方案如下代套 S S.d := 0; S S “(“ L.d := S.d +1; L“)“ S a print(S.d); L L1.d := L.d ; L1， S.d := L.d ; S L S.d := L.d ; S 西北大學(xué)軟件工程研究所 龔曉慶第 3339頁2010-06-22 習(xí)題解答 第7章 中間代碼生成 西北大學(xué)軟件工程研究所 龔曉慶第 3439頁2010-06-22 1. 給出下面表達(dá)式的逆波蘭式（后綴式） 解答 表達(dá)式逆波蘭式表達(dá)式逆波蘭式 a*(b+c)abc+* a+b*(c+d/e)abcde/+*+a+b (c+d/e)abcde/+ + -a+b*(-c+d)abcd+*+ not A or not (C or not D)A not CD not or not or (A and B) or (not C or D)AD and C not D or or (A or B)and (C or not D and E)AB or CD not E and or and if (x+y)*z = 0 then (a+b)c else