編譯原理及編譯程序構(gòu)造 部分課后答案(張莉楊海燕編著).

1、第一章練習(xí)12、典型的編譯程序可劃分為哪幾個主要的邏輯部分？各部分的主要功能是什么？典型的編譯程序具有7個邏輯部分：第二章練習(xí)2.24.試證明：A+ =AA*=A*A證： A*=A0A+，A+=A1A2An得：A*=A0A1A2An AA*=A（A0A1A2An）= AA0AA1AA2A An=AA2A3An +1= A+同理可得：A*A =(A0A1A2An)A=A0 AA1AA2AAnA= AA2A3An+1= A+因此： A+ =AA*=A*A練習(xí)2.31.設(shè)G標(biāo)識符的規(guī)則是 ：標(biāo)識符:=a|b|c|標(biāo)識符a|標(biāo)識符c|標(biāo)識符0|標(biāo)識符1試寫出VT和VN，并對下列符號串a(chǎn),ab0,a0c

2、01,0a,11,aaa給出可能的一些推導(dǎo)。解：VT =a,b,c,0,1， VN =標(biāo)識符(1) 不能推導(dǎo)出ab0,11,0a(2)標(biāo)識符=>a(3)標(biāo)識符=>標(biāo)識符1=>標(biāo)識符01=>標(biāo)識符c01=>標(biāo)識符0c01=> a0c01(4)標(biāo)識符=>標(biāo)識符a=>標(biāo)識符aa=>aaa2寫一文法，其語言是偶整數(shù)的集合解：G<偶整數(shù)>：<偶整數(shù)>:= <符號> <偶數(shù)字>| <符號><數(shù)字串><偶數(shù)字><符號> := + | |<數(shù)字串>:

3、= <數(shù)字串><數(shù)字>|<數(shù)字><數(shù)字> := <偶數(shù)字>| 1 | 3 | 5 | 7 | 9<偶數(shù)字> :=0 | 2 | 4 | 6 | 84. 設(shè)文法G的規(guī)則是：A:=b<A>| cc試證明：cc, bcc, bbcc, bbbccLG證：（1）A=>cc（2）A=>bA=>bcc（3）A=>bA=>bbA=>bbcc（4）A=>bA=>bbA=>bbbA=>bbbcc又cc, bcc, bbcc, bbbccVt*由語言定義，cc, bcc,

4、 bbcc, bbbccLG5 試對如下語言構(gòu)造相應(yīng)文法：（1） a(bn)a | n=0,1,2,3,其中左右圓括號為終結(jié)符。（2） （an）（bn） | n=1,2,3, 解：（1）文法GS：S:= a(B)aB:= bB |( 2 ) 文法GS：-錯了，兩個n不等S := (A)(B)A:= aA|aB:= bB|b7.對文法G3表達式表達式:=項|表達式+項|表達式-項項:=因子|項*因子|項/因子因子:=（表達式）| i列出句型表達式+項*因子的所有短語和簡單短語。<表達式> => <表達式> + <項>=> <表達式> +

5、 <項> * <因子>短語有：表達式+項*因子和項*因子簡單短語是：項*因子8 文法V:= aaV | bc的語言是什么？解：L（GV）= a2nbc | n=0,1,2,V aaV aaaaV . a2nbc (n 1)V bc (n=0)練習(xí)2.45.已知文法GE：E:=ET+ | TT:=TF* |FF:=FP |PP:=（E）| i有句型TF*PP+，問此句型的短語，簡單短語，和句柄是什么？解：此句型的短語有：TF*PP+，TF*，PP，P簡單短語有：TF*，P句柄是：TF*8.證明下面的文法G是二義的：S:= iSeS | iS | i證：由文法可知iiiei

6、是該文法的句子，又由文法可知iiiei有兩棵不同的語法樹。所以該文法是二義性文法。第三章練習(xí)3.11畫出下述文法的狀態(tài)圖Z:=BeB:=AfA:= e |Ae使用該狀態(tài)圖檢查下列句子是否是該文法的合法句子f，eeff，eefe2、有下列狀態(tài)圖，其中S為初態(tài)，Z為終態(tài)。（1） 寫出相應(yīng)的正則文法：（2） 寫出該文法的V，Vn和Vt；（3） 該文法確定的語言是什么？解：（1） ZA1|0 AA0|0（2） V=A,Z,0,1Vn=A,ZVt=0,1（3） L (GS)= 0或0n1,n1L (GS)= 0|00*1練習(xí)3.21令A(yù)，B，C是任意正則表達式，證明以下關(guān)系成立：A|A=A（A*）*=

7、A*A*=| AA*（AB）*A = A（BA）*（A|B）* =（A*B*）*=（A*|B*）證明：AAxxL(A)或xL(A)xxL(A)A（A*）*（A*）0（A*）1（A*）2（A*）n(A0A 1A2An) (A1)A0A 1A2AnA*AA*所表示的語言是:LA·LA*LA0LA（LA0LA1LA2）LA0LA1LA2LA*故AA*A*(LALB)*LA=(L(A)LBLALBLALBLALBLALBLALB) LA=LALALBLALALBLALBLALALBLALBLALBLA= LA(LBLALBLALBLA)= LA(LBLA)(AB)*A=A(BA)*三個表達式

8、所描述的語言都是LALB中任意組合（A|B）*=(A*B*)=(A*|B*)*2. 構(gòu)造下列正則表達式相應(yīng)的DFA（1） 1（0|1）*|0（2） 1（1010*|1（010）*1）*04. 5. 構(gòu)造一DFA，它接受=0,1上所有滿足如下條件的字符串：每個1都有0直接跟在右邊。第四章練習(xí)4.22. 有文法GA: A:= (B) | dBeB:= c | Bc試設(shè)計自頂向下的語法分析程序。解：消除左遞歸：A:= (B) | dBeB:= ccprocedure B;if CLASS = 'c' thenbeginnextsym;while CLASS = 'c'

9、 do nextsym;end;elseerror; program G;beginnextsym;A;end;procedure A;if CLASS = '(' thenbeginnextsym;B;if CLASS = ')' thennextsym；elseerrorend；elseif CLASS = 'd' thenbeginnextsym;B;if CLASS = 'e' thennextsym;elseerror;end;elseerror;3. 有文法GZ: Z:= AcB| BdA:=AaB|cB:= aA|a

10、(1) 試求各選擇（候選式）的FIRST集合；(2) 該文法的自頂向下的語法分析程序是否要編成遞歸子程序？為什么？(3) 試用遞歸下降分析法設(shè)計其語法分析程序。解: (1) FIRST(B)=a FIRST(A)=c FIRST(Z)=a,cFIRST(AcB)=c FIRST(Bd) =aFIRST(AaB)=c FIRST(c) =cFIRST(aA) =a FIRST(a) =a(2) 要編成遞歸子程序，因為文法具有遞歸性(3) 改寫文法：Z:= AcB| BdA:= caBB:= aA 練習(xí)4.31 . 對下面的文法GE: E TE E' + E |T FT'T'

11、; T |F PF'F' * F' |P (E)| a | b | (1) 計算這個文法的每個非終結(jié)符號的FIRST和FOLLOW集合(2) 證明這個文法是LL(1)的(3) 構(gòu)造它的預(yù)測分析表解：(1)FIRST( E ) = (, a, b, FOLLOW( E ) = #, ) FIRST( E' ) = +,FOLLOW( E' ) = #, )FIRST( T ) = (, a, b, FOLLOW( T ) = #, ),+FIRST( T' ) = (, a, b, ,FOLLOW( T') = #, ),+ FIRST(

12、F ) = (, a, b, FOLLOW( F ) = (, a, b, ,#, ),+FIRST( F' ) = *,FOLLOW( F' ) = (, a, b, ,#, ),+FIRST( P ) = (, a, b, FOLLOW( P ) = *,(, a, b, ,#, ),+ (2) 證明：FIRST( +E) FIRST() = + = FIRST( +E) FOLLOW( E' ) +#, ) = FIRST( T ) FIRST() (, a, b, = FIRST( T ) FOLLOW( T') = (, a, b, #, ),+ =

13、FIRST( *F' ) FIRST() * = FIRST( *F' ) FOLLOW( F' ) = * (, a, b, ,#, ),+ = FIRST( (E) ) FIRST(a) FIRST(b) FIRST()= 所以此文法是LL(1)文法2. 對于文法GS：S aABbcd | A ASd | B SAh | eC | C Sf | Cg | D aBD | （1) 對每一個非終結(jié)符號，構(gòu)造FOLLOW集；（2) 對每一產(chǎn)生式的各侯選式，構(gòu)造FIRST集；（3) 指出此文法是否為LL（1）文法。解：（1）FIRST(S) = a, FIRST(A) =

14、a,d, FIRST(B) = a,d,h,e, FIRST(C) = a,f,g, FIRST(D) = a, FOLLOW(S) = d,a,f,h#FOLLOW(A) = a,h,e,b,dFOLLOW(B) = b,aFOLLOW(C) = g,b,a(2) FIRST(aABbcd) = aFIRST() = FIRST(ASd) = a,dFIRST() = FIRST(SAh) = a,d,hFIRST(eC) = eFIRST() = FIRST(Sf) = a,fFIRST(Cg) = a,f,gFIRST() = (3) 不是LL(1)文法，因FIRST(Sf) FIRST

15、(Cg) = a,f a,f,g或FOLLOW(S) FIRST(aABbcd)d,a,f,h# a或FOLLOW(A) FIRST(ASd) a,h,e,b,d a,d 或FOLLOW(B) FIRST(SAh) a,b a,d,h 或FOLLOW(C) FIRST(Sf) g,a,b a,f 或FOLLOW(C) FIRST(Cg) g,a,b a,f ,g6. 一個文法G是LL(1)的必要與充分條件是什么？試證明之。充要條件是：對于G的每一個非終結(jié)符A的任何兩條不同規(guī)則A:= |, 有：(1) FIRST()FIRST()= (2) 假若=*=>, 則FIRST()FOLLOW(A

16、)= 證明：充分性：條件（證明：充分性：條件（1）（2）成立反證：若分析表中存在多重入口，即）成立反證：若分析表中存在多重入口，即MB,a = B:= 1, B:= 2 ,表明FIRST(1)FIRST(2) 或MB,a = B:= 1, B:= 2，其中2= 或2=+=> 表明FIRST(1)FOLLOW(B) 與條件（1）（2）矛盾。必要性：文法是）矛盾。必要性：文法是LL(1)文法，即分析表中不含多重入口若條件文法，即分析表中不含多重入口若條件(1)不成立，即存在某非終結(jié)符B的兩條規(guī)則B:= 1|2，F(xiàn)IRST(1)FIRST(2) 則對任意的aFIRST(1)FIRST(2)，有

17、MB,a = B:= 1, B:= 2,矛盾若條件（矛盾若條件（2）不成立，即存在某非終結(jié)符B的兩條規(guī)則B:= 1|2，2=*=> 有FIRST(1)FOLLOW(B) 則對任意的aFIRST(1)FOLLOW (B)，有MB,a = B:= 1, B:= 2,矛盾練習(xí)4.44.有文法GE: E:= E+T | TT:= T*F | FF:= (E) | i列出下述句型的短語和素短語：E、T、i、T*F、F*F、i*F 、F* i、F+F+F練習(xí)4.51. 考慮具有下列規(guī)則的文法SE# ET|E+T TP| PT PF|P*F Fi|(E)(a) 下列句型的最右推導(dǎo)步驟中，其活前綴的集合

18、是什么？(1) E+i*i#(2) E+P(ii)(b)為下列輸入串構(gòu)造最右推導(dǎo)的逆：(1) i+i*i#(2) i+i(i+i)#解：(a)（1）句柄為i，所以活前綴集合為：E，E，Ei（2）句柄為i，所以活前綴集合為：E，E+, E+P, E+P, E+P(, E+P(I(b) （1）i+i*i# <=F+i*i# <=P + i*i# <=T+i*i# <=E+i*i# <=E+F*i# <=E+P*i# <=E+P*F# <=E+P# <=E+T# <=E# <= S 練習(xí)4.61. 給定具有如下產(chǎn)生式的文法SE# EE

19、-T|T TF|FT Fi|(E)試求下列活前綴的有效項目集：(a) F (b) E-( (c) E-T解：(a)E T.F TF.T T.FT F.i F.(E) (b)E-(F (.E), E .E-T, E .T, T .F, T .FT, T .i, T .(E)(c)E - TE E-T. 練習(xí)4.71. 給定下列產(chǎn)生式的文法：SE ET|E+T TP|T*P PF|FP Fi|(E) (1) 為該文法構(gòu)造SLR（1）分析表。第五章練習(xí)53. 如下非分程序結(jié)構(gòu)語言的程序段，畫出編譯該程序段時將生成的有序符號表。BLOCKREAL X,Y,Z1,Z2,Z3;INTEGER I,J,K,

20、LASTI;STRING LIST-OF-NAMES;LOGICAL ENTRY-ON EXIT-OFF;ARRAY REAL VAL(20);ARRAY INTEGER MIN-VAL-IND(20);END OF BLOCK;5. 畫出下面的分程序結(jié)構(gòu)的程序段當(dāng)程序段3和4的編譯即將完成以前的棧式符號表的圖形(包括有效部分和失效部分）。第六章練習(xí)6.22 考慮下面的類ALGOL程序，畫出當(dāng)程序執(zhí)行到和時，運行棧內(nèi)容的圖像。第七章練習(xí)72. 將下面的語句 A:= (B+C) E+(B+C)*F 轉(zhuǎn)換成三元式，間接三元式和四元式序列。第九章練習(xí)9.11.試分別構(gòu)造一個符號串翻譯文法，它將由一般中綴表達式文法所定義的中綴表達式翻譯成波蘭前綴表達式和波蘭后綴表達式.解：翻譯為波蘭前綴表達式的文法為：E->+E+TE->T T->*T*FT->FF->(E)F->ii翻譯為波蘭后綴表達式的文法為：E->E+T+E->T T-&