编译原理(清华大学-第2版)课后习题答案.doc

第三章N=D= 0,1,2,3,4,5,6,7,8,9N=ND=NDDL=a |a(0|1|3、|9)n 且 n=1(0|1|3、|9)n 且 n=1 ab, anbn n=1第6题、(1) = = = i(2) = = = () = ()= ()=(i)(3) = = * = * =i*i(4) = + = + = *+= *+ = *+ = i*i+i(5) = +=+ = +=i+ = i+ = i+() = i+(+)= i+(+) = i+(i+i)(6) = + = + = + = i+ = i+* = i+* = i+i*i第7题第9题 语法树 推导: S=SS*=SS+S*=aa+a*11、 推导:E=E+T=E+T*F 语法树:短语: T*F E+T*F直接短语: T*F句柄: T*F12 短语： 直接短语： 句柄： 13、(1)最左推导：S = ABS = aBS =aSBBS = aBBS = abBS = abbS = abbAa = abbaa最右推导：S = ABS = ABAa = ABaa = ASBBaa = ASBbaa = ASbbaa = Abbaa = a1b1b2a2a3 (2) 文法：S ABSS AaS A aB b (3) 短语：a1 , b1 , b2, a2 , , bb , aa , abbaa, 直接短语： a1 , b1 , b2, a2 , , 句柄：a114 (1)S ABA aAb | B aBb | (2) S 1S0 S A A 0A1 |第四章1. 1、 构造下列正规式相应得DFA(1) 1(0|1)*101NFA(2) 1(1010*|1(010)*1)*0NFA(3)NFA(4)NFA2、解：构造DFA矩阵表示01X0ZXZ *X,ZYX,Z *X,ZX,YYX,YX,YX,Y,ZXX,Y,Z *X,Y,ZX,Y其中0 表示初态，*表示终态用0，1，2，3，4，5分别代替X Z X,Z Y X,Y X,Y,Z得DFA状态图为：3解：构造DFA矩阵表示构造DFA得矩阵表示01S0V,QQ,UV,QZ,VQ,UQ,UVQ,U,ZZ,V*ZZVZQ,U,Z*V,ZQ,U,ZZZZ其中0 表示初态，*表示终态替换后得矩阵0100121322453*66465*35666构造DFA状态转换图（略）4（1）解构造状态转换矩阵： ab00*0,110,1*0,1110转换为ab0*121*12202，3 0，12，3a=0,32,3,0,10,1a=1,1 0,1b=2,2（2）解：首先把M得状态分为两组：终态组0，与非终态组1，2，3，4,5 此时G=( 0,1,2,3,4,5 )1,2,3,4,5a=1,3,0,51,2,3,4,5b=4,3,2,5由于4a=0 1,2,3,5a=1,3,5因此应将1,2,3,4,5划分为4,1,2,3,5G=(041,2,3,5)1,2,3,5a=1,3,51,2,3,5b=4,3,2因为1,5b=4 23b=2,3所以应将1,2,3,5划分为1,52,3G=(01,52,34)1,5a=1,5 1,5b=4 所以1,5 不用再划分2,3a=1,3 2,3b=3,2因为 2a=1 3a=3 所以2,3应划分为23所以化简后为G（ 0,2,3,4,1,5）7、去除多余产生式后，构造NFA如下确定化，构造DFA矩阵abSAQAAB,ZB,ZQDQQD,ZDABD,ZADBQD变换为ab00131122*343354165*14634化简：G=(0,1,3,4,6),(2,5)0,1,3,4,6a=1,30,1,3,4,6b=2,3,4,5,6所以将0,1,3,4,6划分为 0,4,61,3G=(0,4,6),(1,3),(2,5)0,4,6b=3,6,4 所以 划分为0,4,6G=(0),(4,6),(1,3),(2,5)不能再划分，分别用 0，4，1，2代表各状态，构造DFA状态转换图如下；8代入得 S = 0(1S|1)| 1(0S|0) = 01(S|) | 10(S|) = (01|10)(S|) = (01|10)S | (01|10) = (01|10)*(01|10)构造NFA由NFA可得正规式为(01|10)*(01|10)=(01|10)+9、状态转换函数不就是全函数,增加死状态8, G=(1,2,3,4,5,8),(6,7)(1,2,3,4,5,8)a=(3,4,8) (3,4)应分出(1,2,3,4,5,8)b=(2,6,7,8) (1,2,3,4,5,8)c=(3,8)(1,2,3,4,5,8)d=(3,8)所以应将(1,2,3,4,5,8)分为(1,2,5,8), (3,4)G=(1,2,5,8),(3,4),(6,7)(1,2,5,8)a=(3,4,8) 8应分出(1,2,5,8)b=(2,8) (1,2,5,8)c=(8) (1,2,5,8)d=(8) G=(1,2,5),(8),(3,4),(6,7)(1,2,5)a=(3,4,8) 5应分出G=(1,2), (3,4),5, (6,7) ,(8) 去掉死状态8,最终结果为 (1,2) (3,4) 5,(6,7) 以1,3,5,6代替,最简DFA为正规式:b*a(da|c)*bb*第五章1、 S-a | |( T )T - T , S | S(a,(a,a)S = ( T ) = ( T , S ) = ( S , S ) = ( a , S) = ( a, ( T ) =(a , ( T , S ) ) = (a , ( S , S ) = (a , ( a , a ) )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 ) ) , S )= ( ( ( a , a ) , , ( S ) ) , S ) = ( ( ( a , a ) , , ( a ) ) , S ) = ( ( ( a , a ) , , ( a ) ) , a )S-a | |( T )T - T , ST - S消除直接左递归：S-a | |( T )T - S TT - , S T | SELECT ( S-a) = aSELECT ( S-) = SELECT ( S-( T ) ) = ( SELECT ( T - S T) = a , , ( SELECT ( T - , S T ) = , SELECT ( T -) = FOLLOW ( T ) = FOLLOW ( T ) = ） 构造预测分析表a( ),#S - a- - ( T )T- S T- S T- S TT- , S T分析符号串 （ a , a ）#分析栈 剩余输入串 所用产生式 #S ( a , a) # S - ( T )# ) T ( ( a , a) # ( 匹配 # ) T a , a ) # T - S T# ) T S a , a ) # S - a# ) T a a , a ) # a 匹配# ) T ，a) #T - , S T# ) T S , , a ) #, 匹配# ) T S a ) #S-a# ) T aa ) #a匹配# ) T) #T -# ) #)匹配#接受2、E-TE E-+E E- T-FT T-T T- F-PF F-*F F- P-(E) P-a P-b P-非终结符名就是否FIRST集FOLLOW集E否（，a，b，#，）E就是+,#，）T否（，a，b，#，）T就是, （，a，b，#，）F否（，a，b，（，a，b，#，）F就是*,（，a，b，#，）P否（，a，b，*，（，a，b，#，）SELECT（ETE）=FIRST(TE)=FIRST(T)= （，a，b，）SELECT（E+E）=+SELECT（E）=FOLLOW(E)= #，)SELECT（TFT）=FIRST（F）= （，a，b，SELECT（T T）=FIRST（T）= （，a，b，）SELECT(T)=FOLLOW(T)= ，#，)SELECT(F PF)=FIRST(F)= （，a，b，SELECT(F*F)=*SELECT(F)=FOLLOW(F)= （，a，b，#，）3、 S-MH S-a H-Lso H- K-dML K- L-eHf M-K M-bLM FIRST ( S ) =FIRST(MH)= FIRST ( M ) FIRST ( H ) a= a, d , b , e , FIRST( H ) = FIRST ( L ) = e , FIRST( K ) = d , FIRST( M ) = FIRST ( K ) b = d , b , FOLLOW ( S ) = # , o FOLLOW ( H ) = FOLLOW ( S ) f = f , # , o FOLLOW ( K ) = FOLLOW ( M ) = e , # , o FOLLOW ( L ) = FIRST ( S ) o FOLLOW ( K ) FIRST ( M ) FOLLOW ( M ) = a, d , b , e , # , o FOLLOW ( M ) = FIRST ( H ) FOLLOW ( S ) FIRST ( L ) = e , # , o SELECT ( S- M H) = ( FIRST ( M H) ) FOLLOW ( S ) = ( FIRST( M ) FIRST ( H ) ) FOLLOW ( S ) = d , b , e , # , o SELECT ( S- a ) = a SELECT ( H-L S o ) = FIRST(L S o) = e SELECT ( H - ) = FOLLOW ( H ) = f , # , o SELECT ( K- d M L ) = d SELECT ( K- ) = FOLLOW ( K ) = e , # , o SELECT ( L- e H f ) = e SELECT ( M-K ) = ( FIRST( K ) ) FOLLOW ( M ) = d， e , # , o SELECT ( M - b L M )= b 构造LL( 1 ) 分析表abedfo#S- a- M H- M H- M H- M H- M HH-L S o-K- d M L-L- e H fM- b L M-K-K-K-K4 、 文法含有左公因式，变为 S-C $ b, a C- b A b C- a B a A - b A A b A- a A a A- $ , a, b A- C a , b B-a B B a B - b B b B- $ , a , b B- C a, b 5、 - S A B C D E -F S-begin A end S-begin A end begin A- B A- B A a , if A- A ; B A- ; B A ; A- end B- CB- C a B- D B- D if C- a C- a a D- E D- E D if D- E else B D- else B else D- ; , end E- FCE- FC if F- if b then F- if b then if 非终结符就是否为空S否 A否 A就是 B否 C否 D否 D就是 E否 F否FIRST(S) = begin FIRST(A) = FIRST(B) FIRST(A) = a , if , ; , FIRST(A) = ; , FIRST(B) = FIRST(C) FIRST(D) = a , if FIRST(C) = aFIRST(D) = FIRST（E）= if FIRSR(D) = else , FIRST(E) = FIRST(F) = if FIRST(F) = if FOLLOW(S) = # FOLLOW(A) = endFOLLOW(A) = end FOLLOW(B) = ; , end FOLLOW (C) = ; , end , else FOLLOW(D) = ; , end FOLLOW( D ) = ; , end FOLLOW(E) = else , ; end FOLLOW(F) = a S A A B C D D E F if then else begin end a b ; ifthenelsebeginendab;#S-begin A endA- B A- B AA- ; B AB- D- CC- aD- E DD- else B D-E-FC F-if b then6、 1、(1) S - A | B(2) A - aA|a(3)B - bB |b提取 （2），（3）左公因子(1) S - A | B(2) A - aA(3) A- A|(4) B - bB(5) B- B |2、(1) S-AB(2) A-Ba|(3) B-Db|D(4) D- d|提取（3）左公因子(1) S-AB(2) A-Ba|(3) B-DB(4) B-b|(5) D- d|3、(1) S-aAaB | bAbB(2) A- S| db(3) B-bB|a4(1) S-i|(E)(2) E-E+S|E-S|S提取（2）左公因子(1) S-i|(E)(2) E-SE(3) E-+SE|-SE |5(1) S-SaA | bB(2) A-aB|c(3) B-Bb|d消除（1）(3)直接左递归(1) S-bBS(2) S-aAS|(3) A-aB | c(4) B - dB(5) B-bB|6、(1) M-MaH | H(2) H-b(M) | (M) |b消除（1）直接左递归，提取（2）左公因子(1) M- HM(2) M- aHM |(3) H-bH | ( M )(4) H-(M) |7、 (1) 1) A-baB 2) A-3) B-Abb4) B-a将1）、2)式代入3）式1) A-baB2) A-3) B-baBbb4) B-bb5) B-a提取3）、4）式左公因子1) A-baB2) A-3) B-bB4) B-aBbb | b5) B-a(3)1) S-Aa2) S-b3) A-SB4) B-ab将3）式代入1）式1) S-SBa2) S-b3) A-SB4) B-ab消除1）式直接左递归1) S-bS2) S-BaS |3) S-b4) A-SB5) B-ab删除多余产生式4）1) S-bS2) S-BaS |3) S-b4) B-ab（5）1) S-Ab2) S-Ba3) A-aA4) A-a5) B-a提取3） 4）左公因子1) S-Ab2) S-Ba3) A-aA4) A- A |5) B-a将3）代入1） 5）代入21) S-aAb2) S-aa3) A-aA4) A- A |5) B-a提取1） 2） 左公因子1) S- aS2) S-Ab | a3) A-aA4) A- A |5) B-a删除多余产生式5）1) S- aS2) S-Ab | a3) A-aA4) A- A |A A S S将3）代入4）1) S- aS2) S-Ab | a3) A-aA 4) A- aA |将4）代入2）1) S- aS2) S-aAb 3) S-a 4) S-b5) A-aA 6) A- aA |对2）3)提取左公因子1) S-aS2) S-aS3) S-Ab|4) S-b5) A-aA 6) A- aA |删除多余产生式5）1) S-aS2) S-aS3) S-Ab|4) S-b5) A- aA |第六章1S a | | ( T )T T , S | S解：(1) 增加辅助产生式 SS求 FIRSTVT集FIRSTVT（S） #FIRSTVT（S） a ( a ( FIRSTVT (T) , FIRSTVT( S ) = , a ( 求 LASTVT集LASTVT（S） # LASTVT（S） a )LASTVT (T) , a )(2)算符优先关系表a(),#a(=,#=因为任意两终结符之间至多只有一种优先关系成立，所以就是算符优先文法 (3) a (),#F 1 1 1 1 1 1g 1 1 1 1 1 1f22132 1g22212 1f33133 1g44412 1f33133 1g44412 1(4) 栈 优先关系 当前符号 剩余输入串 移进或规约 ( a,a)# 移进( ,a)# 规约(T , a)# 移进(T， ) #规约(T,T)# 规约(T = )# 移进(T) 规约T=接受4. 扩展后得文法S#S# SS;G SG GG(T) GH Ha H(S)TT+S TS（1）FIRSTVT(S)=;FIRSTVT(G) = ; , a , ( FIRSTVT(G)= ( FIRSTVT(H) = a , ( FIRSTCT(H)=a , ( FIRSTVT(T) = + FIRSTVT(S) = + , ; , a , ( LASTVT(S) = ; LASTVT(G) = ; , a , )LASTVT(G) = ) LASTVT(H) = a , )LASTVT(H) = a, )LASTVT(T) = + LASTVT(S) = + , ; , a , ) 构造算符优先关系表;()a+#；(a+#因为任意两终结符之间至多只有一种优先关系成立，所以就是算符优先文法（2） 句型a(T+S);H;(S)得短语有：a(T+S);H;(S) a(T+S);H a(T+S) a T+S (S) H 直接短语有: a T+S H (S)句柄： a素短语：a T+S (S) 最左素短语：a(3)分析a；（aa） 栈优先关系当前符号剩余输入串移进或规约aTT；T；（T；（aT；（TT；（TT；（TaT；（TTT；（TT；（T）T；TTa；（aa）；（aa）（aa）（aa）aa）a）a）a）移进规约移进移进移进规约移进移进规约规约移进规约规约接受分析a；（aa）栈优先关系当前符号剩余输入串移进或规约（a（T（T（Ta（TT（T（T）T(aa）aa）a）a） a）移进移进规约移进移进规约规约移进规约接受（4）不能用最右推导推导出上面得两个句子。第七章1、已知文法： A aAd|aAb|判断该文法就是否就是SLR（1）文法，若就是构造相应分析表，并对输入串ab#给出分析过程。解：(0) A A(1) A aAd(2) A aAb(3) A 构造该文法得活前缀DFA：aI0： A A A aAdA aAbA 由上图可知该文法就是SLR（1）文法。构造SLR（1）得分析表：状态ACTIONGOTOadb#A0S2R3R3R311acc2S2R3R3R333S4S54R1R1R15R2R2R2输入串ab#得分析过程：步骤状态栈符号栈输入串ACTIONGOTO10#ab#S2202#ab#R333023#aAb#S540235#aAb#R21501#A#acc3、考虑文法：S AS|b ASA|a(1) 列出这个文法得所有LR（0）项目(2) 按（1）列出得项目构造识别这个文法活前缀得NFA，把这个NFA确定化为DFA，说明这个DFA得所有状态全体构成这个文法得LR（0）规范族。(3) 这个文法就是SLR得吗？若就是，构造出它得SLR分析表。(4) 这个文法就是LALR或LR（1）得吗？解：（0）SS (1)SAS (2)Sb (3)ASA (4)Aa (1)列出所有LR（0）项目： SS Sb Aa S S Sb Aa S AS ASA S AS ASA S AS ASA (3)构造该文法得活前缀NFA：I0：SSS ASS bA SAA aI1：S SA SAA SAA