蒋立源编译原理第三版-习题与答案

1、第五章习题5-1设有文法GS：S-A/A-*aA I AS | /(1) 找出部分符号序偶间的简单优先关系。(2) 验证GS不是简单优先文法。5-2对于算符文法GS：S-E EE-T I T T-T*F I F F-P I P P-(E) I i(1) 找出部分终结符号序偶间的算符优先关系。(2) 验证GS不是算符优先文法。5-3设有文法L E：E-Ei Ei-Ei+Ti|Ti TlT T-T*F F F-(E) | i其相应的简单优先矩阵如题图5-3所示，试给出对符号串(i+i)进行简单优先分析的 过程。题图5-3文法G E的简单优先矩阵5-4设有文法GE：E-E+T|TT-T*F|FF-

2、(E) | i其相应的算符优先矩阵如题图5-4所示。试给出对符号串(i+i)进行算符优先分析的 过程。(+)#(C*+)# 题图5-4文法GE的算符优先矩阵5-5对于下列的文法，试分别构造识别其全部可归前缀的DFA和LR(O)分析表，并 判断哪些是LR(O)文法。(1) S-*aSb I aSc I ab(2) S-aSSb I aSSS I c(3) S-AA-Ab I a5-6下列文法是否是SLR(l)文法若是，构造相应的SLR(l)分析表，若不是，则阐 明其理由。(1) Sf Sab | bRRf S I a(2) S-aSAB | BAA-aA | BB-b(3) S-aA I bBA

3、cAd 1 B-cBdd |5-7对如下的文法分别构造LR(O)及SLR(l)分析表，并比较两者的异同。S-cAd | b AASc I a5-8对于文法GS：S-AA-BA | eB-aB I b(1) 构造LR(1)分析表；(2) 给出用LR(1)分析表对输入符号串abab的分析过程。5-9对于如下的文法，构造LR(1)项目集族，并判断它们是否为LR(1)文法。(1) S-AA-AB | eB-aB I b(2) S-*aSa I a第4章习题答案25-1 解：(1)由文法的产生式和如答案图5-1 (a)所示的句型A/a/的语法树，可得G中 的部分优先关系如答案图5-1 (b)所示。(2)

4、由答案图5-1(b)可知，在符号A和/之间，即存在等于关系，又存在低于关系, 故文法GS不是简单优先文法。5-2 解:(1) 由文法GS的产生式可直接看出:此外，再考察句型一P一一 (E)和i*(T*F)的语法树(见答案图5-2(a)及(b)。由答案图5-2(a)可得：- - , - - , - (由答案图5-2(b)可得：i * ,* ( ,( * ,* )(2) 由答案图5-2(a)可知，在终结符号一和一之间，存在两种算符优先关系:故文法GS不是算符优先文法。5-3解：对符号串(iH)进行简单优先分析的过程如答案表5-3所示。因为分析成功，所以符号串(i+i)是文法G E的合法句子。答案表

5、5-3符号串(i+i)的筒单优先分析过程步骤分析栈关系当前符号余留输入串句柄所用产生式0#低于(i+i)#1#(低于12#(i优于+:二1F-i3#(F优于+2FT-F4#(T优于+i)3TsTlT5#Cn优于+i)tiTt6#(E|等于+i)37#(Ei+低于18#(Ei+i优于)1F-i9#(Ei+F优于#FT-F10#(Ei+T优于)TTlT11#(Et+Ti优于) Ei+TiElEH12#(Ei优于)E,E-E,13#(E等于)#14#(E)优于(E)F- (E)15#F优于FT-F16#T优于TTlT17#T,优于TiElTi18#Ei优于E,E-Ei19#E优于I分析成功5-4解：

6、对符号串（i+i）进行算符优先分析的过程如答案表5-4所示。 因为分析成功，所以符号串（i+i）是文法GE的合法句子。句子（i+i）及其分析过程中所得句型的语法树如答案图5-4所示。答案表5-4符号串（i+i）的算符优先分析过程步骤分析栈当前栈顶终结符号优先关系当前输入符号余留输入串最左素短语0#(i+i)#1#(1+i)#2#(i+i)#3#(F(+i)#%4#(F+1)#5# (F+l)#6Bn (f+f+)#F+F7#(E()#8#(E)#(E)9#F#分析成功5-5 解:(1) 在文法GS中引入一个新的开始符号S,且将S -S作为第0个产生式添 加到文法G中，从而得到G的拓广文法L S

7、：9 f Sf aScf aSb ab识别文法GS全部可归前缀的DEA如答案图5-5-( 1)所示。因为文法GS的每个LR(O)项目集中都不含冲突项目，所以文法GS是LR(O)文法, 故可构造出不含冲突动作的LR(O)分析表如答案表5-5-(!)所示。答案表5-5-(1)文法GS的LR(O)分析表状态ACTIONGOTOabcS0a11S2acc233s.：s.4SfiI5r3r3r：6rririri(2) 在文法GS中引入一个新的开始符号S,且将S -S作为第0个产生式添 加到文法G中，从而得到G的拓广文法G S：，_S-aSSSf aSSb c识别文法GS全部可归前缀的DFA如答案图5-5

8、-(2)所示。因为文法GS的毎个LR(O)项目集中都不含冲突项目，所以文法GS是LR(O)文法, 故可构造出不含冲突动作的LR(O)分析表如答案表5-5-(2)所示。答案表5-5-(2)文法GS的LR(O)分析表状态ACTIONGOTOab(S0、：s11acc2s2 -14(3r：r：r：.4S2S355S376ririri7(3) 在文法GS中引入一个新的开始符号S,且将S -S作为第0个产生式添 加到文法G中，从而得到G的拓广文法G S：-AbA-*a识别文法GS全部可归前缀的DFA如答案图5-5-(3)所示。因为在LR(O)项目集R中含有移进-归约冲突项目，所以文法GS不是LR (0)

9、文法, 故构造出的LR(0)分析表中含有冲突动作。文法GS的LR(0)分析表如答案表5-5-(3) 所示。答案表5-5-(3)文法GS的LR(0)分析表状态ACTIONGOTO1 abSA0s121)acc2ririir3Sir33r：-4r25-6 解:(1)在文法GS中引入一个新的开始符号S,且将S -S作为第0个产生式添加到文法G中，从而得到G的拓广文法G S：f s-sSab2. S-bR识别文法GS全部可归前缀的DFA如答案图5-6-( 1)所示。由答案图5-6-( 1)可知，在项目集L和I,中都存在移进-归约”冲突。在项目集 I = R-*S , S-S ab 中.由于 FOLLO

10、R(R)=a, FOLLOR(R) n a = a =#=,所以其项 目集的“移进-归约”冲突不可能通过SLR(l)规则得到解决，从而该文法不是SLR(l)文 法。(2)在文法GS中引入一个新的开始符号S,且将S -S作为第0个产生式添 加到文法G中，从而得到G的拓广文法G S：f Sf aA-aS AB-B-BA- b识别文法GS全部可归前缀的DFA如答案图5-6-(2)所示。答案图5-6-(2)识别GS全部可归前缀的DFA因为文法GS的毎个LR(O)项目集中都不含冲突项目，所以文法GS是LR(O)文法, 故也是SLR(l)文法。因为 FOLLOW (S) = a, b,#)t FOLLOW

11、 (A) = (a, b,#, FOLLOW (B) = a, b,#,所以文法 GS的SLR(l)分析表如答案表5-6-(2)所示。答案表5-6-(2)文法GS的SLR(l)分析表ACTIONGOTO状态abSAB0S2131acc(3) 在文法GS中引入一个新的开始符号S，且將S -S作为第0个产生式添 加到文法G中，从而得到G的拓广文法G S：f S aA cBdd-bBe3. A-cAd识别文法GS全部可归前缀的DFA如答案图5-6-(3)所示。由答案图5-6- (3)可知，在项目集I2,L5和1$中都存在“移进-归约”冲突。因为在项目集L和Is中，由于FOLLOR= df#, FOL

12、LOR(A) n c=,所以其项目集的“移进-归约”冲突能通过SLR(l)规则得到解决；又因为在项目集h和19中，由于FOLLOR(B) = d,#), FOLLOR(B) n c=,所以其项目集的“移进-归约”冲突也能通过SLR(l)规则得到解决；所以文法GS是SLR(l)文法。因为 FOLLOR (S) = #, FOLLOR (A) = d,#, FOLLOR (B) = d,#,所以文法 GS的 SLR (1) 分析表如答案表5-6-(3)所示。答案表5-6-(3)文法GS的SLR(l)分析表ACTIONGOTO状态abc)#SABd0S2S：j-11iacc2-j!S9ri483re

13、n.4ri5S5门r.-6c6s；7i-r8匚9S9r1010r6?V11Sil12rs5-7解：在文法GS中引入一个新的开始符号S,且将S -S作为第0个 产生式添加到文法G中，从而得到G的拓广文法G S：ASccAd-b识别文法GS全部可归前缀的DFA如答案图5-7所示。因为文法GS的每个LR(O)项目集中都不含冲突项目，所以文法GS是LR(O)文法。 文法GS的LR(O)分析表如答案表5-7-(a)所示。答案表5-7- (a)文法G S的LR (0)分析表状态ACTIONGOTObcdftSA0S311s.acc25Si匚r23r2rr.r；4r.厂：riSa5S3S2r|:76riPi

14、ri(r(7Sb8r：j厂:r.rrs因为 FOLLOR(S) = #,c, FOLLOR(A) = b,c,dt 所以文法 GS的 SLR(l)分析表如答 案表5-7-(b)所示。答案表5-7-(b)文法GS的SLR(l)分析表状态ACTIONGOTOabcd#SAS3S210acc1Si52rX3r.s4S3!f.51S2S76riri7Sbr1-8两个表的相同之处为：(1) 两个表的GOTO表部分完全相同。(2) 在两个表的ACTION表中，不含归约项目的项目集对应的行的元素完全相同， 即第0,2,5,7行完全相同。Y两个表的不同之处为：在两个表的ACTION表中，含有归约项目的项目集对

15、应的行的元素不同，即第3,4,6,8行的元素不同。以第3行为例，答案表5-7-(a)中的所有元素都为“；而在答 案表5-7-(b)中，因为FOLLOR(S)打#.c,故仅在和“c”列对应的元素为“。5-8 解:(1)在文法GS中引入一个新的开始符号S，且将S -S作为第0个产生式添加到文法G中，从而得到G的拓广文法L S：Sf -ATA文法GS的LR(1)项目集及DFA如答案图5-8所示。文法GS的LR(1)分析表如答案表5-8-(1)所示。答案表5-8-(1)文法GS的LR(1)分析表状态ACTIONGOTOab#SAB0SiS5rn1231acc2ri3Sir364Sis535fr5r-,

16、76r27FiVi(2)用LR(1)分析表对输入符号串abab的分析过程如答案表5-8-(2)所示。因为 分析成功，所以符号串abab是文法GS的合法句子。答案表5-8-(2)符号串abab的LR分析过程步骤状态栈符号栈余留输入串分析动作下一状态1Io#abab#s：42IoL#abab#S553lollls#abab#GOTO L ,B=74Iolib#aBab#r.GOTO L ,B=35IoL#Bab#Si46luIJi#Bab#S557I0I3I1I5#Bab# GOTOI ,B=78luI.I.I；#BaB#IGOTOEL tB=39I0I3I3rGOTOEL ,A=610I0I3I3I6#BBA#G()TOI3 ,A二611IoIsIb#BAGOTO Io ,Al=212IoL#A#FiGOTO Io ,S=113loll#Sacc5-9 解:(1)在文法GS中引入一个新的开始符号S,且将S -S作为第0个产生式添 加到文法G中，从而得到G的拓广文法L S：f Sf A aB-AB-b文法GS的LR(1)项目集及DEA如答案图5-9-( 1)所示。文法GS的LR(1)分析表如答案表5-9-(1)所示。因为分析表中不含多重定义的元 素，所以文法GS是LR(1)文法。答案表5-9-(1)文法GS的LR(1)分析表状态ACTIONGOTOabSAB0r3r：；121acc3