西北工业大学版(蒋立源第三版)编译原理课后习题答案

第一章习题解答1解：源程序是指以某种程序设计语言所编写的程序。目标程序是指编译程序（或解释程序）将源程序处理加工而得的另一种语言（目标语言）的程序。翻译程序是将某种语言翻译成另一种语言的程序的统称。编译程序与解释程序均为翻译程序，但二者工作方法不同。解释程序的特点是并不先将高级语言程序全部翻译成机器代码，而是每读入一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读入下一条语句继续进行解释、执行，如此反复。即边解释边执行，翻译所得的指令序列并不保存。编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的空间中，在用户需要时再执行之。即先翻译、后执行。2解：一般说来，编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。3解：C语言的关键字有：autobreakcasecharconstcontinuedefaultdodoubleelseenumexternfloatfbrgotoifintlongregisterreturnshortsignedsizeofstaticstructswitchtypedefunionunsignedvoidvolatilewhileo上述关键字在C语言中均为保留字。4解：C语言中括号有三种：｛｝,[],（）«其中，｛｝用于语句括号：口用于数组；（）用于函数（定义与调用）及表达式运算（改变运算顺序）。C语言中无END关键字。逗号在C语言中被视为分隔符和运算符，作为优先级最低的运算符，运算结果为逗号表达式最右侧子表达式的值（如：（a,b,c,d）的值为d）。5略第二章习题解答1.(1)答:26*26=676(2)答：26*10260(3)答：{%1乂,・・・,2^0再1,..・丹9,犯・・・,32,・・・,22再00声01,.・・,222},共26+26*36+26*36*36=34658个.构造产生下列语言的文法{anbn|n^O}解:对应文法为G(S)=({S},{a,b},{S-£|aSb},S){anbmcp|n,m,p0}解：对应文法为G(S)=({S,X,Y},{ahc},{SfaS|X,X~bX|Y,Y-*cY|E},S){an#bn|n20}U{cn#dn|n20}解：对应文法为G(S)=({S,X,Y},{a,b,c,d,#},{SfX,S-Y,X^aXb|#,Y-cYd|#},S){w#wr#|w?{O,l}*,wr是w的逆序排列}解：G(S)=({S,W,R},{O,1,#},{S-W#,W-*OWO|1W1|#},S)(5)任何不是以0打头的所有奇整数所组成的集合解：G(S)=({S,A,B,IJ},{-,0,l,2,3,4,5,6,7,8,9},{S— I—J|2|4|6|8,Ja1|3|5|7|9},S)(6)所有偶数个0和偶数个1所组成的符号串集合解：对应文法为S^OA|lB|e,A^OS|1CB-OC|1SC^1A|OB.描述语言特点SflOSOSfaAAfbAAfa解：本文法构成的语言集为：L(G尸{(10)nabma0n|n,m20}。SfSSSflAOAflAOAf£解：L(G)={1n1On11n20n2…1nmOnm|nl,n2,…,nm》O；且nl,n2,…nm不全为零}该语言特点是：产生的句子中，0、1个数相同，并且若干相接的1后必然紧接数量相同连续的0。S—lASfBOAflAAfCBfBOBYC-*1C0C—e解：本文法构成的语言集为:L(G尸{lplnOn|p》l,n》O}U{lnOnOq|q》l,n》O},特点是具有IplnOn或InOnOq形式，进一步，可知其具有形式ln0mn,m20,且n+m>0。SfbAdcA-AGSGfeA^a解：可知，S=>…=>baSndcn20该语言特点是：产生的句子中，是以ba开头de结尾的串，且ba、de个数相同。SfaSSSfa解：L(G)={a(2n-l)|nNl}可知：奇数个a.解：此文法产生的语言是：以终结符al、a2…an为运算对象，以八、V、〜为运算符,以［、］为分隔符的布尔表达式串. 5」解：由于此文法包含以下规则：AA-e,所以此文法是0型文法。5.2证明：略.解:(1)最左推导：〈程序＞T＜分程序＞T〈标号〉：〈分程序〉TL：〈分程序〉TL：〈标号〉：〈分程序〉TL：L：〈分程序〉TL：L：〈无标号分程序〉TL：L：〈分程序首部〉；〈复合尾部〉TL：L：〈分程序首部〉；〈说明〉；〈复合尾部〉TL：L：begin〈说明〉；〈说明〉;v复合尾部〉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〈标号〉：〈标号〉：〈分程序首部〉：〈复合尾部〉Tv标号〉：〈标号〉：〈分程序首部〉；〈语句〉；〈复合尾部〉Tv标号》:v标号》:〈分程序首部》;vTv标号》:v标号》:〈分程序首部》;v语句〉；〈语句〉；endTv标号》:〈标号〉：v分程序首部〉；v语句〉；s；endT<标号〉：〈标号〉：v分程序首部》；s；s；endTv标号〉：〈标号》：v分程序首部〉；说明；s；s；endTv标号〉：〈标号〉：v分程序首部〉；d：s；s；endTv标号〉：v标号〉：begin说明；d；s；s；endTv标号〉：〈标号〉：begind；d；s；s；endTv标号,：L：begind；d：s；s；endTL：L：begind；d：s；s；end(2)句子L：L：begind；d；s；send的相应语法树是:.解：aacb是文法G[S]中的句子，相应语法树是:最右推导：S=>aAcB=>aAcb=>aacb最左推导：S=>aAcB=>aacB=>aacbaabacbadcd不是文法G[S]中的句子因为文法中的句子不可能以非终结符d结尾aacbccb不是文法G[S]中的句子可知，aacbccb仅是文法G[S]的一个句型的一部分，而不是一个句子。aacabcbcccaacdca不是文法G[S]中的句子因为终结符d后必然要跟终结符a,所以不可能出现…de…这样的句子。aacabcbcccaacbca不是文法G[S]中的句子由(1)可知：aacb可归约为S,由文法的产生式规则可知，终结符c后不可能跟非终结符S,所以不可能出现…caacb…这样的句子。.证明：用归纳法于n,n=l时，结论显然成立。设n=k时，对于a1a2...akT*b,存在Bi：i=l,2,..,k,aiT*bi成立，现在设a1a2...akak+lT*b,因文法是前后文无关的，所以a1a2…ak可推导出b的一个前缀b',ak+1可推导出b的一个后缀=b"(不妨称为bk+1)。由归纳假设，对于b',存在Bi：i=l,2,..,k,b'=B1B2...Bk,使得aiT*bi成立，另外,我们有ak+lT*b"(=bk+1).即n=k+l时亦成立。证毕。.证明：(1)用反证法。假设a首符号为终结符时，B的首符号为非终结符。即设：a=a3；B=A3，且a=>♦0«由题意可知：a=a3T…TA3,=p,由于文法是CFG,终结符a不可能被替换空串或非终结符，因此假设有误。得证；(2)同(1),假设：B的首符号为非终结符时，a首符号为终结符。即设：a=as：P=A3,且a=a3T…TA3,=p,与(1)同理，得证。.证明：因为存在句子：abc,它对应有两个语法树(或最右推导)：STABTAbeTabeSTDCTDcTabc所以，本文法具有二义性。.解：STABTAaSbTAacbTbAacbTbbAacbTbbaacb上面推导中，下划线部分为当前句型的句柄。对应的语法树为：全部的短语:第一个a(al)是句子bbaacb相对于非终结符A(A1)(产生式A?a)的短语(直接短语)；blal是句子bbaacb相对于非终结符A2的短语；b2blal是句子bbaacb相对于非终结符A3的短语；c是句子bbaacb相对于非终结符S1(产生式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=>FPtTFEtTFET+tTFEF+tTFEP+tTFEi+tTFTi+tTFTF*i+tTFTP*i+tTFTi*i+tTFFi*i+tTFPi*i+fTFii*i+tTPii*i+tTiii*i+t.证明：充分性：当前文法下的每一符号串仅有一个句柄和一个句柄产生式T对当前符号串有唯一的最左归约T对每一步推导都有唯一的最右推导T有唯一的语法树。必要性：有唯一的语法树T对每一步推导都有唯一的最右推导T对当前符号串有唯一的最左归约T当前文法下的每一符号串仅有一个句柄和一个句柄产生式.化简下列各个文法⑴解:S—bCACdAfcSA|cCCCfcS|c(2)解：S—aAB|fA|gA—e|dDADfeABff(3)解：S-ac.消除下列文法中的e产生式⑴解:SfaAS|aS|bAfcS(2)解：S-aAA|aA|aA-bAc|be|dAe|de.消除下列文法中的无用产生式和单产生式(1)消除后的产生式如下：SfaB|BCB-DB|bC-bDi|DB(2)消除后的产生式如下：S-SA|SB|()|(S)|[]|[S]A-0|(S)|[]|[S]Ba[]|[S](3)消除后的产生式如下：E-E+T|T*F|(E)|PtF|iTfT*F|(E)|PtF|iFfPtF|(E)|iPf(E)|i第三章习题解答1.从略2.3假设W:表示载狐狸过河，G:表示载山羊过河，C:表示载白菜过河用到的状态1：狐狸和山羊在左岸2：狐狸和白菜载左岸3:羊和白菜在左岸4:狐狸和山羊在右岸5:狐狸和白菜在右岸6:山羊和白菜在右岸F:全在右岸4证明：只须证明文法G:A-aB或A~a(A,BGVN,aGVT+)等价于Gl:A-aB或Afa(aCVT+)G1的产生式中A-aB,则B也有BfbC,CfcD….所以有Afabc…B',a,b,c…CVT,B'SVN所以与G等价。2)G的产生式AfaB,aCVT+,因为a是字符串，所以肯定存在着一个终结符a,使AfaB可见两者等价，所以由此文法产生的语言是正规语言。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)其对应的右线性文法是：AfOD,B^OA,B-*1C,C-111F,C^1|OA,F-O|OE|1A,D-OB|1C,E-*1C|OB(2)最短输入串Oil(3)任意接受的四个串011,0110,0011,000011(4)任意以1打头的串.8从略。9(2)相应的3型文法(i)S-aAS-bSA-aAA-bBB-a|aBB-*b|bBS-aA|aS-bBB-aB|bBA-aBA-b|bAS-*aAS-bBA-bAA-aCB-aBB-*bCC-a|aCC-*b|bCS-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,Bf£,AfaG2等价的右线性文法：S—dD,S-aB,D-C,B-abC,B-bB,B~bA,Bfe,C~cA,A—a(3)对G1文法,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'文法都不能产生。11将右线性文法化为左线性文法的算法：(1)对于G中每一个形如A-aB的产生式且A是开始符，将其变为B-a,否则若A不是开始符，B-Aa;(2)对于G中每一个形如A-*a的产生式，将其变为S-Aa12(1)状态矩阵是：记[S]=qO[B]=ql[AB]=q2[SA]=q3，最小化和确定化后如图(2)记[S]=qO,[A]=ql,[BS]=q2最小化和确定化后的状态转换图如下(1)将具有e动作的NFA确定化后，其状态转换图如图：记{SO,Sl,S3)=qO{Sl}=ql{S2S3}=q2{S3}=q3(2)记{S}=qO{Z}=ql{UR}=q2{SX}=q3{YUR}=q4{XSU}=q5{YURZ}=q6{ZS}=q7(1)从略(2)化简后SO和SI作为一个状态，S5和S6作为一个状态。状态转换图如图15从略。16从略。(l)r*表示的正规式集是{e,r,rr,rrr,…}(e|r)*表示的正规式集是{e,ee，…}U{r,rr,rrr,…}={e,r,rr,rrr,…}e|rr*表示的正规式集是{e,r,rr,rrr,…}(r*)*=r*={£,r,rr,rrr,…}所以四者是等价的。(2)(rs)*i•表示的正规式集是{e,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)A=abS+bB(3)C=D(4)D=bB+d⑸把(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⑵B=Bb+a⑶C=D+Bab⑷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<stdio.h>#include<string.h>#include<ctype.h>#defineONI#defineTW2#defineTHRE3#defineTE10#defineHUNDRE100#defineWHITE9999%}upper[A-Z]%%ONEretumON;TWOretumTW;THREEreturnTHRE;TENretumTE;TWENTYretumTWENT;HUNDREDretumHUNDRE;"M+|\tretumWHITE;\nretumO;%%main(intargc,char*argv[]){intc,i=0;chartmp[30];if(argc=2)if((yyin=fbpen(aigv[l],urn))=NULL)printf(Mcan*topen%s\n**,argv[1]);exit(0);while((c=yylex())!=0)(switch(c){caseON:c=yylex();if(c=0)goto{i+=l;label;}c=yylex();if(c==HUNDRE)i+=100;elsei+=l;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(n%d\nn,i);return;}24(1)Dn表示的正规集是长度为2n任意a和b组成的字符串。此正规式的长度是2n用来识别Dn的DFA至多需要2n+l个状态。25从略。26(1)由{}括住的，中间由任意个非{组成的字符串，如{},{}}，5},86鱼}等等。(2)匹配一行仅由一个大写字母和一个数字组成的串，如A1,F8,Z2等。(3)识别\r\n和除数字字符外的任何字符。由‘和’括住的，中间由两个或者非'和正组成的任意次的字符串。如''''，'a'bb'def', 等等270[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])\,)28A[a-zA-Z_]+[0-9]*[a-zA-Z」*29参考程序如下：%{//include<stdio.h>#include<string.h>#include<ctype.h>//defineUPPER2#defineWHITE3%)upper[A-Z]%%{upper}+retumUPPER;\t|HH+retumWHITE;%%main(intargc,char*argv[])(intc,i；if(argc=2){if((yyin=fbpen(argv[1],"r"))==NULL){printff'can'topen%s\nM,argv[1]);exit(0);)}while((c=yylex())!=EOF)if(c==2)for(i=O;yytext[i];i-H-)printfi(,,%cH,tolower(yytext[i]));yytext[O]='\OOO,;}if(c==3)printff")；elseprintf{M%s,*,yytext);}return;)yywrap()(return;}30从略。第四章习题参考答案.解：(1)S-*(S)Z21|()Z21|[S]Z31|[]Z31A^(S)Z22|()Z22|[S]Z32|[]Z32B-*(S)Z23|()Z23|[S]Z33|[]Z33Zll-£|AZ11|BZ21Z12fAz12|BZ22Z13fAz13|BZ23Z21-Z11Z22fe|Z12Z23fzi3Z31fz21Z32-Z22Z33f£|Z23(2)S-bZH|aZ21A-bZl2|aZ22Zlie|AZ21Z12fAz22Z21fsz21Z22f£|SZ22(3)S-*(T)Z11|aZll|ZllS-(T)Z12|aZ12|Z12Zllfe|Z21Z12fz22Z21-,SZ21Z22f£|,SZ22.解：SAbBlJ.l(表示第1步，用产生式LI推导，以下同)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,31eddfbbedSd7,4.1eddfbbaSd7,4.2eddfbbd6,32.解：以下Save表示savetoken_pointervalue,Restore表示restoretoken_pointervalueo(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;Ifnexttoken=,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'f+VE'|£V7FunctionP: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;Restore;S:=false;End;FunctionC:boolean;BeginSave;C:=true;Ifnext_token=,,if5thenIfEthenIfnext_token=^^then^^thenIfSthenreturn;Restore;C:=false;End;FunctionE:boolean;BeginSave;E:=true;IfVthenIfEpthenreturn;Restore;E:=false;End;FunctionEp:boolean;BeingSave;Ep:=true;Ifnext_token=,+,thenIfVthenIfE'thenreturn;Return;End;.解：.证：因为是左递归文法，所以必存在左递归的非终结符A,及形如A-a|B的产生式，且aT*Ad.则first(Ad)Clfirst(B)W，从而first(a)nflrst(B)W巾，即文法不满足LL(1)文法条件。得证。.证：LL(1)文法的分析句子过程的每一步，永远只有唯一的分析动作可进行。现在，假设LL(1)文法G是二义性文法，则存在句子a,它有两个不同的语法树。即存在着句子a有两个不同的最左推导。从而可知，用LL(1)方法进行句子a的分析过程中的某步中，存在两种不同的产生式替换，且均能正确进行语法分析，即LL(1)分析动作存在不确定性。与LL(1)性质矛盾。所以，G不是LL(1)文法。.解：(1)D产生式两个候选式fD和f的first集交集不为空，所以不是LL(1)的。(2)此文法具有左递归性，据第5题结论，不是LL(1)的。.解：(1)消除左递归性，得：S-bZll|aZ21A-bZ12|aZ22Zll-bZll|eZ12fbz12Z21fbz11|aZ21Z22fbz121az22|e消除无用产生式得：S^bZll|aZ21Zll^bZll|eZ21fbz1l|aZ21此文法已满足LL(1)文法的三个条件，所以G'[S]:S-*bZll|aZ21ZH-bZll|eZ21-bZll|aZ21(2)G’文法的各非终结符的FIRST集和FOLLOW集：产生式FIRST集FOLLOW集SiZllfaZ21{b}{a}{#}Zll-bZll—►€{b}⑻{#}Z21-bZllfaZ21{b}{a}{#}LL(1)分析表为：aaZ21bZHZllbZllZ21aZ21bZll.解：(1)产生式first集follow集S—SaBfbB{b}{b}A-S{b}B—Ac{a,b}⑵将S-SaB|bB改写为SfbBS',S'-aBS'⑷,可验证，新文法是LL⑴的。10.解:1)为方便书写，记：〈布尔表达式＞为人，〈布尔因子》为B,〈布尔二次量＞为C,v布尔初等量》为D,原文法可以简化为：A-AVB|BB-BAC|CC--|D|DD-(A)|true|false,显然，文法含有左递归，消去后等价LL(1)文法为：A-BA'A'-VBA'⑼BYB',B'-ACB'|wC-1D|DD-(A)|true|false⑵略证:若LL(1)文法G有形如B-aAAb的产生式，且AT+£及AT*ag,根据FIRST集FOLLOW集的构造算法可知，FIRST(A)中一切非£加到FOLLOW(A)中，贝UadFOLLOW(A)；又因为a£FIRST(ag),所以两集合相交非空，因此，G不是LL(1)文法；与前提矛盾，假设不成立,得证。解：(1)SA不是简单优先文法。)>A>是简单优先文法。是简单优先文法。首先消去无用产生式Z-E,Z-E+TSZT#i<<<I>>(<<<)>>化简后的文法是简单优先文法;解：SA/AS>>AA和/之间同时有关系=和＜，所以不是简单优先文法；提示：分析教材中给出的算法，选择一种合适的表示给定文法的方法（尽量简单），使得对文法的输入比较简单的同时（需要把输入转化为计算机语言表示，这种转化应该尽量简单），能够比较简单地构造3个基本关系矩阵（=,LEAD和LAST）。证明：设xjxj+l...xi是满足条件xj-l＜xj=xj+l=...=xi＞xi+l的最左子串。由=关系的定义，可知xjxj+L.xi必出现在某产生式的右部中。又因xj-l＜xj可知xj-l与xj不处于同一产生式，且xj是某右部的首符。同理，xi为某产生式的尾符号。即存在产生式Ufxjxj+L..xi设ST*aUb其中，aT*...xj-l,bT*xi+1...对于aUb可构造一语法树，并通过对其剪枝（归约），直到U出现在句柄中。从而xjxj+l...xi必为句柄。反之，若xjxj+l...xi是句柄，由简单优先关系的定义，必满足上述条件。解：为描述方便，用符号表示各非终结符：D=＜变量说明＞,L=＜变量表＞，V=＜变量＞1=＜类型＞，a=VAR,则消去V,并采用分层法改写文法，得到：DfaW:T;W—LL-L,i|iT~r|n|b|c其全部简单优先关系是：DWTLar|n|b|cDWTr|n|b|c>是简单优先文法。证：设STna,我们对n用归纳法，证明a不含两个非终结符相邻情况。n=l时，STa,即S，a是文法的产生式，根据定义，它不含上述情况。设n=k时，上述结论成立，且设STkdAb,由归纳假设，A两侧必为终结符。我们再进行一步推导，得STkdAbTdub,其中，A-u是文法中的产生式，由定义，u中不含两个非终结符相邻情况，从而dub两个非终结符相邻情况。得证。证：由于G不是算符文法，G中至少有一个产生式，其右部含有两个非终结符相邻的情况。不失一般性，设其形为U-xABy,x,yCV*,由于文法不含无用产生式，则必存在含有U的句型dUb,即存在推导ST*dUbTdxAByb.得证。文法为：E-EtA|AAfA*T|A/T|TT-T+V|T-V|VV-i|(E)解：(1)构造算符优先矩阵：(2)在(-,-)、(-,*)和(*,-)处有多重定义元素，不是算符优先文法；(3)改写方法：将E-E-T中的减号与F--P中的赋值运算符强制规定优先关系；或者将F-P中的赋值运算符改为别的符号来表示；(1)证明：由设句型a=“Ua…中含a的短语不含U,即存在A,A=>*ay,则a可归约为a=♦•Ua-U*-UA-=b,b是G的一个句型，这与G是算符文法矛盾，所以，a中含有a的短语必含U。(2)的证明与(1)类似，略。证：(1)对于a=“aU…是句型，必有ST*a(=…aU…)T+…ab….即在归约过程中,b先于a被归约,从而,a<b.对于⑵的情况类似可以证明。证明略.证明略.证明略。证：(1)用反证法。设没有短语包含b但是不包含a,则a,b一定同时位于某个短语中，从而必使得a,b同时位于同一产生式的右部，所以a=b,与G是算符优先文法(=与<不能并存)矛盾。(2)、(3)类似可证。证：只要证u中不含有除自身以外的素短语。设有这样的素短语存在，即存在bx・「by是素短语，其中l<x或者y<n之一成立。因素短语是短语，根据短语定义，则必有：l<xTbx-l<bx或y<nTby>by+l,与bx-l=bx及by=by+l矛盾，得证。提示：根据27题的结论，只要证u是句型a的短语，根据=关系的定义容易知道u是句型a的素短语。证：与28题的不同点只是aO,an+l可以是',不影响结论。证：设不能含有素短语，则只能是含有短语(不能含有终结符号)，则该短语只能含有一个非终结符号，否则不符合算符文法定义，得证。解：(1)算符优先矩阵：

<#<<<<（2）用Floyd方法将优先矩阵线性化得到得的优先函数为:+*）i#F3551771G2466161解：用Floyd方法对已知的优先矩阵构造的优先函数为:z1567747g1654667解：（1）优先矩阵如下:(2)用Bell方法求优先函数的过程如下:f5751g5561显然，文法不是算符优先文法，所以不能线性化。略。解：(1)识别全部活前缀的DFA如下：(略。解：(1)本章中其余的题目也是采用这种形式表示。)状态项目集经过的符号到达的状态10S'f•ss-**aSbS—,aScS—•abaII12IIS'-S•12Sfa•SbSfa,ScS-a•bS-•aSbSf•aScS—•abSab1312S-*aS•b151614S-*ab,15S-*aSb•16S-^aSc•(2)识别全部活前缀的DFA如下:状态项目集经过的符号到达的状态10S'f.SSf•cAS-**ccBII12S-c•AS—c•cBA—•cAA-**aAca13141513S—cA・14S-*cc•BA—c,ABf•ccBB-**bA—•cAA-**aBAcb161517181515A-*a•16S->ccB•17B—c•cBAfc•AAf•cAAf•aCAa19IIO1518B~b•19B-*cc,BAfc•ABf•ccBA—•cAA一•aBAcbaIIIIIO171815IIOA-*cA•IllBfccB•所求的LR(O)项目规范族C={IO,H,…,111}(3)状态项目集经过的符号到达的状态S—•aSSbS-•aSSSS-•cScaII1213IIS'-S•12S—c•13Sfa•SSbS-*a・SSSS-•aSSbS一-aSSSS—•cSca1412SfaS•SbS-aS•SSSf•aSSbS-*•aSSSS—•cSca15121315S-^aSS•bS-aSS•SS一•aSSbS-•aSSSS—•cSabc171316S-aSSb-17S—aSSS•(4)状态项目集经过的符号到达的状态10S，一•SS—•AA-•AbAf•aII1213IIS'-S・12S-A•S-A•bb1413A—a•14S-Ab•解：(1)是LR(O)文法，其SLR(l)分析表如下：FOLLOW(S)={#,b,c)ACTIONGOTOS2ACCS2S43S5S6R3R3R3RIRIRIR2R2R2(2)是LR(O)文法，其SLR(l)分析表如下:FOLLOW(S)=FOLLOW(A)=FOLLOW(B)={#}ACTIONGOTOc#SAB0S211ACC2S5S433RI4S5S8S7R4R27S5S9108R69S5S8S7101110R311R5(3)是LR(0)文法，其SLR(l)分析表如下：FOLLOW(S)={#,a,b,c}ACTIONGOTO0S3S2ACCR3R3R3R3S3S24S3S25S3S6S27RIRIRIRIR2R2R2R2(4)因为12中含有冲突项目，所以不是LR(O)文法，其SLR(l)分析表如下：FOLLOW(S)={#}n{b}=e(所以可以用SLR⑴规则解决冲突),FOLLOW(A尸{b,#}ACTIONGOTOb#SAS312ACCS4RIR3R3R2R2解：状态项目集经过的符号到达的状态10S'f•SS一•(SRSf•aII1213IIS'-*s•12S-*(•SRS一•(SRS-**aS(a14121313S-*a•14S-(S•RS一•(SRS—,aRf•,SRR一•))131215161715Sf(SR•16Rf,•SRSf•(SRSf•aS(a18121317Rf)・18Rf,S•RRf•,SRR17161919Rf,SR•LR(O)分析表如下:ACTIONGOTOa()#SR0S3S2ACC2S3S24R2R2R2R2R2S3S2S7S65RIRIRIRIRIS3S2R4R4R4R4R4S69R3R3R3R3R3可见是LR(O)文法。解：(1)状态项目集经过的符号到达的状态10S'—•SS—•SabS-•bRII12II（冲突项目）S'-S・S-*S•abaacc1312S-b•RR-*•SR-**aS—•Sab1415161213SfSa•bb1714S-bR•r215R-S•ST•aba1316R—a•17S-Sab•项目11,15同时具有移进和归约项目，对于I5={R-S•,S-S•ab},follow(R)={a},follow(R)D{a}={a},所以SLR⑴规则不能解决冲突，从而该文法不是SLR(l)文法。(2)状态项目集经过的符号到达的状态10S，一•SS—•aSABS-**BAB-**bSaBbII121314IIS'-S・12S-a•SABS—•aSABS—•BAB-•bSa12131413S-B•AAf•aAA一•BB一•bAaBb1617181414B-b•r515S-*aS•ABAf•aAA—•BB-**bABb1917181416S—BA•r217A-*a,AAf•BAf•aAB一•bABabIIO18171418A-B•r419S-aSA•BB—•bBIll14IIOA->aA•r3IllSfaSAB•rl不存在冲突项目，故该文法是LR(O)文法，也是SLR(l)文法。SLR⑴分析表如下：ACTIONGOTOab#SABS2S413ACCS2S453S7S468R5R5R5S7S498R2R2R2S7S48R4R4R4S4R3R3R311RIRIRI(3)先求识别全部活前缀的DFA：状态项目集经过的符号到达的状态10S'—•SS-•aSbS--bSaSf•ab111213IIS'一S-acc12Sfa•SBSfa•bS—•aSbS—•bSaSf•abSba14151213S-*b,SaS-•aSbS—•bSaSf•abSab16121314SfaS•bb17S-ab•r316S-bS•aa1817S—aSb•rl18S-*bSa•r2不存在冲突项目，故该文法是LR(O)文法，也是SLR(l)文法。SLR(l)分析表如下：ACTIONGOTOS2S31ACCS2S54S2S3S7R3R3R3S8RIRIRIR2R2R2（4）先求识别全部活前缀的DFA：状态项目集经过的符号到达的状态10S'一•SS—•aASf•bBSIIS'—S•acc12（冲突）S-a•AA—•cAdAf•Ac1415r413（冲突）S-b•BB-*•cBddB一•Bc1617r6S-aA•rl（冲突）A-*c,AdA—•cAdA—•A1815r416S-bB•r217（冲突）Bfc•BddB—c•BddBf•B1917r618A-*cA•ddIIO19B-*cB•dddIllIIOA-*cAd•IllB-*cBd,dd112112B—cBdd•r5因为fbllow(A尸fbUow(B)={执d},所以冲突项目12,13,15,17可以用SLR⑴规则得以解决，从而该文法为SLR(l)文法。其SLR(l)分析表如下：ACTIONGOTOabcd#SAB0S2S3AccR4R443S7R6R664RIS5R4R486R27S7R6R698S109Sil10R3R311S12R5(5)解：原文法等价化为ql-*q2,ql-q3,q2—q4;q5,q4-beginD,q4fq4;D,q5fsend,q5fS;q5,q3-beginq5,先求识别全部活前缀的DFA：状态项目集经过的符号到达的状态10ql，-**qlq[f•q2qL,q3q2f,q4;q5q3f•beginq5q4f,beginDq4f•q4;Dqiq2q3q4beginII1213Ilql'—ql•ACC12ql->q2•RI13ql~q3•R214q2fq4•;q5q4fq4,;D5D1615q3fbegin•q5q3fbegin•Dq5f•Sendq5f・S;q5q5D17181916q2fq4;•q5q5-**Sendq5f,S;q5q5DSIIOIll1917q3fbeginq5•R818q3fbeginD•R419q5fs•endq5fs•;q5end112113IIOq2fq4;q5•R3Illq4fq4;D•R5q5-*Send•R6113q5-*s;•q5q5—•Sendq5f•S;q5q511419114q5fs;q5•R7不存在冲突项目，故该文法是LR(O)文法，也是SLR(l)文法。SLR(l)分析表如下：ACTIONGOTObeginDSend#qiq2q3q4q51Acc2RI3R24S65S8S976S7S9107R88R49S13S1210R311R512S914R7（6）解：原文法可化为等价形式：ql-*beginq2q3end,q2fq2d;,q2f£,q3fq3;q4,q3fq4,q4fS,q4f£,先求识别全部活前缀的DFA：状态项目集经过的符号到达的状态10ql'-**qlql—•beginq2q3endqibeginII12IIql'fql•ACC12ql-*begin•q2q3endq2f・q2d;q2一•q2q213（冲突项目）QI-*beginq2,q3endq2fq2•d;q3-**q3;q4q3f•q4q4f,Sq4-*q3Ddq4S14IIO1516R714ql-*beginq2q3•endq3fq3,;q4end17q3fq4•R516q4fs,R617q1-*beginq2q3end,RI18（冲突项目）q3fq3;,q4q4f•Sq4f,q41916R719q3fq3;q4•R4IIOq2fq2d・;IIIIllq2fq2d;,R2因为foHow(q4)={end,#},故冲突项目可以通过SLR⑴规则来解决，从而文法为SLR(l)文法。SLR(l)分析表如下：actiongotobeginenddS#qiq2q3q4S2R3R3R3R3R7S10R7S6L5S7S8R6R6RIR7R7S699R4R41011R2R2R2R2解：识别活前缀的DFA及LR(0)分析表:状态项目集经过的符号到达的状态10S'一•SS—•AAdS—•cAdS--bA—•AScA—•SbA一•aSAabc1016151413IIS'—S•A-S•bb1212A—Sb,13S—c•AdA—c•dA-*•AScA-•SbA-**cdS—•AAdSf•cAdS—•bSAabcd18191514131714S-b•15A—a•16SfA•AdAfA•ScAf•AScAf•SbA—,aSf•AAdS—•cAdS—・bSAabcIllIK)15141317A-*cd•18A-*S,bb1219S-*cA•dA-A•ScS—,AAdS—,cAdS-*•bAf-AScA一SbA-*•cdA—•aSAabcdIllIIO151413114IIOS—AA•dAfA•ScS-A•AdSf•AAdS—•cAdS—•bA—•AScA—•SbA—•cdAf•aSAabcdIllIIO151413113IllA-AS•cAfS•bb112112A-*ASc•113S-*AAd•114S—cAd•ACTIONGOTOabcd#SAs4s2accr5r5r5r5r5s5s4s3s789r3r3r3r7r7r7s5s4r6r6r6r6r61110s2s5s4s3sl41110s5s4s3S13111011s2sl212r4r4r4r4r413rlrlrlrl14r2r2r2r2r2SLR⑴分析法：FOLLOW(S)={c,b}FOLLOW(A)={a,b,c,d}ACTIONGOTObcd#s5s4s36s2accr5r5r5r5s5s4s3s789r3r3r7s5s4s3r6r6r61110s2s5s4s3S14111010s5s4s3sl3111011s2s1212R4r4r4r413rlrl14r2两表的异同：两表都用ACTION表和GOTO表反映了移进、归约(包括接受)的状态和动作。不同之处在于SLR(l)增加了在归约的时候考虑向前符号a以解释可能出现的“移进一一归约”冲突；SLR(1)的分析较稀疏些，原因是填写归约项时，并不是在一状态对应行上全部填写归约动作，而是考虑了相应非终结符的FOLLOW集因素。另外，在分析效率上SLR(1)分析的效率更高一些，因为在发现错误方面，SLR(I)比LR(0)分析发现的更早些。解：求LR(1)项目集和状态转换表：状态项目集经过的符号到达的状态10S'f.S#S-*•A#Af•BA#A—•#B—•aB#,a,bB-*•b#,a,bSABabII1213IlS'T・#12S-A•#13A—B•A#A—•#Af•BA#B-**aB#,a,bB一•b#,a,bABab1613141514B-*a•B#,a,bB—•aB#,a,bB-•b#,a,bBab1515B-*b•#,a,b16A-BA•#17B-aB•#,a,b相应的LR(1)分析表为:STATEACTIONGOTO0S4S5R31231ACC2R2S4R3634S4S575R5R5R56R27R4R4R4用LR(1)分析表对输入符号串abab的分析过程:步骤状态栈中符号余留符号分析动作下一状态10#abab#S44204#abab#S5045#abab#R57047#aBab#R4303#Bab#S44034#Bab#S550345#Bab#R470347#BaB#R43033#BB#R36100336#BBA#R2611036#BA#R211201#A#acc解：(1)求LR(1)项目集和状态转换图:状态项目集经过的符号到达的状态10S'一•S#S-*•A#Af•AB#,a,bAf•AII12IIS'—S・#12SfA•#AfA•B#,a,bB一•aB#,a,bB—•b#,a,bBab13151413A-AB•#,a,b14Bfb•#,a,b15B~*a•B#,a,bB-*•aB#,a,bBf•b#,a,bB16151416B-*aB•#,a,b相应的LR(1)分析表为:STATEACTIONGOTOab#SAB0R3R3R312AccS5S4RIR2R2R2R5R5R5S5S46R4R4R4表中没有多从定义的元素，所以文法是LR(1)文法。(2)LR⑴分析法：状态项目集经过的符号到达的状态10E'f・E#E•E+T#/+Ef•T#/+T-*•(E)#/+Tf•a#/+ETIl1514IIE，—E・#E—E•+T#/++1212EfE+•T#/+T-*•(E)#/+T—•a#/+T13151413E—E+T•#/T14T-*a•#/+15T-(•E)#/+E--E+T+/)E—•T)/+)0+e•-10+E)•-14-/(1•一日(/+i+n•-a+/((a•)-i81inon4-((/+±+•a-a+/#(・3)-1L\+/#•I-H912116181L\1DH(/+e,一工(/+(a)-一工ET181121141919E-T•+/)IIOT-(E)•#/+IllEfE+•T+/)T-*•(E)+/)T-**a+/)(Tfa•+/)113EfE+T•)/+114T-(E•)+/)E—E•+T+/)Ill115115T-(E)•+/)LALR(l)分析：(合并同心集)状态项目集经过的符号到达的状态10E'f•E#Ef•E+T#/+Ef•T#/+Tf•(E)#/+T-*•a#/+EII16/1914/112E，—E・#E-*E•+T#/++12/11112/111E—E+•T#/+/)T一•(E)#/+/)T-•a#/+/)T13/11315/1814/11213/113E-E+T•)/+/#14/112Tfa•+/)/#15/18T-(•E)#/+/)Ef•E+T+/)Ef•T)/+T—•(E)+/)T-**a+/)T16/1915/1817/11414/11216/19E-T•+/)/#17/114T-(E•)+/)/#EfE•+T+/))12/111110/115110/115Tf(E)•+/)/#LR⑴ACTIONGOTOI()a#ET0S5S41S2ACCS5S43RIRIR4R4S8S1279R2R2SilS10S8S12149R2R210R311S8S121312R4R413RIRI14SilS1515R3R3可以看出，表中无冲突项，所以是LR(1)文法；LALR(1)分析表:LR(1)ACTIONGOTO)a#ET0S5/S8S4/S1216/92/11S5/S8S4/S123/133/13RIRIRI4/12R4R4R45/8S5/S8S4/S127/146/96/9R2R2R210/15R3R3R37/14S2/S11S10/S15解：(1)求LR(1)项目集和状态转换图:状态项目集经过的符号到达的状态10E'一•E#E-*•E+E#,+,*E-•E*E#,+,*E—•i#,+,*EiII12IIE，T・#E—E•+E#,+,*E-*E•*E#,+,*+*131412E-*i•#,+,*13EfE+•E#,+,*E—•E+E#,+,*E—•