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

1、第三章第三章 N=D=N=D= 0,1,2,3,4,5,6,7,8,90,1,2,3,4,5,6,7,8,9 N=ND=NDDN=ND=NDD L=aL=a |a(0|1|3.|9)|a(0|1|3.|9)n n 且且 n=1n=1 (0|1|3.|9)(0|1|3.|9)n n 且且 n=1n=1 ab,ab, a an nb bn n n=1n=1 第第 6 6 题题. . (1)(1) = = = i i (2)(2) = = = () = () = ()=(i)=(i) (3)(3) = = * = * =i*i=i*i (4)(4) = + + = + = *+ = *+ = *+

2、= = i*i+ii*i+i (5)(5) = +=+ = +=i+=i+ = i+i+ = i+(i+() = i+(i+(+) = i+(i+(+) = i+(i+i)i+(i+i) (6)(6) = + = + = + = i+i+ = i+i+* = i+i+* = = i+i*ii+i*i 第第 7 7 题题 * *i i i i+ + i i + + i i i i* * i i 第第 9 9 题题 语法树语法树 s ss * ss+a aa 推导: S=SS*=SS+S*=aa+a* 11.11. 推导推导:E=E+T=E+T*F:E=E+T=E+T*F 语法树语法树: : E

3、E+ T TF* 短语短语: : T*FT*F E+T*FE+T*F 直接短语直接短语: : T*FT*F 句柄句柄: : T*FT*F 1212 短语：短语： 直接短语：直接短语： 句柄：句柄： 13.(1)13.(1)最左推导：最左推导：S S = ABSABS = aBSaBS =aSBBS=aSBBS = aBBSaBBS = abBSabBS = abbSabbS = abbAaabbAa = abbaaabbaa 最右推导：最右推导：S S = ABSABS = ABAaABAa = ABaaABaa = ASBBaaASBBaa = ASBbaaASBbaa = ASbbaaAS

4、bbaa = AbbaaAbbaa = a1b1b2a2a3a1b1b2a2a3 (2)(2) 文法：文法：S S ABSABS S S AaAa S S A A a a B B b b (3)(3) 短语：短语：a1a1 , , b1b1 , , b2,b2, a2a2 , , , , bbbb , , aaaa , , abbaa,abbaa, 直接短语：直接短语： a1a1 , , b1b1 , , b2,b2, a2a2 , , , , 句柄：句柄：a1a1 1414 (1)(1) S S ABAB A A aAbaAb | | B B aBbaBb | | (2)(2) S S 1S

5、01S0 S S A A A A 0A10A1 | 第四章第四章 1.1. 1.1. 构造下列正规式相应的构造下列正规式相应的 DFADFA (1)(1)1(0|1)*1011(0|1)*101 NFANFA 0123 1101 0,1 4 (2)(2) 1(1010*|1(010)*1)*01(1010*|1(010)*1)*0 NFANFA 2 00 0 4 0 0 0 0 10 11 1 01 0 1 0 (3)NFA(3)NFA (4)NFA 01 b 3 6 a 2 bb 4 a b 5 b 2.2.解：构造解：构造 DFADFA 矩阵表示矩阵表示 0 01 1 XX0 0ZZXX

6、ZZ * *X,ZX,ZYY X,ZX,Z * *X,ZX,ZX,YX,Y YYX,YX,Y 01 a 3 4 b a,b 2 aa b X,YX,YX,Y,ZX,Y,ZXX X,Y,ZX,Y,Z * *X,Y,ZX,Y,ZX,YX,Y 其中其中 0 表示初态， 表示初态，* *表示终态表示终态 用用 0 0，1 1，2 2，3 3，4 4，5 5 分别代替分别代替 X ZZ X,ZX,Z YY X,YX,Y X,Y,ZX,Y,Z 得得 DFADFA 状态图为：状态图为： 3 50 2 1 1 4 0 0 1 0 0 1 1 0 1 0 3 3解：构造解：构造 DFADFA 矩阵表示矩阵表示

7、构造构造 DFADFA 的矩阵表示的矩阵表示 0 01 1 SS0 0V,QV,QQ,UQ,U V,QV,QZ,VZ,VQ,UQ,U Q,UQ,UVVQ,U,ZQ,U,Z Z,V* ZZZZ VVZZ Q,U,Z* *V,ZV,ZQ,U,ZQ,U,Z ZZZZZZ 其中其中 0 表示初态， 表示初态，* *表示终态表示终态 替换后的矩阵替换后的矩阵 0 01 1 0 00 01 12 2 1 13 32 2 2 24 45 5 3* 6 66 6 4 46 6 5* 3 35 5 6 66 66 6 构造构造 DFADFA 状态转换图（略）状态转换图（略） 4 4 （1 1）解）解 构造状态转

8、换矩阵：构造状态转换矩阵： a ab b 000* 0* 0,10,111 0,10,1* *0,10,111 1100 转换为转换为 a ab b 0 0* *1 12 2 1 1* *1 12 2 2 20 0 22，33 00，11 22，3a=0,33a=0,3 2,3,0,12,3,0,1 0,1a=1,10,1a=1,1 0,1b=2,20,1b=2,2 （2 2）解：首先把）解：首先把 M M 的状态分为两组：终态组的状态分为两组：终态组00，和非终态组，和非终态组11，2 2，3 3，4,54,5 此时此时 G=(G=( 0,0, 1,2,3,4,51,2,3,4,5 ) )

9、1,2,3,4,51,2,3,4,5a a=1,3,0,5=1,3,0,5 1,2,3,4,51,2,3,4,5b b=4,3,2,5=4,3,2,5 由于由于44a a=0=0 1,2,3,51,2,3,5a a=1,3,5=1,3,5 因此应将因此应将1,2,3,4,51,2,3,4,5划分为划分为4,1,2,3,54,1,2,3,5 G=(041,2,3,5)G=(041,2,3,5) 1,2,3,51,2,3,5a a=1,3,5=1,3,5 1,2,3,51,2,3,5b b=4,3,2=4,3,2 因为因为1,51,5b b=4=4 2323b b=2,3=2,3 所以应将所以应将

10、1,2,3,51,2,3,5划分为划分为1,52,31,52,3 G=(01,52,34)G=(01,52,34) 1,51,5a a=1,5=1,5 1,51,5b b=4=4 所以所以1,51,5 不用再划分不用再划分 2,32,3a a=1,3=1,3 2,32,3b b=3,2=3,2 因为因为 22a a=1=1 33a a=3=3 所以所以2,32,3应划分为应划分为2323 所以化简后为所以化简后为 G G（ 0,2,3,4,1,50,2,3,4,1,5） 7.7.去除多余产生式后，构造去除多余产生式后，构造 NFANFA 如下如下 S A B D Q Z a b b a b b

11、 b a b a b 确定化，构造确定化，构造 DFADFA 矩阵矩阵 a ab b S SA AQ Q A AA AB,ZB,Z B,ZB,ZQ QD D Q QQ QD,ZD,Z D DA AB B D,ZD,ZA AD D B BQ QD D 变换为变换为 a ab b 0 00 01 13 3 1 11 12 2 2 2* *3 34 4 3 33 35 5 4 41 16 6 5 5* *1 14 4 6 63 34 4 化简：化简： G=(0,1,3,4,6),(2,5)G=(0,1,3,4,6),(2,5) 0,1,3,4,6a=1,30,1,3,4,6a=1,3 0,1,3,4

12、,6b=2,3,4,5,60,1,3,4,6b=2,3,4,5,6 所以将所以将0,1,3,4,60,1,3,4,6划分为划分为 0,4,61,30,4,61,3 G=(0,4,6),(1,3),(2,5)G=(0,4,6),(1,3),(2,5) 0,4,6b=3,6,40,4,6b=3,6,4 所以所以 划分为划分为0,4,60,4,6 G=(0),(4,6),(1,3),(2,5)G=(0),(4,6),(1,3),(2,5) 不能再划分，分别用不能再划分，分别用 0 0，4 4，1 1，2 2 代表各状态，构造代表各状态，构造 DFADFA 状态转换图如下；状态转换图如下； 01 4

13、a,b a a b ba b 2 8 8代入得代入得 S S = = 0(1S|1)|0(1S|1)| 1(0S|0)1(0S|0) = = 01(S|)01(S|) | | 10(S|)10(S|) = = (01|10)(S|)(01|10)(S|) = = (01|10)S(01|10)S | | (01|10)(01|10) = = (01|10)(01|10)* *(01|10)(01|10) 构造构造 NFANFA S A B Z 0 1 0 1 1 0 由由 NFANFA 可得正规式为可得正规式为(01|10)(01|10)* *(01|10)=(01|10)(01|10)=(0

14、1|10)+ + 9.9.状态转换函数不是全函数状态转换函数不是全函数, ,增加死状态增加死状态 8,8, G=(1,2,3,4,5,8),(6,7)G=(1,2,3,4,5,8),(6,7) (1,2,3,4,5,8)(1,2,3,4,5,8)a a=(3,4,8)=(3,4,8) (3,4)(3,4)应分出应分出 (1,2,3,4,5,8)(1,2,3,4,5,8)b b=(2,6,7,8)=(2,6,7,8) (1,2,3,4,5,8)(1,2,3,4,5,8)c c=(3,8)=(3,8) (1,2,3,4,5,8)(1,2,3,4,5,8)d d=(3,8)=(3,8) 所以应将所以

15、应将(1,2,3,4,5,8)(1,2,3,4,5,8)分为分为(1,2,5,8),(1,2,5,8), (3,4)(3,4) G=(1,2,5,8),(3,4),(6,7)G=(1,2,5,8),(3,4),(6,7) (1,2,5,8)a=(3,4,8)(1,2,5,8)a=(3,4,8) 8 8 应分出应分出 (1,2,5,8)b=(2,8)(1,2,5,8)b=(2,8) (1,2,5,8)c=(8)(1,2,5,8)c=(8) (1,2,5,8)d=(8)(1,2,5,8)d=(8) G=(1,2,5),(8),(3,4),(6,7)G=(1,2,5),(8),(3,4),(6,7)

16、 (1,2,5)a=(3,4,8)(1,2,5)a=(3,4,8) 5 5 应分出应分出 G=(1,2),G=(1,2), (3,4),5,(3,4),5, (6,7)(6,7) ,(8),(8) 去掉死状态去掉死状态 8,8, 最终结果为最终结果为 (1,2)(1,2) (3,4)(3,4) 5,(6,7)5,(6,7) 以以 1,3,5,61,3,5,6 代替代替, ,最简最简 DFADFA 为为 13 a c b b da 5 6 b 正规式正规式:b:b* *a(da|c)a(da|c)* *bbbb* * 第五章第五章 1. S-a | |( T ) T - T , S | S (a

17、,(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 )

18、, 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 , S T - S 消除直接左递归：消除直接左递归： S-a | |(

19、 T ) T - S T T - , S T | SELECT ( S-a) = a SELECT ( 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 T T - - , S T 分析符号串分析符号串 （ a , a ）# 分析栈分析栈 剩余输入串剩余输入串 所用产生式所用产生式 #

20、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- 非终结符名非终结符名

21、是否是否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，

22、） 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 ,

23、 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) ) FO

24、LLOW ( 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

25、 ( M ) = d， e , # , o SELECTSELECT ( ( M M - b b L L M M )=)= b b 构造构造 LL( 1 ) 分析表分析表 abedfo# S- a- M H- M H- M H- M H- M H H-L S o - K - - d M L - L- e H f M- b L M-K-K-K-K 4 . 文法含有左公因式，变为文法含有左公因式，变为 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- $ ,

26、 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-B- C CB-B- C C a 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否否

27、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) = a FIRST(D) = FIRST（E）= if FIRSR(D) = else , FIRST(E) = FIRST(F) = if FIRST(F) = if FOLLOW(S) = # FOLLOW(A) = end FOLLOW(A) = end FOLLOW(B) = ; , end FOLLOW (C) = ;

28、 , 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 end A- B A- B A A - - ; B A B- D- C C- a D- E D D- else B D - E-FC F-if b then 6. 1. (1) S - A | B (2) A - aA|a (3)B - bB |b

29、提取提取 （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|a 4 (1)S-i|(E) (2)E-E+S|E-S|S 提取（提取（2）左公因子）左公因子 (1) S-i|(E) (2) E-SE

30、 (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-Abb 4)B-a 将将 1） 、2)式代入式代入 3

31、）式）式 1)A-baB 2)A- 3)B-baBbb 4)B-bb 5)B-a 提取提取 3） 、4）式左公因子）式左公因子 1)A-baB 2)A- 3)B-bB 4)B-aBbb | b 5)B-a (3) 1)S-Aa 2)S-b 3)A-SB 4)B-ab 将将 3）式代入）式代入 1）式）式 1)S-SBa 2)S-b 3)A-SB 4)B-ab 消除消除 1）式直接左递归）式直接左递归 1)S-bS 2)S-BaS | 3)S-b 4)A-SB 5)B-ab 删除多余产生式删除多余产生式 4） 1)S-bS 2)S-BaS | 3)S-b 4)B-ab （5） 1)S-Ab 2)

32、S-Ba 3)A-aA 4)A-a 5)B-a 提取提取 3） 4）左公因子）左公因子 1)S-Ab 2)S-Ba 3)A-aA 4)A- A | 5)B-a 将将 3）代入）代入 1） 5）代入）代入 2 1)S-aAb 2)S-aa 3)A-aA 4)A- A | 5)B-a 提取提取 1） 2） 左公因子左公因子 1)S- aS 2)S-Ab | a 3)A-aA 4)A- A | 5)B-a 删除多余产生式删除多余产生式 5） 1)S- aS 2)S-Ab | a 3)A-aA 4)A- A | A A S S 将将 3）代入）代入 4） 1)S- aS 2)S-Ab | a 3)A-

33、aA 4)A- aA | 将将 4）代入）代入 2） 1)S- aS 2)S-aAb 3)S-a 4)S-b 5)A-aA 6)A- aA | 对对 2）3)提取左公因子提取左公因子 1)S-aS 2)S-aS 3)S-Ab| 4)S-b 5)A-aA 6)A- aA | 删除多余产生式删除多余产生式 5） 1)S-aS 2)S-aS 3)S-Ab| 4)S-b 5)A- aA | 第六章第六章 1 1 S S a a | | | | ( ( T T ) ) T T T T , , S S | | S S 解：解：(1)(1) 增加辅助产生式增加辅助产生式 SSS S 求求 FIRSTVTFI

34、RSTVT 集集 FIRSTVTFIRSTVT（SS ） # FIRSTVTFIRSTVT（S S） aa ( ( a a ( ( FIRSTVTFIRSTVT (T)(T) , FIRSTVT(FIRSTVT( S S ) ) = = , , a a ( ( 求求 LASTVTLASTVT 集集 LASTVTLASTVT（SS ） # # LASTVTLASTVT（S S） a a ) LASTVTLASTVT (T)(T) , , a a ) (2) 算符优先关系表算符优先关系表 a (),# a ( = , # = 因为任意两终结符之间至多只有一种优先关系成立，所以是算符优先文法因为任意

35、两终结符之间至多只有一种优先关系成立，所以是算符优先文法 (3) a (),# F 1 1 1 1 1 1 g 1 1 1 1 1 1 f22 132 1 g22 21 2 1 f33 133 1 g44 41 2 1 f33 133 1 g44 41 2 1 (4) 栈栈 优先关系优先关系 当前符号当前符号 剩余输入串剩余输入串 移进或规约移进或规约 ( a,a)# 移进移进 ( ,a)# 规约规约 (T , a)# 移进移进 (T， ) #规约规约 (T,T)# 规约规约 (T = )# 移进移进 (T) 规约规约 T=接受接受 4.扩展后的文法扩展后的文法 S#S# SS;G SG GG

36、(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 , ) 构造算符优先关系表构造算符优先关系表 ;(

37、)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） 栈栈优先关系优先关系当前符号当前符号剩余输入串剩余输入串移进或规约移进或规约 a a T T T T； T T；（；（ T T；

38、（；（a a T T；（；（T T T T；（；（T T T T；（；（T Ta a T T；（；（T TT T T T；（；（T T T T；（；（T T） T T；T T T T a a ； ； （ a a a a ） ） ） ；（；（a aa a） （a aa a） （a aa a） a aa a） a a） a a） a a） ） 移进移进 规约规约 移进移进 移进移进 移进移进 规约规约 移进移进 移进移进 规约规约 规约规约 移进移进 规约规约 规约规约 接受接受 分析分析 a；（；（aa） 栈栈优先关系优先关系当前符号当前符号剩余输入串剩余输入串移进或规约移进或规约 （ （a a

39、 （T T （T T （T Ta a （T TT T （T T （T T） T T ( ( a a a ） ） ） a aa a） a a） a a） a a） ） 移进移进 移进移进 规约规约 移进移进 移进移进 规约规约 规约规约 移进移进 规约规约 接受接受 （4） 不能用最右推导推导出上面的两个句子。不能用最右推导推导出上面的两个句子。 第七章第七章 1 1、已知文法：、已知文法： A A aAd|aAb|aAd|aAb| 判断该文法是否是判断该文法是否是 SLRSLR（1 1）文法，若是构造相应分析表，并对输入串）文法，若是构造相应分析表，并对输入串 ab#ab#给出分析过程。给出分

40、析过程。 解：解：(0) A A (1) A aAd (2) A aAb (3) A 构造该文法的活前缀 DFA： I0： A A A aAd A aAb A 由上图可知该文法是 SLR（1）文法。 构造 SLR（1）的分析表： ACTIONACTIONGOTOGOTO 状态状态 a ad db b# #A A 0 0S2S2R3R3R3R3R3R31 1 1 1accacc 2 2S2S2R3R3R3R3R3R33 3 3 3S4S4S5S5 4 4R1R1R1R1R1R1 5 5R2R2R2R2R2R2 输入串 ab#的分析过程： 步骤步骤状态栈状态栈符号栈符号栈输入串输入串 ACTION

41、ACTIONGOTOGOTO 1 10#ab#S2 2 202#ab#R33 3 3023#aAb#S5 4 40235#aAb#R21 5 501#A#acc 3 3、考虑文法：、考虑文法： S S AS|bAS|b ASA|aASA|a (1)(1)列出这个文法的所有列出这个文法的所有 LRLR（0 0）项目）项目 (2)(2)按（按（1 1）列出的项目构造识别这个文法活前缀的）列出的项目构造识别这个文法活前缀的 NFANFA，把这个，把这个 NFANFA 确定化为确定化为 DFADFA，说明这个，说明这个 DFADFA 的所有状态全体构成这个文法的的所有状态全体构成这个文法的 LRLR（

42、0 0）规范族。）规范族。 (3)(3)这个文法是这个文法是 SLRSLR 的吗？若是，构造出它的的吗？若是，构造出它的 SLRSLR 分析表。分析表。 (4)(4)这个文法是这个文法是 LALRLALR 或或 LRLR（1 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： a I0： SS S AS S b A SA A a I1： S S A SA A SA A a S AS S b SI

43、3： A SA S AS S AS S b A SA A a I5： S AS A SA A SA A a S AS S b I2： S AS S AS S b A SA A a I4： A SA A SA A a S AS S b I6： S b I7： A a A A S AA S A S AS S b a b b b b a a aa a b 由上可知：I1 I3 I5 中存在着移进和归约冲突 在 I1中含项目：S S 归约项 Follow(S)=# A a 移进项 Follow(S)a= S b 移进项 Follow(S)b= 在 I3中含项目：A SA 归约项 Follow(A)=a

44、,b S b 移进项 Follow(A) b A a 移进项 Follow(A) a 在 I5中含项目：S AS 归约项 Follow(S)=#,a,b A a 移进项 Follow(S) a S b 移进项 Follow(S) b 由此可知，I3、I5 的移进与归约冲突不能解决，所以这个文法不是 SLR（1）文法。 （4）做 LR（1）项目集规范族 I1： S S ,# A SA ,a/b A SA ,a/b A a ,a/b S AS ,a/b S b ,a/b I0： SS ，# S AS ，a/b/# S b ,a/b/# A SA ,a/b A a ,a/b I2： S AS ,a/

45、b/# S AS ,a/b/# S b ,a/b/# A SA ,a/b A a ,a/b 由上可知该文法不是 LR（1）文法，也不是 LALR（1）文法。 5 5、一个类、一个类 ALGOLALGOL 的文法如下：的文法如下： Statement Block; Blockheadbeginbegin d d Block;dhead;d SS endend S;S; CompoundStatementbeginbegin 试构造其试构造其 LRLR（0 0）分析表。）分析表。 解：解：设=A =B =C =D =E AB AC BD；E Dbegin d DD;d Es end Es;E Cb

46、egin E (0)A A (1) AB (2)AC (3)BD;E (4) Dbegin d (5) DD;d (6) Es end (7) Es;E (8) Cbegin E 构造该文法的活前缀 DFA： I3： S b ,a/b/# I4： A a ,a/b/# I5：(I1-A-) A SA ,a/b S AS ,a/b S AS ,a/b S b ,a/b A SA ,a/b A a ,a/b I6：(I1-S-) A SA ,a/b A SA ,a/b A a ,a/b S AS ,a/b S b ,a/b I7：(I2-S-) S AS ,a/b/# A SA ,a/b/# A

47、SA ,a/b A a ,a/b S AS ,a/b S b ,a/b I0： AA AB AC BD；E Cbegin E Dbegin d DD;d I4： BD；E DD； d I5： Cbegin E Dbegin d ES end ES;E I13： ES；E ESend ES；E I14： ES；E I11： DD； d I10： BD； E I1： A A I2： AB I3： AC I8： Cbegin E I9： Dbegin d A D beginbegin BC Ed E ； d S S； E I112： ES end end 构造 LR（0）分析表： ACTIONACT

48、IONGOTOGOTO 状状 态态 beginbegin ； d dS Sendend# #A AB BC CD DE E 0 0S5S51 12 23 34 4 1 1accacc 2 2R1R1R1R1R1R1R1R1R1R1R1R1 3 3R2R2R2R2R2R2R2R2R2R2R2R2 4 4S6S6 5 5S9S9S7S78 8 6 6S11S11S7S71010 7 7S13S13S12S12 8 8R8R8R8R8R8R8R8R8R8R8R8R8 9 9R4R4R4R4R4R4R4R4R4R4R4R4 1010R3R3R3R3R3R3R3R3R3R3R3R3 1111R5R5R5

49、R5R5R5R5R5R5R5R5R5 I6： BD；E DD；d ES end ES;E S I7： ESend ES；E 1212R6R6R6R6R6R6R6R6R6R6R6R6 1313S7S71414 1414R7R7R7R7R7R7R7R7R7rR7rR7R7 6 6、文法、文法 G=G=（UU，T T，SS，a,b,c,d,e,P,Sa,b,c,d,e,P,S）其中）其中 P P 为：为： SUTa|TbSUTa|Tb TS|Sc|dTS|Sc|d UUS|eUUS|e （1 1）判断判断 G G 是是 LRLR（0 0） ，SLRSLR（1 1） ，LALRLALR（1 1）还是）

50、还是 LRLR（1 1） ，说明理由。，说明理由。 （2 2）构造相应的分析表。构造相应的分析表。 解：解：（0）SS (1)SUTa (2)STb (3)TS (4) TSc (5)Td (6)UUS (7)Ue 首先做 LR（0）分析： I0：SS SUTa STb UUS Ue TS TSc Td I1:SS TSc （I1 产生移进规约冲突，但 Follow（S ） c= 可以用 SLR（1）解决） I2: SUTa UUS SUTa STb UUS Ue TS TSc Td I3: ST.b I4: Ue I5:Td I6:TSc I7:SUTa STb I8:UUS TS TSc

51、产生移进规约喝规约规约冲突 Follow(U)=d,e Follow(T)=a,b 可以用 SLR（1）的方法解决 I9: SUTa I10: STb 所以该文法是所以该文法是 SLRSLR（1 1）文法，也是）文法，也是 LALRLALR（1 1）文法，）文法，LRLR（1 1）文法。）文法。 构造 SLR（1）分析表： ACTIONGOTO状态状态 abcde#SUT 0S12S11123 1S6acc 2S5S4827 3S10 4R7R7 5R5R5 6R4R4 7S9S10 8R3R3S6R6R6 9R1R1R1R1 10R2R2R2R2 7 7 证明下面文法不是证明下面文法不是 L

52、RLR（0 0）但是）但是 SLRSLR（1 1） 。 SASA AAb|bBaAAb|bBa BaAc|a|aAbBaAc|a|aAb 证明：证明：（0）S S (1)SA (2)AAb (3)AbBa (4)BaAc (5) Ba (6)BaAb 构造该文法的活前缀 DFA： 在 I2项目集中含有：SA 归约项 Follow(S)=# AAb 移进项 Follow(S)b= 在 I4项目集中含有：Ba 归约项 Follow(B)=a AbBa 移进项 Follow(B)b= 在 I9 项目集中有 BaAb 规约项 Follow(B)=a AAb 规约项 Follow(A)=b,c,# Fo

53、llow(B) Follow(A)= 文法的冲突项可以用 SLR（1）文法来解决，所以该文法是 SLR（1）文法，不是 LR（0）文法。 1111、设文法、设文法 GSGS为：为： SAS|SAS| AaA|bAaA|b （1 1）证明证明 GSGS是是 LRLR（1 1）文法；）文法； （2 2）构造它的构造它的 LRLR（1 1）分析表；）分析表； （3 3）给出输入符号串给出输入符号串 abab#abab#的分析过程。的分析过程。 解：解： （0）SS (1)SAS (2) S (3)AaA (4)Ab 证明： 构造该文法的活前缀 DFA： S I0： SS SA AAb AbBa I2： SA AAb I3： AbBa BaAc Ba BaAb I1： S S I4： BaAc Ba BaAb AAb AbBa I7： AAb I5： AbBa I6： BaAc BaAb AAb I10： BaAc I9： BaAb AAb I8： AbBa S A b b B a a b A c b I0： SS ，# SAS ，# S ，# AaA ，a/b/#