《编译原理(清华大学-第2版)课后习题答案(共40页).doc》由会员分享，可在线阅读，更多相关《编译原理(清华大学-第2版)课后习题答案(共40页).doc（41页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上第三章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题 语法树 推导:
2、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, 直
3、接短语： 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的矩阵表示
4、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,
5、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*1
6、4634化简：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可得正规式为(
7、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、(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
9、,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 ) )
10、, 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 -) = FOLLO
11、W ( 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匹配# )
12、 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
13、）=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 )
14、 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
15、 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 )
16、) 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-be
17、gin 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 ,
18、; , 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) = els
19、e , ; 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)
20、 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
21、) | (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
22、-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
23、 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
24、) , 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 = )# 移进(
25、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) = + , ; ,
26、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；（
27、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 I2：A aAdA aAbA aAdA aAbA aI3： A aAdA aAbAI4： A aAdI5：A aAbdbI1：A AAFollow(A
28、)a=由上图可知该文法是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（