編譯原理課后答案-第二版

1、第三章 1、 L(GS)= abc 2、 L(GN)= n位整數(shù)或空字符串 | n>0 3、 GE：E>E+D | E-D | DD>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 94、 L(GZ)= anbn | n>0 5、 (1) 考慮不包括“0”的情況GS：S>0S | ABC | 2 | 4| 6 | 8A>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 B>AB | 0B | C>0 | 2 | 4 | 6 | 8 考慮包括“0”的情況： GS：S>AB | C B>AB |

2、CA>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 C>0 | 2 | 4 | 6 | 8(2)方法1：GS：S> ABC | 2 | 4 | 6 | 8A>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 B>AB | 0B | C>0 | 2 | 4 | 6 | 8方法2：GS：S>AB | C B> AB | 0B | C | 0 A> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 C>2 | 4 | 6 | 86、 設(shè)<表達(dá)式>為E，<項&

3、gt;為T，<因子>為F，注：推導(dǎo)過程不能省略，以下均為最左推導(dǎo)(1) E => T => F => i(4) E => E+T => T+T => T*F+T => F*F+T => i*F+T => i*i+T => i*i+F => i*i+i(6) E => E+T => T+T => F+T => i+T => i+T*F => i+F*F => i+i*F => i+i*I<表達(dá)式><表達(dá)式>*<表達(dá)式><表達(dá)式&g

4、t;+<表達(dá)式> i i i<表達(dá)式><表達(dá)式>+<表達(dá)式> i<表達(dá)式>*<表達(dá)式> i i7、 8、 是有二義性的，因為句子abc有兩棵語法樹（或稱有兩個最左推導(dǎo)或有兩個最右推導(dǎo)）最左推導(dǎo)1：S => Ac => abc 最左推導(dǎo)2：S => aB => abc9、 (1)SSS*+SSaaa(2) 該文法描述了變量a和運算符+、*組成的逆波蘭表達(dá)式10、(1) 該文法描述了各種成對圓括號的語法結(jié)構(gòu)(2) 是有二義性的，因為該文法的句子()()存在兩種不同的最左推導(dǎo)：最左推導(dǎo)1：S =>

5、S(S)S => (S)S => ()S => ()S(S)S => ()(S)S => ()()S => ()()最左推導(dǎo)2：S => S(S)S => S(S)S(S)S => (S)S(S)S => ()S(S)S => ()(S)S => ()()S => ()()11、(1) 因為從文法的開始符E出發(fā)可推導(dǎo)出E+T*F，推導(dǎo)過程如下：E => E+T => E+T*F ，所以E+T*F是句型。 從子樹和短語之間的關(guān)系可知：E+T*F是句型E+T*F相對于E的短語；T*F是句型E+T*F相對于T的

6、短語，也是簡單短語和句柄。13、(1) 最左推導(dǎo)：S => ABS => aBS => aSBBS => aBBS => abBS => abbS => abbAa => abbaa(2) S>ABS | Aa | A>a B>SBB | b(3) 首先為了區(qū)別句子abbaa中的a和b，把它寫成a1b1b2a2a3 該句子的短語有：a1b1b2a2a3，b1b2，a2a3，a1，a2，b1，b2， 直接短語有：a1，a2，b1，b2， 句柄：a114、(1) GS：S>ABA>aAb |B>aBb |(2) G

7、S：S>1S0 | A A>0A1 |(3) GS：S>0S0 | aSa | a16、(1) GA：A>aA |(2)GA：A> aA | aB B> bB | b (3)GA：A>aA | B B> bB | C C>cC |17、習(xí)題6、習(xí)題7和習(xí)題7中的文法所描述的語言都是由變量i、+、-、*、/、（和）組成算術(shù)表達(dá)式，因此它們之間是等價的。第四章參考答案第1題：(1) 0,1 1 1 0 1CBAS Z確定化：I0I1SAAAABABACABACAABZ+ABZACAB S ABC Z重新命名，令A(yù)B為B、AC為C、ABZ為Z其中

8、S為初態(tài)，Z為終態(tài)01SAAABBCBCAD+ZCBa,b(3)abZAS aaBb確定化：IaIbSAAABAZABABABZ+AZABAZ+ABZABABZ 0 1 2 3 4重新命名，以0、1、2、3、4代替S,A, AB,AZ,ABZ得DFA其中0為初態(tài)，3，4為終態(tài)IaIb01123224+323+424第2題：I0I1XZX+ZXZY+XZXZXYYXYXYXYZX+XYZXYZXY A B C DEF重新命名，以A、代替X,Z ,XZ , Y , XY ,XYZ得DFA其中A為初態(tài)，為終態(tài)01ABA+BCD+CCEDEEFA+FFE第3題：確定化：.I0I1SVQQUVQVZQU

9、QUVQUZ+VZZZVZ.+QUZVZQUZ+ZZZ A BCDEFG重新命名，以A、代替S,VQ ,QU , VZ , V ,QUZ,Z得DFA其中A為初態(tài)，D，F(xiàn)，G為終態(tài).01ABCBDCCEF+DGGEG.+FDF+GGG第4題：(1)確定化：IaIb+0011+0101110 A B C重新命名，以、代替0、01、1得其中A為初態(tài)，A，B為終態(tài)ab+ABC+BBCCA最小化：初始分劃得終態(tài)組A,B，非終態(tài)組C0：A,B，C 對終態(tài)組進(jìn)行審查，判斷A和B是等價的，故這是最后的劃分重新命名，以A、C代替A,B、C得DFAab+AACCA(2)這是DFA，直接最小化初始分劃得：終態(tài)組0，

10、非終態(tài)組1,2,3,4,50：0，1,2,3,4,5 對1,2,3,4,5進(jìn)行審查： 4 輸入a后到達(dá)0，1,2,3,5輸入a后到達(dá)1,3,5，故得到新分劃 0,1,3,5，41：0，4，1,2,3,5 對1,2,3,5進(jìn)行審查：1,5 輸入b后到達(dá)4，2,3 輸入b后到達(dá)2,3，故得到新分劃 1, 5，2,32：0，4，1, 5，2,3對1, 5，2,3進(jìn)行審查：1, 5 輸入a后到達(dá)1, 5 2 輸入a后到達(dá)1，3 輸入a后到達(dá)3，故得到新分劃2，33：0，2，3，4，1, 5 這是最后分劃了重新命名，以0，2，3，4，1代替0，2，3，4，1, 5得DFA略 bbbbbabaaSAaQb

11、ZaBD第7題首先判斷E，F(xiàn)為多余狀態(tài)根據(jù)正則文法轉(zhuǎn)化為NFA的方法構(gòu)造NFA 確定化：IaIb-àabSAQ012AABZ113QQDZ224+BZQD+325+DZAB+416DAB516BQD6250123456最小化：初始分劃得：終態(tài)組3,4，非終態(tài)組0,1,2,5,60：3,4,0,1,2,5,6對0,1,2,5,6進(jìn)行審查：1,2輸入b到達(dá)3,4，而0,5,6輸入b到達(dá)2,5,6，故得到新分劃1,2,0,5,61：3,4,1,2,0,5,6 對0,5,6進(jìn)行審查：0經(jīng)過b到達(dá)，5,6經(jīng)過b到達(dá)5,6，故得到新分劃05,63：0，1,2，3,4，5,6 這是最后劃分了。重新

12、命名，以0，1，3，5代替0，1,2，3,4，5,6得DFA略第9題這是DFA，直接最小化初始分劃得：終態(tài)組6,7，非終態(tài)組1,2,3,4,50：6,7,1,2,3,4,5對1,2,3,4,5進(jìn)行審查：1,2輸入b到達(dá)2，而3,4輸入b到達(dá)6,7，5輸入b不會有任何動作，故得到新分劃1,2,3,4,51：6,7,3,4,5,1,21 35b6cab這是最后劃分了。重新命名，以1，3，5，6代替1,2,3,4,5,6,7得DFAba d所識別的語言是b*a (c| da)*bb*第11題根據(jù)正則文法（左線性文法）轉(zhuǎn)化為NFA的方法構(gòu)造NFA：bZ ASaaa確定化：IaIb-àab+Z

13、SAA+011AAS12+ASASA+221012重新命名，以0、1、2代替ZS、A、AS得DFA其中0為初態(tài)，0，2為終態(tài)b12aa,ba0所識別的語言是：| (a|b) a (ba|a)*第13題（1） 假設(shè)d A,B,Y,Z n 0,1,2,8,9，文法可以等價得化為：<單詞>> <標(biāo)識符> | <整數(shù)><標(biāo)識符>> <標(biāo)識符>d | <標(biāo)識符>n | d<整數(shù)>><整數(shù)>n | n（2） 根據(jù)正則文法（左線性文法）轉(zhuǎn)化為NFA的方法構(gòu)造NFA：重新命名狀態(tài)，令A(yù)、B、C分別

14、代表<單詞>、<標(biāo)識符>、<整數(shù)>BAd,nSCdnn第五章 習(xí)題參考答案1、(1) 對(a,(a,a)的最左推導(dǎo)為：S(T) (T,S) (S,S) (a,S) (a,(T) (a,(T,S) (a,(S,S)(a,(a,S)(a,(a,a) 對(a,a),(a),a) 的最左推導(dǎo)為：S(T) (T,S)(S,S) (T),S)(T,S),S) (T,S,S),S)(S,S,S),S) (T),S,S),S)(T,S),S,S),S)(S,S),S,S),S)(a,S),S,S),S) (a,a),S,S),S) (a,a),S),S) (a,a),(T)

15、,S) (a,a),(S),S) (a,a),(a),S) (a,a),(a),a)對( a, a ), Ù, ( a ), a )的最左推導(dǎo)為：S Þ ( T ) Þ ( T, S ) Þ ( S, S ) Þ ( T ), S ) Þ ( T, S ), S ) Þ( T, S, S ), S ) Þ ( S, S, S ), S ) Þ ( T ), S, S ), S ) Þ ( T, S ), S, S ), S ) Þ ( S, S ), S, S ), S ) Þ

16、; ( a, S ), S, S ), S ) Þ ( a, a ), S, S ), S ) Þ ( a, a ), Ù, S ), S ) Þ ( a, a ), Ù, ( T ), S ) Þ ( a, a ), Ù, ( S ), S ) Þ ( a, a ), Ù, ( a ), S ) Þ ( a, a ), Ù, ( a ), a )對( a, a ), Ù, ( a ), a )的最左推導(dǎo)為：S Þ ( T ) Þ ( T, S ) 

17、22; ( T, a ) Þ ( S, a ) Þ ( T ), a ) Þ ( T, S ), a )Þ ( T, ( T ), a ) Þ ( T, ( S ), a ) Þ ( T, ( a ), a ) Þ ( T, S, ( a ), a ) Þ ( T, Ù, ( a ), a ) Þ ( S, Ù, ( a ), a ) Þ ( T ), Ù, ( a ), a ) Þ ( T, S ), Ù, ( a ), a ) Þ

18、( T, a ), Ù, ( a ), a ) Þ ( S, a ), Ù, ( a ), a ) Þ ( a, a ), Ù, ( a ), a ) (2) 改寫文法為： 0) Sa 1) S 2) S( T ) 3) TS N4) N, S N5) N 入口入口入口S: T:N: ，YNNSNYaRead(w)YNNS出口N出口Y(出錯Read(w)TN)Read(w)出口(3)非終結(jié)符FIRST集FOLLOW集Sa,(#,)Ta,().N,.).對左部為N的產(chǎn)生式可知：SELECT(Sa)SELECT(S) SELECT(S( T )=S

19、ELECT(N , S N)SELECT(N ) =， )=所以文法是LL(1)的。 預(yù)測分析表 a(),#Sa(T)   TS NS NS N   N   , S N 也可由預(yù)測分析表中無多重入口判定文法是LL(1)的。(4) 對輸入串（a,a）#的分析過程為：棧（STACK）當(dāng)前輸入符（CUR_CHAR）剩余輸入符（INOUT_STRING）所用產(chǎn)生式（OPERATION）#S #)T(#)T #)NS #)Na#)N#)NS,#)NS #)Na#)N#)#(aaa,aa)#a,a

20、)#.a,a)#.,a)#.,a)#.,a)#.a)#.a)#.)#.)#.#.#.S(T).TSNSa.N,SN.Sa.N可見輸入串（a,a）#是文法的句子。6.(2) 不是LL(1)文法以A的產(chǎn)生式代入S，以D的產(chǎn)生式代入B中，提取左公共因子并刪除多余產(chǎn)生式得文法：SBCCaB|BdF|FFb|分析表為abd#SBCBCBCBCBFFdFFCaBFb結(jié)論：經(jīng)改寫之后的文法是（）文法。遞歸下降分析器如同題1，從略6.(4)消除左遞歸為：SiS(E)ESFF+SFF-SFF分析表為：+-i()ESFSFF+SF-SFSi(E)結(jié)論：經(jīng)改寫之后的文法是（）文法。遞歸下降分析器如同題1，從略7.(

21、1)文法不存在左遞歸第一種改法：以A的產(chǎn)生式替入B 產(chǎn)生式中BbaBbbBbbBa消除左公共因子：BbCCaBbbCbBa改寫之后的文法的分析表：ab#BabCCaBbbb改寫之后的文法是LL(1)文法第二種改法：以B的產(chǎn)生式替入A產(chǎn)生式中AbaAbbAbaaA消除左公共因子后為AAbaCCAbbCaSELECT(AbaC) SELECT(A) = b # ,b 所以，改寫之后的文法不是LL(1)文法7.(3)第1種改寫：用A的產(chǎn)生式右部代替S的產(chǎn)生式右部的A得： SSBa|bBab消除左遞歸后文法變?yōu)椋?0) Sb N1) NB a N2) N3) Ba b 非終結(jié)符FIRST集FOLLOW

22、集Sb.#Ba.aN,a#SELECT(NB a N)SELECT(N) = a # =所以文法是LL(1)的。預(yù)測分析表 ab#S b N Ba b  NB a N 第2種改寫：用S的產(chǎn)生式右部代替A的產(chǎn)生式右部的S得： SAa|bAAaB|bBBab 消除左遞歸后文法變?yōu)椋?0) SA a 1) Sb 2) Ab B N3) Na B N4) N 5) Ba b非終結(jié)符FIRST集FOLLOW集Sb.#Ab.aBa.aNa,aSELECT(SA a)SELECT(Sb) = b b = b SELECT(Na B N)SELECT

23、(N) = a a = a 所以文法不是LL(1)的。7.(5)以A、B的產(chǎn)生式代入S的產(chǎn)生式中的A、B，得新文法：SaCCAb|b|aAaA|a以A的產(chǎn)生式代入C中提取左公共因子得：SaCCaD|bDAb|b|AaA|a以A的產(chǎn)生式代入D中提取左公共因子得：SaCCaD|bDaE|EAb|bAaA|a以A的產(chǎn)生式代入E中提取左公共因子得：SaCCaD|bDaE|EaFFAb|bAaA|a可以看出，繼續(xù)用A的產(chǎn)生式替換，只能使文法的產(chǎn)生式越來越多。改寫之后的文法不是LL(1)文法第1題(1) FIRSTVT - LASTVT表 非終結(jié)符FIRSTVT集LASTVT集S a ( . a ) .T

24、 a ( , a , (2) 算符優(yōu)先關(guān)系表 a Ù ( ) , a·> ·> Ù ·> ·> ( <· <· <· <· ) ·> ·> , <· <· <· ·> ·>優(yōu)先關(guān)系唯一，所以是一個算符優(yōu)先文法。 (3) 算符優(yōu)先函數(shù)表： a Ù , ( ) f 4 4 4 2 4 g 5 5 3 5 2(4)對輸入串（a,a）#

25、的算符優(yōu)先分析過程為棧（STACK）當(dāng)前輸入字符（CHAR）剩余輸入串（INPUT_STRING）動作（ACTION）#(#(a#(S#(S,#(S,a#(S,S#(T#(S)#S(a,a)#a,a)#.,a)#.a)#.a)#.)#.#.#.#.移進(jìn)移進(jìn)歸約: Sa移進(jìn)移進(jìn)歸約: Sa歸約: TT,S移進(jìn)歸約: S(T)對輸入串（a,(a,a)）# 的算符優(yōu)先分析過程為：棧 f(SYN(top) 關(guān)系 剩余序列 動作 產(chǎn)生式 # 0 <· a,(a,a)# 移進(jìn)，讀 # ( 2 <· ,(a,a)# 移進(jìn)，讀# ( a 4 ·> (a,a)#

26、歸約，不讀 Sàa # ( 2 <· (a,a)# 移進(jìn)，讀 # ( , 4 <· a,a)# 移進(jìn)，讀 # (, ( 2 <· ,a)# 移進(jìn)，讀 # ( , ( a 4 ·> a)# 規(guī)約，不讀 Sàa # ( , ( 2 <· a)# 移進(jìn)，讀# ( , ( , 4 <· )# 移進(jìn)，讀 # ( , ( , a 4 ·> )# 歸約，不讀 Sàa#( , (, 4 ·> )# 歸約，不讀 TàT,S# ( , ( 2 )#

27、 移進(jìn)，讀#( ,() 4 ·> # 規(guī)約，不讀 Sà(T)#( , 4 ·> # 規(guī)約，不讀 TàT,S# ( 2 # 移進(jìn)，讀# () 4 ·> 規(guī)約，不讀 Sà(T)# S OK第2題文法：Sa|(T) TT,S|S (a,a)的最右推導(dǎo)過程為：S(T) (T,S) (T,a)(S,a) (a,a)(a,(a,a)的最右推導(dǎo)過程為: S(T) (T,S)(T,(T) (T,(T,S)(T,(T,a) (T,(S,a) (T,(a,a)(S,(a,a) (a,(a,a) 對輸入串(a,a)# 的規(guī)范歸約過程為：

28、棧（stack）剩余輸入串（input left）動作（action）#( #( a#( S#( T#( T,#( T,a#( T,S#( T#(T)#S(a,a)#.a,a)#.,a)#.,a)#.,a)#.a)#.)#.)#.)#.#.#.移進(jìn)移進(jìn)歸約 by :S a歸約 by :TS移進(jìn)移進(jìn)歸約 by :S a歸約 by :T T,S移進(jìn)歸約 by :S (T)對輸入串（a,(a,a)）# 的規(guī)范歸約過程為：棧剩余輸入串動作#( #( a#( S#( T#( T,#( T,(#( T,(a#( T,(S#( T,(T#( T,(T,#( T,(T,a#( T,(T,S#( T,(T#(

29、T,(T)#( T,(S#( T#( T)#S(a,(a,a)#.a,(a,a)#.,(a,a)#.,(a,a)#.,(a,a)#.(a,a)#.a,a)#.,a)#.,a)#.,a)#.a)#.)#.)#.)#.)#.)#.)#.#.#.移進(jìn)移進(jìn)歸約 by :S a歸約 by :TS移進(jìn)移進(jìn)移進(jìn)歸約 by :S a歸約 by :T S移進(jìn)移進(jìn)歸約 by :S a歸約 by :T TS移進(jìn)歸約 by :S (T)歸約 by :T T,S移進(jìn)歸約 by :S (T)規(guī)范歸約是最左歸約過程，首先確定符號（包括終結(jié)符及非終結(jié)符）之間優(yōu)先關(guān)系，建立優(yōu)先關(guān)系表，在歸約過程中根據(jù)各符號之間的優(yōu)先關(guān)系決定是

30、移進(jìn)還是歸約，當(dāng)出現(xiàn)句柄時進(jìn)行歸約; 算符優(yōu)先歸約方法不是規(guī)范的歸約過程，首先確定終結(jié)符之間優(yōu)先關(guān)系，在歸約過程中根據(jù)最左素短語進(jìn)行歸約。1、(1) a*(-b+c) ：ab-c+* (3) abcde/+*+ (4) ABCD(7) xy+z*0=sab+c*:=sab*c*:=￥（注：￥表示if-then-else運算）2、四元式(1) (+, a, b, t1)(2) (+, c, d, t2)(3) (*, t1, t2, t3) (4) (-, t3, /, t4) (5) (+, a, b, t5)(6) (-, t4, t5, t6)間接三元式序列 間接碼表(1) (+ a, b

31、)(1)(2) (+ c, d)(2) (3) (* (1), (2) (3) (4) (- (3), /) (4)(5) (- (4), (1) (1) (5)三元式 (1) (+ a, b) (2) (+ c, d) (3) (* (1), (2) (4) (- (3), /) (5) (+ a, b) (6) (- (4), (5) 4、(0) SE if error1 then print E.VAL (1) EE1+E2 if E1.TYPE=int AND E2.TYPE=int thenbeginE.VAL:=E1.VAL + E2.VAL;E.YTPE:=int;end els

32、e if E1.TYPE=real AND E2.TYPE=real then begin E.VAL:=E1.VAL + E2.VAL;E.YTPE:=real; end else error=1 (2) EE1*E2 if E1.TYPE=int AND E2.TYPE=int then beginE.VAL:=E1.VAL * E2.VAL; E.YTPE:=int; end else if E1.TYPE=real AND E2.TYPE=real thenbeginE.VAL:=E1.VAL * E2.VAL; E.YTPE:=real;end else error=1 (3) E(

33、E1) E.VAL:=E1.VAL; E.TYPE:=E1.TYPE (4) En E.VAL:=n.LEXVAL;E.TYPE:=n.LEXTYPE 5、產(chǎn)生式語義規(guī)則SàL1.L2SàLS.val:=L.valLàL1BL.val:=L1.val*2+B.val L.length:=L1.length+1LàBL.val:=B.val L.length:=1Bà0B.val:=0Bà1B.val:=16、1)產(chǎn)生式語義規(guī)則EàE1+TIF (E1.type=integer) and (T.type=integer) TH

34、EN E.type:=integerELSE E.type:=realEàTE.type:=T.typeTàn.nT.type:=realTànT.type:=integer產(chǎn)生式(消除左遞歸之后)語義規(guī)則EàTRR.i:=T.type E.Type:=R.sRà+TR1IF (R.i=integer) and (T.type=integer) THEN R1.i:=integer ELSER1.i :=realR.s:=R1.sRàR.s:=R.iTàn.nT.type:=realTànT.type:=integ

35、er2)產(chǎn)生式語義規(guī)則EàE1+TIF (E1.type=integer) and (T.type=integer) THEN BEGIN E.type:=integer Print(E1.val,T.val, +) ENDELSE BEGIN E.type:=real IF E1.type=integer THEN Begin E1.type:=realE1.val:=inttoreal(E1.val) End IF T.type:=integer THEN Begin T.type:=real T.val:=inttoreal(T.val) End Print(E1.val,T.val, +)ENDEàTE.type:=T.type E.val:=T.valTàn.nT.type:=real T.val:=n.n.lexvalTànT.typ