编译原理课后习题答案

1、第三章N=D= 0,1,234,5,6,7,8,9N=ND=NDDL=a |a(0|1|3.|9) n 且 n=1 (0|1|3.|9) n 且 n=1ab,a b n=1第6题.(1) = = = i = = = ()= ()= ()=(i) = = * = * =i*i(4) = + = + = *+= *+ = *+ =i*i+i(5) = +=+ = +=i+= i+ = i+()= i+(+)= i+(+)= i+(i+i)(6) = + = + = + = i+= i+* = i+* =i+i*i语法树a推导：S=SS*=SS+S*=aa+a*11. 推导：E=E+T=E+T*F语

2、法树：短语：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) 短语：al , bl , b2, a2 , , bb , aa , abbaa,直接短语：al , bl , b2, a2 ,句柄：al14 (1)SABAaAb |BaBb

3、|(2)S1S0SAA0A1 |第四章1. 1.构造下列正规式相应的DFA(1) 1(0|1)*101NFA0,1(2) 1(1010*|1(010)*1)*0NFA(3) NFAba,b(4)NFA2.解：构造DFA矩阵表示01X0ZX*Z 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,ZY X,Y X,Y,Z得DFA状态图为：3. 解：构造DFA矩阵表示构造DFA的矩阵表示01S0r v,qQ,UV,QZ,VQ,UQ,UpVQ,U,ZZ,V *；ZZVZQ,U,Z *:V

4、,ZQ,U,ZZZZ其中0表示初态，*表示终态替换后的矩阵010012132245*366465*35666构造DFA状态转换图（略）4. （1 ）解构造状态转换矩阵:ab00*0,11 n0,1 *0,1110转换为ab*012*112202 , 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,5 a=1,3,0,51,2,3,4,5b=4,3,2,5由于4 a=0 1,2,3,5 a=1,3,5 因此应将1,2,3,4,5 划

5、分为4,1,2,3,5 G=(041,2,3,5)1,2,3,5a=1,3,51,2,3,5b=4,3,2因为1,5 b=4 23 b=2,3所以应将1,2,3,5戈U分为1,52,31,5 a=1,5 1,5b=4 所以1,5不用再划分G=(01,52,34)2,3 a=1,3 2,3b=3,2因为2 a=1 3a=3所以2,3应划分为23所以化简后为 G=( 0,2,3,4,1,5)7.去除多余产生式后，构造NFA如下确定化，构造 DFA矩阵abSAQAAB,ZB,ZQDQQD,ZDABD,ZADBQD变换为ab00131122*34335416*514634化简:G=(0,1,3,4,6

6、),(2,5)0,1,3,4,6a=1,30,1,3,4,6b=2,3,4,5,6所以将0,1,3,4,6戈U分为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状态转换图如下;&代入得S = 0(1S|1)| 1(0S|0)=01(S| ) | 10(S| )=(01|10)(S| )=(01|10)S | (01|10)=(01|10) *(01|10)9.状态转换函数不是全函数，增加死状态8,G=(1,2,3,4,5,8),(

7、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) 去掉死状态8,最终结果为(1,2) (3,4) 5,(6,7)以1,3,5,6代替,最简DFA为b正规式：b*a(da|c) *bb*第五章S-a | 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 )

9、 =( ( 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 ) , A , S ) , S ) = ( ( ( a , a ) , A , ( T ) ) ,S )= (a , a ) , A , ( S ) ) , S )= ( ( a , a ) , A , ( a ) ) , S ) = ( ( ( a , a ) , A ,( a )

10、) , a )S-a | A |( T )T - T , ST - S消除直接左递归：S-a | A |( T )T - S T T , S T ESELECT ( S-a) = aSELECT ( S-A) = 人SELECT ( S-( T ) ) = (SELECT ( T - S T ) = a , a , (SELECT ( T - , S T) = ,SELECT ( T - E ) = FOLLOW ( T ) = FOLLOW ( T ) = )构造预测分析表aA()5#S- a- A- (T )T- S T - S T - S T T- E- ,S T 分析符号串（a,a ）

11、 #分析栈剩余输入串所用产生式#S(a , a) #S - ( T )# ) T (a , a) #（匹配# ) Ta , a ) #T - S T # ) TSa , a ) #S - a# ) Taa , a ) #a匹配# ) T，a) #T- , S T# )s ,a ) #,匹配# ) TSa ) #S-a# ) Taa ) #a匹配# ) T)#T-E# )#）匹配#接受2.E-TE E-+EE- E T-FT T-T T- E F-PF F-*F F- EP-(E) P-a P-b P- A非终结符名是否= eFIRST 集FOLLOW 集E否 (, a, b, a#,)E是+,

12、 e #,)T否 (, a, b, a+ , #,) T是e ,(, a, b, a+ , #,) F否 (, a, b, a (, a, b, a ,+, #,)F是*, e (, a, b, a , + , # ,) P否 (, a, b, a*, ( , a , b , a, #,)SELECT(E TE)=FIRST(TE )=FIRST(T)= (,a , b , a )SELECT(E， +E )=+SELECT(E e)=FOLLOW(E)=# ,)SELECT(T FT =FIRST (F)=(,a , b ,ASELECT(T T )=FIRST (T)=(,a , b ,A

13、 )SELECT(T )=FOLLOW(T )= +, #, )SELECT(F PF )=FIRST(F)= (, a, b, ASELECT(F *F )=*SELECT(F )=FOLLOW(F )= (, a, b, a ,+, #,)3. S-MH S-a H-Lso H- EK-dML K- E L-eHf M-K M-bLMFIRST ( S ) =FIRST(MH)= FIRST ( M ) U FIRST ( H ) U E U a= a, d , b , e , E FIRST( H ) = FIRST ( L ) U E = e , E FIRST( K ) = d ,

14、E FIRST( M ) = FIRST ( K ) U b = d , b , E FOLLOW ( S ) = # , o FOLLOW ( H ) = FOLLOW ( S ) U f = f , # , o FOLLOW ( K ) = FOLLOW ( M ) = e , # , o FOLLOW ( L ) = FIRST ( S )- E U o U FOLLOW ( K )U FIRST ( M )- E U FOLLOW ( M )=a, d , b , e , # , o FOLLOW ( M ) = FIRST ( H )- E U FOLLOW ( S )U FIRST

15、 ( L )- E = e , # , o SELECT ( S- M H) = ( FIRST ( M H) - E ) U FOLLOW ( S )=(FIRST( M ) U FIRST ( H )- E ) U FOLLOW ( S )= d , b , e , # , o SELECT ( S- a ) = a SELECT ( H-L S o ) = FIRST(L S o) = e SELECT ( H - E ) = FOLLOW ( H ) = f , # , o SELECT ( K- d M L ) = d SELECT ( K- E ) = FOLLOW ( K )=

16、e , # , o SELECT ( L- e H f ) = e SELECT ( M-K ) = ( FIRST( K )- E ) U FOLLOW ( M )= d , e , # , o S-C $ b, a C- b A b C- a B a A - b A A b A- a A a A- E $ , a, b A- C a , b B-a B B a B - b B b B- E $ , a , b B- C a, b 5. -S语句表A 语句如果语句E如果子句-FS-beg in A endS-begi n A endA- BA- B A A- A ; BA- ; B A4.文

17、法含有左公因式，变为B 无条件语句 C 条件语句 D B- CB- CB- DB- DC- aC- aD- ED- E D D- E else BD - else BD- EE- FCE- FCF- if b thenF- if b thenA- E begin a , if ; end a if a if else ; , end if if SELECT ( M - b L M )= b 构造LL( 1 )分析表abedfo#S- a- M H- M H- M H- M H- M HH-L S o- E- E- EK- E- d M L- E- EL- e H fM- b L M-K-K-

18、K-K非终结符是否为空S否A 否B 否C否 D否D 早E否 F否FIRST(S) = begi n FIRST(A) = FIRST(B) FIRST(A = ; , E U FIRST(A U E = a , if , ; , E FIRST(B) = FIRST(C)FIRST(C) = aU FIRST(D) = a , if FIRST(D) = FIRST ( E) = if FIRSR(D = else , E FIRST(E) = FIRST(F) = if FIRST(F) = if FOLLOW(S) = # FOLLOW(A) = e nd FOLLOW(A = end F

19、OLLOW(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 Fif then else begin end a b ;ifthe nelsebeginendab#S-begi n A endA- B A - B A A- E- ;BAB- D- CC- aD- E D D- else BD，- E- EE-FCF-if b the n6. 1.(1) S - A | B(2

20、) A - aA|aB - bB |b提取 (2) , ( 3)左公因子(1) S - A | B A - aA A，- A| E B - bB B B | E2.(1) S-AB(2) A-Ba| E(3) B-Db|D(4) D- d|E提取( 3)左公因子(1) S-AB(2) A-Ba| E(3) B-DB (4) B-b|E(5) D- d|E3.(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 | E5(1)

21、S-SaA | bB(2) A-aB|c(3) B-Bb|d消除( 1) (3)直接左递归(1) S-bBS (2) S-aAS |E(3) A-aB | c(4) B - dB (5) B -bB |E6.(1) M-MaH | H2）左公因子(2) H-b(M) | (M) |b消除( 1)直接左递归，提取(1) M- HM (2) M- aHM |E(3) H-bH |( M )(4) H -(M) | E1) A-baB2) A- E3) B-Abb4) B-a将 1)、 2 )式代入 3)式1) A-baB2) A- E3) B-baBbb4) B-bb5) B-a提取 3 )、 4

22、)式左公因子1) A-baB2) A- E3) B-bB 4) 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-bS 2) S-BaS |E3) S-b4) A-SB5) B-ab 删除多余产生式 4)1) S-bS 2) S-BaS |E3) S-b4) B-ab(5)1) S-Ab2) S-Ba3) A-aA4) A-a5) B-a提取 3) 4)左公因子1) S-Ab2) S-Ba3) A-aA 4) A - A | E5) B-

23、a将 3 )代入 1) 5 )代入 21) S-aAb2) S-aa3) A-aA 4) A- A | E5) B-a提取 1) 2) 左公因子1) S- aS2) S-A b | a3) A-aA 4) A- A | E5) B-a删除多余产生式 5)1) S- aS2) S-A b | a3) A-aA 4) A- A | EA A S S将 3 )代入 4)1) S- aS2) S-A b | a3) A-aA 4) A- aA|E将 4)代入 2)1) S- aS2) S- aA b3) S-a4) S-b5) A-aA 6) A- aA|E对 2) 3)提取左公因子1) S-aS2)

24、 S-aS3) S-Ab| E4) S-b5) A-aA 6) A- aA|E删除多余产生式 5)1) S-aS2) S-aS3) S-Ab| E4) S-b5) A - aA E第六章1S a | A |( T )T T , S | S解：增加辅助产生式 S # S#求 FIRSTVT 集FIRSTVT (S)= #FIRSTVT (S) = aA ( = a A ( FIRSTVT (T) = ,U FIRSTVT( S ) = , aA ( 求LASTVT集LASTVT( S) = # LASTVT (S) = a A )LASTVT (T) = , a A )算符优先关系表aA()5#

25、aA( .5# .因为任意两终结符之间至多只有种优先关系成立，所以是算符优先文法(3)aA()5#F11111 1g11111 1f221321g2221 21f331331g4441 21f331331g4441 21栈优先关系当前符号剩余输入串移进或规约#(a,a)#移进# (5a)#规约# (T5a)#移进# (T,)#规约# (T,T)#规约# (T .)#移进# (T)#规约# T .#接受4.扩展后的文法S#S#S S;G S G G G(T) G H H a H (S)T T+ST S(1)FIRSTVT(S)=; U FIRSTVT(G) = ; , a , ( FIRSTVT

26、(G)= ( U FIRSTVT(H) = a , ( FIRSTCT(H)=a , ( FIRSTVT(T) = + U FIRSTVT(S) = + , ; , a , ( LASTVT(S) = ; U LASTVT(G) = ; , a , )LASTVT(G) = ) U LASTVT(H) = a , )LASTVT(H) = a, )LASTVT(T) = + U LASTVT(S) = + , ; , a , ) 构造算符优先关系表()a+#;(=a+#=因为任意两终结符之间至多只有一种优先关系成立，所以是算符优先文法(2)句型 a(T+S);H;(S)的短语有：a(T+S);

27、H;(S) a(T+S);H a(T+S) a T+S (S) H 直接短语有：a T+S H (S)句柄： a素短语：a T+S最左素短语：a(3)分析 a; ( a+ a)(S)栈优先关系当前符号剩余输入串移进或规约#;(a + a)#规约# T;(a + a)#移进# T;(a + a)#移进# T;(+a)#规约# T; (T+a)#移进# T; (T+)#规约# T; (T+ T)#规约# T; (T=)#移进# T; (T)#规约# T; T#规约# T=#接受分析 a; ( a+ a)栈优先关系当前符号剩余输入串移进或规约#(a + a) #移进#(+a) #规约#( T+a)

28、#移进#( T+)#规约#( T+ T)#规约#( T=)#移进#( T)#规约# T=#接受(4)不能用最右推导推导出上面的两个句子。第七章1已知文法：A t aAd|aAb| E判断该文法是否是 SLR (1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。解：(0) A t A(1) A t aAd A t aAb(3) A t e构造该文法的活前缀 DFA由上图可知该文法是 SLR (1)文法。 构造SLR (1)的分析表：状态ACTIONGOTOadb#A0S2R3R3R311acc2S2R3R3R333S4S54R1R1R15R2R2R2输入串ab#的分析过程:步骤状态栈符

29、号栈输入串ACTIONGOTO10#ab#S2202#ab#R333023#aAb#S540235#aAb#R21501#A#acc3、考虑文法：S tAS|b A tSA|a(1) 列出这个文法的所有 LR( 0)项目DFA(2) 按(1)列出的项目构造识别这个文法活前缀的NFA把这个NFA确定化为DFA说明这个的所有状态全体构成这个文法的LR ( 0)规范族。这个文法是SLR的吗？若是，构造出它的SLR分析表。这个文法是LALR或 LR (1)的吗？解:(0)St S(1)S t as(2)S t b (3)At SA (4)A t a(1)列出所有1LR (0)项目:S t. SStbA

30、taS t S St b At a St. asAt. SASt A SAT S ASt as-At SA-(3) 构造该文法的活前缀NFA由上可知：Il I315中存在着移进和归约冲突在Il中含项目：Sts 归约项Follow(S)=#at a移进项Follow(S)n a=/St b移进项Follow(S)n b=/在I3中含项目：at sa-归约项Follow(A)=a,bSt b移进项Follow(A)nbat a移进项Follow(A)naF在I5中含项目：Stas-归约项Follow(S)=#,a,bat a移进项Follow(S)naFSt-b移进项Follow(S)nb 由此可

31、知，13、15的移进与归约冲突不能解决，所以这个文法不是SLR (1)文法。(4) 做LR( 1)项目集规范族Io:St-S , #St-as , a/b/#St-b ,a/b/#at-SA ,a/bat-a ,a/b11:St S ,# At S- A ,a/bat-sa ,a/bat-a ,a/bSt-AS ,a/bSt-b ,a/bI2:S t a S ,a/b/#S aS ,a/b/#S b ,a/b/# A t. SA ,a/bA t a ,a/b|3：S T b ,a/b/#|4：A t a ,a/b/#I6： (li-S-)A t s A ,a/bASA ,a/bAa ,a/bS

32、AS ,a/bSb ,a/bl7： (I 2-S-)S T AS-,a/b/#A t s A ,a/b/#A t. SA ,a/bA t a ,a/bS t. AS ,a/bS t b ,a/b|5： (|i-A-)A tSA- ,a/bS t a S ,a/bS t. AS ,a/bS t. b ,a/b A t. SA ,a/b A t a ,a/b由上可知该文法不是 LR ( 1)文法，也不是 LALR (1)文法。5、一个类ALGOL的文法如下： t t t ; t begin d t ;d t s end t s； t begin试构造其LR (0)分析表。解:设 =A =B =C=

33、D =EAt b a t C B t d； E D t begin d D t D;d E ts end E ts;E C t begin E(0)A t A(1) At B (2)A t C (3)B t d；E (4)DT begind D t D;d(6) Ets end_ E ts;E (8) C t begin E构造该文法的活前缀 DFAI1:AtA -AIIo：At-AAt-BAt-CBt-D ECtbegin EDT-begin dDT-D;dbeg inI2:I3:At B-AT C-1 r-E-c110：4 D; E -I6:Bt d；dt D；Et - s endEt -

34、 S;EI11：D; d -I5：CT begin - EDt begin dEt- s endEt- S;EI7:Et s - endEt S-; EIl3 :Et S； EEt - SendencI112:Et s endI8：Ct begin E -I9：Dt begi n derIl4 :EtS； e-Et - S; E状态ACTIONGOTObegin；dSend#ABCDe0S512341acc2R1R1R1R1R1R13R2R2R2R2R2R24S65S9S786S11S7107S13S128R8R8R8R8R8R89R4R4R4R4R4R410R3R3R3R3R3R311R5R

35、5R5R5R5R5构造LR ( 0)分析表:12R6R6R6R6R6R613S71414R7R7R7R7R7rR76、文法 G= (U, T, S, a,b,c,d,e,P,S)其中 P 为：St UTa|Tb T S|Sc|d U US|e(1) 判断 G是 LR (0) , SLR (1), LALR (1)还是 LR (1),说明理由。(2) 构造相应的分析表。解:(0) St s (1)S t UTa(2)St Tb (3)T t STt Sc (5)T t d(6)U t US(7)Ut e首先做LR ( 0)分析：I0 :S-S S- UTa S-Tb U-US U - e T S

36、T- Sc T- dI1:SS- T S- c(11产生移进-规约冲突，但Follow(S) n c= e可以用SLR (1)解决)12: S U Ta U U - S S UTa S Tb U US U e T S T Sc T d13: ST.b14: Ue I5:T d I6:T Sc I7:S UT- a S T bI8:U US- T S- T S - c产生移进一规约喝规约规约冲突Follow(U)=d,e Follow(T)=a,b可以用SLR( 1)的方法解决19: S UTa-110: S Tb - 所以该文法是 SLR (1)文法，也是 LALR (1)文法，LR (1)文

37、法。构造SLR ( 1)分析表:状态ACTIONGOTOabcde#SUT0S12S111231S6acc2S5S48273S104R7R75R5R56R4R47S9S108R3R3S6R6R69R1R1R1R110R2R2R2R27证明下面文法不是 LR ( 0)但是SLR (1)。St A A t Ab|bBaB t aAc|a|aAb证明：(0) St s(1)St A (2)A t Ab (3)A t bBa (4)B t aAc(5) Bt a(6)Bt aAb构造该文法的活前缀DFA在I2项目集中含有:St A-归约项Follow(S)=#At a- b移进项Follow(S)n b=在14项目集中含有:Bt a -归约项Follow(B)=aAt - bBa移进项Follow(B