蒋立源编译原理第三版第四章习题

1、蒋立源编译原理第三版第四章习题及答案蒋立源编译原理第三版第四章习题及答案15/15蒋立源编译原理第三版第四章习题及答案第五章习题5-1设有文法GS：SA/AaAAS/找出部分符号序偶间的简单优先关系。考证GS不是简单优先文法。5-2关于算符文法GS：SEEE-TTTT*FFF-PPP(E)i找出部分终结符号序偶间的算符优先关系。考证GS不是算符优先文法。5-3设有文法GE：EEEE+T|T1TTTT*F|FF(E)|i11111其相应的简单优先矩阵如题图5-3所示，试给出对符号串（i+i）进行简单优先剖析的过程。题图5-3文法GE的简单优先矩阵5-4设有文法GE：EE+T|TTT*F|FF(E

2、)|i其相应的算符优先矩阵如题图5-4所示。试给出对符号串（i+i）进行算符优先剖析的过程。(i*+)#(i*+)#题图5-4文法GE的算符优先矩阵5-5关于以下的文法，试分别结构辨别其所有可归前缀的DFA和LR(0)剖析表，并判断哪些是LR(0)文法。SaSbaScabSaSSbaSSScSAAAba5-6以下文法是不是SLR(1)文法？假如，结构相应的SLR(1)剖析表，若不是，则说明其原因。(1)SSabbRRSa(2)SaSABBAAaABBb(3)SaAbBAcAdBcBdd5-7对以下的文法分别结构LR(0)及SLR(1)剖析表，并比较二者的异同。ScAdbAASca5-8关于文法

3、GS:SAABABaBb结构LR(1)剖析表；(2)给出用LR(1)剖析表对输入符号串abab的剖析过程。5-9关于以下的文法，结构LR(1)项目集族，并判断它们能否为LR(1)文法。(1)SAAABBaBb(2)SaSaa第4章习题答案25-1解：(1)由文法的产生式和如答案图5-1(a)所示的句型Aa的语法树，可得G中的部分优先关系如答案图5-1(b)所示。由答案图5-1(b)可知，在符号A和/之间，即存在等于关系，又存在低于关系，故文法GS不是简单优先文法。5-2解：由文法GS的产生式可直接看出：=）别的，再观察句型P(E)和i*(T*F)的语法树(见答案图5-2(a)及(b)。由答案图

4、5-2(a)可得：,(由答案图5-2(b)可得：i*,*(,(*,*）由答案图5-2(a)可知，在终结符号和之间，存在两种算符优先关系：,故文法GS不是算符优先文法。5-3解：对符号串(i+i)进行简单优先剖析的过程如答案表5-3所示。因为剖析成功，因此符号串(i+i)是文法GE的合法句子。答案表5-3符号串(i+i)的简单优先剖析过程目前余留所用步骤剖析栈关系符号输入串句柄产生式0#低于（i+i)#1#(低于i+i)#2#(i优于+i)#iFi3#(F优于+i)#FTF4#(T优于+i)#TT1T5#(T1优于+i)#T1E1T16#(E1等于+i)#7#(E1+低于i)#8#(E1+i优于

5、)#iFi9#(E1+F优于)#FTF10#(E1+T优于)#TT1T11#(E1+T优于)#E+TEE+T11111112#(E1优于)#E1EE113#(E等于)#14#(E)优于#(E)F(E)15#F优于#FTF16#T优于#TT1T17#T1优于#T1E1T118#E优于#EEE11119#E#剖析优于成功5-4解：对符号串(i+i)因为剖析成功，因此符号串进行算符优先剖析的过程如答案表(i+i)是文法GE的合法句子。5-4所示。句子(i+i)及其剖析过程中所得句型的语法树如答案图5-4所示。答案表5-4符号串（i+i)的算符优先剖析过程目前栈顶步骤剖析栈终结符号0#1（#(2i#(

6、i3(#(F4+#(F+5#(F+ii6+#(F+F7#(E(8)#(E)优先目前输余留最左关系入符号输入串素短语（i+i)#i+i)#+i)#i+i)#i)#)#i)#F+F)#(E)剖析9#F#成功5-5解：(1)在文法GS中引入一个新的开始符号S，且将SS作为第0个产生式添加到文法G中，进而获得G的拓广文法GS：SaScaSbab辨别文法GS所有可归前缀的DFA如答案图5-5-(1)所示。因为文法GS的每个LR(0)项目集中都不含矛盾项目，因此文法GS是LR(0)文法，故可结构出不含矛盾动作的LR(0)剖析表如答案表5-5-(1)所示。答案表5-5-(1)文法GS的LR(0)剖析表ACT

7、IONGOTO状态abc#S0s211acc2s2s433s5s64r3r3r3r35r1r1r1r16r2r2r2r2(2)在文法GS中引入一个新的开始符号S，且将SS作为第0个产生式添加到文法G中，进而获得G的拓广文法GS：SaSSSaSSbc辨别文法GS所有可归前缀的DFA如答案图5-5-(2)所示。因为文法GS的每个LR(0)项目集中都不含矛盾项目，因此文法GS是LR(0)文法，故可结构出不含矛盾动作的LR(0)剖析表如答案表5-5-(2)所示。答案表5-5-(2)文法GS的LR(0)剖析表状态ACTIONGOTOabc#S0s2s311acc2s2s343r3r3r3r34s2s35

8、5s2s376r1r1r1r17r2r2r2r2(3)在文法GS中引入一个新的开始符号S，且将加到文法G中，进而获得G的拓广文法GS：SAbAa辨别文法GS所有可归前缀的DFA如答案图5-5-(3)SS作为第所示。0个产生式添因为在LR(0)项目集I2中含有移进-归约矛盾项目，因此文法GS不是LR(0)文法，故结构出的LR(0)剖析表中含有矛盾动作。文法GS的LR(0)剖析表如答案表5-5-(3)所示。答案表5-5-(3)文法GS的LR(0)剖析表状态ACTIONGOTOab#SA0s3121acc2r1s4,r1r13r3r3r34r2r2r25-6解：(1)在文法GS中引入一个新的开始符号

9、S，且将SS作为第0个产生式添加到文法G中，进而获得SSabG的拓广文法GS：Sa2.SbR辨别文法GS所有可归前缀的DFA如答案图5-6-(1)所示。由答案图5-6-(1)可知，在项目集I1和I4中都存在“移进-归约”矛盾。在项目集I4=RS,SSab中,因为FOLLOR(R)=a，FOLLOR(R)a=a?，因此其项目集的“移进-归约”矛盾不行能经过SLR(1)规则获得解决，进而该文法不是SLR(1)文法。(2)在文法GS中引入一个新的开始符号S，且将SS作为第0个产生式添加到文法G中，进而获得G的拓广文法GS：辨别文法SaSABBAGS所有可归前缀的aABbDFA如答案图5-6-(2)所

10、示。答案图5-6-(2)辨别GS所有可归前缀的DFA因为文法GS的每个LR(0)项目集中都不含矛盾项目，因此文法GS是LR(0)文法，故也是SLR(1)文法。因为FOLLOW(S)=a,b,#,FOLLOW(A)=a,b,#,FOLLOW(B)=a,b,#,GS的SLR(1)剖析表如答案表5-6-(2)所示。因此文法答案表5-6-(2)文法GS的SLR(1)剖析表状态ACTIONGOTOab#SAB0s2s4131acc2s2s4533s7s4684r5r5r55s7s4986r2r2r27s7s41188r4r4r49s41010r1r1r111r3r3r3(3)在文法GS中引入一个新的开始

11、符号S，且将SS作为第0个产生式添加到文法G中，进而获得G的拓广文法GS：SaAcBddbB3.AcAd辨别文法GS所有可归前缀的DFA如答案图5-6-(3)所示。由答案图5-6-(3)可知，在项目集I2,I3,I5和I9中都存在“移进-归约”矛盾。因为在项目集I2和I5中,因为FOLLOR(A)=d,#，FOLLOR(A)c=?，因此其项目集的“移进-归约”矛盾能经过SLR(1)规则获得解决；又因为在项目集I3和I9中,因为FOLLOR(B)=d,#，FOLLOR(B)c=?，因此其项目集的“移进-归约”矛盾也能经过SLR(1)规则获得解决；因此文法GS是SLR(1)文法。因为FOLLOR(

12、S)=#，FOLLOR(A)=d,#，FOLLOR(B)=d,#，因此文法GS的SLR(1)剖析表如答案表5-6-(3)所示。答案表5-6-(3)文法状态ACTIONabcd0s2s312s5r43s9r645s5r46s77r389s9r610s1111s1212r5GS的SLR(1)剖析表GOTO#SAB1accr44r68r1r46r3r2r610r55-7解：在文法GS中引入一个新的开始符号S，且将SS作为第0个产生式增添到文法G中，进而获得G的拓广文法GS：SASccAdab辨别文法GS所有可归前缀的DFA如答案图5-7所示。因为文法GS的每个LR(0)项目集中都不含矛盾项目，因此文

13、法GS是LR(0)文法。文法GS的LR(0)剖析表如答案表5-7-(a)所示。答案表5-7-(a)文法GS的LR(0)剖析表ACTIONGOTO状态abcd#SA0s3s211acc2s453r2r2r2r2r24r4r4r4r4r45s3s2s676r1r1r1r1r17s88r3r3r3r3r3因为FOLLOR(S)=#,c，FOLLOR(A)=b,c,d，因此文法GS的SLR(1)剖析表如答案表5-7-(b)所示。答案表5-7-(b)文法GS的SLR(1)剖析表ACTIONGOTO状态abcd#SA0s3s211acc2s453r2r24r4r4r45s3s2s676r1r17s88r3

14、r3r3两个表的同样之处为：两个表的GOTO表部分完整同样。在两个表的ACTION表中，不含归约项目的项目集对应的行的元素完整同样，即第0,2,5,7行完整同样。两个表的不一样之处为：在两个表的ACTION表中，含有归约项目的项目集对应的行的元素不一样，即第3,4,6,8行的元素不一样。以第3行为例，答案表5-7-(a)中的所有元素都为r2；而在答案表5-7-(b)中,因为FOLLOR(S)=#,c，故仅在“#”和“c”列对应的元素为r2。5-8(1)加到文法文法解：在文法GS中引入一个新的开始符号S，且将G中，进而获得G的拓广文法GS：SAaBBAbGS的LR(1)项目集及DFA如答案图5-

15、8所示。SS作为第0个产生式添文法GS的LR(1)剖析表如答案表5-8-(1)所示。答案表5-8-(1)文法GS的LR(1)剖析表状态ACTIONGOTOab#SAB0s4s5r31231acc2r13s4s5r3634s4s575r5r5r56r27r4r4r4(2)用LR(1)剖析表对输入符号串abab的剖析过程如答案表5-8-(2)所示。因为剖析成功，因此符号串abab是文法GS的合法句子。答案表5-8-(2)符号串abab的LR剖析过程步骤状态栈符号栈余留输入串剖析动作下一状态1I0#abab#s442II4#abab#s5503I0I4I5#abab#r5GOTOI4,B=74I0I

16、4I7#aBab#r4GOTOI0,B=35I0I3#Bab#s446III4#Bab#s55037IIII5#Bab#r5GOTOI,B=703448I0I3I4I7#BaB#r4GOTOI3,B=39III3#BB#r3GOTOI,A=603310I0I3I3I6#BBA#r2GOTOI3,A=611III6#BA#r2GOTOI,A=203012II2#A#r1GOTOI,S=10013I0I1#S#acc5-9解：(1)在文法GS中引入一个新的开始符号S，且将SS作为第0个产生式添加到文法G中，进而获得G的拓广文法GS：文法SAABGS的LR(1)项目集及aBbDFA如答案图5-9-(1)所示。文法GS的LR(1)剖析表如答案表5-9-(1)所示。因为剖析表中不含多重定义的元素，因此文法GS是LR(1)文法。答案表5-9-(1)文法GS的LR(1)剖析表状态ACTIONGOTOab#SAB0r3r3r3121acc32s5s4r13r2r