《编译原理》西北工业大学第三版课后答案1

第一章习题解答

1.解：源程序是指以某种程序设计语言所编写的程序。目标程序是指编译程

序（或解释程序）将源程序处理加工而得的另一种语言（目标语言）的程

序。翻译程序是将某种语言翻译成另一种语言的程序的统称。编译程序与

解释程序均为翻译程序，但二者工作方法不同。解释程序的特点是并不先

将高级语言程序全部翻译成机器代码，而是每读入一条高级语言程序语

句，就用解释程序将其翻译成一段机器指令并执行之，然后再读入下一条

语句继续进行解释、执行，如此反复。即边解释边执行，翻译所得的指令

序列并不保存。编译程序的特点是先将高级语言程序翻译成机器语言程

序，将其保存到指定的空间中，在用户需要时再执行之。即先翻译、后执

行。

2.解：一般说来，编译程序主要由词法分析程序、语法分析程序、语义分析

程序、中间代码生成程序、代码优化程序、目标代码生成程序、信息表管

理程序、错误检查处理程序组成。

3.解：C语言的关键字有：autobreakcasecharconstcontinue

defaultdodoubleelseenumexternfloatforgotoifintlong

registerreturnshortsignedsizeofstaticstructswitchtypedef

unionunsignedvoidvolatilewhile。上述关键字在C语言中均为保留

字。

4.解：C语言中括号有三种：｛｝，口，（）。其中，。用于语句括号；口用

于数组；（）用于函数（定义与调用）及表达式运算（改变运算顺序）。

C语言中无END关键字。逗号在C语言中被视为分隔符和运算符，作为优

先级最低的运算符，运算结果为逗号表达式最右侧子表达式的值（如：

（a,b,c,d）的值为d）o

5.略

第二章习题解答

1.⑴答:26*26=676

(2)答：26*10=260

(3)答：{a,b,c,...,z,a0,al,...,a9,aa,...,az,…，zz,aOO,aOl,...,zzz),

共26+26*36+26*36*36=34658个

2.构造产生下列语言的文法

(1){anbn|n>0}

解：对应文法为G(法=({S},{a,b},{S-*e|aSb),S)

(2){anbmcp|n,m,p^O}

解：对应文法为G(S)=({S,X,Y},{a,b,c},{S-aS|X,X-bX|Y,Y-cY|e},S)

(3){an#bMn2O}U{cn#dnIn^O)

解：对应文法为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,R1,{0,1,#},{S-W#,W-*OWO|1W1#},S)

(5)任何不是以0打头的所有奇整数所组成的集合

解解(S)=({S.A,B,I,J},{-,0,1,2,3,4,5,6,7,8,9},{S-j|IBJ,B-OBIB|e,

I-J246|8,Jal|3|5|7|9),S)

(6)所有偶数个0和偶数个1所组成的符号串集合

解:对应文法为S-OA|lB|e,A->OS|ICB-*OCISCTA|0B

3.描述语言特点

(1)S—10S0S-aAA-bAAfa

解：本文法构成的语言集为：L(G)={(10)nabma0n|n,m»0}。

(2)S-SSS-lAOAf1A0A—e

解：L(G)={lnlOnlln20n2…InmOnm|nl,n2,…，nm>0；月.nl,n2,…nm不全

为零}该语言特点是：产生的句子中，0、1个数相同，并且若干相接的1后必然

紧接数量相同连续的0。

(3)S—IAS—BOA—IAA—CB—B0B—CC—1C0C-e

解:本文法构成的语言集为：L(G)={lpln0n|p>l,n>0}U{InOnOq|q^l,

0),特点是具有IplnOn或InOnOq形式，进一■步，可知其具有形式InOmn,m20,

且n+m>0o

(4)S—bAdcA—AGSG-eA-a

解：可知，S=>,,*=>baSndcn20

该语言特点是：产生的句子中，是以ba开头de结尾的串，且ba、de个数相同。

(5)S-aSSS-a

解：L(G)={a(2nT)|n》l}可知:奇数个a

4.解：此文法产生的语言是：以终结符al、a2-an为运算对象，以A、V、

~为运算符，以［、］为分隔符的布尔表达式串

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；〈语句＞end

TL：L：begind；d；s；send

最右推导:

〈程序＞T＜分程序＞T(标号》：〈分程序》

T〈标号》：＜标号＞：〈分程序》

T〈标号〉：〈标号》：〈无标号分程序》

T〈标号〉：〈标号〉：〈分程序首部〉；〈复合尾部》

T〈标号》:〈标号》:〈分程序首部）;〈语句〉；〈复合尾部》

T〈标号）:〈标号》:〈分程序首部》;〈语句〉;〈语句〉；end

T（标号〉:〈标号》：〈分程序首部》;〈语句〉；s；end

T〈标号》:〈标号》:〈分程序首部）;s；s；end

T〈标号》:〈标号》:〈分程序首部〉;说明；s；s；end

T〈标号》:〈标号》:〈分程序首部）;d；s；s；end

T〈标号》:〈标号》:begin说明；d；s；s；end

T〈标号）:〈标号》:begind；d；s；s；end

T〈标号》:L：begind；d；s；s；end

TL：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,所以不可能出现…de…这样的句子。

(5)aacabcbcccaacbca不是文法G[S]中的句子

由(1)可知：aacb可归约为S,由文法的产生式规则可知，终结符c后不可能

跟非终结符S,所以不可能出现…caacb…这样的句子。

8.证明：用归纳法于n,n=l时，结论显然成立。设n=k时，对于a1a2...akT*b,

存在Bi：i=l,2,..,k,aiT*bi成立，现在设

a1a2…akak+lT*b,因文法是前后文无关的，所以ala2...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)o即n=k+l时亦成立。证毕。

9.证明：(1)用反证法。假设a首符号为终结符时，B的首符号为非终结符。即

设：a=as；B=A3'且a=>*B。

由题意可知：a=a3T…TA3'=6,由于文法是CFG,终结符a不可能被替换

空串或非终结符，因此假设有误。得证；

（2）同（1）,假设：B的首符号为非终结符时，a首符号为终结符。即设：a

=as；p=A«*且a=a3T…TAs'=p,与（1）同理，得证。

10.证明：因为存在句子：abc,它对应有两个语法树（或最右推导）：

STABTAbcTabc

STDCTDcTabc

所以，本文法具有二义性。

11.解：

（1）STABTAaSbTAacbTbAacbTbbAacbTbbaacb

上面推导中，下划线部分为当前句型的句柄。对应的语法树为:

全部的短语:

第••个a(al)是句子bbaacb相对于非终结符A(Al)(产生式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)解：t对应的语法树略。

最右推导：ETT=>F=>FPtTFEtTFET+tTFEF+tTFEP+tTFEi+t

TFTi+tTFTF*i+tTFTP*i+tTFTi*i+tTFFi*i+tTFPi*i+t

TFii*i+tTPii*i+tTiii*i+t

12.证明:

充分性：当前文法下的每••符号串仅有一个句柄和一个句柄产生式T对当前符号

串有唯一的最左归约T对每一步推导都有唯一的最右推导T有唯一的语法树。

必要性：有唯一的语法树T对每一步推导都有唯一的最右推导T对当前符号串有

唯••的最左归约T当前文法下的每一符号串仅有一个句柄和一个句柄产生式

13.化简下列各个文法

(1)解：S-bCACdAfcSA|cCCC-cS|c

(2)解：S—aAB|fAIgA~e|dDAD-eAB-f

(3)解：S—ac

14.消除下列文法中的£产生式

(1)解：S-aAS|aSbA-*cS

(2)解：S-aAAaAaA—bAc|be|dAe|de

15.消除下列文法中的无用产生式和单产生式

(1)消除后的产生式如下：

S-aB|BC

B—DB|b

C-b

D-*b|DB

(2)消除后的产生式如下：

S-SA|SB|()I(S)i[][S]

A-()|(S)||[S]

Ba[]|[S]

(3)消除后的产生式如下：

E-E+T|T*F|(E)|PfF|i

T~T*F|(E)|PfF|i

FTtF(E)|i

P-(E)|i

第三章习题解答

3假设W:表示载狐狸过河，G:表示载山羊过河，C:表示载白菜过河

用到的状态1：狐狸和山羊在左岸2：狐狸和白菜载左岸3:羊和白菜在左岸4:

狐狸和山羊在右岸5:狐狸和白菜在右岸6:山羊和白菜在右岸F:全在右岸

4证明：只须证明文法G:A-aB或A-a(A,BGVN,aCVT+)

等价于Gl:A-aB或A-a(a£VT+)

・G1的产生式中A-aB,则B也有B-bC,C-cD….

所以有A-abc…B',a,b,c…GVT,B'eVN

所以与G等价。

2)G的产生式A-aB,aGVT+,因为a是字符串，所以肯定存在着一个终结符

a,使AfaB

可见两者等价，所以由此文法产生的语言是正规语言。

6根据文法知其产生的语言是

L={ambncim,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-OA,B—1C,C-1IF,C-*lOA,F-0|0E1A,D-0B|IC,E-ICOB

(2)最短输入申Oil

(3)任意接受的四个串

011,0110,0011,000011

(4)任意以1打头的串.

8从略。

9

(1)写出向应的状态转换图

(2)相应的3型文法

(i)S-aAS-*bSA->aAA-*bBB-aaBB-b|bB

(ii)S-aA|aS-bBB-aBbBAfaBAfb|bA

(iii)S-aAS-bBA-bAA-*aCB-aBB-bCC-*a|aCC-bbC

(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,DfC,B-Db,C—Be,B—Ab,B-e,A—a

G2等价的右线性文法：

SfdD,S—aB,DfC,BfabC,B—bB,B-bA,B-£,C-cA,A~a

(3)对G1文法,abb的推导序列是：

S=>aA=>abB=>abb

对文法，abb的推导序列是：

S=>Bb=>Abb=>abb

对G2文法，aabca的推导序列是：

S=>Aa=>Cca=>Babca=>aabca

对G2'文法，aabca的推导序列是：

S=>aB=>aabC=>aabcA=>aabca

(4)对串aebd来说，Gl.Gr文法都不能产生。

11将右线性文法化为左线性文法的算法：

(1)对于G中每一个形如A-aB的产生式且A是开始符，将其变

为B—a,否则若A不是开始符，B-Aa;

(2)对于G中每一个形如A-a的产生式,将其变为S-Aa

12(1)

a

s(S.A)

A{&B}-

B{B}力

状态矩阵是：

记[S]=qO[B]=ql[AB]=q2[SA]=q3，最小化和确定化后如图

(2)记[S]=qO,[A]=ql,[BS]=q2最小化和确定化后的状态转换图如下

13(1)将具有e动作的NFA确定化后，其状态转换图如图:

记{S0,Sl,S3}=q0{Sl}=ql{S2S3}=q2{S3}=q3

(2)记{S}=qO{Z)=ql{UR)=q2{SX}=q3{YUR}=q4{XSU}=q5{YURZ}=q6

{ZS}=q7

14(1)从略

(2)化简后SO和SI作为一个状态，S5和S6作为一个状态。

状态转换图如图

15从略。

16从略。

•(1)r*表示的正规式集是{£,r,rr,rrr,…}

(£|r)*表示的正规式集是{£,ee,•••}U{r,rr,rrr,•••}={e,r,rr,rrr,­••}

£Irr*表示的正规式集是{e,r,rr,rrr,…

(r*)*=r*={e,r,rr,rrr,,••)

所以四者是等价的。

(2)(rs)*i•表示的正规式集是{£,rs,rsrs,rsrsrs,…}r

={r,rsr,rsrsr,rsrsrsr,••,}

r(sr)*表示的正规式集是r{e,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*c

S=a*ab*bc*c

・Gl:

S=aA+B(l)

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)把它打入⑴得

S=a(abS+b(cb)*(cd|b))+(cb)*(cd|b)

=aabS+ab(cb)*(cd|b)+(cb)*(cdb)

=(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*abbA=(ab*abb)c+ab*b

S=(ab*ab)b)ca+ab*ba+ab*

=(ab*abb)caab*ba|ab*

20

・识别此语言的正规式是S='LABEL'd(d|,d)*;

•从略。

21从略。

22构造NFA

其余从略。

23下面举一个能够识别1,2,3,10,20,100的例子，读者可以推而广之。

%(

ttinclude<stdio.h>

Sinclude<string.h>

#include<ctype.h>

#defineONI

#defineTW2

#defineTHRE3

#defineTE10

#defineTWENT20

#defineHUNDRE100

#defineWHITE9999

%)

upper[A-Z]

%%

ONEreturnON;

TWOreturnTW;

THREEreturnTHRE;

TENreturnTE;

TWENTYreturnTWENT;

HUNDREDreturnHUNDRE;

""+|\treturnWHITE;

\nreturnO;

%%

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[l]);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;

)

}Awhile*/

label:printf(〃%d\n〃，i);

return;

)

24(1)Dn表示的正规集是长度为2n任意a和b组成的字符串。

・此正规式的长度是2n

・用来识别Dn的DFA至多需要2n+l个状态。

25从略。

26(1)由{}括住的，中间由任意个非{组成的字符串,如{},{}},{a},{defg}等等。

(2)匹配一行仅由一个大写字母和一个数字组成的串，如A1,F8,Z2等。

(3)识别\r\n和除数字字符外的任何字符。

・由'和'括住的，中间由两个''或者非'和\n组成的任意次的字符串。

如‘'''，'a',‘bb','def'等等

270[Xx][0-9]*[a-fA-F]*|[0-9]+1(\'([a-zA-Z]I\\[Xx][0-7][0-7a-fA-F]I\\

,

0[01][0-7H0-7]|\\[a-Z])\)

28~[a-zA-Z_]+[0-9]*[a-zA-Zj*

29参考程序如下：

%(

ttinclude<stdio.h>

ttinclude<string.h>

#include<ctype.h>

#defineUPPER2

#defineWHITE3

%)

upper[A-Z]

%%

{upper}+returnUPPER;

\t|，zz，+returnWHITE;

%%

main(intargc,char*argv[])

(

intc,i;

if(argc==2)

(

if((yyin=fopen(argv[l],"r"))==NULL)

(

printf("can'topen%s\nzz,argv[l]);exit(0);

)

)

while((c=yylex())!=EOF)

if(c==2)

for(i=O;yytext[i];i++)

printf(z/%cz，,tolower(yytext[i]));

yytext[0]='\000';

)

if(c==3)

printfC〃)；

elseprintf(z/%s，z,yytext);

)

return;

)

yywrap()

!

return;

)

30从略。

第四章习题解答

第四章习题参考答案

•1.解：

(1)S-*(S)Z21()Z21[S]Z31[]Z31

A-(S)Z22|()Z22|[S]Z32|[]Z32

B-*(S)Z23|()Z23|[S]Z33|[]Z33

Zll—e|AZ11|BZ21

Z12fAz121BZ22Z13-*AZ13|BZ23

Z21-Z11Z22-e|Z12

Z23fzl3Z31fz21

Z32fz22Z33-e|Z23

(2)S-*bZll|aZ21A-*bZ12|aZ22

Z11-*e|AZ21Z12-AZ22Z21fsz21Z22-£|SZ22

(3)S-(T)Z11aZllZ11S-(T)Z12|aZ12Z12

Zll-eIZ21Z12-Z22Z21-,SZ21Z22-e|,SZ22

・2.解：

SnAbBl,L1(表示第1步，用产生式1.1推导，以下同)

=CAbbB2,2.1

=edAbbB3,4.1

=>edCAbbB4,2.1

=ededAbbbB5,4.1

=edaAbbbB5,4.2(不符合，改写第5步，用4.2)

=edBfbbB4,2.2

=edCSdfbbB5,3.1

=ededSdfbbB6,4.1

=>edaSdfbbB6,4.2

=eddfbbB5,3.2

=>eddfbbCSd6,3.1

=eddfbbedSd7,4.1

^eddfbbaSd7,4.2

=>eddfbbd6,3.2

•3.解：以下Save表示savetoken_pointervalue,Restore表示restore

token_pointervalue。

(1)文法没有左递归。

FunctionP:boolean;

Begin

Save;

P:=true;

Ifnext_token=begin”then

Ifnext_token=,d'then

Ifnext_token=,then

IfXthen

Ifnext_token=nend"thenreturn;

Restore;

P:=false;

End;

FunctionX:boolean;

Begin

Save;

X:=true;

Ifnext_token=,d'then

Ifnext_token=,then

IfXthenreturn;

Restore;

Ifnext_token=,s'then

IfYthenreturn;

Restore;

X:=false;

End;

FunctionY:boolean;

Begin

Save;

Y=true;

Ifnext_token=,then

Ifnext_token=,s'then

IfYthenreturn;

Restore;

End;

(2)消去文法左递归，并记为：

PfbeginSendSfA；CAfV:=ECfifEthenS

E->VE'E'f+VE'|eV->I

FunctionP:boolean;

Begin

Save;

P:=true;

Ifnext_token=vbegin”then

IfSthen

Ifnext_token=wend"thenreturn;;

Restore;

P:=false;

End;

FunctionA:boolean;

Beign

Save;

A:=true;

IfVthen

Ifnext_token=vthen

IfEthenreturn;

Restore;

A:=flase;

End;

FunctionS:boolean;

Beign

Save;

S:=true;

IfAthenreturn;

Restore;

IfCthenreturn;

Restore;

S:=false;

End;

FunctionC:boolean;

Begin

Save;

C:=true;

Ifnext_token=“if“then

IfEthen

Ifnext_token二“then”then

IfSthenreturn;

Restore;

C:=false;

End;

FunctionE:boolean;

Begin

Save;

E:=true;

IfVthen

IfEpthenreturn;

Restore;

E:=false;

End;

FunctionEp:boolean;

Being

Save;

Ep:=true;

Ifnext_token=,+'then

IfVthen

IfE'thenreturn;

Return;

End;

•4.解:

dFIRST集”FOLLOW集。

S—aAB*，

{#}"

f£V(少

A—aAbr

(即

—EC｛少

B-M

—g/｛桃

・5.证：因为是左递归文法，所以必存在左递归的非终结符A,及形如A-

aB的产生式，且aT*Ad.

则first(Ad)Cfirst(B)W@,从而

first(a)Cfirst(B)¥小，即文法不满足LL(1)文法条件。得证。

・6.证：LL(1)文法的分析句子过程的每一步，永远只有唯一的分析动作

可进行。现在，假设LL(1)文法G是二义性文法，则存在句子a,它有两

个不同的语法树。即存在着句子a有两个不同的最左推导。从而可知，用

LL(1)方法进行句子a的分析过程中的某步中，存在两种不同的产生式

替换，且均能正确进行语法分析，即LL(1)分析动作存在不确定性。与

LL(1)性质矛盾。所以，G不是LL(1)文法。

・7.解：

(1)D产生式两个候选式fD和f的first集交集不为空，所以不是LL(1)的。

(2)此文法具有左递归性，据第5题结论，不是LL(1)的。

・8.解：

(1)消除左递归性，得：

S-*bZll|aZ21A->bZ12|aZ22Zll-*bZll|eZ12-*bZ12

Z21-bZl11aZ21Z22-*bZ12|aZ221e

消除无用产生式得：S-*bZll|aZ21Zll-*bZU|eZ21fbz11|aZ21

此文法已满足LL(1)文法的三个条件，

所以G'[S]:S-bZU|aZ21Zll-bZll|eZ21-*bZll|aZ21

(2)G'文法的各非终结符的FIRST集和FOLLOW集:

产生式FIRST集FOLLOW集

S—bZll{b}{#}

-aZ21{a}

Zll-bZll{b}{#}

-*e{£}

Z21fbz11{b}闾

—aZ21{a}

LL⑴分析表为：

ab#

SaZ21bZll

ZllbZlle

Z21aZ21bZll

•9.解：

(1)

产生式first集follow集

S—SaB{b}

{札a,c}

-bB{b}

A-S{b}

{c}

fa{a}

B-*Ac{a,b}{札a,c}

(2)将S-SaBbB改写为S、bBS',S'-aBS'I3,可验证，新文法是LL⑴

的。

・10.解：

•1)为方便书写，记：〈布尔表达式>为人，〈布尔因子》为B,〈布尔二次量》

为C,〈布尔初等量>为口，原文法可以简化为：

A-AVB|BB-BAC|CC-1DDD-*(A)|true|false,

显然，文法含有左递归，消去后等价LL(1)文法为：

A-BA'A'-VBA'SB~CB',

B'fACB'|3C--|DDD—(A)true]false

⑵略

・证：若LL(1)文法G有形如B-aAAb的产生式，且AT+e及AT*ag,根据

FIRST集FOLLOW集的构造算法可知，FIRST(A)中一切非e力「至I」FOLLOW(A)

由则aWFOLLOW(A)；又因为aSFIRST(ag),所以两集合相交非空,因此,

G不是LL(1)文法；与前提矛盾，假设不成立，得证。

•解：

(1)

SA(a)b

S==

A=<=<

(==«<

<

a>=<»

>

)>»»

b»

不是简单优先文法。

SRT()Aa,

S>=

R

T>

(<=«<<

)>>

A>>

a>>

,<=<<<

是简单优先文法。

SR(a,)

S=«

R»

(=«

a»

,=«

)»

是简单优先文法。

o首先消去无用产生式ZfE,Z-E+T

SZT#i()

S

Z==

T>>

#=<«

I>>

(=<«

)>>

化简后的文法是简单优先文法；

•解：

SA/A

S>>

A=<=

<

/>>

a>>

A和/之间同时有关系=和〈,所以不是简单优先文法；

・提示：分析教材中给出的算法，选择一种合适的表示给定文法的方法(尽

量简单)，使得对文法的输入比较简单的同时一(需要把输入转化为计算机

语言表示，这种转化应该尽量简单)，能够比较简单地构造3个基本关系

矩阵(=,LEAD和LAST)。

•证明：设xjxj+1...xi是湎足条件xj-Kxj=xj+l=...=xi＞xi+l的最左子

串。由=关系的定义，可知xjxj+1...xi必出现在某产生式的右部中。又

因xj-Kxj可知xj-1与xj不处于同一产生式，且xj是某右部的首符。

同理,xi为某产生式的尾符号。即存在产生式U-xjxj+L..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|bc

其全部简单优先关系是：

DWTLa:;,ir|n|b|c

D

W

T

L>=

a=<<

<

>>>=

i

r|nib|c>

是简单优先文法。

・丽设STna,我们对n用归纳法，证明a不含两个非终结符相邻情况。n=l

时，STa,即S~a是文法的产生式，根据定义，它不含上述情况。设n=k

时，上述结论成立，且设STkdAb,由归纳假设，A两侧必为终结符。我们

再进行一步推导，得STkdAbTdub,其中，A-u是文法中的产生式，由定

义，u中不含两个非终结符相邻情况，从而dub两个非终结符相邻情况。

得证。

・证：由于G不是算符文法，G中至少有一个产生式，其右部含有两个非终

结符相邻的情况。不失一般性，设其形为U-xABy,x,y@V*,由于文法不

含无用产生式，则必存在含有U的句型dUb,即存在推导ST*dUbTdxAB优.

得证。

・文法为：E-*EtAAA-A*TA/TTT-T+VT-VVV-*i।（E）

•解：

（1）构造算符优先矩阵:

-*()i#

»<><>

«

>

*><><

<

(«<=<

)»>>

I»>>

#«<<

(2)在(-,-)、(-,*)和(*,-)处有多重定义元素，不是算符优先文法；

(3)改写方法：

・将E-E-T中的减号与F—P中的赋值运算符强制规定优先关系；

・或者将F-P中的赋值运算符改为别的符号来表示；

•(1)证明：由设句型a=3Ua…中含a的短语不含U,即存在A,A=>*ay,

则a可归约为a="Ua…U*…UA3=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是素短语，其中l〈x或者y〈n之一成立。因素短语是短

语，根据短语定义，则必有：l〈xTbxT〈bx或y〈nTby>by+l,与bxT=bx

及by=by+l矛盾，得证。

・提示：根据27题的结论，只要证u是句型a的短语，根据=关系的定义容

易知道u是句型a的素短语。

•证：与28题的不同点只是aO,an+1可以是‘#'，不影响结论。

・证：设不能含有素短语，则只能是含有短语(不能含有终结符号)，则该

短语只能含有一个非终结符号，否则不符合算符文法定义，得证。

•解：

(1)算符优先矩阵:

+*t()i#

+>«<><>

*»<<><>

f»<<><>

(«<<=<

)»>>>

I»>>>

#«<<<

(2)用Floyd方法将优先矩阵线性化得到得的优先函数为：

+*tOi#

F3551771

G2466161

・解：用Floyd方法对已知的优先矩阵构造的优先函数为:

zbMLa()

fl567747

gl654667

•解：

(1)优先矩阵如下：

□a#

[>=

]>>

«

a<

»

#«<

（2）用Bell方法求优先函数的过程如下:

g5561

（3）显然，文法不是算符优先文法，所以不能线性化。

•略。

4—35解:

（1）识别全部活前缀的DFA如下：（以表格的形式来表示，很容易可以转化为

图的形式，本章中其余的题目也是采用这种形式表示。）

状态项目集经过的符号到达的状态

S'-•S

I■

a12

I14

S­•ab

S-aS•bb15

13

S-aS-c|H

14S-ab•

15S-aSb,

16S-*aSc•

（2）识别全部活前缀的DFA如下:

状态项目集经过的符号到达的状态

B-*cc•B

BIll

A-*c,A

I■

B-*•ccB

110A-*cA•

IllB-ccB•

所求的LR(0)项目规范族C={I0,n,…，Hl}

(3)

状态项目集经过的符号到达的状态

13

sII

I曲

bIf

道

17S-aSSS•

⑷

状态项目集经过的符号到达的状态

S'一.s

SII

A-**ci

ns'

S-A•

b14

S—A•b

13A-a•

14S~*Ab•

»解:

(1)是LR(O)文法,其SLR(l)分析表如下：FOLLOW(S)={#>b,c}

FOLLOW(S)=FOLLOW(A)=FOLLOW(B)=[#}

(3)是LR(O)文法,其SLR(l)分析表如下:FOLLOW(S)={#,a,b,c}

(4)因为12中含有冲突项目,所以不是LR(0)文法,其SLR(l)分析表如卜：

FOLLOW(S)={#}n{b}=6(所以可以用SLR(l)规则解决冲突)，FOLLOW(A)={b,#}

项目集经过的符号到达的状态

9R3R3R3R3®

可见是LR(O)文法。

4—38解:

(1)

状态项目集经过的符号到达的状态

S'一•S

SII

10Sf,Sab

b12

S一•bR

11S'—S•acc

a

(冲突项目)SfS,ab13

S-b•R

R14

R-・S

S15

12R-*•a

a16

S—,Sab

b12

S一•bR

13S-*Sa,bb17

14SfbR-r2

R—S-

15a13

S-*S•ab

16R-a.

17SfSab,

项目II,15同时具有移进和归约项目，对于I5={R-S・，S-

S«ab},follow(R)={a},follow(R)S{a}={a},所以SLR(l)规则不能解决冲突,

从而该文法不是SLR(1)文法。

(2)

状态项目集经过的符号到达的状态

S'-・SSII

10S一•aSABa12

S-•BAB13

B~•bb14

IlS'-S・

S—a•SABS15

S-*•aSABa12

12

Sf•BAB13

B-*•bb14

S-*B•AA16

卜一,aAa17

13

A-*•BB18

B-•bb14

14B-b•r5

S-aS,ABA19

A—,aAa17

15

A—•BB18

B-*•bb14

16S-*BA•r2

A-*a,AA110

A一•BB18

17

A—,aAa17

B-・bb14

18A~B•r4

S—aSA,BBIll

19

B~・bb14

IIOAfaA•r3

IllS-aSAB•rl

不存在冲突项目，故该文法是LR(O)文法，也是SLR(l)文法。

SLR(1)分析表如卜:

ACTIONGOTO

ab#SAB

0S2S413

1ACC

2S2S453

3S7S468

4R5R5R5

5S7S498

6R2R2R2

7S7S4108

8R4R4R4

9S411

10R3R3R3

11R1R1R1

(3)先求识别全部活前缀的DFA：

状态项目集经过的符号到达的状态

S'一•s

sII

S一•aSb

10a12

Sf•bSa

b13

Sf•ab

IIS'—S'acc

Sfa-Sb

Sfa•bS14

12S一•aSbb15

Sf•bSaa12

S—•ab

S—b•Sa

S16

S-**aSb

13a12

S—•bSa

b13

Sf•ab

14SfaS•bb17

15Sfab•r3

16S—bS•aa18

17SfaSb•rl

18S-bSa•r2

不存在冲突项目，故该文法是LR(O)文法，也是SLR(l)文法。

SLR(1)分析表如下：

ACTIONGOTO

ab#S

0S2S31

1ACC

2S2S54

3S2S36

4S7

5R3R3R3

6S8

7R1R1RI

8R2R2R2

（4）先求识别全部活前缀的DFA：

状态项目集：经过的符号到达的状态

S'--SSII

10S—,aAa12

S-*•bBb13

IIS'-S•ICC

S-*a,A14

12A

A—,cAd15

（冲突）c

A一•r4

S-b•B16

13B

B—,cBdd17

（冲突）c

B一•r6

14S-*aA,rl

A-*c,Ad18

15A

A—,cAd15

（冲突）c

A一•r4

16S-bB•r2

17B-*c,BddB19

(冲突)Bfc•Bddc17

B-•r6

18A-*cA•dd110

19BfcB•dddIll

110A—cAd•r3

IllB—cBd•dd112

112B—cBdd•r5

因为follow(A)=follow(B)={#,d},所以冲突项目12,13,15,17可以用SLR⑴规

则得以解决，从而该文法为SLR(1)文法。其SLR(1)分析表如下：

11S12

12R5R5

(5)解:原文法等价化为qlfq2,qlfq3,q2fq4;q5,q4-beginD,q4-q4;D,

q5—Send,q5-*S;q5,q3—beginq5,

先求识别全部活前缀的DFA：

状态项目集经过的符号到达的状态

qP一•ql

qlII

qi-•q2

q212