《编译原理》蒋立源课后答案 97页

'课后答案网www.khdaw.com第一章习题解答1.解：源程序是指以某种程序设计语言所编写的程序。目标程序是指编译程序（或解释程序）将源程序处理加工而得的另一种语言（目标语言）的程序。翻译程序是将某种语言翻译成另一种语言的程序的统称。编译程序与解释程序均为翻译程序，但二者工作方法不同。解释程序的特点是并不先将高级语言程序全部翻译成机器代码，而是每读入一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读入下一条语句继续进行解释、执行，如此反复。即边解释边执行，翻译所得的指令序列并不保存。编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的空间中，在用户需要时再执行之。即先翻译、后执行。2.解：一般说来，编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。3.解：C语言的关键字有：autobreakcasecharconstcontinuedefaultdodoubleelseenumexternfloatforgotoifintlongregisterreturnshortsignedsizeofstaticstructswitchtypedefunionunsignedvoidvolatilewhile。上述关键字在C语言中均为保留字。4.解：C语言中括号有三种：{}，[]，（）。其中，{}用于语句括号；[]用于数组；（）用于函数（定义与调用）及表达式运算（改变运算顺序）。C语言中无END关键字。逗号在C语言中被视为分隔符和运算符，作为优先级最低的运算符，运算结果为逗号表达式最右侧子表达式的值（如：(a,b,c,d)的值为d）。0。（4）S→bAdcA→AGSG→εA→a 课后答案网www.khdaw.com解：可知，S=>…=>baSndcn≥0该语言特点是：产生的句子中，是以ba开头dc结尾的串,且ba、dc个数相同。（5）S→aSSS→a解：L(G)={a(2n-1)|n≥1}可知：奇数个a4.解：此文法产生的语言是：以终结符a1、a2…an为运算对象，以∧、∨、~为运算符，以[、]为分隔符的布尔表达式串5.5.1解：由于此文法包含以下规则：AA→e，所以此文法是0型文法。5.2证明：略6.解：（1）最左推导：<程序>T<分程序>T<标号>：<分程序>TL：<分程序>TL：<标号>：<分程序>TL：L：<分程序>TL：L：<无标号分程序>TL：L：<分程序首部>；<复合尾部>TL：L：<分程序首部>；<说明>；<复合尾部>TL：L：begin<说明>；<说明>；<复合尾部>TL：L：begind；<说明>；<复合尾部>TL：L：begind；d；<复合尾部>TL：L：begind；d；<语句>；<复合尾部>TL：L：begind；d；s；<复合尾部.TL：L：begind；d；s；<语句>endTL：L：begind；d；s；send 课后答案网www.khdaw.com最右推导：<程序>T<分程序>T<标号>：<分程序>T<标号>：<标号>：<分程序>T<标号>：<标号>：<无标号分程序>T<标号>：<标号>：<分程序首部>；<复合尾部>T<标号>：<标号>：<分程序首部>；<语句>；<复合尾部>T<标号>：<标号>：<分程序首部>；<语句>；<语句>；endT<标号>：<标号>：<分程序首部>；<语句>；s；endT<标号>：<标号>：<分程序首部>；s；s；endT<标号>：<标号>：<分程序首部>；说明；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的相应语法树是： 课后答案网www.khdaw.com7.解：aacb是文法G[S]中的句子，相应语法树是：最右推导：S=>aAcB=>aAcb=>aacb最左推导：S=>aAcB=>aacB=>aacb（2）aabacbadcd不是文法G[S]中的句子因为文法中的句子不可能以非终结符d结尾（3）aacbccb不是文法G[S]中的句子可知，aacbccb仅是文法G[S]的一个句型的一部分，而不是一个句子。 课后答案网www.khdaw.com（4）aacabcbcccaacdca不是文法G[S]中的句子因为终结符d后必然要跟终结符a，所以不可能出现…dc…这样的句子。（5）aacabcbcccaacbca不是文法G[S]中的句子由（1）可知：aacb可归约为S，由文法的产生式规则可知，终结符c后不可能跟非终结符S，所以不可能出现…caacb…这样的句子。8.证明：用归纳法于n，n=1时，结论显然成立。设n=k时，对于α1α2...αkT*b,存在βi：i=1,2,..,k，αiT*bi成立，现在设α1α2...αkαk+1T*b，因文法是前后文无关的，所以α1α2...αk可推导出b的一个前缀b"，αk+1可推导出b的一个后缀=b"(不妨称为bk+1)。由归纳假设，对于b"，存在βi：i=1,2,..,k，b"=β1β2...βk,使得αiT*bi成立，另外,我们有αk+1T*b"(=bk+1）。即n=k+1时亦成立。证毕。9.证明：(1)用反证法。假设α首符号为终结符时，β的首符号为非终结符。即设：α=aω；β=Aω’且α=>*β。由题意可知：α=aωT…TAω’=β，由于文法是CFG，终结符a不可能被替换空串或非终结符，因此假设有误。得证；（2）同（1），假设：β的首符号为非终结符时，α首符号为终结符。即设：α=aω；β=Aω’且α=aωT…TAω’=β，与（1）同理，得证。10.证明：因为存在句子：abc，它对应有两个语法树（或最右推导）：STABTAbcTabcSTDCTDcTabc所以，本文法具有二义性。11.解： 课后答案网www.khdaw.com(1)STABTAaSbTAacbTbAacbTbbAacbTbbaacb上面推导中，下划线部分为当前句型的句柄。对应的语法树为：全部的短语：第一个a(a1)是句子bbaacb相对于非终结符A(A1)(产生式A?a）的短语（直接短语）；b1a1是句子bbaacb相对于非终结符A2的短语；b2b1a1是句子bbaacb相对于非终结符A3的短语；c是句子bbaacb相对于非终结符S1（产生式S?c）的短语（直接短语）；a2cb3是句子bbaacb相对于非终结符B的短语；b2b1a1a2cb3是句子bbaacb相对于非终结符S2的短语；注：符号的下标是为了描述方便加上去的。（2）句子（（（b）a（a））（b））的最右推导：ST（AS）T（A（b））T（（SaA）（b））T（（Sa（a））（b））T（（（b）a（a））（b））相应的语法树是： 课后答案网www.khdaw.com（3）解：iii*i+↑对应的语法树略。最右推导：ETT=>F=>FP↑TFE↑TFET+↑TFEF+↑TFEP+↑TFEi+↑TFTi+↑TFTF*i+↑TFTP*i+↑TFTi*i+↑TFFi*i+↑TFPi*i+↑TFii*i+↑TPii*i+↑Tiii*i+↑12.证明：充分性：当前文法下的每一符号串仅有一个句柄和一个句柄产生式T对当前符号串有唯一的最左归约T对每一步推导都有唯一的最右推导T有唯一的语法树。必要性：有唯一的语法树T对每一步推导都有唯一的最右推导T对当前符号串有唯一的最左归约T当前文法下的每一符号串仅有一个句柄和一个句柄产生式13.化简下列各个文法（1）解：S→bCACdA→cSA|cCCC→cS|c（2）解：S→aAB|fA|gA→e|dDAD→eAB→f（3）解：S→ac14.消除下列文法中的ε产生式（1）解：S→aAS|aS|bA→cS（2）解：S→aAA|aA|aA→bAc|bc|dAe|de15.消除下列文法中的无用产生式和单产生式（1）消除后的产生式如下： 课后答案网www.khdaw.comS→aB|BCB→DB|bC→bD→b|DB（2）消除后的产生式如下：S→SA|SB|（）|（S）|[]|[S]A→()|（S）|[]|[S]Bà[]|[S]（3）消除后的产生式如下：E→E+T|T*F|(E)|P↑F|iT→T*F|(E)|P↑F|iF→P↑F|(E)|iP→(E)|i第三章习题解答1．从略2． 课后答案网www.khdaw.com3假设W:表示载狐狸过河，G:表示载山羊过河，C:表示载白菜过河用到的状态1：狐狸和山羊在左岸2：狐狸和白菜载左岸3:羊和白菜在左岸4:狐狸和山羊在右岸5:狐狸和白菜在右岸6:山羊和白菜在右岸F:全在右岸4证明：只须证明文法G:A→αB或A→α（A,B∈VN,α∈VT+）等价于G1:A→aB或A→a(a∈VT+)•G1的产生式中A→aB,则B也有B→bC,C→cD….所以有A→abc…B’,a,b,c…∈VT,B’∈VN所以与G等价。2）G的产生式A→αB，α∈VT+，因为α是字符串，所以肯定存在着一个终结符a，使A→aB可见两者等价，所以由此文法产生的语言是正规语言。56根据文法知其产生的语言是 课后答案网www.khdaw.comL={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打头的串.8从略。9 课后答案网www.khdaw.com 课后答案网www.khdaw.com（2）相应的3型文法(i)S→aAS→bSA→aAA→bBB→a|aBB→b|bB(ii)S→aA|aS→bBB→aB|bBA→aBA→b|bA(iii)S→aAS→bBA→bAA→aCB→aBB→bCC→a|aCC→b|bC(iv)S→bSS→aAA→aCA→bBB→aBB→bCC→a|aCC→b|bC（3）用自然语言描述输入串的特征(i)以任意个(包括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所组成的任意串结尾或者以任意个（包括0）b开头，中间跟ab后再接任意（包括0）a再接b，最后由一个a,b所组成的任意串结尾10（1）G1的状态转换图：G2的状态转换图： 课后答案网www.khdaw.com(2)G1等价的左线性文法：S→Bb,S→Dd,D→C,B→Db,C→Bc,B→Ab,B→ε,A→aG2等价的右线性文法：S→dD,S→aB,D→C,B→abC,B→bB,B→bA,B→ε,C→cA,A→a（3）对G1文法,abb的推导序列是：S=>aA=>abB=>abb对G1’文法，abb的推导序列是：S=>Bb=>Abb=>abb对G2文法，aabca的推导序列是：S=>Aa=>Cca=>Babca=>aabca对G2’文法，aabca的推导序列是：S=>aB=>aabC=>aabcA=>aabca（4）对串acbd来说，G1,G1’文法都不能产生。11将右线性文法化为左线性文法的算法：o（1）对于G中每一个形如A→aB的产生式且A是开始符，将其变为B→a,否则若A不是开始符，B→Aa;o（2）对于G中每一个形如A→a的产生式,将其变为S→Aa12(1) 课后答案网www.khdaw.com状态矩阵是：记[S]=q0[B]=q1[AB]=q2[SA]=q3,最小化和确定化后如图（2）记[S]=q0,[A]=q1,[BS]=q2最小化和确定化后的状态转换图如下13（1）将具有ε动作的NFA确定化后，其状态转换图如图：记{S0,S2,S3}=q0{S1}=q1{S2S3}=q2{S3}=q3 课后答案网www.khdaw.com(2)记{S}=q0{Z}=q1{UR}=q2{SX}=q3{YUR}=q4{XSU}=q5{YURZ}=q6{ZS}=q714（1）从略(2)化简后S0和S1作为一个状态，S5和S6作为一个状态。状态转换图如图15从略。16从略。•(1)r*表示的正规式集是{ε,r,rr,rrr,…}(ε|r)*表示的正规式集是{ε,εε,…}∪{r,rr,rrr,…}={ε,r,rr,rrr,…}ε|rr*表示的正规式集是{ε,r,rr,rrr,…} 课后答案网www.khdaw.com(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(1)B=cB+c(2)T=bT+bB(3)所以B=c*cT=b*bc*cS=a*ab*bc*c•G1:S=aA+B(1)B=cC+b(2)A=abS+bB(3)C=D(4)D=bB+d(5)把（4）（5）代入（2），得B＝c(bB+d)+b=cbB+cd+b得B=(cb)*(cd|b),代入（3）得A=abS+b(cb)*(cd|b)把它打入（1）得S=a(abS+b(cb)*(cd|b))+(cb)*(cd|b)=aabS+ab(cb)*(cd|b)+(cb)*(cd|b)=(aab)*(ab(cb)*(cd|b)|(cb)*(cd|b)) 课后答案网www.khdaw.comG2:S=Aa+B(1)A=Cc+Bb(2)B=Bb+a(3)C=D+Bab(4)D=d(5)可得D=dB=ab*C=ab*ab|bA=(ab*ab|b)c+ab*bS=(ab*ab|b)ca+ab*ba+ab*=(ab*ab|b)ca|ab*ba|ab*20•识别此语言的正规式是S=’LABEL’d(d|,d)*;•从略。21从略。22构造NFA其余从略。23下面举一个能够识别1,2,3,10,20,100的例子，读者可以推而广之。%{#include#include 课后答案网www.khdaw.com#include#defineON1#defineTW2#defineTHRE3#defineTE10#defineTWENT20#defineHUNDRE100#defineWHITE9999%}upper[A-Z]%%ONEreturnON;TWOreturnTW;THREEreturnTHRE;TENreturnTE;TWENTYreturnTWENT;HUNDREDreturnHUNDRE;""+|treturnWHITE;nreturn0;%%main(intargc,char*argv[]){intc,i=0;chartmp[30]; 课后答案网www.khdaw.comif(argc==2){if((yyin=fopen(argv[1],"r"))==NULL){printf("can"topen%sn",argv[1]);exit(0);}}while((c=yylex())!=0){switch(c){caseON:c=yylex();if(c==0)goto{i+=1;label;}c=yylex();if(c==HUNDRE)i+=100;elsei+=1;break;caseTW:c=yylex();c=yylex();if(c==HUNDRE)i+=200;elsei+=2; 课后答案网www.khdaw.combreak;caseTWENT:i+=20;break;caseTE:i+=10;break;default:break;}}/*while*/label:printf("%dn",i);return;}24（1）Dn表示的正规集是长度为2n任意a和b组成的字符串。•此正规式的长度是2n•用来识别Dn的DFA至多需要2n＋1个状态。25从略。26（1）由{}括住的,中间由任意个非{组成的字符串,如{},{}},{a},{defg}等等。（2）匹配一行仅由一个大写字母和一个数字组成的串，如A1,F8,Z2等。（3）识别rn和除数字字符外的任何字符。•由’和’括住的，中间由两个’’或者非’和n组成的任意次的字符串。如’’’’,‘a’,’bb’,’def’，’’’’’’等等27O[Xx][0-9]*[a-fA-F]*|[0-9]+|(’([a-zA-Z]|\[Xx][0-7][0-7a-fA-F]|\0[01][0-7][0-7]|\[a-z])’)28^[a-zA-Z_]+[0-9]*[a-zA-Z_]*29参考程序如下： 课后答案网www.khdaw.com%{#include#include#include#defineUPPER2#defineWHITE3%}upper[A-Z]%%{upper}+returnUPPER;t|""+returnWHITE;%%main(intargc,char*argv[]){intc,i;if(argc==2){if((yyin=fopen(argv[1],"r"))==NULL){printf("can"topen%sn",argv[1]);exit(0);}}while((c=yylex())!=EOF){ 课后答案网www.khdaw.comif(c==2){for(i=0;yytext[i];i++)printf("%c",tolower(yytext[i]));yytext[0]="00";}if(c==3)printf("");elseprintf("%s",yytext);}return;}yywrap()第四章习题解答1.解：(1)S→(S)Z21|()Z21|[S]Z31|[]Z31A→(S)Z22|()Z22|[S]Z32|[]Z32B→(S)Z23|()Z23|[S]Z33|[]Z33Z11→ε|AZ11|BZ21Z12→AZ12|BZ22Z13→AZ13|BZ23 课后答案网www.khdaw.comZ21→Z11Z22→ε|Z12Z23→Z13Z31→Z21Z32→Z22Z33→ε|Z23(2)S→bZ11|aZ21A→bZ12|aZ22Z11→ε|AZ21Z12→AZ22Z21→SZ21Z22→ε|SZ22(3)S→(T)Z11|aZ11|Z11S→(T)Z12|aZ12|Z12Z11→ε|Z21Z12→Z22Z21→,SZ21Z22→ε|,SZ22•2.解：SAbB1,1.1(表示第1步，用产生式1.1推导,以下同)CAbbB2,2.1edAbbB3,4.1edCAbbB4,2.1ededAbbbB5,4.1edaAbbbB5，4.2(不符合，改写第5步，用4.2)edBfbbB4,2.2edCSdfbbB5,3.1ededSdfbbB6,4.1edaSdfbbB6,4.2eddfbbB5,3.2eddfbbCSd6,3.1eddfbbedSd7,4.1eddfbbaSd7,4.2eddfbbd6,3.2 课后答案网www.khdaw.com•3.解：以下Save表示savetoken_pointervalue,Restore表示restoretoken_pointervalue。(1)文法没有左递归。FunctionP:boolean;BeginSave;P:=true;Ifnext_token=”begin”thenIfnext_token=’d’thenIfnext_token=’;’thenIfXthenIfnext_token=”end”thenreturn;Restore;P:=false;End;FunctionX:boolean;BeginSave;X:=true;Ifnext_token=’d’thenIfnext_token=’;’thenIfXthenreturn;Restore;Ifnext_token=’s’then 课后答案网www.khdaw.comIfYthenreturn;Restore;X:=false;End;FunctionY:boolean;BeginSave;Y=true;Ifnext_token=’;’thenIfnext_token=’s’thenIfYthenreturn;Restore;End;(2)消去文法左递归，并记为：P→beginSendS→A|CA→V:=EC→ifEthenSE→VE’E’→+VE’|εV→IFunctionP:boolean;BeginSave;P:=true;Ifnext_token=”begin”thenIfSthenIfnext_token=”end”thenreturn;;Restore; 课后答案网www.khdaw.comP:=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;FunctionC:boolean;Begin 课后答案网www.khdaw.comSave;C:=true;Ifnext_token=”if”thenIfEthenIfnext_token=”then”thenIfSthenreturn;Restore;C:=false;End;FunctionE:boolean;BeginSave;E:=true;IfVthenIfEpthenreturn;Restore;E:=false;End;FunctionEp:boolean;BeingSave;Ep:=true;Ifnext_token=’+’thenIfVthen 课后答案网www.khdaw.comIfE’thenreturn;Return;End;•4.解：••5.证：因为是左递归文法，所以必存在左递归的非终结符A，及形如A→α|β的产生式,且αT*Ad.则first(Ad)∩first(β)≠φ,从而first(α)∩first(β)≠φ，即文法不满足LL（1）文法条件。得证。•6.证：LL（1）文法的分析句子过程的每一步，永远只有唯一的分析动作可进行。现在，假设LL(1)文法G是二义性文法，则存在句子α，它有两个不同的语法树。即存在着句子α有两个不同的最左推导。从而可知，用LL（1）方法进行句子α的分析过程中的某步中，存在两种不同的产生式替换，且均能正确进行语法分析，即LL（1）分析动作存在不确定性。与LL（1）性质矛盾。所以，G不是LL(1)文法。•7.解：(1)D产生式两个候选式fD和f的first集交集不为空，所以不是LL(1)的。(2)此文法具有左递归性，据第5题结论，不是LL(1)的。•8.解：(1)消除左递归性,得：S→bZ11|aZ21A→bZ12|aZ22Z11→bZ11|εZ12→bZ12Z21→bZ11|aZ21Z22→bZ12|aZ22|ε消除无用产生式得：S→bZ11|aZ21Z11→bZ11|εZ21→bZ11|aZ21 课后答案网www.khdaw.com此文法已满足LL(1)文法的三个条件，所以G’[S]:S→bZ11|aZ21Z11→bZ11|εZ21→bZ11|aZ21(2)G’文法的各非终结符的FIRST集和FOLLOW集：产生式FIRST集FOLLOW集S→bZ11{b}{#}→aZ21{a}Z11→bZ11{b}{#}→ε{ε}Z21→bZ11{b}{#}→aZ21{a}LL(1)分析表为：ab#SaZ21bZ11Z11bZ11εZ21aZ21bZ11•9.解：(1)产生式first集follow集S→SaB{b}{#,a,c}→bB{b}A→S{b}{c}→a{a}B→Ac{a,b}{#,a,c}(2)将S→SaB|bB改写为S→bBS’,S’→aBS’|ω,可验证，新文法是LL(1)的。•10.解：•1）为方便书写，记：<布尔表达式>为A，<布尔因子>为B，<布尔二次量>为C，<布尔初等量>为D，原文法可以简化为：A→A∨B|BB→B∧C|CC→┐D|DD→(A)|true|false, 课后答案网www.khdaw.com显然，文法含有左递归，消去后等价LL(1)文法为：A→BA’A’→∨BA’|ωB→CB’,B’→∧CB’|ωC→┐D|DD→(A)|true|false(2)略11、证：若LL（1）文法G有形如B→aAAb的产生式，且AT+ε及AT*ag,根据FIRST集FOLLOW集的构造算法可知，FIRST(A)中一切非ε加到FOLLOW(A)中，则a∈FOLLOW(A)；又因为a∈FIRST(ag),所以两集合相交非空，因此，G不是LL(1)文法；与前提矛盾，假设不成立，得证。12、解：(1)SA(a)bS==A=<=<(==<<<=<>>>)>>>>>b>>不是简单优先文法。(2)SRT()∧a,S>=R=T>(<=<<<<)>>∧>>a>>,<=<<<是简单优先文法。(3)SR(a,) 课后答案网www.khdaw.comS=<>(=<>,=<<)>>是简单优先文法。o首先消去无用产生式Z→E,Z→E+TSZT#i()SZ==T>>#=<<>(=<<<)>>化简后的文法是简单优先文法；13、解：SA/AS>>=A=<=>a>>A和/之间同时有关系=和<,所以不是简单优先文法；•提示：分析教材中给出的算法，选择一种合适的表示给定文法的方法（尽量简单），使得对文法的输入比较简单的同时(需要把输入转化为计算机语言表示，这种转化应该尽量简单)，能够比较简单地构造3个基本关系矩阵（=，LEAD和LAST）。•证明：设xjxj+1...xi是满足条件xj-1xi+1的最左子串。由=关系的定义，可知xjxj+1...xi必出现在某产生式的右部中。又因xj-1,L=<变量表>,V=<变量>,T=<类型>，a=VAR,则消去V，并采用分层法改写文法，得到：D→aW:T;W→LL→L,i|iT→r|n|b|c其全部简单优先关系是：DWTLa:;,ir|n|b|cDW=T=L>=a=<<:=<;,>>>=ir|n|b|c>是简单优先文法。•证：设STna,我们对n用归纳法，证明a不含两个非终结符相邻情况。n=1时，STa,即S→a是文法的产生式，根据定义，它不含上述情况。设n=k时，上述结论成立，且设STkdAb，由归纳假设，A两侧必为终结符。我们再进行一步推导，得STkdAbTdub,其中，A→u是文法中的产生式，由定义，u中不含两个非终结符相邻情况，从而dub两个非终结符相邻情况。得证。•证：由于G不是算符文法，G中至少有一个产生式，其右部含有两个非终结符相邻的情况。不失一般性，设其形为U→xABy,x,y∈V*,由于文法不含无用产生式，则必存在含有U的句型dUb，即存在推导ST*dUbTdxAByb.得证。•文法为：E→E↑A|AA→A*T|A/T|TT→T+V|T-V|VV→i|(E)•解：（1）构造算符优先矩阵：-*（）i#>>-<><><<>*><><<(<<<=< 课后答案网www.khdaw.com)>>>>I>>>>#<<<<（2）在（-，-）、（-，*）和（*，-）处有多重定义元素，不是算符优先文法；（3）改写方法：•将E→E-T中的减号与F→-P中的赋值运算符强制规定优先关系；•或者将F-P中的赋值运算符改为别的符号来表示；•(1)证明：由设句型a=…Ua…中含a的短语不含U，即存在A，A=>*ay,则a可归约为a=…Ua…ü*…UA…=b，b是G的一个句型，这与G是算符文法矛盾，所以，a中含有a的短语必含U。（2）的证明与（1）类似，略。•证：（1）对于a=…aU…是句型，必有ST*a(=…aU…)T+…ab….即在归约过程中,b先于a被归约,从而,aby+1，与bx-1=bx及by=by+1矛盾，得证。•提示：根据27题的结论，只要证u是句型α的短语，根据=关系的定义容易知道u是句型α的素短语。•证：与28题的不同点只是a0,an+1可以是’#’,不影响结论。•证：设不能含有素短语，则只能是含有短语（不能含有终结符号），则该短语只能含有一个非终结符号，否则不符合算符文法定义，得证。•解：（1）算符优先矩阵：+*↑（）i#+><<<><>*>><<><>↑>><<><>(<<<<=< 课后答案网www.khdaw.com)>>>>>I>>>>>#<<<<<（2）用Floyd方法将优先矩阵线性化得到得的优先函数为：+*↑()i#F3551771G2466161•解：用Floyd方法对已知的优先矩阵构造的优先函数为：zbMLa()f1567747g1654667•解：（1）优先矩阵如下：[]a#[>=]>><>#<<<（2）用Bell方法求优先函数的过程如下：[]a#f5751g5561 课后答案网www.khdaw.com（3）显然，文法不是算符优先文法,所以不能线性化。•略。•解：（1）识别全部活前缀的DFA如下：（以表格的形式来表示，很容易可以转化为图的形式，本章中其余的题目也是采用这种形式表示。）状态项目集经过的符号到达的状态S’→·SS→·aSbSI1I0S→·aScaI2S→·abI1S’→S·S→a·SbS→a·ScSI3S→a·bI2aI2S→·aSbbI4S→·aScS→·abS→aS·bbI5I3S→aS·ccI6I4S→ab·I5S→aSb·I6S→aSc·（2）识别全部活前缀的DFA如下：状态项目集经过的符号到达的状态S’→·SSI1I0S→·cAcIS→·ccB·I1S’→S·S→c·AAI3I2 课后答案网www.khdaw.comS→c·cBcI4A→·cAaI5A→·aI3S→cA·S→cc·BBI6A→c·AAI5B→·ccBI4cI7B→·bbI8A→·cAaI5A→·aI5A→a·I6S→ccB·B→c·cBCI9A→c·AI7AI10A→·cAaI5A→·aI8B→b·B→cc·BBI11A→c·AAI10B→·ccBI9cI7B→·bbI8A→·cAaI5A→·aI10A→cA·I11B→ccB·所求的LR(0)项目规范族C={I0,I1,…,I11}（3）状态项目集经过的符号到达的状态 课后答案网www.khdaw.comS’→·SSI1S→·aSSbI0cI2S→·aSSSaI3S→·cI1S’→S·I2S→c·S→a·SSbS→a·SSSSI4I3S→·aSSbcI2S→·aSSSaI3S→·cS→aS·SbS→aS·SSSI5I4S→·aSSbcI2S→·aSSSaI3S→·cS→aSS·bSI7S→aSS·SaI3I5S→·aSSbbI6S→·aSSScI2S→·cI6S→aSSb·I7S→aSSS·（4）状态项目集经过的符号到达的状态S’→·SSI1I0S→·AAI2 课后答案网www.khdaw.comA→·AbaI3A→·aI1S’→S·S→A·I2bI4S→A·bI3A→a·I4S→Ab·•解：（1）是LR(0)文法，其SLR(1)分析表如下：FOLLOW(S)={#,b,c}ACTIONGOTOabc#S0S211ACC2S2S433S5S64R3R3R35R1R1R16R2R2R2（2）是LR(0)文法，其SLR(1)分析表如下：FOLLOW(S)=FOLLOW(A)=FOLLOW(B)={#}GOTACTIONOabc#SAB0S211ACC2S5S433R14S5S8S7365R46R27S5S9108R69S5S8S7101110R311R5（3）是LR(0)文法，其SLR(1)分析表如下：FOLLOW(S)={#,a,b,c} 课后答案网www.khdaw.comACTIONGOTOabc#S0S3S211ACC2R3R3R3R33S3S244S3S255S3S6S276R1R1R1R17R2R2R2R2（4）因为I2中含有冲突项目，所以不是LR(0)文法，其SLR(1)分析表如下：FOLLOW(S)={#}∩{b}=φ(所以可以用SLR(1)规则解决冲突),FOLLOW(A)={b,#}ACTIONGOTOab#SA0S3121ACC2S4R13R3R34R2R2•解：状态项目集经过的符号到达的状态S’→·SSI1I0S→·(SR(I2S→·aaI3I1S’→S·S→(·SRSI4I2S→·(SR(I2S→·aaI3I3S→a·S→(S·RaI3S→·(SR(I2I4S→·aRI5R→·,SR,I6 课后答案网www.khdaw.comR→·))I7I5S→(SR·R→,·SRSI8I6S→·(SR(I2S→·aaI3I7R→)·R→,S·R)I7I8R→·,SR,I6R→·)RI9I9R→,SR·LR(0)分析表如下：GOTACTIONOa(),#SR0S3S211ACC2S3S243R2R2R2R2R24S3S2S7S655R1R1R1R1R16S3S287R4R4R4R4R48S7S699R3R3R3R3R3可见是LR(0)文法。•解：（1）状态项目集经过的符号到达的状态S’→·SSI1I0S→·SabbI2S→·bRI1S’→S·acca(冲突项目)S→S·abI3 课后答案网www.khdaw.comS→b·RRI4R→·SSI5I2R→·aaI6S→·SabbI2S→·bRI3S→Sa·bbI7I4S→bR·r2R→S·I5aI3S→S·abI6R→a·I7S→Sab·项目I1,I5同时具有移进和归约项目，对于I5={R→S·,S→S·ab},follow(R)={a},follow(R)∩{a}={a},所以SLR(1)规则不能解决冲突，从而该文法不是SLR(1)文法。（2）状态项目集经过的符号到达的状态S’→·SSI1S→·aSABaI2I0S→·BABI3B→·bbI4I1S’→S·S→a·SABSI5S→·aSABaI2I2S→·BABI3B→·bbI4S→B·AAI6A→·aAaI7I3A→·BBI8B→·bbI4 课后答案网www.khdaw.comI4B→b·r5S→aS·ABAI9A→·aAaI7I5A→·BBI8B→·bbI4I6S→BA·r2A→a·AAI10A→·BBI8I7A→·aAaI7B→·bbI4I8A→B·r4S→aSA·BBI11I9B→·bbI4I10A→aA·r3I11S→aSAB·r1不存在冲突项目，故该文法是LR(0)文法，也是SLR(1)文法。SLR(1)分析表如下：ACTIONGOTOab#SAB0S2S4131ACC2S2S4533S7S4684R5R5R55S7S4986R2R2R27S7S41088R4R4R49S41110R3R3R311R1R1R1（3）先求识别全部活前缀的DFA：状态项目集经过的符号到达的状态 课后答案网www.khdaw.comS’→·SSI1S→·aSbI0aI2S→·bSabI3S→·abI1S’→S·accS→a·SBS→a·bSI4I2S→·aSbbI5S→·bSaaI2S→·abS→b·SaSI6S→·aSbI3aI2S→·bSabI3S→·abI4S→aS·bbI7I5S→ab·r3I6S→bS·aaI8I7S→aSb·r1I8S→bSa·r2不存在冲突项目，故该文法是LR(0)文法，也是SLR(1)文法。SLR(1)分析表如下：ACTIONGOTOab#S0S2S311ACC2S2S543S2S364S75R3R3R36S87R1R1R18R2R2R2 课后答案网www.khdaw.com（4）先求识别全部活前缀的DFA：状态项目集经过的符号到达的状态S’→·SSI1I0S→·aAaI2S→·bBbI3I1S’→S·accS→a·AI4I2AA→·cAdI5(冲突)cA→·r4S→b·BI6I3BB→·cBddI7(冲突)cB→·r6I4S→aA·r1A→c·AdI8I5AA→·cAdI5(冲突)cA→·r4I6S→bB·r2B→c·BddI9I7BB→c·BddI7(冲突)cB→·r6I8A→cA·ddI10I9B→cB·dddI11I10A→cAd·r3I11B→cBd·ddI12I12B→cBdd·r5因为follow(A)=follow(B)={#,d},所以冲突项目I2,I3,I5,I7可以用SLR(1)规则得以解决，从而该文法为SLR(1)文法。其SLR(1)分析表如下：ACTIONGOTOabcd#SAB0S2S311Acc2S5R4R443S7R6R66 课后答案网www.khdaw.com4R15S5R4R486R27S7R6R698S109S1110R3R311S1212R5R5（5）解：原文法等价化为q1→q2,q1→q3,q2→q4;q5,q4→beginD,q4→q4;D,q5→Send,q5→S;q5,q3→beginq5,先求识别全部活前缀的DFA：状态项目集经过的符号到达的状态q1’→·q1q1→·q2q1I1q1→·q3q2I2I0q2→·q4;q5q3I3q3→·beginq5q4I4q4→·beginDbeginI5q4→·q4;DI1q1’→q1·ACCI2q1→q2·R1I3q1→q3·R2q2→q4·;q5;I4I6q4→q4·;DDq3→begin·q5q5I7q3→begin·DI5DI8q5→·SendSI9q5→·S;q5q2→q4;·q5q5I10I6q4→q4;·DDI11 课后答案网www.khdaw.comq5→·SendSI9q5→·S;q5I7q3→beginq5·R8I8q3→beginD·R4q5→S·endendI12I9q5→S·;q5;I13I10q2→q4;q5·R3I11q4→q4;D·R5I12q5→Send·R6q5→s;·q5q5I14I13q5→·SendSI9q5→·S;q5I14q5→s;q5·R7不存在冲突项目，故该文法是LR(0)文法，也是SLR(1)文法。SLR(1)分析表如下：ACTIONGOTO;beginDSend#q1q2q3q4q5012341Acc2R13R24S65S8S976S7S9107R88R49S13S1210R311R512R613S91414R7（6）解：原文法可化为等价形式：q1→beginq2q3end,q2→q2d;,q2→ε,q3→q3;q4,q3→q4,q4→S,q4→ε,先求识别全部活前缀的DFA： 课后答案网www.khdaw.com状态项目集经过的符号到达的状态q1’→·q1q1I1I0q1→·beginq2q3endbeginI2I1q1’→q1·ACCq1→begin·q2q3endq2I3I2q2→·q2d;q2R3q2→·Q1→beginq2·q3endI4q2→q2·d;q3I10I3q3→·q3;q4DdI5(冲突项目)q3→·q4q4I6q4→·SSR7q4→·q1→beginq2q3·endendI7I4q3→q3·;q4;I8I5q3→q4·R5I6q4→S·R6I7q1→beginq2q3end·R1q3→q3;·q4I9I8q4q4→·SI6(冲突项目)Sq4→·R7I9q3→q3;q4·R4I10q2→q2d·;;I11I11q2→q2d;·R2因为follow(q4)={end,#}，故冲突项目可以通过SLR(1)规则来解决，从而文法为SLR(1)文法。SLR(1)分析表如下：actiongotobeginendd;S#q1q2q3q40S2112R3R3R3R333R7S10R7S6454S7S8 课后答案网www.khdaw.com5R5R56R6R67R18R7R7S699R4R41011R2R2R2R2•解：识别活前缀的DFA及LR(0)分析表：状态项目集经过的符号到达的状态S’→·SS→·AAdSI0S→·cAdAI6S→·bI0aI5A→·AScbI4A→·SbcI3A→·cdA→·aS’→S·I1bI2A→S·bI2A→Sb·S→c·AdA→c·dSI8A→·AScAI9A→·SbaI5I3A→·cdbI4A→·acI3S→·AAddI7S→·cAd 课后答案网www.khdaw.comS→·bI4S→b·I5A→a·S→A·AdA→A·ScA→·AScSI11A→·SbAI10I6A→·cdaI5A→·abI4S→·AAdcI3S→·cAdS→·bI7A→cd·I8A→S·bbI2S→cA·dA→A·ScS→A·AdSI11S→·AAdAI10S→·cAdaI5I9S→·bbI4A→·ASccI3A→·SbdI14A→·cdA→·aS→AA·dSI11I10A→A·ScAI10 课后答案网www.khdaw.comS→A·AdaI5S→·AAdbI4S→·cAdcI3S→·bdI13A→·AScA→·SbA→·cdA→·aA→AS·cbI2I11A→S·bcI12I12A→ASc·I13S→AAd·I14S→cAd·ACTIONGOTOabcd#SA0s5s4s3161s2acc2r5r5r5r5r53s5s4s3s7894r3r3r3r3r35r7r7r7r7r76s5s4s37r6r6r6r6r611108s29s5s4s3s14111010s5s4s3s13111011s2s1212r4r4r4r4r413r1r1r1r1r114r2r2r2r2r2SLR(1)分析法：FOLLOW(S)={c,b}FOLLOW(A)={a,b,c,d}ACTIONGOTOabcd#SA0s5s4s3161s2acc 课后答案网www.khdaw.com2r5r5r5r53s5s4s3s7894r3r35r7r7r7r76s5s4s37r6r6r6r611108s29s5s4s3s14111010s5s4s3s13111011s2s1212R4r4r4r413r1r114r2r2两表的异同：两表都用ACTION表和GOTO表反映了移进、归约（包括接受）的状态和动作。不同之处在于SLR(1)增加了在归约的时候考虑向前符号a以解释可能出现的“移进——归约”冲突；SLR（1）的分析较稀疏些，原因是填写归约项时，并不是在一状态对应行上全部填写归约动作，而是考虑了相应非终结符的FOLLOW集因素。另外，在分析效率上SLR（1）分析的效率更高一些，因为在发现错误方面，SLR（1）比LR（0）分析发现的更早些。•解：求LR(1)项目集和状态转换表：状态项目集经过的符号到达的状态S’→·S#SI1S→·A#AI2A→·BA#I0BI3A→·#aI4B→·aB#,a,bbI5B→·b#,a,bI1S’→S·#I2S→A·#A→B·A#AI6A→·#BI3I3A→·BA#aI4B→·aB#,a,bbI5 课后答案网www.khdaw.comB→·b#,a,bB→a·B#,a,bBI7I4B→·aB#,a,baI4B→·b#,a,bbI5I5B→b·#,a,bI6A→BA·#I7B→aB·#,a,b相应的LR(1)分析表为：STATEACTIONGOTOab#SAB0S4S5R31231ACC2R23S4S5R3634S4S575R5R5R56R27R4R4R4用LR(1)分析表对输入符号串abab的分析过程：步骤状态栈中符号余留符号分析动作下一状态10#abab#S44204#abab#S553045#abab#R574047#aBab#R43503#Bab#S446034#Bab#S5570345#Bab#R4780347#BaB#R439033#BB#R36100336#BBA#R2611036#BA#R211201#A#acc•解：（1）求LR(1)项目集和状态转换图：状态项目集经过的符号到达的状态 课后答案网www.khdaw.comS’→·S#S→·A#SI1I0A→·AB#,a,bAI2A→·I1S’→S·#S→A·#BI3A→A·B#,a,bI2aI5B→·aB#,a,bbI4B→·b#,a,bI3A→AB·#,a,bI4B→b·#,a,bB→a·B#,a,bBI6I5B→·aB#,a,baI5B→·b#,a,bbI4I6B→aB·#,a,b相应的LR(1)分析表为：STATEACTIONGOTOab#SAB0R3R3R3121Acc2S5S4R13R2R2R24R5R5R55S5S466R4R4R4表中没有多从定义的元素，所以文法是LR(1)文法。（2）LR(1)分析法：状态项目集经过的符号到达的状态E’→·E#EI1I0E→·E+T#/+TI1 课后答案网www.khdaw.comE→·T#/+(I5T→·(E)#/+aI4T→·a#/+E’→E·#I1+I2E→E·+T#/+E→E+·T#/+TI3I2T→·(E)#/+(I5T→·a#/+aI4I3E→E+T·#/TI4T→a·#/+T→(·E)#/+EI7E→·E+T+/)CI8I5E→·T)/+TI9T→·(E)+/)aI12T→·a+/)I6E→T·#/+T→(E·)#/+)I10I7E→E·+T+/)+I11T→(·E))/+(I8E→·E+T+/)aI12I8E→·T)/+EI14T→·(E)+/)TI9T→·a+/)I9E→T·+/)I10T→(E)·#/+E→E+·T+/)(I8I11T→·(E)+/)TI13T→·a+/)aI12I12T→a·+/)I13E→E+T·)/+ 课后答案网www.khdaw.comT→(E·)+/)+I11I14E→E·+T+/))I15I15T→(E)·+/)LALR(1)分析：（合并同心集）状态项目集经过的符号到达的状态E’→·E#E→·E+T#/+EI1I0E→·T#/+TI6/I9T→·(E)#/+aI4/I12T→·a#/+E’→E·#I1+I2/I11E→E·+T#/+E→E+·T#/+/）TI3/I13I2/I11T→·(E)#/+/）(I5/I8T→·a#/+/）aI4/I12I3/I13E→E+T·)/+/#I4/I12T→a·+/)/#T→(·E)#/+/）TI6/I9E→·E+T+/)(I5/I8I5/I8E→·T)/+EI7/I14T→·(E)+/)aI4/I12T→·a+/)I6/I9E→T·+/)/#T→(E·)+/)/#+I2/I11I7/I14E→E·+T+/))I10/I15I10/I15T→(E)·+/)/#GOTLR(1ACTIONO)+()a#ET0S5S4161S2ACC 课后答案网www.khdaw.com2S5S433R1R14R4R45S8S12796R2R27S11S108S8S121499R2R210R3R311S8S121312R4R413R1R114S11S1515R3R3可以看出，表中无冲突项，所以是LR(1)文法；LALR（1）分析表：LR(1ACTIONGOTO)+()a#ET0S5/S8S4/S1216/91S2/S11ACC2/11S5/S8S4/S123/133/13R1R1R14/12R4R4R45/8S5/S8S4/S127/146/96/9R2R2R210/15R3R3R37/14S2/S11S10/S15•解：（1）求LR(1)项目集和状态转换图：状态项目集经过的符号到达的状态E’→·E#E→·E+E#,+,*EI1I0E→·E*E#,+,*iI2E→·i#,+,*E’→E·#+I3I1E→E·+E#,+,**I4 课后答案网www.khdaw.comE→E·*E#,+,*I2E→i·#,+,*E→E+·E#,+,*E→·E+E#,+,*EI5I3E→·E*E#,+,*iI2E→·i#,+,*E→E*·E#,+,*E→·E+E#,+,*EI6I4E→·E*E#,+,*iI2E→·i#,+,*E→E+E·#,+,*+I3I5E→E·+E#,+,**I4E→E·*E#,+,*E→E*E·#,+,*+I3I6E→E·+E#,+,**I4E→E·*E#,+,*依据以上图求出该文法的LR(1)分析表知道由于项目I5,I6导致了有多重定义的元素，所以不是LR(1)文法。事实上，从文法本身可以看出它是二义性的，因此不可能是LR（1）文法。等价的LR(1)文法为：E→E+T|TF→T*F|FF→i。另外，对原文法的冲突项来说，若考虑算术运算符的运算优先级别，以及结合方式，上述冲突是可解决的。例如，假设表达式运算满足左结合律（即a+b+c=(a+b)+c而不是右结合律：a+b+c=a+(b+c)）,及*运算和优化优先级高于+运算，上述文法相应的LR（1）分析表为ACTIONGOT状O态i+*#E0s211s3s4acc2r3r3r33s254s265r1s4r16r2r2r2 课后答案网www.khdaw.com（2）解：LR(1)：状态项目集经过的符号到达的状态S’→·S#S→·aSa#SI1I0S→·bSb#aI2S→·a#bI3S→·b#I1S’→S·#S→a·Sa#S→a·#SI4S→·aSaaI2aI7S→·bSbabI6S→·aaS→·baS→b·Sb#S→b·#SI11S→·aSabI3aI14S→·abbI13S→·bSbbS→·bbI4S→aS·a#aI5I5S→aSa·#S→b·SbaSI10S→b·aI6aI14S→·aSabbI13S→·bSbb 课后答案网www.khdaw.comS→·abS→·bbS→a·SaaS→a·aSI8S→·aSaaI7aI7S→·bSbabI6S→·aaS→·baI8S→aS·aaaI9I9S→aSa·aI10S→bS·babI15I11S→bS·b#bI12I12S→bSb·#S→b·SbbS→b·bSI16S→·aSabI13aI14S→·bSbbbI13S→·abS→·bbS→a·SabS→a·bSI18S→·aSaaI14aI7S→·bSbabI6S→·aaS→·baI15S→bSb·aI16S→bS·bbbI17I17S→bSb·bI18S→aS·abaI19I19S→aSa·b 课后答案网www.khdaw.com有移进——归约冲突，不是LR(1)文法。（3）求LR(1)项目集和状态转换图：状态项目集经过的符号到达的状态S’→·S#SI1S→·V:=E#VI2I0S→·LS#LI3L→·I:III4V→·I:I1S’→S·#I2S→V·:=E#:I5S→L·S#S→·V:=E#SI6I3S→·LS#LI3V→·I:II4L→·I:IL→I·:II4:I7V→I·:I5S→V:·=E#=I8I6S→LS·#I7L→I:·II8S→V:=·E#EI9I9S→V:=E·#依据以上图求出该文法的LR(1)分析表知道由于项目I4导致了有多重定义的元素，所以不是LR(1)文法。（4）略。•证：根据第3章“词法分析及词法分析程序”，我们知道任一正规集可以由某一正规式r表示，而对于任一正规式r，都可以构造一个DFA,并且两者在表述语言的意义下等价。根据这个DFA，我们可以很容易地构造一个分析表。方法是对于DFA中的每一个子图，如果从状态Ii，经过了终结符号a,到达状态Ij,则在分析表中有ACTION(Ii,a)=Sj，如果Sj是一个终结状态，则置ACTION(Ii,a)=ACC。 课后答案网www.khdaw.com•解：SLR(1)分析表比LR(0)分析表在采用一定形式存储时（如稀疏矩阵），会少一些存储空间。另外，在分析进行到归约动作时，LR（0）无论下一符号是什么（即使是错误的输入），都将先进行归约，然后才判断下一输入符是否正确；而SLR（1）在进行归约时还要先看看下一符号是否正确，否则将报错。从而可知，对于有错误的输入串，SLR（1）分析效率要高一些。•证：考察LR分析器的总控程序，可以知道访问GOTO分析表元素的可能只有两种，下面分情况讨论：•先访问ACTION(Sm,ai)=”移进”，再访问GOTO(Sm,ai)=Sm+1,其中ai是一个终结符。查看构造LR分析表的算法的条目（1），可以知道当ai是一个终结符时，填写ACTION(Sm,ai)=”移进”总是伴随着填写GOTO(Sm,ai)=Sm+1，所以这种情况下结论成立。•先访问ACTION(Sm,ai)=rj，其中ai是一个终结符,rj意指按文法的第j个产生式A→Xm-r+1Xm-r+2···Xm进行归约，再访问GOTO(Sm-r,A)=Sl,其中A是一个非终结符。查看构造LR分析表的算法的条目（1），可以知道当ai是一个非终结符时，填写GOTO(Sm,ai)=Sm+1，即只有归约出了ai时，再状态转换到Sm+1,和总控程序情况一致，所以这种情况下结论成立。综上所述，结论成立。46．证明：在文法G[S]中，只有非终结符S有两个候选式，AaAb及BbBa，而两个候选的FIRST集分别为{a}和{b}，它们不相交，所以，文法G[S]满足LL（1）文法的条件，是LL（1）文法。在SLR（1）方法识别活前缀的DFA中，项目I0={S"→·S,S→·AaAb,S→·BbBa,A→e·,B→e·}中出现归约-归约冲突，而follow(A)=follow(B)={a,b}，用SLR（1）方法不能解决冲突。47．略。48．略。第五章习题解答5.1解：•属性文法是文法符号带有语义属性的前后文无关文法；•属性翻译文法首先是对文法的属性依赖关系作出限制，不允许出现属性的直接或间接的循环定义，即要求属性文法是良定义的；其次还应将属 课后答案网www.khdaw.com性定义规则改造为计算属性值的语义程序，即将静态的定义规则改写为可动态执行的语义动作；•属性文法是静态描述，而属性翻译文法是动态描述，有语义动作。5.2解：•综合属性有：Z.aZ.pX.dX.c继承属性有：X.b•属性依赖出现了循环；5.3解：S属性文法一定是L属性文法，因为前者是在后者基础上加上限制条件，即非终结符只有综合属性；反之当然不正确。5.4解：•A-BC+*DE-^•ad*c+d/e+f*g+•ax+4<=cd3*/\/•de*c+b/a/f^•s0=;i1=;i100<=BZssii*+=;ii1+=;BRS2’5.5解：•a+b*c•a*(b-c)-(c+d)/e•有误•if(a0doifA=1thenC:=C+1elsewhileA<=DdoA:=A+2用产生式W1→while归约，得(1)Wl.loop→2.当前句型为WlA0doifA=1thenC:=C+1elsewhileA<=DdoA:=A+2用产生式Expr→idenropiden归约，得(1)Wl.loop→Expr.TC→(j0doifA=1thenC:=C+1elsewhileA<=DdoA:=A+2用产生式Expr^→Expr’ù’归约，得(1)Wl.loop→(j0doifA=1thenC:=C+1elsewhileA<=DdoA:=A+2用产生式Expr→idenropiden归约，得(1)Wl.loop→(j,B.0,0)(4)Expr2.FC→(j,0,0,0);5.当前句型为WlExpr^ExprdoifA=1thenC:=C+1elsewhileA<=DdoA:=A+2用产生式Expr→Expr^Expr归约，得(1)Wl.loop→(j,B.0,0) 课后答案网www.khdaw.com(4)Expr.FC→(j,0,0,2);6.当前句型为WlExprdoifA=1thenC:=C+1elsewhileA<=DdoA:=A+2用产生式WED→W1Exprdo归约，得(1)WED.loop→(j,B.0,5)(4)WED.CH→(j,0,0,2);7.当前句型为WEDifA=1thenC:=C+1elsewhileA<=DdoA:=A+2用产生式Expr→idenropiden归约，得(1)WED.loop→(j,B.0,5)(4)WED.CH→(j,0,0,2);(5)Expr.TC→(j=,A,1,0)(6)Expr.FC→(j,0,0,0)8.当前句型为WEDifExprthenC:=C+1elsewhileA<=DdoA:=A+2用产生式Condition→ifExprthen归约，得(1)WED.loop→(j,B.0,5)(4)WED.CH→(j,0,0,2);(5)(j=,A,1,7)(6)Condition.CH→(j,0,0,0)9.当前句型为WEDConditionC:=C+1elsewhileA<=DdoA:=A+2将赋值语句C:=C+1归约为Statement，得 课后答案网www.khdaw.com(1)WED.loop→(j,B.0,5)(4)WED.CH→(j,0,0,2);(5)(j=,A,1,7)(6)Condition.CH→(j,0,0,0)(7)(+.,C,1,T1)(8)(=,T1,1,C)10.当前句型为WEDConditionStatementelsewhileA<=DdoA:=A+2用产生式CondStElseàConditionStatement归约，(1)WED.loop→(j,B.0,5)(4)WED.CH→(j,0,0,2);(5)(j=,A,1,7)(6)(j,0,0,10)(7)(+.,C,1,T1)(8)(=,T1,1,C)(9)CondStElse→(j,0,0,0)11.当前句型为WEDCondStElsewhileA<=DdoA:=A+2用产生式W1’→while归约，得(1)WED.loop→(j,B.0,5) 课后答案网www.khdaw.com(4)WED.CH→(j,0,0,2);(5)(j=,A,1,7)(6)(j,0,0,10)(7)(+.,C,1,T1)(8)(=,T1,1,C)(9)CondStElse→(j,0,0,0)(10)Wl.loop→12.当前句型为WEDCondStElseWlA<=DdoA:=A+2用产生式Expr→idenropiden归约，得(1)WED.loop→(j,B.0,5)(4)WED.CH→(j,0,0,2);(5)(j=,A,1,7)(6)(j,0,0,10)(7)(+.,C,1,T1)(8)(=,T1,1,C)(9)CondStElse→(j,0,0,0)(10)Wl.loop→Expr.TC→(j,A,D,0)(11)Expr.FC→(j,0,0,0)13.当前句型为WEDCondStElseWlExprdoA:=A+2用产生式WED→WlExprdo归约，得(1)WED.loop→(j,B.0,5)(4)WED.CH→(j,0,0,2);(5)(j=,A,1,7)(6)(j,0,0,10)(7)(+.,C,1,T1)(8)(=,T1,1,C)(9)CondStElse→(j,0,0,0)(10)WED.loop→(j,A,D,12)(11)WED.CH→(j,0,0,0)14.当前句型为WEDCondStElseWEDA:=A+2将赋值语句归约A:=A+2为Statement得(1)WED.loop→(j,B.0,5)(4)WED.CH→(j,0,0,2);(5)(j=,A,1,7)(6)(j,0,0,10)(7)(+.,C,1,T1)(8)(=,T1,,C)(9)CondStElse→(j,0,0,0)(10)WED.loop→(j,A,D,12)(11)WED.CH→(j,0,0,0)(12)(+,A,2,T2)(13)(=,T2,,A) 课后答案网www.khdaw.com15.当前句型为WEDCondStElseWEDStatement,用产生式Statement→WEDStatement归约，得(1)WED.loop→(j,B.0,5)(4)WED.CH→(j,0,0,2);(5)(j=,A,1,7)(6)(j,0,0,10)(7)(+.,C,1,T1)(8)(=,T1,,C)(9)CondStElse→(j,0,0,0)(10)(j,A,D,12)(11)Statement.CH→(j,0,0,0)(12)(+,A,2,T2)(13)(=,T2,,A)(14)(j,0,0,10)16.当前句型为WEDCondStElseStatement,用产生式Statement→CondStElseStatement归约，得(1)WED.loop→(j,B.0,5)(4)WED.CH→(j,0,0,2);(5)(j=,A,1,7)(6)(j,0,0,10) 课后答案网www.khdaw.com(7)(+.,C,1,T1)(8)(=,T1,,C)(9)(j,0,0,0)(10)(j,A,D,12)(11)Statement.CH→(j,0,0,9)(12)(+,A,2,T2)(13)(=,T2,,A)(14)(j,0,0,10)17.当前句型为WEDStatement,用产生式Statement→WEDStatement归约，得(1)(j,B.0,5)(4)Statement.CH→(j,0,0,2);(5)(j=,A,1,7)(6)(j,0,0,10)(7)(+.,C,1,T1)(8)(=,T1,,C)(9)(j,0,0,1)(10)(j,A,D,12)(11).(j,0,0,1)(12)(+,A,2,T2)(13)(=,T2,,A)(14)(j,0,0,10) 课后答案网www.khdaw.com(15)(j,0,0,1)(16)5.9解：1）First→foriden":="Expr{intT=NewTemp);GEN(=,$4.PLACE,0,ENTRY($2));$$.VAR=ENTRY($2);GEN(=,0,,T);$$.temp=ENTRY(T);$$.loop=NXQ;}Second→FirststepExpr{intU=NewTemp();$$.loop=$1.loop;GEN(j=,$1.temp,0,NXQ+2);GEN(+,$1.VAR,$3.PLACE,$1.VAR);GEN(=,1,,$1.temp);$$.VAR=$1.VAR;$$.DELTA=$3.PLACE;}Third→SeconduntilExpr{intT,T1,q=NXQ;$$.loop=$1.loop;T=NewTemp();GEN(J<,$1.DELTA,0,q+4);GEN(J>,$1.DELTA,0,q+6);GEN(=,0,,T); 课后答案网www.khdaw.comGEN(J,,,q+7);GEN(=,-1,,T);GEN(J,,,q+7);GEN(=,1,,T);T1=NewTemp();GEN(-,$1.DELTA,$3.PLACE,T1);GEN(*,T,T1,T1);GEN(J<,T1,0,q+11);$$.CH=NXQ;GEN(J,,,0);S→ThirddoS{BackPatch($3.CH,$1.loop);GEN(J,,,$3.loop);$$.CH=$3.CH;}2）•R→repeat{$$.loop=NXQ;}•Rs→RS{$$.loop=$1.loop;BackPath($2.chain,NXQ);}•S→RsuntilExpr{$$.chain=$3.TC;BackPatch($3.FC,$1.loop);}5.10解：1)(*,I,20,T1)•(+,J,T1,T1)•(-,a,Ca,T2)•(=,J,0,T)•(+,T,1,T)•(=,I,0,P1)•(=,J,0,P2)•(-,P1,P2,P1’)•(=,I,0,T1) 课后答案网www.khdaw.com•(=,J,0,T2)•(+,T1,T2,T1’)•(*,P1’,20,T3’)•(+,T1’,T3’,T3’)•(-,a,Ca,T’)•(=[],T’[T3’],T3)•(*,T,20,T)•(+,T3,T,T)•(=,I,0,T4)•(+,T4,1,T4)•(*,T,10,T5)•(+,T4,T5,T5)•(-,b,Cb,T6)•(=[],T6[T5],0,T7)•([]=,T7,0,T2[T1])5.11解：•采用值调用:N=2•采用引用调用:N=95.12解：•采用值调用:b[]={1,2,3,4}•采用引用调用:b[]={20,5,3,4}•采用结果调用:error•采用值结果调用:b[]={3,5,3,4}5.13解：1)DPart→varD2)D→VarList":"Type{BackChain($1.CH,$2.type);}3)Type→integer{$$.type="i";}4)Type→real{$$.type="r";}5)Type→boolean{$$.type="b";}6)Type→char{$$.type="c";}7)VarList→iden{$$.CH=NewChain();AddToChain($$.CH,ENTRY($1));}8)VarList→VarList","iden 课后答案网www.khdaw.com{AddToChain($1.CH,ENTRY($1));$$.CH=$1,CH;}5.14解：源程序PROGRAMProcAsPara;USESwincrt;VARputin,result:integer;PROCEDUREchild(VARa:INTEGER,FUNCTIONf,i:INTEGER);BEGINa:=f(i)END;FUNCTIONfunc(x:INTEGER):INTEGER;BEGINfunc=x*x;RETURNEND;BEGINputin:=8;child(result,func,putin);writeln(result);END.执行结果：645.15解：•由于C语言数值的下界为0，所以内情向量中只需放各维的上界，即放ui,n,c,a，共n+3个单元；••Varable→ArrayVar{$$=$1}•ArrayMSG→iden[number{$$=Entry($1);VarList[$$].CAT=Array;/*种属为数组*/ 课后答案网www.khdaw.comVarLIst[$$].IsPointer=0;VarList[$$].ADDR->DIM=1;/*记录维数*//*下面为内情向量申请空间，并填入第一维下标信息，其中，前两个单元（下标为[0]和[1]）用来存放a、C之值（此时暂不填写），n值可由DIM保存，因此不必另存。*/VarList[$$].ADDR->Vector=malloc(3*sizeof(int));VarList[$$].ADDR->Vector[2]=$3;/*第一维上界*/}|ArrayMSG,number{intdim=VarList[$$].ADDR->DIM+1;$$=$1;VarList[$$].ADDR->DIM++;/*维数加1*//*下面增加向量空间，记录新一维的信息*/VarList[$$].ADDR->Vector=realloc(VarList[$$].ADDR->Vector,(dim+2)*sizeof(int));/*下面记录当前维的上界*/VarList[$$].ADDR->Vector[3*dim-1]=$3;}ArrayVar→ArrayMSG]{$$=$1;/*传递数组名在表中序号*/FillArrMSG_C($$);/*计算并填写数组内情向量的C值*/ 课后答案网www.khdaw.com}5.16解：在此种情况下，可以通过使用堆栈，从左到右依次处理各下标表达式，且每当处理完一个下标表达式Ei时，就将相应的Ei.PLACE推入堆栈，待全部下标表达式处理完毕之后，再产生按从右到左累计VARPART的四元式序列。这需要在有关的语义子程序中用一段循环程序来实现。属性翻译文法略。5.17解：•Condition→if(Expr){BackPatch($2.TC,NXQ);$$.Chain=$2.FC;}•Statement→ConditionStatement{$$.Chain=Merge($1.Chain,$2.Chain);}•CondStElse→ConditionStatement;else{intq=NXQ;GEN(j,0,0,0);BackPatch($1.Chain,NXQ);$$.Chain=Merge($2.Chain,q);}•Statement→CondStElseStatement;{$$.Chain=Merge($1.Chain,$2.Chain);}第六章习题解答1．答：对于有嵌套分程序结构的程序设计语言的编译程序而言，可将sin、cos等标准函数的名字视为最外层分程序定义的全局变量名，这样对其的任何引用均可在最外层符号表中找到其相关信息。另一种解决方案是，在文法定义中就将其定义为一类特殊（类似于关键字）的终结符，并为其定义专门的调用标准函数的文法，这样在词法分析阶段就可区分出它与其它标识符的不同。 课后答案网www.khdaw.com2．解：（1）当扫描到PROCEDUREa时，符号表如图6-1：（2）当扫描到PROCEDUREb所在行时，符号表如图6-2。（3）当扫描到PROCEDUREc所在行时，符号表如图6-3。 课后答案网www.khdaw.com（4）当扫描到PROCEDUREc的begin语句时，符号表如图6-4。（5）当扫描到PROCEDUREb的begin语句时，符号表如图6-5。 课后答案网www.khdaw.com（6）当扫描到PROCEDUREA的begin语句时，符号表如图6-6。（7）当扫描到PROGRAMex62的begin语句时，符号表如图6-7。（8）因主程序外层再无其它程序，所以，主程序的变量在符号表中的位置不必再挪动。也就是说，图`6-7即为最终符号表的状态。 课后答案网www.khdaw.com3．略7．1设有由五个程序段组成的FORTRAN程序，各程序段间的的相互调用关系如下图所示。试为此程序的各程序段合理地分配局部数据区。解：假定数据区从1号单元开始分配，则名程序段所占单元情况为：5：1~84：1~122：9~233：13~221：24~44整个程序占用单元数为447．2解：（提示）一般来说，FORTRAN语言不允许递归调用，但嵌套调用是允许的。其产生中间代码的方式与其它语言别无二致。7．3解：设每个变量均占用一个单元，临时变量的个数≤m。定义一个数组a[m]记录每个临时变量（按出现顺序编号命名）分配单元的地址（≤n≤m，按1、2、3…编号），初值均为0。用另一数组T[n]标记每个单元被使用的最后期限，初值为0。引入全局变量LAST记录当前被使用的最后一个单元的地址，初值为1。•令i=1；•取出有序对（Fi，Li）； 课后答案网www.khdaw.com•令j=1;•若(T[j]TmpVarNum)TmpVarNum=CurTmpVarNum;②若两个运算对象均为临时变量，则只需用其中之一存放运算结果，另一临时变量可释放之：CurTmpVarNum--;③若运算对象之一为临时变量，则只需用该临时变量存放运算结果即可，使用临时变量的个数不变。5．解：为便于描述，我们用过程名代表其相应的活动记录，并视主程序ex75亦为一过程（0层）。则程序运行至各标号处的运行栈情况如下：1）运行至L6处：ex752)运行至L4处：ex75p2•运行至L5处与至L4处相同；•运行至L1处： 课后答案网www.khdaw.comex75P2P1•运行至L3处与至L5处相同；•运行至L2处：ex75P2P1F•从函数F返回时：ex75P2P18）从P1返回时：ex75P29）从P2返回时直至L7处时：ex756．解：与上题描述方法相同：•调用f(10)后，栈内容为：ex76f(10)2)在函数f()内，又一次调用了函数f自身（即第二次进入f）：ex76f(10)f(9)7.略第八章习题解答8.1解：划分情况及控制流程如下图： 课后答案网www.khdaw.com8.2解：四元式序列如下（省略临时变量使用及形实结合代码）：gotoproglowterm:numcopy:=numdencopy:=denloop:ifdencopt<>0gotoL1gotoL2L1:remainder:=numcopymoddencopynumcopy:=dencopydencopy:=remaindergotoloopL2:ifnumcopy>1gotoL3gotoL4L3:num:=numdivnumcopyden:=dendivnumcopy 课后答案网www.khdaw.comL4:returnprog:inputnumeratorinputdenominatorparnumeratorpardenominatorcalllowtermoutputnmeratoroutputdenominator 课后答案网www.khdaw.com8.3解：四元式序列为：i:=1gotoCHECKiLOOPi:i:=i+1CHECKi:ifi<=ngotoL1gotoOUTiL1:j:=1 课后答案网www.khdaw.comgotoCHECKjLOOPj:j:=j+1CHECKj:ifj<=ngotoL2gotoOUTjL2:T1:=i-1t1:=T1*nT1:=T1+jT2:=addr(C)T1[T2]:=0gotoLOOPjOUTj:gotoLOOPiOUTi:i:=1gotoCHKiLPi:i:=i+1CHKi:ifi<=ngotoL3gotoOTiL3:j:=1gotoCHKjLPj:j:=j+1CHKj:ifj<=ngotoL4gotoOTjL4:k:=1gotoCHKkLPk:k:=k+1 课后答案网www.khdaw.comLLk:ifk<=ngotoL5gotoOTkL5:T1:=i-1T1:=T1*nT1:=T1+jT2:=addr(C)T3:=i-1T3:=T3*nT3:=T3+jT4:=addr(C)TT1:=T3[T4]T5:=i-1T5:=T5*nT5:=T5+kT6:=addr(A)TT2:=T5[T6]T7:=k-1T7:=T7*nT7:=T7+jT8:=addr(B)TT3:=T7[T8]T9:=TT2*TT3T10:=TT1+TT2T1[T2]:=T10 课后答案网www.khdaw.comgotoLPkOTk:gotoLPjOTj:gotoLPiOTi:halt基本块划分与流程图略8.4解：DAG图见右，优化后的代码为D:=B*CE:=A+BB:=DA:=E+D8.5解：（1）DAG图见下图。若只有G、L、M在出口之后活跃，则优化后的代码为： 课后答案网www.khdaw.comG:=B*CH:=G*GL:=H*GM:=L若只有L在出口之后活跃，则代码为G:=B*CH:=G*GL:=H*G（2）DAG见右图。若只有G、L、M活跃，则代码为D:=A+CE:=A*CF:=D+EG:=3+FL:=F+15M:=L若只有L活跃，则代码为D:=A+C 课后答案网www.khdaw.comE:=A*CF:=D+EL:=F+158．6解：(a)必经结点集：D2={2}D3={2,3}，D4={2,4}D5={2,4,5}D6={2,4,6}D7={2,4,7}D8={2,4,7,8}回边及相应循环：7→4：{4,5,6,7}8→2：{2,3,4,5,6,7,8}(b)必经结点集：D1={1}D2={1,2}D3={1,2,3}D4={1,2,3,4}D5={1,2,3,5}D6={1,2,3,6}D7={1,2,7}D8={1,2,7,8}回边及相应循环：7→2：{2,3,4,5,6,7}(c)必经结点集：D1={1},D2={1,2},D3={1,2,3},D4={1,2,4},D5=1,2,5},D6={1,2,3,6},D7={1,2,7}回边及相应循环：5→2：{2，3，4，5}6→6：{6}注意：5→4不是回边。因为4不是5的控制结点。8.7略8.8解（1）四元式序列：I:=1gotoCHECKLOOP:I:=I+1CHECK:ifI<=ngotoLgotoOUTL:T1:=I-1T1:=T1*n 课后答案网www.khdaw.comT1:=T1+JT2:=addr(A)T3:=I-1T3:=T3*nT3:=T3+JT4:=addr(A)T5:=T3[T4]T6:=J-1T6:=T6*nT6:=T6+IT7:=addr(A)T8:=T6[T7]T9:=T7+T8T1[T2]:=T9gotoLOOPOUT:halt（2）无循环不变量；（3）优化后代码：I:=1gotoCHECKLOOP:I:=I+1CHECK:ifI<=ngotoLgotoOUTL:T1:=I-1 课后答案网www.khdaw.comT1:=T1*nT1:=T1+JT2:=addr(A)T3:=T1[T2]T6:=J-1T6:=T6*nT6:=T6+IT6:=T6[T2]T3:=T3+T8T1[T2]:=T3gotoLOOPOUT:halt8.9优化后的代码为readJ,KA:=0B:=0I:=100*KL:A:=A+KB:=B+JC:=A*BwriteCifA