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

蒋立源编译原理第三版第四章-习题与答案第五章习题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)进行简单优先分析得过程。题图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第4章习题答案25-1解:(1)由文法得产生式与如答案图5-1(a)所示得句型A／／a／得语法树,可得G中得部分优先关系如答案图5-1(b)所示。(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*,*(,(*,*)(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##分析成功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)所示。因为文法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)所示。因为文法G[S]得每个LR(0)项目集中都不含冲突项目,所以文法G[S]就是LR(0)文法,故可构造出不含冲突动作得LR(0)分析表如答案表5-5-(2)所示。答案表5-5-(2)文法G[S]得LR(0)分析表状态ACTIONGOTOabc#S01234567s2s2r3s2s2r1r2r3r1r2s3s3r3s3s3r1r2accr3r1r21457(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)所示。因为在LR(0)项目集I2中含有移进-归约冲突项目,所以文法G[S]不就是LR(0)文法,故构造出得LR(0)分析表中含有冲突动作。文法G[S]得LR(0)分析表如答案表5-5-(3)所示。答案表5-5-(3)文法G[S]得LR(0)分析表状态ACTIONGOTOab#SA01234s3r1r3r2s4,r1r3r2accr1r3r2125-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)可知,在项目集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)所示。答案图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)可知,在项目集I2,I3,I5与I9中都存在“移进-归约”冲突。因为在项目集I2与I5中,由于FOLLOR(A)={d,#},FOLLOR(A)∩{c}=,所以其项目集得“移进-归约”冲突能通过SLR(1)规则得到解决;又因为在项目集I3与I9中,由于FOLLOR(B)={d,#},FOLLOR(B)∩{c}=,所以其项目集得“移进-归约”冲突也能通过SLR(1)规则得到解决;所以文法G[S]就是SLR(1)文法。因为FOLLOR(S)={#},FOLLOR(A)={d,#},FOLLOR(B)={d,#},所以文法G[S]得SLR(1)分析表如答案表5-6-(3)所示。答案表5-6-(3)文法G[S]得SLR(1)分析表状态ACTIONGOTOabcd#SAB0123456789101112s2s3s5s9s5s9r4r6r4s7r3r6s11s12r5accr4r6r1r4r3r2r6r51468105-7解:在文法G[S]中引入一个新得开始符号S′,且将S′→S作为第0个产生式添加到文法G中,从而得到G得拓广文法G′[S′]:0、S′→S3、A→ASc1、S→cAd4、A→a2、S→b识别文法G[S]全部可归前缀得DFA如答案图5-7所示。因为文法G[S]得每个LR(0)项目集中都不含冲突项目,所以文法G[S]就是LR(0)文法。文法G[S]得LR(0)分析表如答案表5-7-(a)所示。答案表5-7-(a)文法G[S]得LR(0)分析表状态ACTIONGOTOabcd#SA012345678s4r2r4r1r3s3r2r4s3r1r3s2r2r4s2r1s8r3r2r4s6r1r3accr2r4r1r3175因为FOLLOR(S)={#,c},FOLLOR(A)={b,c,d},所以文法G[S]得SLR(1)分析表如答案表5-7-(b)所示。答案表5-7-(b)文法G[S]得SLR(1)分析表状态ACTIONGOTOabcd#SA012345678s4s3r4s3r3s2r2r4s2r1s8r3r4s6r3accr2r1175两个表得相同之处为:(1)两个表得GOTO表部分完全相同。(2)在两个表得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)在文法G[S]中引入一个新得开始符号S′,且将S′→S作为第0个产生式添加到文法G中,从而得到G得拓广文法G′[S′]:0、S′→S3、A→ε1、S→A4、B→aB2、A→BA5、B→b文法G[S]得LR(1)项目集及DFA如答案图5-8所示。文法G[S]得LR(1)分析表如答案表5-8-(1)所示。答案表5-8-(1)文法G[S]得LR(1)分析表状态ACTIONGOTOab#SAB01234567s4s4s4r5r4s5s5s5r5r4r3accr1r3r5r2r4126337(2)用LR(1)分析表对输入符号串abab得分析过程如答案表5-8-(2)所示。因为分析成功,所以符号串abab就是文法G[S]得合法句子。答案表5-8-(2)符号串abab得LR分析过程步骤状态栈符号栈余留输入串分析动作下一状态1I0#abab#s442I0I4#abab#s553I0I4I5#abab#r5GOTO[I4,B]=74I0I4I7#aBab#r4GOTO[I0,B]=35I0I3#Bab#s446I0I3I4#Bab#s557I0I3I4I5#Bab#r5GOTO[I4,B]=78I0I3I4I7#BaB#r4GOTO[I3,B]=39I0I3I3#BB#r3GOTO[I3,A]=610I0I3I3I6#BBA#r2GOTO[I3,A]=611I0I3I6#BA#r2GOTO[I0,A]=212I0I2#A#r1GOTO[I0,S]=113I0I1#S#acc