蒋立源《编译原理》西北工业大学出版社第3版课后答案

《编译原理》课后习题答案第一章解：源程序是指以某种程序设计语言所编写的程序。目标程序是指编译程序〔或解释程序〕将源程序处理加工而得的另一种语言〔目标语言〕的程序。翻译程序是将某种语言翻译成另一种语言的程序的统称。编译程序与解释程序均为翻译程序，但二者工作方法不同。解释程序的特点是并不先将高级语言程序全部翻译成机器代码，而是每读入一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读入下一条语句继续进行解释、执行，如此反复。即边解释边执行，翻译所得的指令序列并不保存。编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的空间中，在用户需要时再执行之。即先翻译、后执行。解：一般说来，编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。解：C语言的关键字有：auto

break

casecharconst

continuedefaultdodoubleelseenumexternfloatforgotoifintlongregisterreturnshortsignedsizeofstaticstructswitchtypedefunionunsignedvoidvolatilewhile。上述关键字在C语言中均为保存字。解：C语言中括号有三种：{}，[]，〔〕。其中，{}用于语句括号；[]用于数组；〔〕用于函数〔定义与调用〕及表达式运算〔改变运算顺序〕。C语言中无END关键字。逗号在C语言中被视为分隔符和运算符，作为优先级最低的运算符，运算结果为逗号表达式最右侧子表达式的值〔如：(a,b,c,d)的值为d〕。略第二章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→1A

解：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|iT→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将右线性文法化为左线性文法的算法：〔1〕对于G中每一个形如A→aB的产生式且A是开始符，将其变为B→a,否则假设A不是开始符，B→Aa;〔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}=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,…}(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*cG1: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<stdio.h>#include<string.h>#include<ctype.h>#defineON1#defineTW2#defineTHRE3#defineTE10#defineTWENT20#defineHUNDRE100#defineWHITE9999%}upper[A-Z]%%ONEreturnTWOreturnTW;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%s\n",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("%d\n",i);return;}24〔1〕Dn表示的正规集是长度为2n任意a和b组成的字符串。此正规式的长度是2n用来识别Dn的DFA至多需要2n＋1个状态。25从略。26〔1〕由{}括住的,中间由任意个非{组成的字符串,如{},{}},{a},{defg}等等。〔2〕匹配一行仅由一个大写字母和一个数字组成的串，如A1,F8,Z2等。〔3〕识别\r\n和除数字字符外的任何字符。由’和’括住的，中间由两个’’或者非’和\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<stdio.h>#include<string.h>#include<ctype.h>#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%s\n",argv[1]);exit(0);}}while((c=yylex())!=EOF){if(c==2){for(i=0;yytext[i];i++)printf("%c",tolower(yytext[i]));yytext[0]='\000';}if(c==3)printf("");elseprintf("%s",yytext);}return;}yywrap(){return;}从略。第四章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|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→ε|,SZ222.解：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.23.解：以下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=’+’thenIfVthenIfE’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εZ21aZ21bZ119.解：(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)文法；与前提矛盾，假设不成立，得证。12。解：(1)SA(a)bS==A=<=<(==<<<a>=<><>>)>>>>>b>>不是简单优先文法。(2)SRT()∧a,S>=R=T>(<=<<<<)>>∧>>a>>,<=<<<是简单优先文法。(3)SR(a,)S=<<R>>(=<<a>>,=<<)>>是简单优先文法。首先消去无用产生式Z→E,Z→E+TSZT#i()SZ==T>>#=<<<I>>(=<<<)>>化简后的文法是简单优先文法；13.解：SA/AS>>A=<=<=/>>a>>A和/之间同时有关系=和<,所以不是简单优先文法；提示：分析教材中给出的算法，选择一种适宜的表示给定文法的方法〔尽量简单〕，使得对文法的输入比拟简单的同时(需要把输入转化为计算机语言表示，这种转化应该尽量简单)，能够比拟简单地构造3个根本关系矩阵〔=，LEAD和LAST〕。证明：设xjxj+1...xi是满足条件xj-1<xj=xj+1=...=xi>xi+1的最左子串。由=关系的定义，可知xjxj+1...xi必出现在某产生式的右部中。又因xj-1<xj可知xj-1与xj不处于同一产生式，且xj是某右部的首符。同理，xi为某产生式的尾符号。即存在产生式U→xjxj+1...xi设ST*aUb其中，aT*...xj-1,bT*xi+1...对于aUb可构造一语法树，并通过对其剪枝〔归约〕，直到U出现在句柄中。从而xjxj+1...xi必为句柄。反之，假设xjxj+1...xi是句柄，由简单优先关系的定义，必满足上述条件。解：为描述方便，用符号表示各非终结符：D=<变量说明>,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)20.解：〔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被归约,从而,a<b.对于(2)的情况类似可以证明。证明略.证明略.证明略。证：(1)用反证法。设没有短语包含b但是不包含a，则a,b一定同时位于某个短语中，从而必使得a,b同时位于同一产生式的右部，所以a=b，与G是算符优先文法〔=与<不能并存〕矛盾。〔2〕、〔3〕类似可证。证：只要证u中不含有除自身以外的素短语。设有这样的素短语存在，即存在bx···by是素短语，其中1<x或者y<n之一成立。因素短语是短语，根据短语定义，则必有：1<xTbx-1<bx或y<nTby>by+1，与bx-1=bx及by=by+1矛盾，得证。提示：根据27题的结论，只要证u是句型α的短语，根据=关系的定义容易知道u是句型α的素短语。证：与28题的不同点只是a0,an+1可以是’#’,不影响结论。证：设不能含有素短语，则只能是含有短语〔不能含有终结符号〕，则该短语只能含有一个非终结符号，否则不符合算符文法定义，得证。31.解：〔1〕算符优先矩阵：+*↑〔〕i#+><<<><>*>><<><>↑>><<><>(<<<<=<)>>>>>I>>>>>#<<<<<〔2〕用Floyd方法将优先矩阵线性化得到得的优先函数为：+*↑()i#F3551771G246616132.解：用Floyd方法对的优先矩阵构造的优先函数为：zbMLa()f1567747g165466733.解：〔1〕优先矩阵如下：[]a#[>=]>>a<><><#<<<〔2〕用Bell方法求优先函数的过程如下：[]a#f5751g5561〔3〕显然，文法不是算符优先文法,所以不能线性化。略。35解：〔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·AS→c·cBA→·cAA→·aAcaI3I4I5I3S→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→·AA→·AbA→·aSAaI1I2I3I1S’→S·I2S→A·S→A·bbI4I3A→a·I4S→Ab·36解：〔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#SA0S3121ACC2S4R13R3R34R2R237解：状态工程集经过的符号到达的状态I0S’→·SS→·(SRS→·aS(aI1I2I3I1S’→S·I2S→(·SRS→·(SRS→·aS(aI4I2I3I3S→a·I4S→(S·RS→·(SRS→·aR→·,SRR→·)a(R,)I3I2I5I6I7I5S→(SR·I6R→,·SRS→·(SRS→·aS(aI8I2I3I7R→)·I8R→,S·RR→·,SRR→·)),RI7I6I9I9R→,SR·LR(0)分析表如下：ACTIONGOTOa(),#SR0S3S211ACC2S3S243R2R2R2R2R24S3S2S7S655R1R1R1R1R16S3S287R4R4R4R4R48S7S699R3R3R3R3R3可见是LR(0)文法。38解：〔1〕状态工程集经过的符号到达的状态I0S’→·SS→·SabS→·bRSbI1I2I1(冲突工程)S’→S·S→S·abaaccI3I2S→b·RR→·SR→·aS→·SabS→·bRRSabI4I5I6I2I3S→Sa·bbI7I4S→bR·r2I5(冲突工程)R→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→·bAaBbI6I7I8I4I4B→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#SAB0S2S311Acc2S5R4R443S7R6R664R15S5R4R486R27S7R6R698S109S1110R3R311S1212R5R5〔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;·Dq5→·Sendq5→·S;q5q5DSI10I11I9I7q3→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#q1q2q3q40S2112R3R3R3R333R7S10R7S6454S7S85R5R56R6R67R18R7R7S699R4R41011R2R2R2R239解：识别活前缀的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→·cAdS→·bSAabcdI8I9I5I4I3I7I4S→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·ScS→A·AdS→·AAdS→·cAdS→·bA→·AScA→·SbA→·cdA→·aSAabcdI11I10I5I4I3I13I11A→AS·cA→S·bbcI2I12I12A→ASc·I13S→AAd·I14S→cAd·ACTIONGOTOabcd#SA0s5s4s3161s2acc2r5r5r5r5r53s5s4s3s7894r3r3r3r3r35r7r7r7r7r76s5s4s37r6r6r6r6r611108s29s5s4s3s14111010s5s4s3s13111011s2s1212r4r4r4r4r413r1r1r1r1r114r2r2r2r2r2SLR(1)分析法：FOLLOW(S)={c,b}FOLLOW(A)={a,b,c,d}ACTIONGOTOabcd#SA0s5s4s3161s2acc2r5r5r5r53s5s4s3s7894r3r35r7r7r7r76s5s4s37r6r6r6r611108s29s5s4s3s14111010s5s4s3s13111011s2s1212R4r4r4r413r1r114r2r2两表的异同：两表都用ACTION表和GOTO表反映了移进、归约〔包括接受〕的状态和动作。不同之处在于SLR(1)增加了在归约的时候考虑向前符号a以解释可能出现的“移进——归约〞冲突；SLR〔1〕的分析较稀疏些，原因是填写归约项时，并不是在一状态对应行上全部填写归约动作，而是考虑了相应非终结符的FOLLOW集因素。另外，在分析效率上SLR〔1〕分析的效率更高一些，因为在发现错误方面，SLR〔1〕比LR〔0〕分析发现的更早些。40解：求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,bB→·b#,a,bABabI6I3I4I5I4B→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#acc41解：〔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#/+E→·T#/+T→·(E)#/+T→·a#/+ET(aI1I1I5I4I1E’→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#ET0S5S4161S2ACC2S5S433R1R14R4R45S8S12796R2R27S11S108S8S121499R2R210R3R311S8S121312R4R413R1R114S11S1515R3R3可以看出，表中无冲突项，所以是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/S1542解：〔1〕求LR(1)工程集和状态转换图：状态工程集经过的符号到达的状态I0E’→·E#E→·E+E#,+,*E→·E*E#,+,*E→·i#,+,*EiI1I2I1E’→E·#E→E·+E#,+,*E→E·*E#,+,*+*I3I4I2E→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→·bbSabI10I14I13I7S→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*ca*(b-c)-(c+d)/e有误if(a<b)x=(a-b)^c;elseg=h;5.6略5.7略5.8解：(+,B,C,T1)(*,A,T1,T2)(+,T2,D,T3)(=,T3,0,X)2〕如下所示：当前句型〔方框括起来局部为句柄〕A/\(BV(CVD/\?F))用产生式Expr→iden归约，得(1)Expr.TC→(jnz,A,0,0);

(2)Expr.FC→(j,0,0,0);当前句型Expr/\(BV(CVD/\?F))用产生式Expr^→Expr’/\’归约，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);当前句型Expr^(BV(CVD/\?F))用产生式Expr→iden归约，得(1)(jnz,A,0,0);

(2)Expr^.FC→(j,0,0,0);

(3)Expr.TC→(jnz,B,0,0);

(4)Expr.FC→(j,0,0,0);当前句型Expr^(ExprV(CVD/\?F))用产生式Exprv→Expr'V'归约，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);当前句型Expr^(Exprv(CVD/\?F))用产生式Expr→iden归约，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);(5)Expr.TC→(jnz,C,0,0);(6)Expr.FC→(j,0,0,0);当前句型Expr^(Exprv(ExprVD/\?F)),用产生式Exprv→Expr’V’归约，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);(5)Exprv.TC→(jnz,C,0,0);(6)(j,0,0,7);当前句型Expr^(Exprv(ExprvD/\?F)),用产生式Expr4→iden归约，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);(5)Exprv.TC→(jnz,C,0,0);(6)(j,0,0,7);(7)Expr.TC→(jnz,D,0,0);(8)Expr.FC→(j,0,0,0);当前句型Expr^(Exprv(ExprvExpr/\?F)),用产生式Expr^→exrp’/\’归约，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);(5)Exprv.TC→(jnz,C,0,0);(6)(j,0,0,7);(7)(jnz,D,0,9);(8)Expr^.FC→(j,0,0,0);当前句型Expr^(Exprv(ExprvExpr^?F)),用产生式Expr→iden归约，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);(5)Exprv.TC→(jnz,C,0,0);(6)(j,0,0,7);(7)(jnz,D,0,9);(8)Expr^.FC→(j,0,0,0);(9)Expr.TC→(jnz,F,0,0);(10)Expr.FC→(j,0,0,0);当前句型Expr^(Exprv(ExprvExpr^?Expr)),用产生式Expr→?Expr归约，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);(5)Exprv.TC→(jnz,C,0,0);(6)(j,0,0,7);(7)(jnz,D,0,9);(8)Expr^.FC→(j,0,0,0);(9)Expr.FC→(jnz,F,0,0);(10)Expr.TC→(j,0,0,0);当前句型Expr^(Exprv(ExprvExpr^Expr)),用产生式Expr→Expr^Expr归约，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);(5)Exprv.TC→(jnz,C,0,0);(6)(j,0,0,7);(7)(jnz,D,0,9);(8)(j,0,0,0);(9)Expr.FC→(jnz,F,0,8);(10)Expr.TC→(j,0,0,0);当前句型Expr^(Exprv(ExprvExpr)),用产生式Expr→ExprvExpr归约，得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)Exprv.TC→(jnz,A,0,0);(4)(j,0,0,5);(5)(jnz,C,0,0);(6)(j,0,0,7);(7)(jnz,D,0,9);(8)(j,0,0,0);(9)Expr.FC→(jnz,F,0,8);(10)Expr.TC→(j,0,0,5);当前句型Expr^(Exprv(Expr)),用产生式Expr→(Expr)归约，所得四元式序列不变当前句型Expr^(ExprvExpr),用产生式Expr→ExprvExpr归约,得(1)(jnz,A,0,3);(2)Expr^.FC→(j,0,0,0);(3)(jnz,A,0,0);(4)(j,0,0,5);(5)(jnz,C,0,3);(6)(j,0,0,7);(7)(jnz,D,0,9);(8)(j,0,0,0);(9)Expr.FC→(jnz,F,0,8);(10)Expr.TC→(j,0,0,5);当前句型Expr^(Expr),用产生式Expr→(Expr)归约，所得四元式序列不变当前句型Expr^Expr,用产生式Expr→Expr^Expr归约,得(1)(jnz,A,0,3);(2)(j,0,0,0);(3)(jnz,A,0,0);(4)(j,0,0,5);(5)(jnz,C,0,3);(6)(j,0,0,7);(7)(jnz,D,0,9);(8)(j,0,0,2);(9)Expr.FC→(jnz,F,0,8);(10)Expr.TC→(j,0,0,5);3〕假设所产生的四元式序列编号从1开始1.当前句型为whileA<CùB>0doifA=1thenC:=C+1elsewhileA<=DdoA:=A+2用产生式W1→while归约，得(1)Wl.loop→2.当前句型为WlA<CùB>0doifA=1thenC:=C+1elsewhileA<=DdoA:=A+2用产生式Expr→idenropiden归约，得(1)Wl.loop→Expr.TC→(j<A,C,0);(2)Expr.FC→(j,0,0,0);3.当前句型为WlExprùB>0doifA=1thenC:=C+1elsewhileA<=DdoA:=A+2用