蔣立源《編譯原理》西北工業(yè)大學出版社第3版課后答案

《編譯原理》課后習題答案

第一章

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

釋程序）將源程序處理加工而得的另一種語言（目標語言）的程序。翻譯程序是將

某種語言翻譯成另一種語言的程序的統(tǒng)稱。編邑程序與解釋程序均為翻譯程序，但

二者工作方法不同。解釋程序的特點是并不先將高級語言程序全部翻譯成機器代碼,

而是每讀入一條高級語言程序語句，就用解釋程序?qū)⑵浞g成一段機器指令并執(zhí)行

之，然后再讀入下一條語句繼續(xù)進行解釋、執(zhí)行，如此反復(fù)。即邊解釋邊執(zhí)行，翻

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

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

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

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

處理程序組成。

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

dodoubleelseenuirexternfloatforgotoifintlongregisterreturnshort

signedsizeofstaticstructswitchtypedefunionunsignedvoidvolatile

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

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

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

鍵字。逗號在C語言中被視為分隔符和運算符，作為優(yōu)先級最低的運算符，運算結(jié)

果為逗號表達式最右側(cè)子表達式的值（如：（a,b,c,d）的值為d）。

5.略

第二章

1.(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)

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

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

解：對應(yīng)文法為G(S)=({S,X,Y},{a,b,c},{S->aS|X,X->bX|Y,Y->cY|￡},S)

(3)(an#bn|n^O}U{cn#dn|n'O}

解：對應(yīng)文法為G(S)=((S,X,Y),{a,b,c,d,#},{SfX,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->OWO|1W1|#},S)

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

解：G(S)=((S,A,B,I,J),{-,0,1,2,3,4,5,6,7,8,9),{S-J|IBJ,B-OB|IB|e,I-

J|2|4|6|8,Jdl|3|5|7|9},S)

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

解：對應(yīng)文法為S->OA|lB|e,A-*OS|1CB-*OC|1SC-*1A|OB

3?描述語言特點

(1)SflOSOS-aAA-bAA-a

解：本文法構(gòu)成的語言集為:L(G)={(10)nabmaOn|n,m2。}。

(2)S-*SSS-*lAOA-*lADA->￡

解；L(G)-{InlOnlln20n2…lnmOnm|nl,n2,?,,,nm^O；且nl,n2,…nm不全為零}該

語言特點是：產(chǎn)生的句子中，0、1個數(shù)相同，并且假設(shè)干相接的1后必然緊接數(shù)量相同連

續(xù)的0。

(3)S->lASfBOA-*1AA-CBfBOB-CC-1C0C-e

解：本文法構(gòu)成的語言集為：L(G)為lpln0n|p21,u20}U{ln0n0q|qNl,n》0},特點

是具有IplnOn或InOnOq形式,進一步，可知其具有形式InOmn,m^0,且n+m>0o

(4)SfhAdcAfAGSG—￡A—a

解：可知,S=>-=>baSndcn20

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

(5)S-aSSS-a

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

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

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

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

5.2證明：略

6.解:

（1）最左推導：

〈程序＞T＜分程序〉T〈標號〉：〈分程序）TL：〈分程序》

匚：〈標號》：〈分程序》

TL：L：〈分程序》

TL：L：〈無標號分程序》

TL：L：＜分程序首部＞；＜復(fù)合尾部）

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

TL：L：begin〈說明〉；〈說明〉；〈復(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

最右推導:

〈程序＞T〈分程序訂〈標號》：〈分程序〉

T〈標號〉：〈標號》：〈分程序〉

T〈標號〉：〈標號）：〈無標號分程序》

T〈標號〉：〈標號）：〈分程序首部〉；〈復(fù)合尾部）

以標號:：＜標號）：＜分程序首部〉；＜語句）；＜復(fù)合尾部）

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的相應(yīng)語法樹是:

7,解:

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

最右推導：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é)論顯然成立。設(shè)n=＜時，對于ci1a2...akT*b,存在B

i：aiT*bi成立，現(xiàn)在設(shè)

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

前綴b',Qk+1可推導出b的一個后綴二b〃（不妨稱為bk+1）。由歸納假設(shè)，對于b',存在

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

aiT*bi成立,另外,我們有ak+lT*b〃（=bk+1）。即產(chǎn)k+1時亦成立。證畢。

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

3；B二A3'且a=>*P0

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

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

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

二As'且a=a3T…TA。'=0,與（1）同理，得證。

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

STABTAbcTabc

STDCTDcTabc

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

11.解：

（1）STABTAaSbrAacbTbAacbTbbAacbTbbaacb

上面推導中，下劃線局部為當前句型的句柄。對應(yīng)的語法樹為：

全部的短語：

第一個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))

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

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

最右推導:ETT=>F=>FPtTFEtTFET+fTFEF+tTFEP+tTFEi+t

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

TFii*i+tTPii*i+fTiii*i+t

12.證明:

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

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

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

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

13.化簡以下各個文法

(1)解：S->bCACdA->cSA|cCCC-cS|c

(2)解：S-aAB|fA|gA-e|dDAD^eAB^f

(3)解；S-ac

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

(1)解：S-aAS|aS|bA-cS

(2)解：S-aAA|aA|aA-bAc|be|dAe|de

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

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

S-aB|BC

B-DB|b

Ci

D-bDB

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

STA|SB|0|(S)|[]|[S]

A7)|(S)

Ba[]|[S]

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

E-E+T|T*F|(E)|PtFIi

T-T*F|(E)|PtF|i

F-PtF|(E)|i

P-(E)|i

第三章

1.從略

2.

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

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

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

4證明：只須證明文法G:AfciB或A-a(A,BEVN,aeVT+)

等價于Gl:A—aB或Afa(aeVT+)

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

所以有A-abc-B,,a,b,c-eVT,B,eVN

所以與G等價。

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

~aB

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

5

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

L={ambnci|m,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)其對應(yīng)的右線性文法是：

A->0D,B-OA,B->IC,C->1|1F,C->1|OA,F-01OE11A,D-OB|IC,E-IC|OB

(2)最短輸入串Oil

(3)任意接受的四個串

011,0110,0011,000011

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

8從略。

9

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

⑴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所組成的任意串結(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,SfDd,D-C,B-Db,C-Be,B-Ab,B-e,A-*a

G2等價的右線性文法：

SfdD,S-aB,D-C,B-abC,B->bB,B—?■bA,B—*,￡,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)對串a(chǎn)ebd來說，Gl,Gr文法都不能產(chǎn)生。

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

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

則假設(shè)A不是開始符，B-Aa;

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

12(1)

a

S{S用}

A0

B{B}4)?

狀態(tài)矩陣是：

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

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

13(1)將具有￡動作的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)從略

⑵化簡后SO和SI作為一個狀態(tài)，S5和S6作為一個狀態(tài)。

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

15從略。

16從略。

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

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

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

(r*)*=r*={￡,r,rr,rrr,…}

所以四者是等價的。

(2)(rs)*r表示的正規(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⑴

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(3)

OD⑷

Db=B+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)*(cdb))

G2:

S=Aa+B(1)

A=Cc+Bb(2)

B=Bb+a(3)

C=D+Bab(4)

D二d⑸

可得D=dB=ab*C=ab*ab|bA=(ab*ab|b)c+ab*b

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

=(ab*ab|b)ca|ab*ba|ab*

20

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

從略。

21從略。

22構(gòu)造NFA

其余從略。

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

%{

#include<stdio.h>

#include<string.h>

#include<ctype.h>

#defineONI

^defineTW2

defineTHRE3

加efineTE10

#defineTWENT20

^defineHUNDRE100

defineWHITE9999

船

upper[A-Z]

%%

ONEreturnON;

TVOreturnTW;

THREEreturnTHRE;

T亦returnTE;

TWENTYreturnTWENT;

HUNDREDrcturnHUNDRE;

z/+1\treturnWHITE;

\nreturnO;

%%

main(intargc,char*argv[])

(

intc,i=0;

chartmp[30];

if(argc==2)

(

if((yyin=fopen(argv[1],vrz，))==NULL)

(

printf("can'topen%s\n，z,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;

)

上/*\vhi1e*/

label:printf("%d\n”,i);

return;

)

21(1)Dn表示的正規(guī)集是長度為2n任意a和b組成的字符串。

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

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

25從略。

26⑴由｛｝括住的，中間由任意個非｛組成的字符串,如｛｝,｛｝｝,⑻，｛defg｝等等。

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

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

?由'和'括住的，中間由兩個‘'或者非'和\n組成的任意次的字符串。如‘'''

，a，,，bb','def',，，，，，，等等

270[Xx][0-9]*[a-fA-F]*|[0-9]+|(\T([a-zA-Z]|\\[Xx][0-7][0-7a-fA-F]|\\0[01][0-7

][0-7]|\\[a-z])\,)

28*[a-zA-ZJ+[0-9]*[a-zA-Z」*

29參考程序如下：

%(

Sinclude<stdio.h>

Sinclude<string.h>

^include<ctype.h>

#defineUPPER2

^defineW1HTE3

upper[A-Z]

%%

{upper}+returnUPPER;

\t|z，，z+returnWHTTE;

%%

main(intargc,char*argv[])

(

intc,i;

if(argc==2)

if((yyin=fopen(argv[1],vrz，))—NULL)

printf(〃can'topen%s\n/z,argv[l]);exit(0);

)

}

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

(

if(c=2)

(

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

printf(〃％c”,tolower(yytext[i]));

yytext[0]=\000*;

)

if(c==3)

printf(〃”)；

elseprintf(〃%s“，yytext);

}

return;

)

yywrap()

{

return;

)

30從略o

第四章

1.解：

(l)Sf(S)Z21|()Z21|[S]Z31|[]Z31

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

B-(S)Z231()Z231[S]Z331口Z33

ZU-*e|AZ11|BZ21

Z12->AZ12|BZ22Z13->AZ13|BZ23

Z21-Z11Z22f￡|Z12

Z23fzi3Z31fz21

Z32fz22Z33f￡|Z23

(2)S->bZl11aZ21A->bZ121aZ22

Zll->￡|AZ21Z12-AZ22Z21-SZ21Z22f￡|SZ22

⑶S-(T)Z11|aZll|Z11S->(T)Z12|aZ12|Z12

ZU->￡|Z21Z12fz22Z21-，SZ21Z22fe|,SZ22

?2.解：

SnAbBl,1.1(表示第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<>

⑴文法沒有左遞歸。

FunctionP:boolean;

Begin

Save;

P:=true;

Ifnext_token="，begin”then

Ifnext_token=,d'then

Ifnext_token=,then

IfXthen

Ifnext_token=",end"thenreturn;

Restore;

P:二false;

End;

FunctionX:boolean;

Begin

Save;

X:=true;

Ifnexttoken='d'then

Ifnext_tokcn=,;'then

IfXthenreturn;

Restore;

Ifnext_token=,s'then

IfYthenreturn;

Restore;

X:=false;

End;

FunctionY:boolean;

Begin

Save;

Y=true;

Ifnext_tokcn=,then

Ifnext_token=,s'then

IfYthenreturn;

Restore;

End;

⑵消去文法左遞歸，并記為：

PfbeginSendS-ACA->V:二ECfifEthenS

E—E'E'-+VE'|￡VT

FunctionP:boolean;

Begin

Save;

P:=true;

Ifnext_tokcn=",begin”then

IfSthen

Ifnext_token=",end"thenreturn;;

Restore;

P:=false;

End;

FunctionA:boolean;

Beign

Save;

A:=true;

IfVthen

Ifnext_token=,/:="then

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;

ED：=true;

Ifnext_token=,+'then

IfVthen

IfE'thenreturn;

Return;

End;

?4.解：

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

生式，且QT*Ad.

則first(Ad)Gfirst(B)W4),從而

first(a)Gfirsl(B)Wd),即文法不滿足LL(1)文法條件。得證。

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

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

存在著句子a有兩個不同的最左推導。從而可知，用LL(1)方法進行句子a的分

析過程中的某步中，存在兩種不同的產(chǎn)生式替換，且均能正確進行語法分析，即LL

(1)分析動作存在不確定性。與LL(1)性質(zhì)矛盾。所以，G不是LL(1)文法。

?7.解：

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

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

?8.解：

⑴消除左遞歸性，得：

S-*bZll|aZ21A-*bZ12|aZ22Zll-*bZll|eZ12fbz12

Z21fbz11|aZ21Z22fbz121az221e

消除無用產(chǎn)生式得:S->bZll|aZ21Zll->bZll|eZ21-bZll|aZ21

此文法已滿足LL(D文法的三個條件,

所以G'[S]:S->bZll|aZ21Zll->bZll|￡Z21->bZll|aZ21

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

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

S-bZll{#)

-aZ21{a}

Zll->bZll{#}

—￡{￡}

Z21fbz11{#}

-*aZ21{a}

L，(l)分析表為*

ab#

SaZ21bZll

ZllbZH￡

Z21aZ21bZll

?9.解:

(1)

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

S-*SaB

{#,a,c)

fbB

A->S

{c}

-*a(d

BfAc{a,b}{#,a,c}

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

?10.解；

?1)為方便書寫，記：〈布爾表達式＞為人，＜布爾因子＞為13,〈布爾二次量＞為(：，〈布

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

A-AVB|BB-BAC|CC-?D|DD-*(A)|true|false,

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

AfBA'A'-VBA'|coB-CB',

B'ACB'|3C-?D|DD-＞(A)|true|false

⑵略

?證：假設(shè)LL(1)文法G有形如B-aAAb的產(chǎn)生式，且AT+￡及AT*ag,根據(jù)FIRST

集FOLLOW集的構(gòu)造算法可知，F(xiàn)IRSTS)中一切非￡加到FOLLOWS)中，則aW

FOLLOW(A)；又因為a￡FIRST(ag),所以兩集合相交非空,因此,G不是LL⑴文法;

與前提矛盾，假設(shè)不成立，得證。

?12o解:

(1)

SA(a)b

S==

A=<=<

(==?<

<

a>=<?

>

)>??

b?

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

(2)

SRT()Aa,

S>=

R

T>

(<=?<<

)>>

A>>

a>>

,<=<<<

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

(3)

SR(a,)

S=?

R?

(=?

a?

，;?

)?

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

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

SZT#i()

S

Z二二

T>>

#=<?

T>>

(=(?

)>>

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

?13.解：

SA/A

S>>

A=<

<

/>>

a>>

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

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

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

該盡量簡單），能夠比擬簡單地構(gòu)造3個根本關(guān)系矩陣（=,LEAD和LAST）。

?證明：設(shè)xjxj+1...xi是滿足條件xjTVxj=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+l...xi設(shè)ST*aUb其中，aT*...xj-1,bT*xi+1...對于

aUb可構(gòu)造一語法樹，并通過對其剪枝（歸約），直到U出現(xiàn)在句柄中。從而

xjxj+1...xi必為句柄。反之，假設(shè)xjxj+1...xi是句柄，由簡單優(yōu)先關(guān)系的定義,

必滿足上述條件。

?解：為描述方便，用符號表示各非終結(jié)符:DX變量說明》,LW變量表），V=〈變量>,T=<

類型），a=VAR,則消去V,并采用分層法改寫文法,得到：D->aW:T;W->LL-L,i|iT

-*rn|b|c

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

DWTLair|n|b|c

D

W

T=

L>=

a=<<

:=<

,>>>=

i

r|n|b|c>

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

?證：設(shè)STna,我們對n用歸納法，證明a不含兩個非終結(jié)符相鄰情況。產(chǎn)1時，STa,

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

且設(shè)STkdAb,由歸納假設(shè)，A兩側(cè)必為終結(jié)符。我們再進行一步推導，得STkdAbTdub,

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

兩個非終結(jié)符相鄰情況。得證。

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

的情況。不失一般性，設(shè)其形為U-xABy,%y￡V*,由于文法不含無用產(chǎn)生式，則必

存在含有U的句型dUb,即存在推導ST*dUbTdMB_Fb.得證。

?文法為：E-*EtA|AAfA*T|A/T|TT->T+V|T-V|VV-*i|(E)

?20.解：

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

i#

?

-<><>

?

>

*><X

、/

(?<=<

)?>>

I?>>

#?<<

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

(3)改寫方法：

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

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

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

為a=…UE…U*…UA…=b,b是G的一個句型，這與G是算符文法矛盾，所以，a中

含有a的短語必含U。

(2)的證明與(1)類似，略。

?證:(1)對于a二…aU…是句型,必有ST*a(=…all…)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??4”

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

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

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

是句型a的素短語。

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

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

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

?31.解：

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

+*fUi#

+>?<><>

*?<<><>

t?<<><>

(?<<=<

)?>>>

I?>>>

n?<<<

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

+*t0i#

F3551771

G2466161

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

zbMLa()

fl567747

gl654667

?33.解：

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

□a#

[>=

]>>

?

a<

?

n<?

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

[]a#

f5751

g5561

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

?略。

35解:

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

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

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

10S'-*?SSII

S-**aSba12

S一?aSc

S一?ab

11S'-S?

12S-*a?SbS13

Sfa?Sca12

Sfa?bb14

S-**aSb

Sf?aSc

S一?ab

13SfaS?bb15

S-*aS?cc16

14Sfab?

15S->aSb?

16S-aSc?

(2)識別全部活前綴的DFA如下:

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

10S'f?SSII

Sf?cAcI

S一?ccB■

11S，—S?

12S-*c?AA13

Sfc?cBc14

A一?cAaT5

A—?a

13S—cA?

14Sfcc?BB16

A-*c?AA15

B一?ccBc17

B--bb18

A-**cAa15

A-**a

15A—a?

16S-*ccB?

17Bfc-cBC19

卜一c?AA110

A一?cAa15

A-*?a

18B-*b?

19B-cc?BBIll

A—c?AA110

Bf?ccBc17

Bf?bb18

A一?cAa15

Af?a

110A-*cA?

IllBfccB?

所求的LR(O)工程標準族C={IO,II,-,111}

⑶

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

10S'-?SSII

S--aSSbc12

S--aSSSaT3

S-**c

IIS'-S?

12S-*c-

13S-*a?SSbS14

S-a?SSSc12

S-*?aSSba13

S->?aSSS

Sf?c

14S-*aS?SbS15

SfaS?SSc12

S--aSSba13

5一?aSSS

S一?c

15S-*aSS?bS17

S-*aSS-Sa13

S一?aSSbb16

S--aSSSc12

Sf?c

16S-aSSb?

17S-aSSS?

⑷

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

10S'f?sSII

S一?AAT2

Af-Aba13

A—?a

11S'fS?

12S-A?bT4

S-A?b

13A-*a?

14SfAb?

36W：

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

ACTIONGOTO

abcS

0S21

1ACC

2S2S43

3S5S6

4R3R3R3

5RIRIRI

6R2R2R2

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

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

ACTIONGOTO

abcUSAB

0S21

1ACC

2S5S43

3RI

4S5S8S736

5R4

6R2

7S5S910

8R6

9S5S8S71011

10R3

11R5

⑶是LR(O)文法,其SLR(l)分析表如下：FOLLOW(S)={?,a,b,c)

ACTIONGOTO

abc#S

0S3S21

1ACC

2R3R3R3R3

3S3S24

4S3S25

5S3S6S27

6RIRIRIRI

7R2R2R2R2

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

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

ACTIONGOTO

abSA

0S312

1ACC

2S4RI

3R3R3

4R2R2

37解:

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

roS'一?sSII

Sf-(SR(12

S-**aa13

riS'fS?

12Sf(?SRS14

Sf?(SR(12

S一?aa13

13S-*a?

14S-*(S?Ra13

Sf?(SR(12

S一?aR15

Rf?,SR16

Rf?))17

15Sf(SR?

16Rf,?SRs18

Sf?(SR(12

S—?aa13

17Rf)?

18R-,S?R)17

Rf?，SR16

Rf?)R19

19Rf,SR?

LM(O)分析表如下:

ACTIONGOTO

a()nSR

0S3S21

1ACC

2S3S24

3R2R2R2R2R2

4S3S2S7S65

5RIRIRIRIRi

6S3S28

7R4R4R4R4R4

8S7S69

9R3R3R3R3R3

可見是LR(O)文法。

38解:

⑴

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

10S，一?SST1

Sf?Sabb12

Sf?bR

11S'fS?aacc

(沖突工程)SfS?ab13

12Si?RR14

R-?SS15

Rf?aa16

S一?Sabb12

Sf?bR

13SfSa?bb17

14S-bR-r2

T5R—S?a13

(沖突工程)SfS?ab

16R-*a?

17S-*Sab-

工程II,15同時具有移進和歸約工程，對于15={RfS?，S-*

S-ab),follow(R)={a},follow(R)S{a}={a},所以SLR(l)規(guī)則不能解決沖突,從而該文

法不是SLR(1)文法。

⑵

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

roS'一?sSII

S-**aSA