編譯原理課后答案(第三版蔣立源康慕寧編)

編譯原理課后答案（第三版蔣立源康慕寧編）

第一章習(xí)題解答

1解：源程序是指以某種程序設(shè)計語言所編寫的程序。目標(biāo)程序是指編譯程序（或解釋

程序）將源程序處理加工而得的另一種語言（目標(biāo)語言）的程序。翻譯程序是將某種語言翻

譯成另一種語言的程序的統(tǒng)稱。編譯程序與解釋程序均為翻譯程序，但二者工作方法不同。

解釋程序的特點是并不先將高級語言程序全部翻譯成機器代碼，而是每讀入一條高級語言程

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

解釋、執(zhí)行，如此反復(fù)。即邊解釋邊執(zhí)行，翻譯所得的指令序列并不保存。編譯程序的特點

是先將高級語言程序翻譯成機器語言程序，將其保存到指定的空間中，在用戶需要時再執(zhí)行

之。即先翻譯、后執(zhí)行。

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

代碼生成程序、代碼優(yōu)化程序、目標(biāo)代碼生成程序、信息表管理程序、錯誤檢查處理程序組

成。

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

enumexternfloatforgotoifintlongregisterreturnshortsignedsizeofstaticstructswitchtypedef

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

4解：C語言中括號有三種：｛｝,[],（）o其中，（｝用于語句括號；口用于數(shù)組；（）用

于函數(shù)（定義與調(diào)用）及表達式運算（改變運算順序）。C語言中無END關(guān)鍵字。逗號在C

語言中被視為分隔符和運算符，作為優(yōu)先級最低的運算符，運算結(jié)果為逗號表達式最右側(cè)子

表達式的值（如：（a,b,c,d）的值為d）。

5略

第二章習(xí)題解答

1.(1)答：26*26=676

(2)答：26*10=260

(3)答：{a,b,c,...,z,a0,al，…,a9,aa,...,az,...,zz,a00,a01,...,zzz},共26+26*36+26*36*36=34658

個

2.構(gòu)造產(chǎn)生下列語言的文法

(1){anbnlnNO}

解:對應(yīng)文法為G(S)=({S},{a,b},{S-elaSb},S)

(2){anbmcpln,m,p20}

解：對應(yīng)文法為G(S)=({S,X,Y},{a,b,c},{S-aSIX,XfbXIY,Y-cYle),S)

(3){an#bnln^O}U{cn#dnln^O}

解：對應(yīng)文法為G(S)=({S,X,Y},{a,b,c,d,#},{SfX,S-Y,XfaXbl#,YfcYdl#},S)

(4){w#wr#lw?{0,l}*,wr是w的逆序排列}

解:G(S)=({S,W,R),{O,1,#},{S^W#,W^OWOIlWil#},S)

(5)任何不是以0打頭的所有奇整數(shù)所組成的集合

解:G(S)=({S,A,B,l,J},{-,0,l,2,3,4,5,6,7,8,9},{SfJIIBJ,BfOBIIBIe,I—JI2I4I6I8,Ja

113151719),S)

(6)所有偶數(shù)個0和偶數(shù)個1所組成的符號串集合

解：對應(yīng)文法為S-*OAIlBle,A-OSI1CB^OCIISC-1AIOB

3.描述語言特點

(1)SflOSOSfaAAfbAAfa

解：本文法構(gòu)成的語言集為：L(G)={(lO)nabmaOnln,m?O}。

(2)SfSSSf1AOA—lAOAfe

解：L(G)={lnl0nlln20n2InmOnmInl,n2,…,nmNO；且nl,n2,…nm不全為零}該語言

特點是：產(chǎn)生的句子中，0、1個數(shù)相同，并且若干相接的1后必然緊接數(shù)量相同連續(xù)的0。

(3)S-*1AS-BOA-1AA-*CB-*BOB-*CC-1C0C-e

解：本文法構(gòu)成的語言集為：L(G)={1p1nOnlp>1,n>0}U{1nOnOqlq1,n0},特點是具

有IplnOn或InOnOq形式，進一步，可知其具有形式ln0mn,m20,且n+m>0。

(4)SfbAdcAfAGSGfeA-a

解：可知，S=>“=>baSndcn20

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

(5)SfaSSSfa

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

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

以卜］為分隔符的布爾表達式串

5.5.1解：由于此文法包含以下規(guī)則：AA—e,所以此文法是0型文法。

5.2證明：略

6.解：

（1）最左推導(dǎo)：

（程序＞T＜分程序＞T＜標(biāo)號＞：〈分程序〉TL：〈分程序〉

TL：＜標(biāo)號＞：＜分程序）

TL：L：〈分程序〉

TL：L：〈無標(biāo)號分程序〉

TL：L：〈分程序首部〉；〈復(fù)合尾部〉

TL：L：〈分程序首部〉；〈說明〉：〈復(fù)合尾部）

TL：L：beginc說明〉；〈說明〉；〈復(fù)合尾部〉

TL：L：begind；〈說明〉；〈復(fù)合尾部〉

TL：L：begind；d；〈復(fù)合尾部〉

TL：L：begind；d；＜語句＞；〈復(fù)合尾部〉

TL：L：begind；d；s；〈復(fù)合尾部.

TL：L：begind；d；s；＜語句〉end

TL：L：begind；d；s；send

最右推導(dǎo)：

〈程序＞T＜分程序＞T＜標(biāo)號＞：〈分程序〉

T〈標(biāo)號〉：〈標(biāo)號〉：〈分程序〉

T〈標(biāo)號〉：〈標(biāo)號〉：〈無標(biāo)號分程序〉

Tv標(biāo)號〉：〈標(biāo)號〉：〈分程序首部〉；〈復(fù)合尾部〉

Tv標(biāo)號＞：＜標(biāo)號》：〈分程序首部〉；〈語句〉；〈復(fù)合尾部〉

Tv標(biāo)號〉：〈標(biāo)號〉：〈分程序首部〉；〈語句〉；〈語句〉；end

T＜標(biāo)號＞：＜標(biāo)號＞：〈分程序首部〉；〈語句〉；s；end

Tv標(biāo)號＞：＜標(biāo)號＞：〈分程序首部〉；s；s；end

Tv標(biāo)號〉：〈標(biāo)號〉：〈分程序首部〉；說明；s；s；end

Tv標(biāo)號〉：〈標(biāo)號〉：〈分程序首部》;d；s；s；end

1＜標(biāo)號〉：〈標(biāo)號》：begin說明；d；s；s；end

Tv標(biāo)號〉：〈標(biāo)號〉:begind；d；s；s；end

Tv標(biāo)號〉：L：begind；d；s；s；end

TL：L：begind；d；s；s；end

(2)句子L：L：begind；d；s；send的相應(yīng)語法樹是:

7.解:

aacb是文法G[S]中的句子，相應(yīng)語法樹是:

最右推導(dǎo)：S=＞aAcB=＞aAcb=＞aacb

最左推導(dǎo)：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é)論顯然成立。設(shè)n=k時，對于a1a2...akT*b,存在Bi：

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

aIa2...akak+lT*b,因文法是前后文無關(guān)的，所以a1a2...ak可推導(dǎo)出b的一個前綴

b',ak+1可推導(dǎo)出b的一個后綴=b”（不妨稱為bk+1）。由歸納假設(shè)，對于b',存在Bi：

i=l,2,..,k,b'=B1B2...Bk,使得

aiT*bi成立，另外，我們有ak+lT*b"（=bk+1）。即n=k+l時亦成立。證畢。

9.證明：（1）用反證法。假設(shè)a首符號為終結(jié)符時，8的首符號為非終結(jié)符。即設(shè)：a=a3；

6=A3，月.a=>*0。

由題意可知：a=a3T…TA。，=B,由于文法是CFG,終結(jié)符a不可能被替換空串或非

終結(jié)符，因此假設(shè)有誤。得證；

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

3,且a=a3T…TA3'=6,與（1）同理，得證。

10.證明：因為存在句子：abc,它對應(yīng)有兩個語法樹（或最右推導(dǎo)）：

STABTAbeTabe

STDCTDcTabc

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

11.解:

（1）STABTAaSbTAacbTbAacbTbbAacbTbbaacb

上面推導(dǎo)中，下劃線部分為當(dāng)前句型的句柄。對應(yīng)的語法樹為:

全部的短語：

第一個231)是句子此222相對于非終結(jié)符人(人1)(產(chǎn)生式人?2)的短語(直接短語)；

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

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

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

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

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

注：符號的下標(biāo)是為了描述方便加上去的。

(2)句子(((b)a(a))(b))的最右推導(dǎo)：

ST(AS)T(A(b))T((SaA)(b))T((Sa(a))(b))

T(((b)a(a))(b))

相應(yīng)的語法樹是：

(3)解：iii*i+t對應(yīng)的語法樹略。

最右推導(dǎo)：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.證明：

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

的最左歸約T對每一步推導(dǎo)都有唯一的最右推導(dǎo)T有唯一的語法樹。

必要性：有唯一的語法樹T對每一步推導(dǎo)都有唯一的最右推導(dǎo)T對當(dāng)前符號串有唯一的最

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

13.化簡下列各個文法

⑴解：S-bCACdA-cSAIcCCC-cSIc

(2)解：S-aABIfAIgA-eIdDAD-eAB-*f

(3)解：S-ac

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

(1)解：S-aASIaSIbA-cS

⑵解:S-aAAIaAIaA-bAcIbeIdAelde

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

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

SfaBIBC

B-DBlb

C-b

D-bIDB

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

S-SAISBI()I(S)l[]I[S1

Af()l(S)l[]l[S]

Ba[]l[S]

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

E^E+TIT*FI(E)IPtFIi

TfT*FI(E)IPtFIi

F-PtFI(E)Ii

P-(E)Ii

第三章習(xí)題解答

1.從略

2.

3假設(shè)W:表示載狐貍過河，G:表示我山羊過河，C:表示載白菜過河

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

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

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

等價于GLAfaB或Afa(aGVT+)

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

所以有Afabb“B',a,b,b“GVT,B'eVN

所以與G等價。

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

faB

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

5

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

L={ambncilm,n,i=1}

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

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

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

7(1)其對應(yīng)的右線性文法是：

A-OD,B—OA,B-1C,C—WF,CfllOA,FfOlOEIlAQfOBIlC,Ef1CI0B

⑵最短輸入串Oil

(3)任意接受的四個串

011,0110,0011,000011

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

8從略。

9

(2)相應(yīng)的3型文法

(i)S-aAS-bSA-aAA-bBB-alaBB-blbB

(ii)S-aAlaS-bBB-aBIbBA-aBA-*blbA

(iii)S-aAS-bBA-bAA-aCB-aBB-bCC-alaCC-*blbC

(iv)S-bSS-aAA-aCA-bBB-aBB-bCC-alaCC-blbC

(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等價的左線性文法：

SfBb,SfDd,DfC,BfDb,C—Bc,BfAb,Bfe,Afa

G2等價的右線性文法：

SfdD,SfaB,DfC,BfabC,BfbB,BfbA,Bf￡,CfcA,Afa

(3)對G1文法,abb的推導(dǎo)序列是：

S=>aA=>abB=>abb

對Gl'文法,abb的推導(dǎo)序列是：

S=>Bb=>Abb=>abb

對G2文法，aabca的推導(dǎo)序列是：

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

對G2'文法，aabca的推導(dǎo)序列是：

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

(4)對串a(chǎn)cbd來說，G1,GT文法都不能產(chǎn)生。

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

(1)對于G中每一個形如A-aB的產(chǎn)生式且A是開始符，將其變?yōu)锽-a,否則若A不是

開始符，B-Aa;

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

12(1)

狀態(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)換圖如圖：

記{SO,Sl,S3}=qO{Sl}=ql{S2S3}=q2{S3}=q3

⑵記{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ī)式集是{e,r,rr,rrr,…}

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

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

(r*)*=r*={e,r,rr,nr,…}

所以四者是等價的。

(2)(rs)*r表示的正規(guī)式集是{￡,rs,rsrs,rsrsrs,…}r={r,rsr,rsrsr,rsrsrsr,…}

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

S=a*ab*bc*c

Gl:

S=aA+B⑴

B=cC+b(2)

A=abS+bB⑶

C=D(4)

D=bB+d(5)

把(4)(5)代入(2),得B=c(bB+d)+b=cbB+cd+b得B=(cb)*(cdlb),代入(3)得

A=abS+b(cb)*(cdlb)把它打入(1)得

S=a(abS+b(cb)*(cdlb))+(cb)*(cdlb)

=aabS+ab(cb)*(cdlb)+(cb)*(cdlb)

=(aab)*(ab(cb)*(cdlb)l(cb)*(cdlb))

G2:

S=Aa+B(1)

A=Cc+Bb(2)

B=Bb+a⑶

C=D+Bab(4)

D=d(5)

可得D=dB=ab*C=ab*ablbA=(ab*ablb)c+ab*b

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

=(ab*ablb)calab*balab*

20

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

從略。

21從略。

22構(gòu)造NFA

其余從略。

23下面舉一個能夠識別1,2,3/0,20,100的例子，讀者可以推而廣之。

%{

#include<stdio.h>

#include<string.h>

#include<ctype.h>

#defineON1

#defineTW2

#defineTHRE3

#defineTE10

#defineTWENT20

#defineHUNDRE100

#defineWHITE9999

%}

upper[A-Z]

%%

ONEreturnON;

TWOreturnTW;

THREEreturnTHRE;

TENretumTE;

TWENTYreturnTWENT;

HUNDREDreturnHUNDRE;

""4-l\tretumWHITE;

\nretumO;

%%

main(intargc,char*argv[])

(

intc,i=0;

chartmp[30];

if(argc==2)

if((yyin=fopen(argv[l],"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+=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(u%d\nH,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'Jdef',‘'''''等等

27O[Xx][0-9]*[a-fA-F]*l[0-9]+l(\,(fa-zA-Z]IW[Xx][0-7][0-7a-fA-F]l\\0[01][0-7][0-7]l\\[a-z])\,)

28A[a-zA-ZJ+[0-9]*[a-zA-ZJ*

29參考程序如下：

%{

#include<stdio.h>

#include<string.h>

#include<ctype.h>

#defineUPPER2

#defineWHITE3

%)

upper[A-Z]

%%

{upper}+returnUPPER;

\tln"+returnWHITE;

%%

main(intargc,char*argv[])

(

intc,i;

if(argc==2)

(

if((yyin=fopen(argv[1],nr*'))==NULL)

(

printfC'can^open%s\n",argvf1]);exit(0);

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

if(c==2)

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

printf(H%cH,tolower(yytext[i]));

yytext[0]=,\000';

)

if(c==3)

printf(nn);

elseprintf(n%su,yytext);

}

return;

)

yywrapO

(

return;

)

30從略。

第四章習(xí)題參考答案

1.解:

(1)S-(S)Z21I()Z21I[S]Z31l[]Z31

A-(S)Z22I()Z22I[S]Z32I[]Z32

B-*(S)Z23I()Z23I[S]Z33I[]Z33

ZU-eIAZ11IBZ21

Z12-AZ12IBZ22Z13-AZ13IBZ23

Z21-Z11Z22-￡IZ12

Z23fzi3Z31-Z21

Z32-Z22Z33fe|Z23

(2)SfbZlllaZ21A-bZ121az22

Zllf￡IAZ21Z12-AZ22Z21-SZ21Z22feISZ22

(3)S->(T)Z11laZllIZUS-(T)Z12laZ12IZ12

ZU-￡IZ21Z12->Z22Z21-,SZ21Z22-el,SZ22

2.解：

SAbBI』.l(表示第1步，用產(chǎn)生式1.1推導(dǎo)，以下同)

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表示restoretoken_pointervalue。

(1)文法沒有左遞歸。

FunctionP:boolean;

Begin

Save;

P:=true;

Ifnext_token=vbegin”then

Ifnext_token=?d'then

Ifnext_token=';'then

IfXthen

Ifnext_token="end“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)消去文法左遞歸，并記為：

P-beginSendS-AICA—V:=EC一ifEthenS

E-VE'E'-*+VE,HV-*I

FunctionP:boolean;

Begin

Save;

P:=true;

Ifnext_token="begin”then

IfSthen

Ifnext_token=end“thenreturn;;

Restore;

P:=false;

End;

FunctionA:boolean;

Beign

Save;

A:=true;

IfVthen

Ifnext_token=n:=wthen

IfEthenreturn;

Restore;

A:=flase;

End;

FunctionS:boolean;

Beign

Save;

S:=true;

IfAthenreturn;

Restore;

IfCthenreturn;

Restore;

S:=false;

End;

FunctionCiboolean;

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解:

5.證：因為是左遞歸文法，所以必存在左遞歸的非終結(jié)符A,及形如A-aIB的產(chǎn)生式，且

aT*Ad.

則first(Ad)Afirst(B)W6,從而

first(a)Cfirst(B)關(guān)6,即文法不滿足LL(1)文法條件。得證。

6.證：LL(1)文法的分析句子過程的每一步，永遠只有唯一的分析動作可進行?，F(xiàn)在，假

設(shè)LL(1)文法G是二義性文法，則存在句子a,它有兩個不同的語法樹。即存在著句子a有

兩個不同的最左推導(dǎo)。從而可知，用LLQ)方法進行句子a的分析過程中的某步中，存在

兩種不同的產(chǎn)生式替換，且均能正確進行語法分析，即1X(1)分析動作存在不確定性。與

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

7解:

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

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

8廨：

⑴消除左遞歸性，得：

S->bZlllaZ21A->bZ12laZ22Zll->bZllleZ12fbz12

Z21-bZ11laZ21Z22-bZ12laZ221e

消除無用產(chǎn)生式得：S-bZlllaZ21Zll-bZllleZ21-bZlllaZ21

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

所以G'[Sl：S-bZlllaZ21Zll^bZllleZ21-bZlllaZ21

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

產(chǎn)生式

FIRST集

FOLLOW集

SfbZll

faZ21

{a}

{#}

Zll-bZll

fE



{$}

{#}

Z21-bZll

faZ21



{a}

{#}

LL(1)分析表為：

a

b

#

s

aZ21

bZH

Zll

bZll

Z21

aZ21

bZll

9.解：

(1)

產(chǎn)生式

first集

follow集

S-SaB

—bB



{#,a,c}

A-S

fa

{a}

{c}

B-*Ac

{a,b}

{#,a,c}

⑵將S-SaBIbB改寫為S-bBS',S'-aBS'g,可驗證，新文法是LL(1)的。

10.解：

1)為方便書寫，記：〈布爾表達式＞為A,〈布爾因子〉為B,〈布爾二次量＞為C,〈布爾初

等量,為D,原文法可以簡化為：

A-AVBIBB-BACICC^nDIDD—(A)ItrueIfalse,

顯然，文法含有左遞歸，消去后等價LL(1)文法為：

AfBA'A'-VBA'|3B—CB',

B'fACB'|3Cf-iDIDD-(A)ltruelfalse

⑵略

證:若LL(1)文法G有形如B-aAAb的產(chǎn)生式,且AT+e及AT*ag,根據(jù)FIRST集FOLLOW

集的構(gòu)造算法可知，F(xiàn)IRST(A)中一切非e加到FOLLOW(A)中，則aEFOLLOW(A)；又因

為aGFIRST(ag),所以兩集合相交非空，因此，G不是LL(1)文法；與前提矛盾，假設(shè)不成立,

得證。

解：

(1)

S

A

(

a

)

b

S

A

<

<

<

<

<

a

>

<

>

<

>

>

)

>

>

>

>

>

b

>

>

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

(2)

S

R

T

(

)

A

a

S

R

T

>

<

<

<

<

<

)

>

>

A

>

>

a

>

<

<

<

<

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

(3)

S

R

(

a

)

S

<

<

R

>

>

(

<

<

a

>

>

<

<

)

>

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

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

S

z

T

#

)

Z

T

>

>

#

<

<

<

I

>

>

(

<

<

<

)

>

>

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

解：

S

A

/

A

S

>

>

A

<

<

>

>

a

>

>

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

提示：分析教材中給出的算法，選擇一種合適的表示給定文法的方法（盡量簡單），使得對

文法的輸入比較簡單的同時（需要把輸入轉(zhuǎn)化為計算機語言表示，這種轉(zhuǎn)化應(yīng)該盡量簡單），

能夠比較簡單地構(gòu)造3個基本關(guān)系矩陣（=，LEAD和LAST）。

證明：設(shè)xjxj+L..xi是滿足條件xj-lvxj=xj+l=?..=xi＞xi+l的最左子串。由=關(guān)系的定義,可

知xjxj+l...xi必出現(xiàn)在某產(chǎn)生式的右部中。又因xj-l＜xj可知xj-1與xj不處于同一產(chǎn)生式，

且xj是某右部的首符。同理，xi為某產(chǎn)生式的尾符號。即存在產(chǎn)生式U-xjxj+I...xi設(shè)ST*

aUb其中，aT*...xj-1,bT*xi+l...對于aUb可構(gòu)造一語法樹，并通過對其剪枝（歸約），直

到U出現(xiàn)在句柄中。從而xjxj+l...xi必為句柄。反之，若xjxj+l...xi是句柄，由簡單優(yōu)先關(guān)

系的定義，必滿足上述條件。

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

型〉，a=VAR,則消去V,并采用分層法改寫文法，得到：DfaW:T;W-LL-L,iliTf「lnlblc

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

D

W

T

L

a

rlnlblc

D

W

T

L

>

a

<

<

<

>

>

>

rlnlblc

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

證：設(shè)STna,我們對n用歸納法，證明a不含兩個非終結(jié)符相鄰情況。n=l時，STa,即S-a

是文法的產(chǎn)生式，根據(jù)定義，它不含上述情況。設(shè)n=k時，上述結(jié)論成立，且設(shè)STkdAb,

由歸納假設(shè)，A兩側(cè)必為終結(jié)符。我們再進行一步推導(dǎo)，得STkdAbTdub,其中，A-u是文

法中的產(chǎn)生式，山定義，u中不含兩個非終結(jié)符相鄰情況，從而dub兩個非終結(jié)符相鄰情況。

得證。

證：由于G不是算符文法，G中至少有一個產(chǎn)生式，其右部含有兩個非終結(jié)符相鄰的情況。

不失一般性，設(shè)其形為U~xABy,x,ydV*,由于文法不含無用產(chǎn)生式，則必存在含有U的句

型dUb,即存在推導(dǎo)ST*dUbTdxAByb.得證。

文法為：E-EfAIAA-A*TIA/TITT-T+VIT-VIVV-iI(E)

解：

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

*

(

)

#

>

<

>

<

<

>

<

>

*

>

<

>

<

>

<

(

<

<

<

<

)

>

>

>

>

I

>

#

<

<

<

<

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

（3）改寫方法：

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

或者將F-P中的賦值運算符改為別的符號來表示；

（1）證明：由設(shè)句型a=-Ua…中含a的短語不含U,即存在A,A=>*ay,則a可歸約為a二…

Ua…（1*…UA3=b,b是G的一個句型，這與G是算符文法矛盾，所以，a中含有a的短語

必含U。

（2）的證明與（1）類似，略。

證:（1）對于a=“?aU…是句型，必有ST*a（=…aU…）T+…ab….即在歸約過程中,b先于a被

歸約,從而,a<b.對于⑵的情況類似可以證明。

證明略.

證明略.

證明略。

證：（1）用反證法。設(shè)沒有短語包含b但是不包含a,則a,b一定同時位于某個短語中，從

而必使得a,b同時位于同一產(chǎn)生式的右部，所以a=b,與G是算符優(yōu)先文法（=與<不能并存）

矛盾。

（2）、（3）類似可證。

證：只要證u中不含有除自身以外的素短語。設(shè)有這樣的素短語存在，即存在bx???by是

素短語，其中l(wèi)<x或者y<n之一成立。因素短語是短語，根據(jù)短語定義，則必有：kxTbx-l<bx

或y<nTby>by+l,與bx-l=bx及by=by+l矛盾,得證。

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

a的素短語。

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

證：設(shè)不能含有素短語，則只能是含有短語（不能含有終結(jié)符號），則該短語只能含有一個

非終結(jié)符號，否則不符合算符文法定義，得證。

解：

（1）算符優(yōu)先矩陣：

+

*

)

#

+

>

<

<

<

>

<

>

>

>

<

<

>

<

>

t

>

>

<

<

>

<

<

<

<

<

<

)

>

>

>

>

I

>

>

>

>

>

#

<

<

<

<

<

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

+

*

)

i

#

F

3

5

5

1

7

7

I

G

2

4

6

6

1

6

1

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

z

b

M

L

a

(

)

5

6

7

7

4

7

1

6

5

4

6

6

7

解：

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

a

#

>

>

a

<

>

<

>

<

#

<

<

<

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

]

a

#

5

7

5

1

g

5

5

6

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

略。

解：

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

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

狀態(tài)

項目集

經(jīng)過的符號

到達的狀態(tài)

10

S'f?S

Sf?aSb

S—?aSc

S-**ab

S

a

II

12

II

S'一S?

12

S—a?Sb

S—a?Sc

S-*a?b

Sf-aSb

S—?aSc

S—?ab

S

a

b

13

12

14

13

SfaS?b

SfaS?c

b

15

16

14

S-*ab?

15

S-aSb?

16

S-^aSc?

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

狀態(tài)

項目集

經(jīng)過的符號

到達的狀態(tài)

10

S'f?S

Sf?cA

S—,ccB

S

II

I

Il

S'-s?

12

S-*c?A

Sfc,cB

A-?cA

A一?a

A

c

a

13

14

15

13

S—cA?

14

S-*cc?B

A—c,A

Bf?ccB

B一?b

Af?cA

Af?a

B

A

b

a

16

15

17

18

15

15

A—a?

16

SfccB?

17

B-c,cB

A-*c?A

A—?cA

A—?a

C

A

a

19

110

15

18

B-b?

19

B-*cc?B

A-*c?A

B—?ccB

B->?b

A—?cA

A一?a

B

A

c

b

a

Ill

IIO

17

18

15

IIO

A-cA?

Ill

B-*ccB,

所求的LR(O)項目規(guī)范族C={IO,I1,-,I11}

(3)

狀態(tài)

項目集

經(jīng)過的符號

到達的狀態(tài)

10

s?s

S一?aSSb

Sf?aSSS

S一?c

S

a

II

12

13

II

S，-S?

12

S-c?

13

S-a?SSb

Sfa?SSS

Sf?aSSb

S-?aSSS

S—?c

S

a

14

12

13

14

SfaS?Sb

S-aS-SS

Sf?aSSb

S—?aSSS

S一?c

S

c

a

15

12

13

15

S-aSS?b

S-aSS?S

Sf?aSSb

Sf?aSSS

S-*?c

S

a

b

c

17

13

16

12

16

S-aSSb?

17

S-aSSS?

(4)

狀態(tài)

項目集

經(jīng)過的符號

到達的狀態(tài)

10

S'f?S

S一?A

Af?Ab

A一,a

S

A

a

II

12

13

II

S'-S?

12

S-A?

S-*A?b

b

14

13

A-*a?

14

SfAb?

解：

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

ACTION

GOTO

a

b

c

#

S

0

S2

1

ACC

2

S2

S4

3

3

S5

S6

4

R3

R3

R3

5

RI

RI

R2

R2

R2

(2)是LR(O)文法，其SLR(l)分析表如下：

FOLLOW(S)=FOLLOW(A)=FOLLOW(B)={#)

ACTION

GOTO

b

c

#

S

A

B

S2

1

ACC

S5

S4

3

RI

S5

S8

S7

3

6

R4

R2

S5

S9

10

R6

S5

S8

S7

10

R3

R5

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

ACTION

GOTO

#

S

S3

S2

1

ACC

R3

R3

R3

R3

S3

S2

4

S3

S2

5

S3

S6

S2

7

RI

RI

RI

RI

R2

R2

R2

R2

(4)因為12中含有沖突項目，所以不是LR(O)文法，其SLR(l)分析表如下:

FOLLOW(S)={#}n=6(所以可以用SLR(l)規(guī)則解決沖突),FOLLOW(A)={b,#}

ACTION

GOTO

a

b

#

S

A

S3

1

2

ACC

S4

RI

R3

R3

R2

R2

解：

狀態(tài)

項目集

經(jīng)過的符號

到達的狀態(tài)

10

S'一?S

S一?(SR

S一?a

S

a

II

12

13

II

S'-S?

12

S->(?SR

S-?(SR

S—?a

S

(

a

14

12

13

13

S-a?

14

S-(S?R

Sf?(SR

Sf?a

Rf?,SR

R一?)

R

)

13

12

15

16

17

15

Sf(SR?

16

Rf,?SR

S一?(SR

S一?a

S

(

a

18

12

13

17

R一)?

18

R-,S?R

Rf?,SR

R-?)

)

R

17

16

19

19

Rf,SR?

LR(O)分析表如F：

ACTION

GOTO

a

)

#

S

R

0

S3

S2

ACC

2

S3

S2

4

3

R2

R2

R2

R2

R2

S3

S2

S7

S6

5

RI

RI

RI

RI

RI

S3

S2

R4

R4

R4

R4

R4

S7

S6

9

R3

R3

R3

R3

R3

可見是LR(O)文法。

解：

(1)

狀態(tài)

項目集

經(jīng)過的符號

到達的狀態(tài)

10

S'f?S

S一?Sab

S一?bR

S

b

II

12

II

(沖突項目)

S'-s?

SfS?ab

a

acc

13

12

S-b?R

R—?S

R-**a

S—,Sab

S一?bR

R

S

a

b

14

15

16

12

13

S-Sa?b

b

17

14

SfbR?

r2

15

RfS?

S-*S,ab

a

13

16

Rfa?

17

SfSab?

項目11,15同時具有移進和歸約項目，對于15={R-S?,S-S?ab),follow(R)={a},follow(R)

n{a}={a},所以SLR(l)規(guī)則不能解決沖突，從而該文法不是SLR(l)文法。

(2)

狀態(tài)

項目集

經(jīng)過的符號

到達的狀態(tài)

10

S'一?S

S—?aSAB

S一?BA

B一?b

S

a

B

b

II

12

13

14

II

S，—S?

12

S->a?SAB

S—?aSAB

S->?BA

B-?b

S

a

B

b

15

12

13

14

13

S-*B?A

A—?aA

A—?B

B—?b

A

a

B

b

16

17

18

14

14

B—b?

r5

15

S-aS?AB

A一?aA

A一?B

B一?b

A

a

B

b

19

17

18

14

16

S-BA?

r2

17

A-^a?A

A—?B

A—?aA

B-?b

A

B

a

b

IIO

18

17

14

18

A—B?

19

S-aSA?B

B一?b

B

Ill

14

IIO

A—aA?

r3

Ill

S-aSAB?

rl

不存在沖突項目，故該文法是LR(O)文法，也是SLR(l)文法。

SLR(l)分析表如下:

ACTION

GOTO

a

b

#

S

A

B

S2

S4

1

3

1

ACC

S2

S4

5

3

S7

S4

6

8

R5

R5

R5

S7

S4

9

8

R2

R2

R2

S7

S4

8

R4

R4

R4

S4

11

10

R3

R3

R3

11

RI

RI

RI

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

狀態(tài)

項目集

經(jīng)過的符號

到達的狀態(tài)

10

S'一?S

S-*?aSb

S一?bSa

S-**ab

S

II

12

13

II

S'—S?

acc

12

S—a?SB

Sfa?b

S--aSb

S-?bSa

Sf?ab

S

b

a

14

15

12

13

Si-Sa

S-*?aSb

S一?bSa

S-**ab

S

a

b

16

12

13

14

S-aS?b

b

17

15

Sfab,

16

S-bS?a

a

18

17

S-*aSb-

18

S-bSa?

r2

不存在沖突項目，故該文法是LR(O)文法，也是SLR(l)文法。

SLR⑴分析表如下：

ACTION

GOTO

a

b

#

S

S2

S3

1

ACC

S2

S5

4

S2

S3

6

S7

R3

R3

R3

S8

RI

RI

RI

R2

R2

R2

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

狀態(tài)

項目集

經(jīng)過的符號

到達的狀態(tài)

10

S'f?S

S-**aA

S-?bB

S

II

12

13

II

S'一S?

acc

12

（沖突）

Sfa?A

Af,cAd

A一?

A

c

14

15

r4

13

（沖突）

S-b-B

B—?cBdd

B—?

B

c

16

17

r6

14

SfaA?

15

（沖突）

A-*c?Ad

Af,cAd

A一?

A

c

18

15

r4

16

S-bB?

r2

17

（沖突）

Bfc?Bdd

B--c?Bdd

B--

B

c

19

17

r6

18

A—cA,d

d

IIO

19

B—cB?dd

d

III

110

A->cAd?

r3

Ill

BfcBd?d

d

112

112

B-*cBdd?

r5

因為follow(A)=follow(B)={#,d},所以沖突項目12,13,15,17可以用SLR⑴規(guī)則得以解決，從而

該文法為SLR⑴文法。其SLR(l)分析表如下：

ACTION

GOTO

a

b

c

d

#

S

A

B

S2

S3

1

1

Acc

2

S5

R4

R4

4

3

S7

R6

R6

6

4

RI

5

S5

R4

R4

8

6

R2

7

S7

R6

R6

9

8

S10

9

Sil

10

R3

R3

11

S12

12

R5

R5

(5)解:原文法等價化為ql-q2,ql-q3,q2fq4;q5,q4->beginD,q4fq4;D,q5fsend,q5

fS;q5,q3-beginq5,

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

狀態(tài)

項目集

經(jīng)過的符號

到達的狀態(tài)

10

qT—?q]

ql-**q2

ql~**q3

q2f?q4;q5

q3f?beginq5

q4f?beginD

q4f?q4;D

qi

q2

q3

q4

begin

II

12

13

14

15

II

ql'-ql?

ACC

12

ql->q2?

RI

13

ql一q3?

R2

14

q2fq4?;q5

q4fq4,;D

D

16

15

q3-*begin,q5

q3-*begin?D

q5f?Send

q5f,S;q5

q5

D

S

17

18

19

16

q2fq4;?q5

q4fq4;?D

q5f?Send

q5f?S;q5

q5

D

S

IIO

Ill

19

17

q3-*beginq5?

R8

18

q3-*beginD?

R4

19

q5fs?end

q5fs?;q5

end

112

113

IIO

q2fq4;q5?

R3

Ill

q4—q4;D?

R5

112

q5fSend?

R6

113

q5fs;?q5

q5f?Send

q5f?S;q5

q5

S

114

19

114

q5fs;q5?

R7

不存在沖突項目，故該文法是LR(O)文法，也是SLR(l)文法。

SLR(l)分析表如下:

ACTION

GOTO

begin

D

S

end

#

qi

q2

q3

q4

q5

0

2

3

4

1

Acc

2

RI

3

R2

4

S6

5

S8

S9

7

6

S7

S9

10

7

R8

8

R4

9

S13

S12

10

R3

11

R5

12

R6

13

S9

14

14

R7

（6）解：原文法可化為等價形式：qLbeginq2q3end,q2fq2d;,q2f￡,q3fq3;q4,q3fq4,

q4fS,q4f￡,

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

狀態(tài)

項目集

經(jīng)過的符號

到達的狀態(tài)

10

qrf?ql

ql—?beginq2q3end

qi

begin

II

12

II

ql'-ql?

ACC

12

ql_*begin?q2q3end

q2f?q2d;

q2一?

q2

q2

13

R3

13

（沖突項目）

Ql-*beginq2?q3end

q2fq2,d;

q3f,q3;q4

q3f?q4

q4f?S

q4f?

q3

Dd

q4

S

14

IIO

15

16

R7

14

ql->beginq2q3?end

q3fq3,;q4

end

17

18

15

q3fq4?

R5

16

q4fs?

R6

17

ql->beginq2q3end?

RI

18

（沖突項目）

q3fq3;,q4

q4f?S

q4f?

q4

S

19

16

R7

19

q3fq3;q4?

R4

IIO

q2fq2d?;

Ill

Ill

q2—q2d;,

R2

因為folk)w(q4)={end,#},故沖突項目可以通過SLR(l)規(guī)則來解決，從而文法為SLR(l)文法。

SLR(l)分析表如下：

action

goto

begin

end

d

S

#

qi

q2

q3

q4

S2

R3

R3

R3

R3

R7

S10

R7

S6

L

5

S7

S8

R5

R5

R6

R6

RI

R7

R7

S6

9

R4

R4

10

11

R2

R2

R2

R2

解：識別活前綴的DFA及LR(0)分析表:

狀態(tài)

項目集

經(jīng)過的符號

到達的狀態(tài)

10

S'-*?S

S—?AAd

Sf?cAd

S-?b

A一?ASc

Af?Sb

A-**cd

A—?a

S

A

a

b

c

10

16

15

14

13

II

S'—S?

A-S?b

b

12

12

A