蒋立源《编译原理》西北工业大学出版社第3版课后答案.docx
编译原理课后习题答案第一章1 .解：源程序是指以某种程序设计语言所编写的程序。目标程序是指编译程序（或解释程序）将源程序处理加工而得的另一种语言（目标语言）的程序。翻译程序是将某种语言翻译成另一种语言的程序的统称。编译程序与解释程序均为翻译程序，但二者工作方法不同。解释程序的特点是并不先将高级语言程序全部翻译成机器代码,而是每读入一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读入下一条语句继续进行解释、执行，如此反复。即边解释边执行，翻译所得的指令序列并不保存。编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的空间中，在用户需要时再执行之。即先翻译、后执行。2 .解：一般说来，编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。3 .解：C语言的关键字有：autobreakcasecharconstcontinuedefaultdodoubleelseenumexternfloatforgotoifintlongregisterreturnshortsignedsizeofstaticstructswitchtypedefunionunsignedvoidvolatileWhileo上述关键字在C语言中均为保存字。4 .解：C语言中括号有三种：,口，Oo其中，用于语句括号；口用于数组；O用于函数（定义与调用）及表达式运算（改变运算顺序）。C语言中无END关键字。逗号在C语言中被视为分隔符和运算符，作为优先级最低的运算符，运算结果为逗号表达式最右侧子表达式的值（如：（a,b,c,d）的值为d）。5 .略第二章1.(1)答：26*26=676(2)答：26*10=260(3)答：a,b,c,.,z,a,al,.,a9,aa,.,az,.,zz,a00,al,.,zzz),共26+26*36+26*36*36=34658个2 ,构造产生以下语言的文法(1) anbnn20解：对应文法为G（三）=（S,a,b,Sf为aSb,S）(2) anbmcpn,m,p>0解：对应文法为G(三)=(S,X,Y,a,b,c,S->aSX,X-bXY,Y-cY,S)(3) an#bnn0Ucn#dnnO解：对应文法为G(三)=(S,X,Y,a,b,c,d,#,S-X,SY,XaXb,YcYd,S)(4) wttwrttIw?0,1*,Wr是W的逆序排列解：G(三)=(S,W,R,0,1,#,S->Wtt,WfoWOllW1|#),S)(5)任何不是以O打头的所有奇整数所组成的集合解：G(三)=(S,A,B,I,J,-,0,1,2,3,4,5,6,7,8,9,S-JIBJ,BOBIBe,IfJ2468,Jl3579,S)(6)所有偶数个0和偶数个1所组成的符号串集合解：对应文法为SOAlBe,AOS1CBOC1SC-IAIoB3 .描述语言特点(1) SfloSoS-aAAfbAA-a解：本文法构成的语言集为：L(G)=(10)nabma0nn,m2。(2) SfSSSflAOAfIAOAf解：L(G)=InlOnlln20n2InmOnmnl,n2,nm0;且nl,n2,nm不全为零该语言特点是：产生的句子中，0、1个数相同，并且假设干相接的1后必然紧接数量相同连续的0。(3) SfIAS-BOAfIAAfCBfBOB-CCfICoCf解：本文法构成的语言集为：L(G)=lpln0np21,n20Ulnnqq21,n2,特点是具有IplnOn或InOnOq形式，进一步，可知其具有形式InOmn,m0,且n+m>0o(4) SfbAdCAfAGSGfAfa解:可知,S=>=>baSndcn-0该语言特点是：产生的句子中，是以ba开头de结尾的串，且ba、de个数相同。(5) SfaSSSfa解：L(G)=a(2nT)InDD可知:奇数个a4 .解：此文法产生的语言是：以终结符al、a2-an为运算对象，以八、V、”为运算符,以、为分隔符的布尔表达式串5 .5.1解：由于此文法包含以下规则：-e,所以此文法是O型文法。5.2证明：略6.解：(1)最左推导:程序以分程序以标号：分程序TL：分程序TL：标号：分程序TL：L：分程序TL：L：无标号分程序TL：L：分程序首部；复合尾部TL：L：分程序首部；说明；复合尾部TL：L：begin说明；说明；复合尾部TL：L：begind；说明；复合尾部TL：L：begind；d；复合尾部TL：L：begind；d；语句；复合尾部T L： L： begin d；T L： L： begin d；d； s； 复合尾部.d； s； 语句 endT L： L： begin d；d； s； s end最右推导:程序T分程序T标号：分程序TC标号：标号:分程序IX标号：标号:无标号分程序T标号：标号:分程序首部;复合尾部T标号：标号：分程序首部;语句;复合尾部T标号：标号：分程序首部；语句;语句;end以标号：标号：分程序首部；语句；s；endTC标号：标号：分程序首部;s； s； endTa示号：标号：分程序首部;说明；s；s；endT标号：标号：分程序首部；d；s；s；endT标号：标号：begin说明;d；s；s；endT标号：标号：begind；d；s；s；endT标号：L：begind；d；s；s；endTL：L：begind；d；s；s；end(2)句子L：L：begind；d；s；send的相应语法树是:7.解:aacb是文法GS中的句子，相应语法树是:最右推导：S=aAcB=aAcb=aacb最左推导：S=acB=aacB=aacb(2) aabacbadcd不是文法GS中的句子因为文法中的句子不可能以非终结符d结尾(3) aacbccb不是文法GS中的句子可知，aacbccb仅是文法GS的一个句型的一局部，而不是一个句子。(4) aacabcbcccaacdca不是文法GS中的句子因为终结符d后必然要跟终结符a,所以不可能出现de这样的句子。(5) aacabcbcccaacbca不是文法GS中的句子由(1)可知：aacb可归约为S,由文法的产生式规则可知，终结符C后不可能跟非终结符S,所以不可能出现CaaCb这样的句子。8 .证明：用归纳法于n,n=l时，结论显然成立。设n=k时，对于12.kT*b,存在Bi：i=l,2,.,k,iT*bi成立,现在设12.akak+lT*b,因文法是前后文无关的，所以aIa2.ak可推导出b的一个前缀b',ak+1可推导出b的一个后缀二b（不妨称为bk+1）。由归纳假设，对于b',存在Bi：i=l,2,.,k,b'=BIB2Bk,使得aiT*bi成立,另外,我们有ak+lT*b（=bk+l）<>即n=k+l时亦成立。证毕。9 .证明：（1）用反证法。假设a首符号为终结符时，B的首符号为非终结符。即设：a=a；B=A'且a=>*B。由题意可知：a=aT-TAy=,由于文法是CFG,终结符a不可能被替换空串或非终结符，因此假设有误。得证；（2）同（1）,假设：B的首符号为非终结符时，首符号为终结符。即设：=a;=A,且=aTTA'=B,与（1）同理，得证。10 .证明：因为存在句子：abc,它对应有两个语法树（或最右推导）：STABTAbcTabcSTDCTDcTabc所以，本文法具有二义性。11 .解：（1）STABTAaSbTAacbTbAacbTbbAacbTbbaacb上面推导中，下划线局部为当前句型的句柄。对应的语法树为：全部的短语：第一个a（al）是句子bbaacb相对于非终结符A（Al）（产生式A?a）的短语（直接短语）；blal是句子bbaacb相对于非终结符A2的短语；b2blal是句子bbaacb相对于非终结符A3的短语；C是句子bbaacb相对于非终结符Sl（产生式S?C）的短语（直接短语）；a2cb3是句子bbaacb相对于非终结符B的短语；b2blala2cb3是句子bbaacb相对于非终结符S2的短语；注：符号的下标是为了描述方便加上去的。（2）句子（b）a（a）（b）的最右推导:ST(AS)T(A(b)T(SaA)(b)T(Sa(a)(b)T(b)a(a)(b)相应的语法树是：(3)解：iii*i+t对应的语法树略。最右推导：ETT=>F=>FPTFEtTFET+tTFEF+tTFEP+tTFEi+tTFTi+TFTF*i+tTFTP*i+tTFTi*i+ITFFi*i+tTFPi*i+TFii*i+tTPii*i+tTiii*i+12 .证明：充分性：当前文法下的每一符号串仅有一个句柄和一个句柄产生式T对当前符号串有唯一的最左归约T对每一步推导都有唯一的最右推导T有唯一的语法树。必要性：有唯一的语法树T对每一步推导都有唯一的最右推导T对当前符号串有唯一的最左归约T当前文法下的每一符号串仅有一个句柄和一个句柄产生式13 .化简以下各个文法解:SfbCACdAfCSAlcCCC-*cSc(2)解：S-aABIfAgA->edDAD->eAB->f(3)解：SfaC14 .消除以下文法中的£产生式(1)解：SfaASIaSbA->cS(2)解：SfaAAIaa->bcbedede15 .消除以下文法中的无用产生式和单产生式(1)消除后的产生式如下：SfaBIBCB-DBIbC-bDfbIDB(2)消除后的产生式如下：S->SISBIOI(三)ISAf()I(三)IISBdS(3)消除后的产生式如下：E-E+TIT*FI(E)IPtFIiTfT*FI(E)IPtFIiF-PfFI(E)IiP-(E)Ii第三章1 .从略2 .3假设W:表示载狐狸过河，G:表示载山羊过河，C:表示载白菜过河用到的状态L狐狸和山羊在左岸2：狐狸和白菜载左岸3:羊和白菜在左岸4:狐狸和山羊在右岸5:狐狸和白菜在右岸6:111羊和白菜在右岸F:全在右岸4证明：只须证明文法G:A-B或A-(A,BVN,VT+)等价于Gl:AfaB或Afa(aVT+)Gl的产生式中->aB,则B也有BfbC,CcD.所以有AabcB,a,b,cVT,B,VN所以与G等价。2)G的产生式AfaB,VT÷,因为a是字符串，所以肯定存在着一个终结符a,使AfaB可见两
