编译原理习题参考答案.doc 14页

'第二章2.构造产生下列语言的文法（2）{anbmcp|n,m,p≥0}解：G(S)：S→aS|X,X→bX|Y,Y→cY|ε（3）{an#bn|n≥0}∪{cn#dn|n≥0}解：G(S)：S→X,S→Y,X→aXb|#,Y→cYd|#}（5）任何不是以0打头的所有奇整数所组成的集合解：G(S)：S→J|IBJ,B→0B|IB|ε,I→J|2|4|6|8,J→1|3|5|7|9}（6）（思考题）所有偶数个0和偶数个1所组成的符号串集合解：对应文法为S→0A|1B|ε，A→0S|1CB→0C|1SC→1A|0B3.描述语言特点（2）S→SSS→1A0A→1A0A→ε解：L(G)={1n10n11n20n2…1nm0nm|n1,n2,…,nm≥0；且n1,n2,…nm不全为零}该语言特点是：产生的句子中，0、1个数相同，并且若干相接的1后必然紧接数量相同连续的0。（5）S→aSSS→a解：L(G)={a(2n-1)|n≥1}可知：奇数个a5.(1)解：由于此文法包含以下规则：AA→ε，所以此文法是0型文法。7.解：(1)aacb是文法G[S]中的句子，相应语法树是：最右推导：S=>aAcB=>aAcb=>aacb最左推导：S=>aAcB=>aacB=>aacb（3）aacbccb不是文法G[S]中的句子 aacbccb不能从S推导得到时，它仅是文法G[S]的一个句型的一部分，而不是一个句子。11.解：最右推导:(1)S=>AB=>AaSb=>Aacb=>bAacb=>bbAacb=>bbaacb上面推导中，下划线部分为当前句型的句柄。对应的语法树为：短语直接短语句柄a1对A1√b1a1对A2b2b1a1对A3c对S1√√a2cb3对Bbbaacb对S2第三章3假设M:人W:载狐狸过河，G:载山羊过河，C:载白菜过河 6根据文法知其产生的语言是L={ambnci|m,n,i≧1}可以构造如下的文法VN={S,A,B,C},VT={a,b,c}P={S→aA,A→aA,A→bB,B→bB,B→cC,C→cC,C→c}其状态转换图如下: 7(1)其对应的右线性文法是:A→0D,B→0A,B→1C,C→1|1F,C→1|0A,F→0|0E|1A,D→0B|1C,E→1C|0B(2)最短输入串011(3)任意接受的四个串：011,0110,0011,000011(4)任意以1打头的串.9．对于矩阵(iii)(1)状态转换图：(2)3型文法（正规文法）S→aA|a|bBA→bA|b|aC|aB→aB|bC|bC→aC|a|bC|b(3)用自然语言描述输入串的特征以a打头，中间有任意个（包括0个）b,再跟a,最后由一个a,b所组成的任意串结尾或者以b打头，中间有任意个（包括0个）a,再跟b,最后由一个a,b所组成的任意串结尾。12(1)确定化：ab[S]S[S,A]A[S,A]A[S,A]A[A,B][A,B][B][A,B][B][B]-----------------------------------------------------以上为第一次作业 最小化：º0º{S,A}{B,C}因为{S}b=φ{A}b={B}所以{S,A}=>{S}{A}因为{C}b=φ{B}b={B}所以{B,C}=>{B}{C}º1º{S}{A}{B}{C}原DFA已为最小DFA。10（1）G1的状态转换图：或(2)G1等价的左线性文法G1’[F]：F→Dd|Bb,D→C,B→S|ε|Ab|Db,A→Sa|a,C→Bc,S→Eb,E→Aa或G1’[F]：F→Dd|Bb,D→C,B→S|ε|Ab|Db,A→Sa|a,C→Bc,S→Aab21求出描述习题3-12中图（2）（3）所给出有限自动机所识别语言的正规式 （2）a(ba)*b或(ab)*ab（3）a（b|aa)*a-----------------------------------------------------以上为第二次作业22(1)((0*|1)(1*0))*0ε1ε10εASBCNFA:确定化：　∑Q00ASBAA010111[S,A,B]S[S,A,B,C]A[B]B[S,A,B,C]A[S,A,B,C]A[B]B[B]B[S,A,B,C]A[B]B第四章1(2)将间接左递归转换成直接左递归，将A->SAA->a代入S->AS由原文法得S->SAS|aS|b消除左递归：S->aSS’|bS’S’->ASS’|ε4又ε属于First(S)，First(S)ÇFollow(S)=Æ 又ε属于First(A)，First(A)ÇFollow(A)=Æ又ε属于First(B)，First(A)ÇFollow(A)=Æ所以此文法为LL(1)文法。8.（1）(a)消除左递归：S->Sb|Ab|b=>S->AbS’|bS’S’->bS’|εA->Aa|a=>A->aA’A’->aA’|ε文法G’：S->AbS’|bS’S’->bS’|εA->aA’A’->aA’|ε(b)判断G’是否为LL(1)文法　FirstFollowS->AbS’{a}{#}S->bS’{b}S’->bS’{b}{#}S"->ε{ε}A->aA’{a}{b}A"->aA’{a}{b}A’->ε{ε}没有冲突，所以文法G’为LL(1)文法。补充题：若有文法G[S]:S->AB|cCA->b|εB->aC|εC->aS|c判断文法G是否为LL（1）文法，写出理由；分别求所有非终结符的First和Follow集；若为LL（1）文法，给出其预测分析表；分析句子caac是否符合该文法。答案：无左递归，无左公因子。First(A)=(b,ε),First(B)={a,ε}因First(A)含ε，First(AB)=First(A)ÈFirst(B)={a,b，ε},First(cC)={c}Follow(S)={#}ÈFollow(C)={#}Follow(A)=First(B)ÈFollow(S)-{ε}={a,#} Follow(B)=Follow(S)={#}Follow(C)=Follow(B)ÈFollow(S)={#}对S，First(AB)ÇFirst(cC)=Æ对A，First(b)ÇFirst(ε)=Æ,因First(A)含ε,First(A)ÇFollow(A)={b,ε}Ç{a,#}=Æ对B，First(aC)ÇFirst(ε)=Æ,因First(B)含ε,First(B)ÇFollow(B)={a,ε}Ç{#}=Æ对C，First(aS)ÇFirst(c)=Æ所以，文法G是LL（1）文法First集：　abceS√√√√　A　√　√B√　√C√　√　Follow集：　abc#S　　√A√　　√B　　　√C　　　√预测分析表　abc#SS->ABS->ABS->cCS->ABAA->εA->b　A->εBB->aC　　B->εCC->aS　C->c　分析句子caac栈输入缓冲区动作#Scaac##Cccaac#S->cC#Caac##Saaac#C->aS#Sac##BAac#S->AB#Bac#A->ε#Caac#B->aC#Cc##cc#C->c##成功-----------------------------------------------------以上为第三次作业 16．对于如下文法G[<变量说明>]：<变量说明>->VAR<变量表>：<类型>;<变量表>-><变量表>,<变量>|<变量><变量>->i<类型>->real|integer|Boolean|char(1)将G改造为等价的算符优先文法G’;令<变量说明>：S，VAR：v,<变量表>：A，<类型>：B，<变量>：Creal：rinteger:gBoolean:bchar:c文法G可改写为：S->vA:B;A->A,C|CC->iB->r|g|b|c该文法是算符文法(2)求出G’的全部优先关系。求FirstVT，得:　virgbc:,;S√　　　　　　　　A　√　　　　　√　C　√　　　　　　　B　　√√√√　　　求LastVT，得：　virgbc:,;S　　　　　　　　√A　√　　　　　√　C　√　　　　　　　B　　√√√√　　　优先关系表：　virgbc:,;#v　<　　　　=<　　i　　　　　　>>　　r　　　　　　　　>　g　　　　　　　　>　b　　　　　　　　>　c　　　　　　　　>　:　　<<<<　　=　,　<　　　　>>　　;　　　　　　　　　>#<　　　　　　　　=无冲突，该文法是算符优先文法。35.对于以下文法，试构造它们的LR(0)项目集规范族及识别全部活前缀的DFA。（2）S->cAS->ccBA->cAA->aB->ccBB->b 解：拓展文法得文法列表：(0)S’->S(1)S->cA(2)S->ccB(3)A->cA(4)A->a(5)B->ccB(6)B->b37．判断下面的文法是哪一类LR文法，并构造LR分析表。S->(SRS->aR->,SRR->)解：拓展文法得文法列表：(0)S’->S(1)S->(SR(2)S->a(3)R->,SR(4)R->)项目集规范族: 分析表：　ActionGOTO　a(,)#SR0　S2　　　1　1　　　　Acc　　2S3S2　　　4　3r2r2r2r2r2　　4　　S6S7　　55r1r1r1r1r1　　6S3S2　　　8　7r4r4r4r4r4　　8　　S6S7　　99r3r3r3r3r3　　无冲突，为LR(0)文法。补充题1：对下列文法G:S®D(R)R®R;P|PP®S|iD®i求出每个非终结符的FIRSTVT集和LASTVT集，并构造算符优先关系矩阵。解：文法G每个非终结符的FIRSTVT集合FIRSTVT(S)={(,i}FIRSTVT(R)={;,(,I}FIRSTVT(P)={i,(}FIRSTVT(D)={i}文法G的每个非终结符的LASTVT集合LASTVT(S)={)}LASTVT(R)={;,),i}LASTVT(P)={i,)}LASTVT(D)={i} 优先关系矩阵（）；i#(<·=·<·<·)·>·>·>;<··>·><·i·>·>·>#<·<·=·补充题2:对于如下的文法，构造LR(1)项目集族，并判断它们是否为LR(1)文法，若是LR(1)方法，分析符号串abab的分析过程。S→AA→ABA→εB→aBB→b解：扩展后文法为：0.S’->S1.S→A2.A→AB3.A→ε4.B→aB5.B→b构造LR(1)项目集族：LR(1)分析表：　ActionGOTO　ab#SAB0R3R3R312　1　　acc　　　2S4S5R1　　33R2R2R2　　　4S4S5　　　65R5R5R5　　　 6R4R4R4　　　分析符号串abab：序号栈　输入　动作00abab#R3,A→ε　#　　　　102　abab#　S4　#A　　　　2024bab#S5　#Aa　　　　30245ab#R5,B→b　#Aab　　　　40246ab#R4,B→aB　#AaB　　　　5023ab#R2,A→AB　#AB　　　　602ab#S4　#A　　　　7024b#S5　#Aa　　　　80245#R5,B→b　#Aab　　　　90246#R4,B→aB　#AaB　　　　10023#R2,A→AB　#AB　　　　1102#R1,S→A　#A　　　　1201#acc　#S　　　　-------------------------------------------------以上为第四、五次作业5.4解：（1）A-BC+*DE-^（2）ad*c+d/e+f*g+（3）ax+4≤cd3*>∨（4）abcdef^*<∧∨（5）123456789101112131415161718192021222324s0=i1=i100≤24jezsii*+=ii1+=7j5.5解：(1)a+b*c (2)a*(b-c)-(c+d)/e(3)a≤b+c∧a>0∨a+b≠0∧a<0(4)if(a,B,0,⑤)④(j,_,_,⒃)⑤(j=,a,1,⑦)⑥(j,_,_,⑩)⑦(+,C,1,T1)⑧(:=,T1,_,C)⑨(j,_,_,⒁)⑩(j<=,A,D,⑿)⑾(j,_,_,⒂)⑿(+,A,2,T2)⒀(:=,T2,_,A)⒁(j,_,_,⑩)⒂(j,_,_,①)⒃-------------------------------------------------以上为第六次作业'