蒋立源《编译原理》西北工业大学出版社第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可见两者等价，所以由此文法产生的语言是正规语言。56根据文法知其产生的语言是L=ambncim,n,i=1可以构造如下的文法VN=S,A,B,C,VT=a,b,c)P-SaA,AaA,AfbB,BfbB,BfCC,CfcC,Cfc其状态转换图如下：7(1)其对应的右线性文法是：A-OD,B-0A,B一IC,C11F,Cl0A,F-OOE11A,D-OB11C,E-ICOB(2)最短输入串Oll(3)任意接受的四个串011,0110,0011,000011(4)任意以1打头的串.8从略。9(2)相应的3型文法(i) SaS->bSAfaAAfbBBfalaBBbbB(ii) SaAaSfbBBfaBbBAfaBAbbA(iii) SfaASfbBAfbAAfaCBfaBBfbCCfalaCCfblbC(iv) SfbSSfaAAfaCAfbBBfaBBfbCC->aaCCfblbC(3)用自然语言描述输入串的特征(D以任意个(包括0)b开头，中间有任意个(大于1)a,跟一个b,还可以有一个由a,b组成的任意字符串(ii)以a打头，后跟任意个(包括0)b(iii)以a打头，中间有任意个(包括0)b,再跟a,最后由一个a,b所组成的任意串结尾或者以b打头，中间有任意个(包括0)a,再跟b,最后由一个a,b所组成的任意串结尾(iv)以任意个(包括0)b开头，中间跟aa最后由一个a,b所组成的任意串结尾或者以任意个(包括O)b开头，中间跟ab后再接任意(包括0)a再接b,最后由一个a,b所组成的任意串结尾10(1)Gl的状态转换图：G2的状态转换图：(2) Gl等价的左线性文法：SfBb,SfDd,D->C,B->Db,CBc,B-Ab,Bf,->aG2等价的右线性文法：SfdD,S->aB,DfC,B->abC,BfbB,BiA,Bf,CfCA,Afa(3)对Gl文法,abb的推导序列是：S=>aA=>abB=>abb对Gl'文法，abb的推导序列是：S=>Bb=>Abb=>abb对G2文法，aabca的推导序列是：S=>Aa=>Cca=>Babca=>aabca对G2'文法，aabca的推导序列是：S->aB=>aabC->aabcA=>aabca(4)对串acbd来说,G1,G1,文法都不能产生。H将右线性文法化为左线性文法的算法：(1)对于G中每一个形如A-aB的产生式且A是开始符，将其变为B-a,否则假设A不是开始符，BfAa;(2)对于G中每一个形如A-a的产生式,将其变为SfAa12(1)ab*jSS,A).AA,B)÷B状态矩阵是：B4j记S=qOB=qlAB=q2SA=q3,最小化和确定化后如图(2)记S=qO,A=ql,BS=q2最小化和确定化后的状态转换图如下13(1)将具有E动作的NFA确定化后，其状态转换图如图：记SO,Sl,S3)=qOSl=qlS2S3=q2S3=q3(2)记S=qOZ=qlUR=q2SX=q3YUR=q4XSU=q5YURZ=q6ZS=q714(1)从略(2)化简后SO和Sl作为一个状态，S5和S6作为一个状态。状态转换图如图15从略。16从略。(1)r*表示的正规式集是Jr,rr,r,(£Ir)*表示的正规式集是,Ur,rr,rrr,=,r,rr,rrr,£Irr*表示的正规式集是,r,rr,rrr,(r*)*=r*=,r,rr,rrr,所以四者是等价的。(2)(rs)*r表示的正规式集是£,rs,rsrs,rsrsrs,r=r,rsr,rsrsr,rsrsrsr,)r(sr)*表示的正规式集是r£,sr,srsr,srsrsr,二r,rsr,rsrsr,rsrsrsr,)所以两者等价。18写成方程组S=aT+aS(l)B=cB+c(2)T=bT+bB(3)所以B=c*cT=b*bc*cS=a*ab*bc*cGl:S=aA+B(l)B=cC+b(2)=abS+bB(3)C=D(4)D=bB+d(5)把(4)(5)代入(2),得B=c(bB+d)+b=CbB+cd+b得B=(Cb)*(Cdlb),代入(3)得A=abS+b(cb)*(cdb)把它打入(1)得S=a(abS+b(cb)*(cdb)+(cb)*(Cdb)=aabS+ab(cb)*(cdb)+(cb)*(cdb)=(aab)*(ab(cb)*(Cdb)(cb)*(Cdb)G2:S=a+B(1)A=Cc+Bb(2)B=Bb+a(3)C=D+Bab(4)D=d(5)可得D=dB=ab*C=ab*abIbA=(ab*abIb)c+ab*bS=(ab*abb)ca+ab*ba+ab*=(ab*ab|b)caab*baab*20识别此语言的正规式是S='LABEL,d(d,d)*;从略。21从略。22构造NFA其余从略。23下面举一个能够识别1,2,3,10,20,100的例子，读者可以推而广之。%(#include<stdio.h>#include<string.h>ttinclude<ctype.h>defineONldefineTW2defineTHRE3ItdefineTE10ttdefineTWENT20defineHUNDRE100defineWHITE9999%upperAZ%ONEreturnON;TWOreturnTW;THREEreturnTHRE;TENreturnTE;TWENTYreturnTWENT;HUNDREDreturnHUNDRE;zz+1treturnWHITE;nreturn;%main(intargc,char*argv)(intc,i=O;chartmp30;if(argc=2)(if(yyin=fopen(argv1,zzr',)NULL)(Printf("can'topen%sn7z,argvl);exit(0);)while(c=yylex()!=0)(switch(c)(caseON:c=yylex();if(C=O)gotoi+=l;label;c=yylex();if(c=HUNDRE)i+=100;elsei+=l;break;caseTW:c=yylexO;c=yylex();if(c=HUNDRE)i+=200;elsei+=2;break;caseTWENT:i+=20;break;caseTE:i+=10;break;default:break;)*while*/label:Printf("%dr,i);return;)24(1)Dn表示的正规集是长度为2n任意a和b组成的字符串。 此正规式的长度是2n 用来识别Dn的DFA至多需要2n+l个状态。25从略。26(1)由括住的，中间由任意个非组成的字符串，如,a,defg等等。(2)匹配一行仅由一个大写字母和一个数字组成的串，如A1,F8,Z2等。(3)识别rn和除数字字符外的任何字符。 由'和'括住的，中间由两个''或者非'和n组成的任意次的字符串。如'''，匕'，bb'Jdef等等270Xx0-9*a-fA-F*0-9+(,(a-zA-ZXx0-70-7a-fA-F0010-70-7a-z),)28a-zA-Z_+0-9*a-zA-Z_*29参考程序如下：%(#include<stdio.h>#include<string.h>include<ctype.h>ttdefineUPPER2defineWHITE3%)upper-Z%upper+returnUPPER;tI+returnWHITE;%main(intargc,char*argv)(intc,i;if(argc=2)if(yyin=fopen(argv1,ff,)=NULL)printf(zzcan,topen%snzz,argvl);exit(0);)while(c=yylex()!=EOF)(if(c=2)(for(i=0;yytexti;i+)Printf(%c，tolower(yytexti);yytext0三,000,;)if(c=3)printf(zz)；elseprintf(7z%s,yytext);)return;)yywrap()(return;)第四章1 .解：(1)S->(三)Z21()Z21SZ31Z31Af(三)Z221()Z221SZ32Z32B-(三)Z23()Z23SZ33Z33Zn-£IAZllIBZ21Z12->Z121BZ22Z13-AZ13BZ23Z21-Z11Z22-Z12Z23->Z13Z31Z21Z32-Z22Z33fZ23(2)SbZllIaZ21AbZ121aZ22Zn-£IAZ21Z12-AZ22Z21-SZ21Z22-£SZ22(3)S->(T)ZllIaZllZ11S(T)Z12aZ12Z12Zll-EIZ21Z12Z22Z21,SZ21Z22,SZ22 2.解：SnAbBI,1.1(表示第1步，用产生式1.1推导，以下同)=>CAbbB2,2.1=>edAbbB3,4.1=>edCAbbB4,2.1=>ededAbbbB5,4.1=>edaAbbbB5,4.2(不符合，改写第5步，用4.2)=edBfbbB4,2.2=edCSdfbbB5,3.1=>ededSdfbbB6,4.1=>edaSdfbbB6,4.2=>eddfbbB5,3.2>eddfbbCSd6,3.1=>eddfbbedSd7,4.1>eddfbbaSd7,4.2Restore 表示 restore=>eddfbbd6,3.2 3.解：以下Save表示savetoken_pointervalue,token_pointervalueo(1)文法没有左递归。FunctionPrboolean;BeginSave;P:=true;Ifnext_token=，/begin"thenIfnext_token=,d'thenIfnext_token=,thenIfXthenIfnext_token=,/end"thenreturn;Restore;P:=false;End;FunctionXrboolean;BeginSave;X:=true;Ifnext_token=,d,thenIfnext_token=,;'thenIfXthenreturn;Restore;Ifnext_token=,s,thenIfYthenreturn;Restore;X:=false;End;FunctionYrboolean;BeginSave;Y=true;Ifnext_token=,;'thenIfnext_token->s,thenIfYthenreturn;Restore;End;消去文法左递归，并记为：PfbeginSendS->C->V:=EC->ifEthenSE-VE'E,一+VE'IV-IFunctionPrboolean;BeginSave;P:=true;Ifnext-token=z,begin"thenIfSthenIfnext_token=，/end“thenreturn;Restore;P:=false;End;FunctionA:boolean;BeignSave;A:=true;IfVthenIfnext_token="，:="thenIfEthenreturn;Restore;A:=flase;End;FunctionS:boolean;BeignSave;S:=true;IfAthenreturn;Restore;IfCthenreturn;Restore;S:=false;End;FunctionCiboolean;BeginSave;C:=true;Ifnext_token=,/if"thenIfEthenIfnext_token="then"thenIfSthenreturn;Restore;C:=false;End;FunctionErboolean;BeginSave;E:=true;IfVthenIfEPthenreturn;Restore;E:=false;End;FunctionEprboolean;BeingSave;Ep:=true;Ifnext_token=,+'thenIfVthenIfE,thenreturn;Return;End; 4.解： 5.证：因为是左递归文法，所以必存在左递归的非终结符A,及形如AfQlB的产生式,且QT*Ad.则first(d)first(),从而first()first(),即文法不满足LL(1)文法条件。得证。 6.证：LL(1)文法的分析句子过程的每一步，永远只有唯一的分析动作可进行。现在，假设LL(D文法G是二义性文法，则存在句子Q,它有两个不同的语法树。即存在着句子。有两个不同的最左推导。从而可知，用LL(I)方法进行句子Q的分析过程中的某步中，存在两种不同的产生式替换，且均能正确进行语法分析，即LL(1)分析动作存在不确定性。与LL(I)性质矛盾。所以，G不是LL(D文法。 7.解：(I)D产生式两个候选式fD和f的first集交集不为空，所以不是LL(I)的。此文法具有左递归性，据第5题结论，不是LL(D的。 8.解：(1)消除左递归性,得：S-bZl11aZ21A-bZ121aZ22Zl1-bZl11Z12-bZ12Z21->bZ111aZ21Z22bZ121aZ221消除无用产生式得：S->bZllaZ21Zll->bZllZ21bZllaZ21此文法已满足LL(D文法的三个条件,所以G,S:SbZllIaZ21Zll-bZllZ21->bZllaZ21(2)G,文法的各非终结符的FIRST集和FOLLOW集:产生式FIRST集FOLLOW集SbZllb#aZ21aZllfbZIlb#Z21->bZllb悔->aZ21aLL分析表为：ab#SaZ21bZllZllbZllZ21aZ21bZll 9.解:(1)产生式first集follow集SfSaBb#,a,cfbBbAfSbcaaB-*Aca,b#,a,c将SfSaBIbB改写为S-bBS',S'-aBS'3,可验证，新文法是LL(D的。 10.解： 1)为方便书写，记：布尔表达式为A,布尔因子为B,布尔二次量为C,布尔初等量为D,原文法可以简化为：A-AVBIBBfBACCC-DDDf（八）truefalse,显然，文法含有左递归，消去后等价LL(I)文法为：AfBA'A,一VBA'IB-CB',B,->CB,I3Cf-IDlDDf（八）Itruefalse略证：假设LL(1)文法G有形如BfaAAb的产生式，且AT+£及AT*ag,根据FlRST集FoLLOW集的构造算法可知，FIRST（八）中一切非£加到FOLLoW（八）中，则aFOLLOW（八）;又因为aFIRST(ag),所以两集合相交非空,因此，G不是LL文法;与前提矛盾，假设不成立，得证。12©解：SA(a)bSA=<=<(=«<<a>=<»>)>»»b»不是简单优先文法。SRTOAa,S>=RT>(<=«<<)>>a>>,<=<<<是简单优先文法。SR(a,)S=«R»(二«a»,二«)»是简单优先文法。O首先消去无用产生式Z-E,Z-E÷TSZTtti（）SZ=T>>n=<«I>>（=<«）>>A >> >化简后的文法是简单优先文法；13.解：S/S>A=<</>a>A和/之间同时有关系二和所以不是简单优先文法； 提示：分析教材中给出的算法，选择一种适宜的表示给定文法的方法（尽量简单），使得对文法的输入比拟简单的同时（需要把输入转化为计算机语言表示，这种转化应该尽量简单），能够比拟简单地构造3个根本关系矩阵（=，LEAD和LAST）。 证明：设xjxj+L.xi是满足条件Xj是<xj=xj件=xi>xi+l的最左子串。由二关系的定义,可知xjxj+1.xi必出现在某产生式的右部中。又因xj-l<xj可知xj-1与Xj不处于同一产生式，且Xj是某右部的首符。同理，Xi为某产生式的尾符号。即存在产生式UfXjXj+1.xi设ST*aUb其中，aT*.xj-1,bT*xi+l.对于aUb可构造一语法树，并通过对其剪枝（归约），直到U出现在句柄中。从而xjxj+L.xi必为句柄。反之，假设xjxj+L.xi是句柄，由简单优先关系的定义,必满足上述条件。 解：为描述方便,用符号表示各非终结符:DX变量说明>,L=<变量表>,V=<变量>,T=<类型>,a=VAR,则消去V,并采用分层法改写文法，得到：DfaW:T;WfLLfL,iIiT-*rInIbIc其全部简单优先关系是:DWTLai rnbcT=L>a=<<：=<9,>>>=irnbc>是简单优先文法。 证：设STna,我们对n用归纳法，证明a不含两个非终结符相邻情况。n=l时，STa,即S-a是文法的产生式，根据定义，它不含上述情况。设n=k时，上述结论成立，且设STkdAb,由归纳假设，A两侧必为终结符。我们再进行一步推导，得STkdAbTdub,其中，A-U是文法中的产生式，由定义，U中不含两个非终结符相邻情况，从而dub两个非终结符相邻情况。得证。证：由于G不是算符文法，G中至少有一个产生式，其右部含有两个非终结符相邻的情况。不失一般性，设其形为UfXABy,x,yV*,由于文法不含无用产生式，则必存在含有U的句型dUb,即存在推导ST*dUbTdMB".得证。 文法为：EfEtAI->*TIA/TTT->T+VT-VVVfi(E) 20.解：(1)构造算符优先矩阵：-*()in»-<><>«>*XX<(«<=<)»>>1»>>#<<<<(2)在(-，-)、*)和(*,-)处有多重定义元素，不是算符优先文法；改写方法： 将E-E-T中的减号与F-P中的赋值运算符强制规定优先关系； 或者将F-P中的赋值运算符改为别的符号来表示； (1)证明：由设句型a=Ua中含的短语不含U,即存在A,A=>*”,则a可归约为a二Ua<l*UA=b,b是G的一个句型，这与G是算符文法矛盾，所以，a中含有a的短语必含Uo的证明与类似,略。证：(1)对于a=aU是句型，必有ST*a(二aU)T+ab.即在归约过程中，b先于a被归约，从而,a<b.对于(2)的情况类似可以证明。各各各 明明明 证证证证：(D用反证法。设没有短语包含b但是不包含a,则a,b一定同时位于某个短语中，从而必使得a,b同时位于同一产生式的右部，所以a=b,与G是算符优先文法(二与<不能并存)矛盾。、(3)类似可证。 证:只要证U中不含有除自身以外的素短语。设有这样的素短语存在，即存在bxUy是素短语，其中Kx或者y<n之一成立。因素短语是短语，根据短语定义，则必有:l<xTbxT<bx或y<nTby>by+L与bxT=bx及by=by+l矛盾,得证。 提示：根据27题的结论，只要证U是句型的短语，根据二关系的定义容易知道U是句型的素短语。 证：与28题的不同点只是a,an+1可以是',不影响结论。 证：设不能含有素短语，则只能是含有短语(不能含有终结符号)，则该短语只能含有一个非终结符号，否则不符合算符文法定义，得证。 31.解：(1)算符优先矩阵：+*()in+>«<><>*»<<>O»<<>O(«<<=<)»>>>I»>>>n«<<<(2)用Floyd方法将优先矩阵线性化得到得的优先函数为：+*()i#F3551771G2466161 32.解：用Floyd方法对的优先矩阵构造的优先函数为：zbMLa()fl567747gl654667 33.解：(1)优先矩阵如下:a#>=>>«a<»#<<<(2)用Bell方法求优先函数的过程如下：a#f5751g5561(3)显然，文法不是算符优先文法，所以不能线性化。略。35解:(1)识别全部活前缀的DFA如下：(以表格的形式来表示，很容易可以转化为图的形式,本章中其余的题目也是采用这种形式表示。)状态工程集经过的符号到达的状态IOS'->SSIlS一aSba12SfaScSfabIlS'-S12SfaSbS13SfaSca12Sfabb14SfaSb