《编译原理》西北工业大学第三版课后答案.doc 97页

'第一章习题解答1.解：源程序是指以某种程序设计语言所编写的程序。目标程序是指编译程序（或解释程序）将源程序处理加工而得的另一种语言（目标语言）的程序。翻译程序是将某种语言翻译成另一种语言的程序的统称。编译程序与解释程序均为翻译程序，但二者工作方法不同。解释程序的特点是并不先将高级语言程序全部翻译成机器代码，而是每读入一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读入下一条语句继续进行解释、执行，如此反复。即边解释边执行，翻译所得的指令序列并不保存。编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的空间中，在用户需要时再执行之。即先翻译、后执行。2.解：一般说来，编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。3.解：C语言的关键字有：auto break casecharconst  continuedefaultdodoubleelseenumexternfloatforgotoifintlongregisterreturnshortsignedsizeofstaticstructswitchtypedefunionunsignedvoidvolatilewhile。上述关键字在C语言中均为保留字。4.解：C语言中括号有三种：{}，[]，（）。其中，{}用于语句括号；[]用于数组；（）用于函数（定义与调用）及表达式运算（改变运算顺序）。C语言中无END关键字。逗号在C语言中被视为分隔符和运算符，作为优先级最低的运算符，运算结果为逗号表达式最右侧子表达式的值（如：(a,b,c,d)的值为d）。5.略第二章习题解答 1.（1）答：26*26=676 （2）答：26*10=260 （3）答：{a,b,c,...,z,a0,a1,...,a9,aa,...,az,...,zz,a00,a01,...,zzz},共26+26*36+26*36*36=34658个2.构造产生下列语言的文法 （1）{anbn|n≥0}  解：对应文法为G(S)=({S},{a,b},{S→ε|aSb},S) （2）{anbmcp|n,m,p≥0}   解：对应文法为G(S)=({S,X,Y},{a,b,c},{S→aS|X,X→bX|Y,Y→cY|ε},S) （3）{an#bn|n≥0}∪{cn#dn|n≥0}  解：对应文法为G(S)=({S,X,Y},{a,b,c,d,#},{S→X,S→Y,X→aXb|#,Y→cYd|#},S) （4）{w#wr#|w?{0,1}*,wr是w的逆序排列}  解：G(S)=({S,W,R},{0,1,#},{S→W#,W→0W0|1W1|#},S) （5）任何不是以0打头的所有奇整数所组成的集合  解：G(S)=({S,A,B,I,J},{-,0,1,2,3,4,5,6,7,8,9},{S→J|IBJ,B→0B|IB|e,I→J|2|4|6|8,Jà1|3|5|7|9},S) （6）所有偶数个0和偶数个1所组成的符号串集合  解：对应文法为S→0A|1B|e，A→0S|1CB→0C|1SC→1A|0B3.描述语言特点 （1）S→10S0S→aAA→bAA→a  解：本文法构成的语言集为：L(G)={(10)nabma0n|n,m≥0}。 （2）S→SSS→1A0A→1A0A→ε  解：L(G)={1n10n11n20n2…1nm0nm|n1,n2,…,nm≥0；且n1,n2,…nm不全为零}该语言特点是：产生的句子中，0、1个数相同，并且若干相接的1后必然紧接数量相同连续的0。 （3）S→1AS→B0A→1AA→CB→B0B→CC→1C0C→ε  解：本文法构成的语言集为：L(G)={1p1n0n|p≥1,n≥0}∪{1n0n0q|q≥1,n≥0}，特点是具有1p1n0n或1n0n0q形式，进一步，可知其具有形式1n0mn,m≥0,且n+m>0。 （4）S→bAdcA→AGSG→εA→a  解：可知，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最右推导：<程序>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的相应语法树是：7.解： aacb是文法G[S]中的句子，相应语法树是：最右推导：S=>aAcB=>aAcb=>aacb最左推导：S=>aAcB=>aacB=>aacb（2）aabacbadcd不是文法G[S]中的句子因为文法中的句子不可能以非终结符d结尾（3）aacbccb不是文法G[S]中的句子可知，aacbccb仅是文法G[S]的一个句型的一部分，而不是一个句子。（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.解：(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））相应的语法树是：（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）消除后的产生式如下：S→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|i T→T*F|(E)|P↑F|iF→P↑F|(E)|iP→(E)|i 第三章习题解答 1．从略2．3假设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根据文法知其产生的语言是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打头的串.8从略。 9 （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的状态转换图：(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)状态矩阵是：记[S]=q0[B]=q1[AB]=q2[SA]=q3,最小化和确定化后如图 （2）记[S]=q0,[A]=q1,[BS]=q2最小化和确定化后的状态转换图如下13（1）将具有ε动作的NFA确定化后，其状态转换图如图：记{S0,S1,S3}=q0{S1}=q1{S2S3}=q2{S3}=q3(2)记{S}=q0{Z}=q1{UR}=q2{SX}=q3{YUR}=q4{XSU}=q5{YURZ}=q6{ZS}=q7 14（1）从略(2)化简后S0和S1作为一个状态，S5和S6作为一个状态。状态转换图如图15从略。16从略。·(1)r*表示的正规式集是{ε,r,rr,rrr,…}(ε|r)*表示的正规式集是{ε,εε,…}∪{r,rr,rrr,…}={ε,r,rr,rrr,…}ε|rr*表示的正规式集是{ε,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(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))G2: 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#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];if(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;break; 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参考程序如下：%{#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){if(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(){return;}30从略。 第四章习题解答 第四章习题参考答案·1.解：(1)S→(S)Z21|()Z21|[S]Z31|[]Z31A→(S)Z22|()Z22|[S]Z32|[]Z32B→(S)Z23|()Z23|[S]Z33|[]Z33 Z11→ε|AZ11|BZ21Z12→AZ12|BZ22Z13→AZ13|BZ23Z21→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.2 eddfbbd6,3.2·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’thenIfYthenreturn;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;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;FunctionC:boolean; BeginSave;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=’+’then IfVthenIfE’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此文法已满足LL(1)文法的三个条件，所以　G’[S]:S→bZ11|aZ21Z11→bZ11|εZ21→bZ11|aZ21(2)G’文法的各非终结符的FIRST集和FOLLOW集：产生式FIRST集FOLLOW集S→bZ11→aZ21{b}{a}{#}Z11→bZ11→ε{b}{ε}{#}Z21→bZ11→aZ21{b}{a}{#}LL(1)分析表为：ab#SaZ21bZ11Z11bZ11εZ21aZ21bZ11·9.解：(1)产生式first集follow集S→SaB→bB{b}{b}{#,a,c}A→S→a{b}{a}{c}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, 显然，文法含有左递归，消去后等价LL(1)文法为：A→BA’A’→∨BA’|ωB→CB’,B’→∧CB’|ωC→┐D|DD→(A)|true|false(2)略·证：若LL（1）文法G有形如B→aAAb的产生式，且AT+ε及AT*ag,根据FIRST集FOLLOW集的构造算法可知，FIRST(A)中一切非ε加到FOLLOW(A)中，则a∈FOLLOW(A)；又因为a∈FIRST(ag),所以两集合相交非空，因此，G不是LL(1)文法；与前提矛盾，假设不成立，得证。·解：(1)SA(a)bS==A=<=<(==<<=<><>>)>>>>>b>>不是简单优先文法。(2)SRT()∧a,S>=R=T>(<=<<<<)>>∧>>a>>,<=<<<是简单优先文法。(3)SR(a,) S=<>(=<>,=<<)>>是简单优先文法。o首先消去无用产生式Z→E,Z→E+TSZT#i()SZ==T>>#=<<>(=<<<)>>化简后的文法是简单优先文法；·解：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#-><><<><>*><><><(<<<=< )>>>>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#+><<<><>*>><<><>↑>><<><>(<<<<=< )>>>>>I>>>>>#<<<<<（2）用Floyd方法将优先矩阵线性化得到得的优先函数为：+*↑()i#F3551771G2466161·解：用Floyd方法对已知的优先矩阵构造的优先函数为：zbMLa()f1567747g1654667·解：（1）优先矩阵如下：[]a#[>=]>>a<><><#<<<（2）用Bell方法求优先函数的过程如下：[]a#f5751g5561 （3）显然，文法不是算符优先文法,所以不能线性化。·略。·解：（1）识别全部活前缀的DFA如下：（以表格的形式来表示，很容易可以转化为图的形式，本章中其余的题目也是采用这种形式表示。）状态项目集经过的符号到达的状态I0S’→·SS→·aSbS→·aScS→·abSaI1I2I1S’→S·I2S→a·SbS→a·ScS→a·bS→·aSbS→·aScS→·abSabI3I2I4I3S→aS·bS→aS·cbcI5I6I4S→ab·I5S→aSb·I6S→aSc·（2）识别全部活前缀的DFA如下：状态项目集经过的符号到达的状态I0S’→·SS→·cAS→·ccBSc·I1II1S’→S·I2S→c·AAI3 S→c·cBA→·cAA→·acaI4I5I3S→cA·I4S→cc·BA→c·AB→·ccBB→·bA→·cAA→·aBAcbaI6I5I7I8I5I5A→a·I6S→ccB·I7B→c·cBA→c·AA→·cAA→·aCAaI9I10I5I8B→b·I9B→cc·BA→c·AB→·ccBB→·bA→·cAA→·aBAcbaI11I10I7I8I5I10A→cA·I11B→ccB·所求的LR(0)项目规范族C={I0,I1,…,I11}（3）状态项目集经过的符号到达的状态 I0S’→·SS→·aSSbS→·aSSSS→·cScaI1I2I3I1S’→S·I2S→c·I3S→a·SSbS→a·SSSS→·aSSbS→·aSSSS→·cScaI4I2I3I4S→aS·SbS→aS·SSS→·aSSbS→·aSSSS→·cScaI5I2I3I5S→aSS·bS→aSS·SS→·aSSbS→·aSSSS→·cSabcI7I3I6I2I6S→aSSb·I7S→aSSS·（4）状态项目集经过的符号到达的状态I0S’→·SS→·ASAI1I2 A→·AbA→·aaI3I1S’→S·I2S→A·S→A·bbI4I3A→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)={#}ACTIONGOTOabc#SAB0S211ACC2S5S433R14S5S8S7365R46R27S5S9108R69S5S8S7101110R311R5（3）是LR(0)文法，其SLR(1)分析表如下：FOLLOW(S)={#,a,b,c} ACTIONGOTOabc#S0S3S211ACC2R3R3R3R33S3S244S3S255S3S6S276R1R1R1R17R2R2R2R2（4）因为I2中含有冲突项目，所以不是LR(0)文法，其SLR(1)分析表如下：FOLLOW(S)={#}∩{b}=φ(所以可以用SLR(1)规则解决冲突),FOLLOW(A)={b,#}ACTIONGOTOab#SA0S3121ACC2S4R13R3R34R2R2·解：状态项目集经过的符号到达的状态I0S’→·SS→·(SRS→·aS(aI1I2I3I1S’→S·I2S→(·SRS→·(SRS→·aS(aI4I2I3I3S→a·I4S→(S·RS→·(SRS→·aR→·,SRa(R,I3I2I5I6 R→·))I7I5S→(SR·I6R→,·SRS→·(SRS→·aS(aI8I2I3I7R→)·I8R→,S·RR→·,SRR→·)),RI7I6I9I9R→,SR·LR(0)分析表如下：ACTIONGOTOa(),#SR0S3S211ACC2S3S243R2R2R2R2R24S3S2S7S655R1R1R1R1R16S3S287R4R4R4R4R48S7S699R3R3R3R3R3可见是LR(0)文法。·解：（1）状态项目集经过的符号到达的状态I0S’→·SS→·SabS→·bRSbI1I2I1(冲突项目)S’→S·S→S·abaaccI3 I2S→b·RR→·SR→·aS→·SabS→·bRRSabI4I5I6I2I3S→Sa·bbI7I4S→bR·r2I5R→S·S→S·abaI3I6R→a·I7S→Sab·项目I1,I5同时具有移进和归约项目，对于I5={R→S·,S→S·ab},follow(R)={a},follow(R)∩{a}={a},所以SLR(1)规则不能解决冲突，从而该文法不是SLR(1)文法。（2）状态项目集经过的符号到达的状态I0S’→·SS→·aSABS→·BAB→·bSaBbI1I2I3I4I1S’→S·I2S→a·SABS→·aSABS→·BAB→·bSaBbI5I2I3I4I3S→B·AA→·aAA→·BB→·bAaBbI6I7I8I4 I4B→b·r5I5S→aS·ABA→·aAA→·BB→·bAaBbI9I7I8I4I6S→BA·r2I7A→a·AA→·BA→·aAB→·bABabI10I8I7I4I8A→B·r4I9S→aSA·BB→·bBbI11I4I10A→aA·r3I11S→aSAB·r1不存在冲突项目，故该文法是LR(0)文法，也是SLR(1)文法。SLR(1)分析表如下：ACTIONGOTOab#SAB0S2S4131ACC2S2S4533S7S4684R5R5R55S7S4986R2R2R27S7S41088R4R4R49S41110R3R3R311R1R1R1（3）先求识别全部活前缀的DFA：状态项目集经过的符号到达的状态 I0S’→·SS→·aSbS→·bSaS→·abSabI1I2I3I1S’→S·accI2S→a·SBS→a·bS→·aSbS→·bSaS→·abSbaI4I5I2I3S→b·SaS→·aSbS→·bSaS→·abSabI6I2I3I4S→aS·bbI7I5S→ab·r3I6S→bS·aaI8I7S→aSb·r1I8S→bSa·r2不存在冲突项目，故该文法是LR(0)文法，也是SLR(1)文法。SLR(1)分析表如下：ACTIONGOTOab#S0S2S311ACC2S2S543S2S364S75R3R3R36S87R1R1R18R2R2R2 （4）先求识别全部活前缀的DFA：状态项目集经过的符号到达的状态I0S’→·SS→·aAS→·bBSabI1I2I3I1S’→S·accI2(冲突)S→a·AA→·cAdA→·AcI4I5r4I3(冲突)S→b·BB→·cBddB→·BcI6I7r6I4S→aA·r1I5(冲突)A→c·AdA→·cAdA→·AcI8I5r4I6S→bB·r2I7(冲突)B→c·BddB→c·BddB→·BcI9I7r6I8A→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 4R15S5R4R486R27S7R6R698S109S1110R3R311S1212R5R5（5）解：原文法等价化为q1→q2,q1→q3,q2→q4;q5,q4→beginD,q4→q4;D,q5→Send,q5→S;q5,q3→beginq5,先求识别全部活前缀的DFA：状态项目集经过的符号到达的状态I0q1’→·q1q1→·q2q1→·q3q2→·q4;q5q3→·beginq5q4→·beginDq4→·q4;Dq1q2q3q4beginI1I2I3I4I5I1q1’→q1·ACCI2q1→q2·R1I3q1→q3·R2I4q2→q4·;q5q4→q4·;D;DI6I5q3→begin·q5q3→begin·Dq5→·Sendq5→·S;q5q5DSI7I8I9I6q2→q4;·q5q4→q4;·Dq5DI10I11 q5→·Sendq5→·S;q5SI9I7q3→beginq5·R8I8q3→beginD·R4I9q5→S·endq5→S·;q5end;I12I13I10q2→q4;q5·R3I11q4→q4;D·R5I12q5→Send·R6I13q5→s;·q5q5→·Sendq5→·S;q5q5SI14I9I14q5→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： 状态项目集经过的符号到达的状态I0q1’→·q1q1→·beginq2q3endq1beginI1I2I1q1’→q1·ACCI2q1→begin·q2q3endq2→·q2d;q2→·q2q2I3R3I3(冲突项目)Q1→beginq2·q3endq2→q2·d;q3→·q3;q4q3→·q4q4→·Sq4→·q3Ddq4SI4I10I5I6R7I4q1→beginq2q3·endq3→q3·;q4end;I7I8I5q3→q4·R5I6q4→S·R6I7q1→beginq2q3end·R1I8(冲突项目)q3→q3;·q4q4→·Sq4→·q4SI9I6R7I9q3→q3;q4·R4I10q2→q2d·;;I11I11q2→q2d;·R2因为follow(q4)={end,#}，故冲突项目可以通过SLR(1)规则来解决，从而文法为SLR(1)文法。SLR(1)分析表如下：actiongotobeginendd;S#q1q2q3q40S2112R3R3R3R333R7S10R7S6454S7S8 5R5R56R6R67R18R7R7S699R4R41011R2R2R2R2·解：识别活前缀的DFA及LR(0)分析表：状态项目集经过的符号到达的状态I0S’→·SS→·AAdS→·cAdS→·bA→·AScA→·SbA→·cdA→·aSAabcI0I6I5I4I3I1S’→S·A→S·bbI2I2A→Sb·I3S→c·AdA→c·dA→·AScA→·SbA→·cdA→·aS→·AAdS→·cAdSAabcdI8I9I5I4I3I7 S→·bI4S→b·I5A→a·I6S→A·AdA→A·ScA→·AScA→·SbA→·cdA→·aS→·AAdS→·cAdS→·bSAabcI11I10I5I4I3I7A→cd·I8A→S·bbI2I9S→cA·dA→A·ScS→A·AdS→·AAdS→·cAdS→·bA→·AScA→·SbA→·cdA→·aSAabcdI11I10I5I4I3I14I10S→AA·dA→A·ScSAI11I10 S→A·AdS→·AAdS→·cAdS→·bA→·AScA→·SbA→·cdA→·aabcdI5I4I3I13I11A→AS·cA→S·bbcI2I12I12A→ASc·I13S→AAd·I14S→cAd·ACTIONGOTOabcd#SA0s5s4s3161s2acc2r5r5r5r5r53s5s4s3s7894r3r3r3r3r35r7r7r7r7r76s5s4s37r6r6r6r6r611108s29s5s4s3s14111010s5s4s3s13111011s2s1212r4r4r4r4r413r1r1r1r1r114r2r2r2r2r2SLR(1)分析法：FOLLOW(S)={c,b}FOLLOW(A)={a,b,c,d}ACTIONGOTOabcd#SA0s5s4s3161s2acc 2r5r5r5r53s5s4s3s7894r3r35r7r7r7r76s5s4s37r6r6r6r611108s29s5s4s3s14111010s5s4s3s13111011s2s1212R4r4r4r413r1r114r2r2两表的异同：两表都用ACTION表和GOTO表反映了移进、归约（包括接受）的状态和动作。不同之处在于SLR(1)增加了在归约的时候考虑向前符号a以解释可能出现的“移进——归约”冲突；SLR（1）的分析较稀疏些，原因是填写归约项时，并不是在一状态对应行上全部填写归约动作，而是考虑了相应非终结符的FOLLOW集因素。另外，在分析效率上SLR（1）分析的效率更高一些，因为在发现错误方面，SLR（1）比LR（0）分析发现的更早些。·解：求LR(1)项目集和状态转换表：状态项目集经过的符号到达的状态I0S’→·S#S→·A#A→·BA#A→·#B→·aB#,a,bB→·b#,a,bSABabI1I2I3I4I5I1S’→S·#I2S→A·#I3A→B·A#A→·#A→·BA#B→·aB#,a,bABabI6I3I4I5 B→·b#,a,bI4B→a·B#,a,bB→·aB#,a,bB→·b#,a,bBabI7I4I5I5B→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)项目集和状态转换图：状态项目集经过的符号到达的状态 I0S’→·S#S→·A#A→·AB#,a,bA→·SAI1I2I1S’→S·#I2S→A·#A→A·B#,a,bB→·aB#,a,bB→·b#,a,bBabI3I5I4I3A→AB·#,a,bI4B→b·#,a,bI5B→a·B#,a,bB→·aB#,a,bB→·b#,a,bBabI6I5I4I6B→aB·#,a,b相应的LR(1)分析表为：STATEACTIONGOTOab#SAB0R3R3R3121Acc2S5S4R13R2R2R24R5R5R55S5S466R4R4R4表中没有多从定义的元素，所以文法是LR(1)文法。（2）LR(1)分析法：状态项目集经过的符号到达的状态I0E’→·E#E→·E+T#/+ETI1I1 E→·T#/+T→·(E)#/+T→·a#/+(aI5I4I1E’→E·#E→E·+T#/++I2I2E→E+·T#/+T→·(E)#/+T→·a#/+T(aI3I5I4I3E→E+T·#/TI4T→a·#/+I5T→(·E)#/+E→·E+T+/)E→·T)/+T→·(E)+/)T→·a+/)ECTaI7I8I9I12I6E→T·#/+I7T→(E·)#/+E→E·+T+/))+I10I11I8T→(·E))/+E→·E+T+/)E→·T)/+T→·(E)+/)T→·a+/)(aETI8I12I14I9I9E→T·+/)I10T→(E)·#/+I11E→E+·T+/)T→·(E)+/)T→·a+/)(TaI8I13I12I12T→a·+/)I13E→E+T·)/+ I14T→(E·)+/)E→E·+T+/)+)I11I15I15T→(E)·+/)LALR(1)分析：（合并同心集）状态项目集经过的符号到达的状态I0E’→·E#E→·E+T#/+E→·T#/+T→·(E)#/+T→·a#/+ETaI1I6/I9I4/I12I1E’→E·#E→E·+T#/++I2/I11I2/I11E→E+·T#/+/）T→·(E)#/+/）T→·a#/+/）T(aI3/I13I5/I8I4/I12I3/I13E→E+T·)/+/#I4/I12T→a·+/)/#I5/I8T→(·E)#/+/）E→·E+T+/)E→·T)/+T→·(E)+/)T→·a+/)T(EaI6/I9I5/I8I7/I14I4/I12I6/I9E→T·+/)/#I7/I14T→(E·)+/)/#E→E·+T+/)+)I2/I11I10/I15I10/I15T→(E)·+/)/#LR(1)ACTIONGOTO+()a#ET0S5S4161S2ACC2S5S43 3R1R14R4R45S8S12796R2R27S11S108S8S121499R2R210R3R311S8S121312R4R413R1R114S11S1515R3R3可以看出，表中无冲突项，所以是LR(1)文法；LALR（1）分析表：LR(1)ACTIONGOTO+()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)项目集和状态转换图：状态项目集经过的符号到达的状态I0E’→·E#E→·E+E#,+,*E→·E*E#,+,*E→·i#,+,*EiI1I2I1E’→E·#E→E·+E#,+,*E→E·*E#,+,*+*I3I4 I2E→i·#,+,*I3E→E+·E#,+,*E→·E+E#,+,*E→·E*E#,+,*E→·i#,+,*EiI5I2I4E→E*·E#,+,*E→·E+E#,+,*E→·E*E#,+,*E→·i#,+,*EiI6I2I5E→E+E·#,+,*E→E·+E#,+,*E→E·*E#,+,*+*I3I4I6E→E*E·#,+,*E→E·+E#,+,*E→E·*E#,+,*+*I3I4依据以上图求出该文法的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）分析表为状态ACTIONGOTOi+*#E0s211s3s4acc2r3r3r33s254s265r1s4r16r2r2r2（2）解：LR(1)： 状态项目集经过的符号到达的状态I0S’→·S#S→·aSa#S→·bSb#S→·a#S→·b#SabI1I2I3I1S’→S·#I2S→a·Sa#S→a·#S→·aSaaS→·bSbaS→·aaS→·baSabI4I7I6I3S→b·Sb#S→b·#S→·aSabS→·abS→·bSbbS→·bbSabI11I14I13I4S→aS·a#aI5I5S→aSa·#I6S→b·SbaS→b·aS→·aSabS→·bSbbS→·abS→·bbSabI10I14I13 I7S→a·SaaS→a·aS→·aSaaS→·bSbaS→·aaS→·baSabI8I7I6I8S→aS·aaaI9I9S→aSa·aI10S→bS·babI15I11S→bS·b#bI12I12S→bSb·#I13S→b·SbbS→b·bS→·aSabS→·bSbbS→·abS→·bbSabI16I14I13I14S→a·SabS→a·bS→·aSaaS→·bSbaS→·aaS→·baSabI18I7I6I15S→bSb·aI16S→bS·bbbI17I17S→bSb·bI18S→aS·abaI19I19S→aSa·b有移进——归约冲突，不是LR(1)文法。 （3）求LR(1)项目集和状态转换图：状态项目集经过的符号到达的状态I0S’→·S#S→·V:=E#S→·LS#L→·I:IV→·I:SVLII1I2I3I4I1S’→S·#I2S→V·:=E#:I5I3S→L·S#S→·V:=E#S→·LS#V→·I:L→·I:ISLII6I3I4I4L→I·:IV→I·::I7I5S→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。·解：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解：·属性文法是文法符号带有语义属性的前后文无关文法；·属性翻译文法首先是对文法的属性依赖关系作出限制，不允许出现属性的直接或间接的循环定义，即要求属性文法是良定义的；其次还应将属性定义规则改造为计算属性值的语义程序，即将静态的定义规则改写为可动态执行的语义动作；·属性文法是静态描述，而属性翻译文法是动态描述，有语义动作。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)(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，得(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)(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)15.当前句型为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)(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)(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);GEN(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)·(=,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{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;/*种属为数组*/VarLIst[$$].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值*/}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等标准函数的名字视为最外层分程序定义的全局变量名，这样对其的任何引用均可在最外层符号表中找到其相关信息。另一种解决方案是，在文法定义中就将其定义为一类特殊（类似于关键字）的终结符，并为其定义专门的调用标准函数的文法，这样在词法分析阶段就可区分出它与其它标识符的不同。2．解：（1）当扫描到PROCEDUREa时，符号表如图6-1：         （2）当扫描到PROCEDUREb所在行时，符号表如图6-2。        （3）当扫描到PROCEDUREc所在行时，符号表如图6-3。        （4）当扫描到PROCEDUREc的begin语句时，符号表如图6-4。 （5）当扫描到PROCEDUREb的begin语句时，符号表如图6-5。        （6）当扫描到PROCEDUREA的begin语句时，符号表如图6-6。          （7）当扫描到PROGRAMex62的begin语句时，符号表如图6-7。         （8）因主程序外层再无其它程序，所以，主程序的变量在符号表中的位置不必再挪动。也就是说，图`6-7即为最终符号表的状态。3．略第七章习题解答 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）；·令j=1;·若(T[j]TmpVarNum)TmpVarNum=CurTmpVarNum;②若两个运算对象均为临时变量，则只需用其中之一存放运算结果，另一临时变量可释放之：CurTmpVarNum--;③若运算对象之一为临时变量，则只需用该临时变量存放运算结果即可，使用临时变量的个数不变。5．解：为便于描述，我们用过程名代表其相应的活动记录，并视主程序ex75亦为一过程（0层）。则程序运行至各标号处的运行栈情况如下：1）运行至L6处：ex752)运行至L4处：ex75p2·运行至L5处与至L4处相同；·运行至L1处：ex75P2P1·运行至L3处与至L5处相同；·运行至L2处：ex75P2P1F·从函数F返回时：ex75P2P18）从P1返回时：ex75P29）从P2返回时直至L7处时：ex75 6．解：与上题描述方法相同：·调用f(10)后，栈内容为：ex76f(10)2)在函数f()内，又一次调用了函数f自身（即第二次进入f）：ex76f(10)f(9)7.略第八章习题解答 8.1解：划分情况及控制流程如下图：  8.2解：四元式序列如下（省略临时变量使用及形实结合代码）：          gotoprog lowterm: numcopy:=num          dencopy:=den loop:    ifdencopt<>0gotoL1           gotoL2 L1:      remainder:=numcopymoddencopy          numcopy:=dencopy          dencopy:=remainder          gotoloop L2:      ifnumcopy>1gotoL3          gotoL4 L3:      num:=numdivnumcopy          den:=dendivnumcopy L4:      return prog:    inputnumerator          inputdenominator          parnumerator          pardenominator          calllowterm          outputnmerator          outputdenominator   8.3解：四元式序列为：          i:=1          gotoCHECKi LOOPi:   i:=i+1 CHECKi:  ifi<=ngotoL1          gotoOUTi L1:      j:=1           gotoCHECKj LOOPj:   j:=j+1 CHECKj:  ifj<=ngotoL2          gotoOUTj L2:      T1:=i-1          t1:=T1*n          T1:=T1+j          T2:=addr(C)          T1[T2]:=0          gotoLOOPj OUTj:    gotoLOOPi OUTi:    i:=1          gotoCHKi LPi:     i:=i+1 CHKi:    ifi<=ngotoL3          gotoOTi L3:      j:=1          gotoCHKj LPj:     j:=j+1 CHKj:    ifj<=ngotoL4          gotoOTj L4:      k:=1          gotoCHKk LPk:     k:=k+1  LLk:     ifk<=ngotoL5          gotoOTk L5:      T1:=i-1          T1:=T1*n          T1:=T1+j          T2:=addr(C)          T3:=i-1          T3:=T3*n          T3:=T3+j          T4:=addr(C)          TT1:=T3[T4]          T5:=i-1          T5:=T5*n          T5:=T5+k          T6:=addr(A)          TT2:=T5[T6]          T7:=k-1          T7:=T7*n          T7:=T7+j          T8:=addr(B)          TT3:=T7[T8]          T9:=TT2*TT3          T10:=TT1+TT2          T1[T2]:=T10           gotoLPk OTk:    gotoLPj OTj:    gotoLPi OTi:     halt 基本块划分与流程图略8.4解：DAG图见右，优化后的代码为 D:=B*C E:=A+B B:=D A:=E+D8.5解：（1）DAG图见下图。  若只有G、L、M在出口之后活跃，则优化后的代码为： G:=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 E:=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:=1         gotoCHECK LOOP:   I:=I+1 CHECK:  ifI<=ngotoL         gotoOUT L:      T1:=I-1         T1:=T1*n          T1:=T1+J         T2:=addr(A)         T3:=I-1         T3:=T3*n         T3:=T3+J         T4:=addr(A)         T5:=T3[T4]         T6:=J-1         T6:=T6*n         T6:=T6+I         T7:=addr(A)         T8:=T6[T7]         T9:=T7+T8         T1[T2]:=T9         gotoLOOP  OUT:   halt （2）无循环不变量； （3）优化后代码：         I:=1         gotoCHECK LOOP:   I:=I+1 CHECK:  ifI<=ngotoL         gotoOUT L:      T1:=I-1          T1:=T1*n         T1:=T1+J         T2:=addr(A)         T3:=T1[T2]         T6:=J-1         T6:=T6*n         T6:=T6+I         T6:=T6[T2]         T3:=T3+T8         T1[T2]:=T3         gotoLOOP OUT:    halt8.9优化后的代码为         readJ,K         A:=0         B:=0         I:=100*K L:     A:=A+K         B:=B+J         C:=A*B         writeC         ifA