编译原理-第5章-习题与答案2

第五章习题5-1设有文法G[S]：S→A/A→aA∣AS∣/(1)找出部分符号序偶间的简单优先关系。(2)验证G[S]不是简单优先文法。5-2对于算符文法G[S]：S→EE→E-T∣TT→T*F∣FF→-P∣PP→(E)∣i(1)找出部分终结符号序偶间的算符优先关系。(2)验证G[S]不是算符优先文法。5-3设有文法G′[E]：E→E1E1→E1+T1|T1T1→TT→T*F|FF→(E)|i其相应的简单优先矩阵如题图5-3所示，试给出对符号串（i+i）进行简单优先分析的过程。======EE1T1TF+*()iEE1T1TF+*()i································题图5-3文法G′[E]的简单优先矩阵5-4设有文法G[E]：E→E+T|TT→T*F|FF→(E)|i其相应的算符优先矩阵如题图5-4所示。试给出对符号串（i+i）进行算符优先分析的过程。(i*+)#(○＜○＜○＜○＜○＝i○＞○＞○＞○＞*○＜○＜○＞○＞○＞○＞+○＜○＜○＜○＞○＞○＞)○＞○＞○＞○＞#○＜○＜○＜○＜题图5-4文法G[E]的算符优先矩阵5-5对于下列的文法，试分别构造识别其全部可归前缀的DFA和LR(0)分析表，并判断哪些是LR(0)文法。(1)S→aSb∣aSc∣ab(2)S→aSSb∣aSSS∣c(3)S→AA→Ab∣a5-6下列文法是否是SLR(1)文法？若是，构造相应的SLR(1)分析表，若不是，则阐明其理由。(1)S→Sab∣bRR→S∣a(2)S→aSAB∣BAA→aA∣BB→b(3)S→aA∣bBA→cAd∣εB→cBdd∣ε5-7对如下的文法分别构造LR(0)及SLR(1)分析表，并比较两者的异同。S→cAd∣bA→ASc∣a5-8对于文法G[S]:S→AA→BA∣εB→aB∣b(1)构造LR(1)分析表；(2)给出用LR(1)分析表对输入符号串abab的分析过程。5-9对于如下的文法，构造LR(1)项目集族，并判断它们是否为LR(1)文法。(1)S→AA→AB∣εB→aB∣b(2)S→aSa∣a第5章习题答案25-1解：(1)由文法的产生式和如答案图5-1(a)所示的句型A／／a／的语法树，可得G中的部分优先关系如答案图5-1(b)所示。答案图5-1(a)句型A//a/的语法树(b)部分符号序偶间的优先关系/S/AaAASA/·AAA/··A/AaAS·===··///aa/··(2)由答案图5-1(b)可知，在符号A和/之间，即存在等于关系，又存在低于关系，故文法G[S]不是简单优先文法。5-2解：(1)由文法G[S]的产生式可直接看出：（○=）此外，再考察句型－P－－(E)和i*(T*F)的语法树(见答案图5-2(a)及(b))。由答案图5-2(a)可得：－○＞－,－○＜－,－○＜(由答案图5-2(b)可得：i○＞*,*○＜(,(○＜*,*○＞）答案图5-2S-TE-PTFEFE)(-PST*F(E)ETF*TFTPi(a)句型-P--(E)的语法树(b)句型i*(T*F)的语法树(2)由答案图5-2(a)可知，在终结符号－和－之间，存在两种算符优先关系：－○＞－,－○＜－故文法G[S]不是算符优先文法。5-3解：对符号串(i+i)进行简单优先分析的过程如答案表5-3所示。因为分析成功，所以符号串(i+i)是文法G′[E]的合法句子。答案表5-3符号串(i+i)的简单优先分析过程步骤分析栈关系当前符号余留输入串句柄所用产生式0#低于（i+i)#1#(低于i+i)#2#(i优于+i)#iF→i3#(F优于+i)#FT→F4#(T优于+i)#TT1→T5#(T1优于+i)#T1E1→T16#(E1等于+i)#7#(E1+低于i)#8#(E1+i优于)#iF→i9#(E1+F优于)#FT→F10#(E1+T优于)#TT1→T11#(E1+T1优于)#E1+T1E1→E1+T112#(E1优于)#E1E→E113#(E等于)#14#(E)优于#(E)F→(E)15#F优于#FT→F16#T优于#TT1→T17#T1优于#T1E1→T118#E1优于#E1E→E119#E优于#分析成功5-4解：对符号串(i+i)进行算符优先分析的过程如答案表5-4所示。因为分析成功，所以符号串(i+i)是文法G[E]的合法句子。句子(i+i)及其分析过程中所得句型的语法树如答案图5-4所示。答案表5-4符号串（i+i)的算符优先分析过程步骤分析栈当前栈顶终结符号优先关系当前输入符号余留输入串最左素短语0##○＜（i+i)#1#○＜(（○＜i+i)#2#○＜(○＜ii○＞+i)#i3#○＜(F(○＜+i)#4#○＜(○＜F++○＜i)#5#○＜(○＜F+○＜ii○＞)#i6#○＜(○＜F+F+○＞)#F+F7#○＜(E(○＝)#8#○＜(○＝E))○＞#(E)9#F##分析成功+T()EETFiFiETF+T()EETFFETF()EETF答案图5-4句子(i+i)及其分析过程中所得句型的语法树5-5解：(1)在文法G[S]中引入一个新的开始符号S′，且将S′→S作为第0个产生式添加到文法G中，从而得到G的拓广文法G′[S′]：0.S′→S2.S→aSc1.S→aSb3.S→ab识别文法G[S]全部可归前缀的DFA如答案图5-5-(1)所示。答案图5-5-(1)识别G[S]G[S]全部可归前缀的DFADFAI0:S’→·SS→·aSbS→·aScS→·abI1:S’→S·SI3:S→aS·bS→aS·cI6:S→aSc·SI2:S→a·SbS→a·ScS→a·bS→·aSbS→·aScS→·abI4:S→ab·aaI5:S→aSb·bbc因为文法G[S]的每个LR(0)项目集中都不含冲突项目，所以文法G[S]是LR(0)文法，故可构造出不含冲突动作的LR(0)分析表如答案表5-5-(1)所示。答案表5-5-(1)文法G[S]的LR(0)分析表状态ACTIONGOTOabc#S0123456s2s2r3r1r2s4s5r3r1r2s6r3r1r2accr3r1r213(2)在文法G[S]中引入一个新的开始符号S′，且将S′→S作为第0个产生式添加到文法G中，从而得到G的拓广文法G′[S′]：0.S′→S2.S→aSSS1.S→aSSb3.S→c识别文法G[S]全部可归前缀的DFA如答案图5-5-(2)所示。答案图5-5-(2)识别G[S]G[S]全部可归前缀的DFADFAI0:S’→·SS→·aSSbS→·aSSSS→·cI1:S’→S·SI4:S→aS·SbS→aS·SSS→·aSSbS→·aSSSS→·cI6:S→aSSb·cI2:S→a·SSbS→a·SSSS→·aSSbS→·aSSSS→·cI7:S→aSSS·aaI3:S→c·cbSScaI5:S→aSS·bS→aSS·SS→·aSSbS→·aSSSS→·ccSa因为文法G[S]的每个LR(0)项目集中都不含冲突项目，所以文法G[S]是LR(0)文法，故可构造出不含冲突动作的LR(0)分析表如答案表5-5-(2)所示。答案表5-5-(2)文法G[S]的LR(0)分析表状态ACTIONGOTOabc#S0123s2s2r3r3s3s3r3accr3144567s2s2r1r2r1r2s3s3r1r2r1r257(3)在文法G[S]中引入一个新的开始符号S′，且将S′→S作为第0个产生式添加到文法G中，从而得到G的拓广文法G′[S′]：0.S′→S2.A→Ab1.S→A3.A→a识别文法G[S]全部可归前缀的DFA如答案图5-5-(3)所示。答案图5-5-(3)识别G[S]G[S]全部可归前缀的DFADFAI1:S’→S·SI4:A→Ab·aI2:S→A·A→A·bAI3:A→a·bI0:S’→·SS→·AA→·AbA→·a因为在LR(0)项目集I2中含有移进-归约冲突项目，所以文法G[S]不是LR(0)文法，故构造出的LR(0)分析表中含有冲突动作。文法G[S]的LR(0)分析表如答案表5-5-(3)所示。答案表5-5-(3)文法G[S]的LR(0)分析表状态ACTIONGOTOab#SA01s3acc12234r1r3r2s4,r1r3r2r1r3r25-6解：(1)在文法G[S]中引入一个新的开始符号S′，且将S′→S作为第0个产生式添加到文法G中，从而得到G的拓广文法G′[S′]：0.S′→S3.R→S1.S→Sab4.R→a2.S→bR识别文法G[S]全部可归前缀的DFA如答案图5-6-(1)所示。答案图5-6-(1)识别G[S]G[S]全部可归前缀的DFADFAI0:S’→·SS→·SabS→·bRI1:S’→S·S→S·abSI6:S→Sa·bI2:S→b·RR→·SR→·aS→·SabS→·bRI7:S→Sab·bbbaRaI3:S→bR·I4:R→S·S→S·abI5:R→a·aS由答案图5-6-(1)可知，在项目集I1和I4中都存在“移进-归约”冲突。在项目集I4={R→S·,S→S·ab}中,由于FOLLOR(R)={a}，FOLLOR(R)∩{a}={a}≠，所以其项目集的“移进-归约”冲突不可能通过SLR(1)规则得到解决，从而该文法不是SLR(1)文法。(2)在文法G[S]中引入一个新的开始符号S′，且将S′→S作为第0个产生式添加到文法G中，从而得到G的拓广文法G′[S′]：0.S′→S3.A→aA1.S→aSAB4.A→B2.S→BA5.B→b识别文法G[S]全部可归前缀的DFA如答案图5-6-(2)所示。I0:S’→·SS→·aSABS→·BAB→·bI1:S’→S·SI9:S→aSA·BB→·baI3:S→B·AA→·aAA→·BB→·bI6:S→BA·BASaAI2:S→a·SABS→·aSABS→·BAB→·bI7:A→a·AA→·aAA→·BB→·bI5:S→aS·ABA→·aAA→·BB→·bI10:S→aSAB·BI4:B→b·bbbI8:A→B·BBBBI11:A→aA·AaaaI4I4bbb答案图5-6-(2)识别G[S]全部可归前缀的DFA因为文法G[S]的每个LR(0)项目集中都不含冲突项目，所以文法G[S]是LR(0)文法，故也是SLR(1)文法。因为FOLLOW(S)={a,b,#},FOLLOW(A)={a,b,#},FOLLOW(B)={a,b,#},所以文法G[S]的SLR(1)分析表如答案表5-6-(2)所示。答案表5-6-(2)文法G[S]的SLR(1)分析表状态ACTIONGOTOab#SAB01234567891011s2s2s7r5s7r2s7r4r1r3s4s4s4r5s4r2s4r4s4r1r3accr5r2r4r1r31569113388810(3)在文法G[S]中引入一个新的开始符号S′，且将S′→S作为第0个产生式添加到文法G中，从而得到G的拓广文法G′[S′]：0.S′→S4.A→ε1.S→aA5.B→cBdd2.S→bB6.B→ε3.A→cAd识别文法G[S]全部可归前缀的DFA如答案图5-6-(3)所示。答案图5-6-(3)识别G[S]G[S]全部可归前缀的DFADFAI0:S’→·SS→·aAS→·bBI1:S’→S·SI8:S→bB·I5:A→c·AdA→·cAdA→·I10:B→cB·ddccI3:S→b·BB→·cBddB→·I7:S→cAd·BabI4:S→aA·AI6:A→cA·dAdI2:S→a·AA→·cAdA→·cI9:B→c·BddB→·cBddB→·I11:B→cBd·ddI12:B→cBdd·dBc由答案图5-6-(3)可知，在项目集I2,I3,I5和I9中都存在“移进-归约”冲突。因为在项目集I2和I5中,由于FOLLOR(A)={d,#}，FOLLOR(A)∩{c}=，所以其项目集的“移进-归约”冲突能通过SLR(1)规则得到解决；又因为在项目集I3和I9中,