《編譯原理》西北工業(yè)大學第三版課后答案1

第一章習題解答

1.解：源程序是指以某種程序設計語言所編寫的程序。目標程序是指編譯程

序（或解釋程序）將源程序處理加工而得的另一種語言（目標語言）的程

序。翻譯程序是將某種語言翻譯成另一種語言的程序的統(tǒng)稱。編譯程序與

解釋程序均為翻譯程序，但二者工作方法不同。解釋程序的特點是并不先

將高級語言程序全部翻譯成機器代碼，而是每讀入一條高級語言程序語

句，就用解釋程序?qū)⑵浞g成一段機器指令并執(zhí)行之，然后再讀入下一條

語句繼續(xù)進行解釋、執(zhí)行，如此反復。即邊解釋邊執(zhí)行，翻譯所得的指令

序列并不保存。編譯程序的特點是先將高級語言程序翻譯成機器語言程

序，將其保存到指定的空間中，在用戶需要時再執(zhí)行之。即先翻譯、后執(zhí)

行。

2.解：一般說來，編譯程序主要由詞法分析程序、語法分析程序、語義分析

程序、中間代碼生成程序、代碼優(yōu)化程序、目標代碼生成程序、信息表管

理程序、錯誤檢查處理程序組成。

3.解：C語言的關(guān)鍵字有：autobreakcasecharconstcontinue

defaultdodoubleelseenumexternfloatforgotoifintlong

registerreturnshortsignedsizeofstaticstructswitchtypedef

unionunsignedvoidvolatilewhile。上述關(guān)鍵字在C語言中均為保留

字。

4.解：C語言中括號有三種：｛｝，口，（）。其中，。用于語句括號；口用

于數(shù)組；（）用于函數(shù)（定義與調(diào)用）及表達式運算（改變運算順序）。

C語言中無END關(guān)鍵字。逗號在C語言中被視為分隔符和運算符，作為優(yōu)

先級最低的運算符，運算結(jié)果為逗號表達式最右側(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.構(gòu)造產(chǎn)生下列語言的文法

(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打頭的所有奇整數(shù)所組成的集合

解解(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)所有偶數(shù)個0和偶數(shù)個1所組成的符號串集合

解:對應文法為S-OA|lB|e,A->OS|ICB-*OCISCTA|0B

3.描述語言特點

(1)S—10S0S-aAA-bAAfa

解：本文法構(gòu)成的語言集為：L(G)={(10)nabma0n|n,m?0}。

(2)S-SSS-lAOAf1A0A—e

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

為零}該語言特點是：產(chǎn)生的句子中，0、1個數(shù)相同，并且若干相接的1后必然

緊接數(shù)量相同連續(xù)的0。

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

解:本文法構(gòu)成的語言集為：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

該語言特點是：產(chǎn)生的句子中，是以ba開頭de結(jié)尾的串，且ba、de個數(shù)相同。

(5)S-aSSS-a

解：L(G)={a(2nT)|n》l}可知:奇數(shù)個a

4.解：此文法產(chǎn)生的語言是：以終結(jié)符al、a2-an為運算對象，以A、V、

~為運算符，以［、］為分隔符的布爾表達式串

5.5.1解：由于此文法包含以下規(guī)則：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]中的句子

因為文法中的句子不可能以非終結(jié)符d結(jié)尾

(3)aacbccb不是文法G[S]中的句子

可知，aacbccb僅是文法G[S]的一個句型的一?部分，而不是一個句子。

(4)aacabcbcccaacdca不是文法G[S]中的句子

因為終結(jié)符d后必然要跟終結(jié)符a,所以不可能出現(xiàn)…de…這樣的句子。

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

由(1)可知：aacb可歸約為S,由文法的產(chǎn)生式規(guī)則可知，終結(jié)符c后不可能

跟非終結(jié)符S,所以不可能出現(xiàn)…caacb…這樣的句子。

8.證明：用歸納法于n,n=l時，結(jié)論顯然成立。設n=k時，對于a1a2...akT*b,

存在Bi：i=l,2,..,k,aiT*bi成立，現(xiàn)在設

a1a2…akak+lT*b,因文法是前后文無關(guān)的，所以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首符號為終結(jié)符時，B的首符號為非終結(jié)符。即

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

由題意可知：a=a3T…TA3'=6,由于文法是CFG,終結(jié)符a不可能被替換

空串或非終結(jié)符，因此假設有誤。得證；

（2）同（1）,假設：B的首符號為非終結(jié)符時，a首符號為終結(jié)符。即設：a

=as；p=A?*且a=a3T…TAs'=p,與（1）同理，得證。

10.證明：因為存在句子：abc,它對應有兩個語法樹（或最右推導）：

STABTAbcTabc

STDCTDcTabc

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

11.解：

（1）STABTAaSbTAacbTbAacbTbbAacbTbbaacb

上面推導中，下劃線部分為當前句型的句柄。對應的語法樹為:

全部的短語:

第??個a(al)是句子bbaacb相對于非終結(jié)符A(Al)(產(chǎn)生式A?a)的短語(直

接短語)；

blal是句子bbaacb相對于非終結(jié)符A2的短語；

b2blal是句子bbaacb相對于非終結(jié)符A3的短語；

c是句子bbaacb相對于非終結(jié)符S1(產(chǎn)生式S?c)的短語(直接短語)；

a2cb3是句子bbaacb相對于非終結(jié)符B的短語；

b2blala2cb3是句子bbaacb相對于非終結(jié)符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.證明:

充分性：當前文法下的每??符號串僅有一個句柄和一個句柄產(chǎn)生式T對當前符號

串有唯一的最左歸約T對每一步推導都有唯一的最右推導T有唯一的語法樹。

必要性：有唯一的語法樹T對每一步推導都有唯一的最右推導T對當前符號串有

唯??的最左歸約T當前文法下的每一符號串僅有一個句柄和一個句柄產(chǎn)生式

13.化簡下列各個文法

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

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

(3)解：S—ac

14.消除下列文法中的￡產(chǎn)生式

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

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

15.消除下列文法中的無用產(chǎn)生式和單產(chǎn)生式

(1)消除后的產(chǎn)生式如下：

S-aB|BC

B—DB|b

C-b

D-*b|DB

(2)消除后的產(chǎn)生式如下：

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

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

Ba[]|[S]

(3)消除后的產(chǎn)生式如下：

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

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

FTtF(E)|i

P-(E)|i

第三章習題解答

3假設W:表示載狐貍過河，G:表示載山羊過河，C:表示載白菜過河

用到的狀態(tài)1：狐貍和山羊在左岸2：狐貍和白菜載左岸3:羊和白菜在左岸4:

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

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

等價于Gl:A-aB或A-a(a￡VT+)

?G1的產(chǎn)生式中A-aB,則B也有B-bC,C-cD….

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

所以與G等價。

2)G的產(chǎn)生式A-aB,aGVT+,因為a是字符串，所以肯定存在著一個終結(jié)符

a,使AfaB

可見兩者等價，所以由此文法產(chǎn)生的語言是正規(guī)語言。

6根據(jù)文法知其產(chǎn)生的語言是

L={ambncim,n,i=1}

可以構(gòu)造如下的文法VN={S,A,B,C},VT={a,b,c}

P={S-*aA,A-*aA,A—bB,B-bB,B-cC,C-*cC,C-c}

其狀態(tài)轉(zhuǎn)換圖如下：

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)寫出向應的狀態(tài)轉(zhuǎn)換圖

(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所組成的任

意串結(jié)尾或者

以b打頭，中間有任意個(包括0)a,再跟b,最后由一個a,b所組成的任意串結(jié)

尾

(iv)以任意個(包括0)b開頭，中間跟aa最后由一個a,b所組成的任意串結(jié)尾

或者

以任意個(包括0)b開頭，中間跟ab后再接任意(包括0)a再接b,最后由

一個a,b所組成的任意串結(jié)尾

10(1)G1的狀態(tài)轉(zhuǎn)換圖：

G2的狀態(tài)轉(zhuǎn)換圖:

(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)對串a(chǎn)ebd來說，Gl.Gr文法都不能產(chǎn)生。

11將右線性文法化為左線性文法的算法：

(1)對于G中每一個形如A-aB的產(chǎn)生式且A是開始符，將其變

為B—a,否則若A不是開始符，B-Aa;

(2)對于G中每一個形如A-a的產(chǎn)生式,將其變?yōu)镾-Aa

12(1)

a

s(S.A)

A{&B}-

B{B}力

狀態(tài)矩陣是：

記[S]=qO[B]=ql[AB]=q2[SA]=q3，最小化和確定化后如圖

(2)記[S]=qO,[A]=ql,[BS]=q2最小化和確定化后的狀態(tài)轉(zhuǎn)換圖如下

13(1)將具有e動作的NFA確定化后，其狀態(tài)轉(zhuǎn)換圖如圖:

記{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作為一個狀態(tài)，S5和S6作為一個狀態(tài)。

狀態(tài)轉(zhuǎn)換圖如圖

15從略。

16從略。

?(1)r*表示的正規(guī)式集是{￡,r,rr,rrr,…}

(￡|r)*表示的正規(guī)式集是{￡,ee,???}U{r,rr,rrr,???}={e,r,rr,rrr,-??}

￡Irr*表示的正規(guī)式集是{e,r,rr,rrr,…

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

所以四者是等價的。

(2)(rs)*i?表示的正規(guī)式集是{￡,rs,rsrs,rsrsrs,…}r

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

r(sr)*表示的正規(guī)式集是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

?識別此語言的正規(guī)式是S='LABEL'd(d|,d)*;

?從略。

21從略。

22構(gòu)造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表示的正規(guī)集是長度為2n任意a和b組成的字符串。

?此正規(guī)式的長度是2n

?用來識別Dn的DFA至多需要2n+l個狀態(tài)。

25從略。

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

(2)匹配一行僅由一個大寫字母和一個數(shù)字組成的串，如A1,F8,Z2等。

(3)識別\r\n和除數(shù)字字符外的任何字符。

?由'和'括住的，中間由兩個''或者非'和\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步，用產(chǎn)生式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.證：因為是左遞歸文法，所以必存在左遞歸的非終結(jié)符A,及形如A-

aB的產(chǎn)生式，且aT*Ad.

則first(Ad)Cfirst(B)W@,從而

first(a)Cfirst(B)￥小，即文法不滿足LL(1)文法條件。得證。

?6.證：LL(1)文法的分析句子過程的每一步，永遠只有唯一的分析動作

可進行。現(xiàn)在，假設LL(1)文法G是二義性文法，則存在句子a,它有兩

個不同的語法樹。即存在著句子a有兩個不同的最左推導。從而可知，用

LL(1)方法進行句子a的分析過程中的某步中，存在兩種不同的產(chǎn)生式

替換，且均能正確進行語法分析，即LL(1)分析動作存在不確定性。與

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

?7.解：

(1)D產(chǎn)生式兩個候選式fD和f的first集交集不為空，所以不是LL(1)的。

(2)此文法具有左遞歸性，據(jù)第5題結(jié)論，不是LL(1)的。

?8.解：

(1)消除左遞歸性，得：

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

Z21-bZl11aZ21Z22-*bZ12|aZ221e

消除無用產(chǎn)生式得：S-*bZll|aZ21Zll-*bZU|eZ21fbz11|aZ21

此文法已滿足LL(1)文法的三個條件，

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

(2)G'文法的各非終結(jié)符的FIRST集和FOLLOW集:

產(chǎn)生式FIRST集FOLLOW集

S—bZll{#}

-aZ21{a}

Zll-bZll{#}

-*e{￡}

Z21fbz11閭

—aZ21{a}

LL⑴分析表為：

ab#

SaZ21bZll

ZllbZlle

Z21aZ21bZll

?9.解：

(1)

產(chǎn)生式first集follow集

S—SaB

{札a,c}

-bB

A-S

{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的產(chǎn)生式，且AT+e及AT*ag,根據(jù)

FIRST集FOLLOW集的構(gòu)造算法可知，F(xiàn)IRST(A)中一切非e力「至I」FOLLOW(A)

由則aWFOLLOW(A)；又因為aSFIRST(ag),所以兩集合相交非空,因此,

G不是LL(1)文法；與前提矛盾，假設不成立，得證。

?解：

(1)

SA(a)b

S==

A=<=<

(==?<

<

a>=<?

>

)>??

b?

不是簡單優(yōu)先文法。

SRT()Aa,

S>=

R

T>

(<=?<<

)>>

A>>

a>>

,<=<<<

是簡單優(yōu)先文法。

SR(a,)

S=?

R?

(=?

a?

,=?

)?

是簡單優(yōu)先文法。

o首先消去無用產(chǎn)生式ZfE,Z-E+T

SZT#i()

S

Z==

T>>

#=<?

I>>

(=<?

)>>

化簡后的文法是簡單優(yōu)先文法；

?解：

SA/A

S>>

A=<=

<

/>>

a>>

A和/之間同時有關(guān)系=和〈,所以不是簡單優(yōu)先文法；

?提示：分析教材中給出的算法，選擇一種合適的表示給定文法的方法(盡

量簡單)，使得對文法的輸入比較簡單的同時一(需要把輸入轉(zhuǎn)化為計算機

語言表示，這種轉(zhuǎn)化應該盡量簡單)，能夠比較簡單地構(gòu)造3個基本關(guān)系

矩陣(=,LEAD和LAST)。

?證明：設xjxj+1...xi是湎足條件xj-Kxj=xj+l=...=xi＞xi+l的最左子

串。由=關(guān)系的定義，可知xjxj+1...xi必出現(xiàn)在某產(chǎn)生式的右部中。又

因xj-Kxj可知xj-1與xj不處于同一產(chǎn)生式，且xj是某右部的首符。

同理,xi為某產(chǎn)生式的尾符號。即存在產(chǎn)生式U-xjxj+L..xi設ST*aUb

其中，aT*...xj-1,bT*xi+1...對于aUb可構(gòu)造一語法樹，并通過對

其剪枝（歸約），直到U出現(xiàn)在句柄中。從而xjxj+1...xi必為句柄。反

之，若xjxj+1...xi是句柄，由簡單優(yōu)先關(guān)系的定義，必滿足上述條件。

?解：為描述方便，用符號表示各非終結(jié)符：D=＜變量說明＞,L=＜變量表＞，V=

〈變量〉,T=＜類型＞，a=VAR,則消去V,并采用分層法改寫文法，得到：D一

aW:T;W-LL-L,i|iT->r|n|bc

其全部簡單優(yōu)先關(guān)系是：

DWTLa:;,ir|n|b|c

D

W

T

L>=

a=<<

<

>>>=

i

r|nib|c>

是簡單優(yōu)先文法。

?麗設STna,我們對n用歸納法，證明a不含兩個非終結(jié)符相鄰情況。n=l

時，STa,即S~a是文法的產(chǎn)生式，根據(jù)定義，它不含上述情況。設n=k

時，上述結(jié)論成立，且設STkdAb,由歸納假設，A兩側(cè)必為終結(jié)符。我們

再進行一步推導，得STkdAbTdub,其中，A-u是文法中的產(chǎn)生式，由定

義，u中不含兩個非終結(jié)符相鄰情況，從而dub兩個非終結(jié)符相鄰情況。

得證。

?證：由于G不是算符文法，G中至少有一個產(chǎn)生式，其右部含有兩個非終

結(jié)符相鄰的情況。不失一般性，設其形為U-xABy,x,y@V*,由于文法不

含無用產(chǎn)生式，則必存在含有U的句型dUb,即存在推導ST*dUbTdxAB優(yōu).

得證。

?文法為：E-*EtAAA-A*TA/TTT-T+VT-VVV-*i?（E）

?解：

（1）構(gòu)造算符優(yōu)先矩陣:

-*()i#

?<><>

?

>

*><><

<

(?<=<

)?>>

I?>>

#?<<

(2)在(-,-)、(-,*)和(*,-)處有多重定義元素，不是算符優(yōu)先文法；

(3)改寫方法：

?將E-E-T中的減號與F—P中的賦值運算符強制規(guī)定優(yōu)先關(guān)系；

?或者將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同時位于同一產(chǎn)生式的右部，所以a=b,

與G是算符優(yōu)先文法(=與〈不能并存)矛盾。

(2)、(3)類似可證。

?證：只要證u中不含有除自身以外的素短語。設有這樣的素短語存在，即

存在bx???by是素短語，其中l(wèi)〈x或者y〈n之一成立。因素短語是短

語，根據(jù)短語定義，則必有：l〈xTbxT〈bx或y〈nTby>by+l,與bxT=bx

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

?提示：根據(jù)27題的結(jié)論，只要證u是句型a的短語，根據(jù)=關(guān)系的定義容

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

?證：與28題的不同點只是aO,an+1可以是‘#'，不影響結(jié)論。

?證：設不能含有素短語，則只能是含有短語(不能含有終結(jié)符號)，則該

短語只能含有一個非終結(jié)符號，否則不符合算符文法定義，得證。

?解：

(1)算符優(yōu)先矩陣:

+*t()i#

+>?<><>

*?<<><>

f?<<><>

(?<<=<

)?>>>

I?>>>

#?<<<

(2)用Floyd方法將優(yōu)先矩陣線性化得到得的優(yōu)先函數(shù)為：

+*tOi#

F3551771

G2466161

?解：用Floyd方法對已知的優(yōu)先矩陣構(gòu)造的優(yōu)先函數(shù)為:

zbMLa()

fl567747

gl654667

?解：

(1)優(yōu)先矩陣如下：

□a#

[>=

]>>

?

a<

?

#?<

（2）用Bell方法求優(yōu)先函數(shù)的過程如下:

g5561

（3）顯然，文法不是算符優(yōu)先文法，所以不能線性化。

?略。

4—35解:

（1）識別全部活前綴的DFA如下：（以表格的形式來表示，很容易可以轉(zhuǎn)化為

圖的形式，本章中其余的題目也是采用這種形式表示。）

狀態(tài)項目集經(jīng)過的符號到達的狀態(tài)

S'-?S

I■

a12

I14

S-?ab

S-aS?bb15

13

S-aS-c|H

14S-ab?

15S-aSb,

16S-*aSc?

（2）識別全部活前綴的DFA如下:

狀態(tài)項目集經(jīng)過的符號到達的狀態(tài)

B-*cc?B

BIll

A-*c,A

I■

B-*?ccB

110A-*cA?

IllB-ccB?

所求的LR(0)項目規(guī)范族C={I0,n,…，Hl}

(3)

狀態(tài)項目集經(jīng)過的符號到達的狀態(tài)

13

sII

I曲

bIf

道

17S-aSSS?

⑷

狀態(tài)項目集經(jīng)過的符號到達的狀態(tài)

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=6(所以可以用SLR(l)規(guī)則解決沖突)，F(xiàn)OLLOW(A)={b,#}

項目集經(jīng)過的符號到達的狀態(tài)

9R3R3R3R3?

可見是LR(O)文法。

4—38解:

(1)

狀態(tài)項目集經(jīng)過的符號到達的狀態(tài)

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)規(guī)則不能解決沖突,

從而該文法不是SLR(1)文法。

(2)

狀態(tài)項目集經(jīng)過的符號到達的狀態(tài)

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：

狀態(tài)項目集經(jīng)過的符號到達的狀態(tài)

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：

狀態(tài)項目集：經(jīng)過的符號到達的狀態(tài)

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⑴規(guī)

則得以解決，從而該文法為SLR(1)文法。其SLR(1)分析表如下：

11S12

12R5R5

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

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

先求識別全部活前綴的DFA：

狀態(tài)項目集經(jīng)過的符號到達的狀態(tài)

qP一?ql

qlII

qi-?q2

q212