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

目錄

第一章習(xí)題解答.....................................................................1

第二章習(xí)題解答.....................................................................2

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

3.描述語(yǔ)言特點(diǎn)...........................................................3

7.解：....................................................................5

10.證明：因?yàn)榇嬖诰渥樱篴bc,它對(duì)應(yīng)有兩個(gè)語(yǔ)法樹(shù)（或最右推導(dǎo)）：.......7

11.解：...................................................................7

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

第三章習(xí)題解答....................................................................10

第四章習(xí)題解答....................................................................24

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

35解:....................................................................36

36解：....................................................................40

37解：....................................................................41

38解：....................................................................42

39解：識(shí)別活前綴的DFA及LR（0）分析表：..................................50

40解:求LR（1）項(xiàng)目集和狀態(tài)轉(zhuǎn)換表:......................................53

41解：....................................................................55

42解：....................................................................58

第五章習(xí)題解答....................................................................64

5.8解：...................................................................65

第一章習(xí)題解答

1.解：源程序是指以某種程序設(shè)計(jì)語(yǔ)言所編寫(xiě)的程序。目標(biāo)程序是指編譯程

序（或解釋程序）將源程序處理加工而得的另一種語(yǔ)言（目標(biāo)語(yǔ)言）的程

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

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

將高級(jí)語(yǔ)言程序全部翻譯成機(jī)器代碼，而是每讀入一條高級(jí)語(yǔ)言程序語(yǔ)

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

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

序列并不保存。編譯程序的特點(diǎn)是先將高級(jí)語(yǔ)言程序翻譯成機(jī)器語(yǔ)言程

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

行。

2.解：一般說(shuō)來(lái)，編譯程序主要由詞法分析程序、語(yǔ)法分析程序、語(yǔ)義分析

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

理程序、錯(cuò)誤檢查處理程序組成。

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

defau11dodoubIeeIseenumexternfIoatforgotoifintIong

registerreturnshortsignedsizeofstaticstructswitchtypedef

unionunsignedvoidvoIatiIewhiIe0上述關(guān)鍵字在C語(yǔ)言中均為保留

字。

4.解：C語(yǔ)言中括號(hào)有三種：｛｝,口，（）o其中，｛｝用于語(yǔ)句括號(hào)：口用

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

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

先級(jí)最低的運(yùn)算符，運(yùn)算結(jié)果為逗號(hào)表達(dá)式最右側(cè)子表達(dá)式的值（如：

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

5.略

第二章習(xí)題解答

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

(2)答：26*10=260

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

共26+26*36+26*36*36=34658個(gè)

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

(1){anbn|n^O}

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

(2){anbmcp|n,m,p，0}

解：對(duì)應(yīng)文法為G(S)二({S,X,Y},{a,b,c},{STaS|X,XTbX|Y,YTcY|

G,S)

(3){an#bn|n20}U{cn#dn|n20}

解：對(duì)應(yīng)文法為G(S)=({S,X,Y},{a,b,c,d,#},{STX,STY,XTaXb|#,Y

TcYd|#},S)

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

解：G(S)=({S,W,R},{0,1,#},{STW#,WTOWO|1W1|#},S)

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

解：G(S)=({S,A,B,I,J},{-,0,1,2,3,4,5,6,7,8,9},{S->j|

0B|IB|e,I-4J|2|4|6|8,JT113151719},S)

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

解：對(duì)應(yīng)文法為S-+0A|lB|e,ATOS|1CB-*OC|1SC->1A|0B

3.描述語(yǔ)言特點(diǎn)

(1)S-MOSOSTaAATbAATa

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

(2)STSSS-MA0AT1A0ATE

解：L(G)={1n10n11n20n21nmOnm|rd,n2,…，nm20;且n1,n2,…nm不

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

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

(3)ST1ASTB0A-MAATCBTB0BTCCT1C0CT￡

解：本文法構(gòu)成的語(yǔ)言集為：L(G)={1p1nOn|p^1,n^O}U{1nOnOq|q^1,n

20},特點(diǎn)是具有1p1nOn或InOnOq形式，進(jìn)一步，可知其具有形式1nOmn,m

》0,且n+m>0o

(4)STbAdcATAGSGTEA-*a

解：可知,S=>?“=>baSndcn20

該語(yǔ)言特點(diǎn)是：產(chǎn)生的句子中，是以ba開(kāi)頭de結(jié)尾的串，且ba、de個(gè)數(shù)相

同。

(5)STaSSSTa

解：L(G)={a(2n-1)|n?1}可知：奇數(shù)個(gè)a

4.解：此文法產(chǎn)生的語(yǔ)言是：以終結(jié)符a1、a2-an為運(yùn)算對(duì)象，以八、V、

~為運(yùn)算符，以［、］為分隔符的布爾表達(dá)式串

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

5.2證明：略

6.解:

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

＜程序＞1■〈分程序＞T＜標(biāo)號(hào)）：＜分程序）TL:〈分程序〉

TL:＜標(biāo)號(hào)＞：〈分程序〉

TL:L:〈分程序）

TL:L:〈無(wú)標(biāo)號(hào)分程序〉

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

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

TL:L:beginUM^明〉；〈說(shuō)明〉；〈復(fù)合尾部〉

TL:L:begind;〈說(shuō)明〉；〈復(fù)合尾部〉

TL:L:begind;d;〈復(fù)合尾部〉

TL:L:begind;d;〈語(yǔ)句〉；〈復(fù)合尾部〉

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

TL:L:begind;d;s;〈語(yǔ)句＞end

TL:L:begind;d;s;send

最右推導(dǎo):

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

IX標(biāo)號(hào)）：〈標(biāo)號(hào)）：〈分程序）

IX標(biāo)號(hào)＞：〈標(biāo)號(hào)〉：〈無(wú)標(biāo)號(hào)分程序〉

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

/標(biāo)號(hào)〉：〈標(biāo)號(hào)）：〈分程序首部＞；＜語(yǔ)句＞；＜復(fù)合尾部）

1標(biāo)號(hào)）:＜標(biāo)號(hào)）：〈分程序首部＞；＜語(yǔ)句）；＜語(yǔ)句）；end

IX標(biāo)號(hào)）:〈標(biāo)號(hào)〉：〈分程序首部〉；〈語(yǔ)句）；s;end

丁＜標(biāo)號(hào)＞：〈標(biāo)號(hào)）：＜分程序首部＞；s;s;end

1標(biāo)號(hào)〉：＜標(biāo)號(hào)）：＜分程序首部〉；說(shuō)明;s;end

T〈標(biāo)號(hào)〉：〈標(biāo)號(hào)〉：〈分程序首部）；d;s;end

?。紭?biāo)號(hào)）：〈標(biāo)號(hào)）：begin說(shuō)明；d;s;s;end

?。紭?biāo)號(hào)）：＜標(biāo)號(hào)）：begind;d;s;s;end

T〈標(biāo)號(hào))：L:begind;d;s;s;end

TL:L:begind;d;s;s;end

(2)句子L:L:begind;d;s;send的相應(yīng)語(yǔ)法樹(shù)是:

7.解:

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

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

最左推導(dǎo)：S=>aAcB=>aacB=>aacb

(2)aabacbadcd不是文法G[S]中的句子

因?yàn)槲姆ㄖ械木渥硬豢赡芤苑墙K結(jié)符d結(jié)尾

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

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

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

因?yàn)榻K結(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=1時(shí)，結(jié)論顯然成立。設(shè)n=k時(shí)，對(duì)于a1a2...akT*b,

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

a1a2...akak+1T*b,因文法是前后文無(wú)關(guān)的，所以a1a2...ak可推導(dǎo)

出b的一個(gè)前綴b',ak+1可推導(dǎo)出b的一個(gè)后綴二b"(不妨稱為bk+1)。由歸

納假設(shè)，對(duì)于b',存在。i:i=1,2,..,k,b'=B102...Bk,使得

aiT*bi成立，另夕卜，我們有ak+1T*b"仁bk+1)。即n=k+1時(shí)亦成立。證畢。

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

設(shè)：a=a3；B=A3'且a=>*0。

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

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

(2)同(1),假設(shè)：B的首符號(hào)為非終結(jié)符時(shí)，a首符號(hào)為終結(jié)符。即設(shè)：a

=aco:B=A3'且a=a3T???TAco'=(i,與(1)同理，得證。

10.證明：因?yàn)榇嬖诰渥樱篴bc,它對(duì)應(yīng)有兩個(gè)語(yǔ)法樹(shù)(或最

右推導(dǎo))：

STABTAbcTabc

11.解:

(1)STABTAaSbTAacbTbAacbTbbAacbTbbaacb

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

全部的短語(yǔ)：

第一個(gè)a(a1)是句子bbaacb相對(duì)于非終結(jié)符A(A1)(產(chǎn)生式A?a)的短語(yǔ)(直

接短語(yǔ))；

b1a1是句子bbaacb相對(duì)于非終結(jié)符A2的短語(yǔ)；

b2b1a1是句子bbaacb相對(duì)于非終結(jié)符A3的短語(yǔ)；

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

a2cb3是句子bbaacb相對(duì)于非終結(jié)符B的短語(yǔ)：

b2b1a1a2cb3是句子bbaacb相對(duì)于非終結(jié)符S2的短語(yǔ)；

注：符號(hào)的下標(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)的語(yǔ)法樹(shù)是:

(3)解：iii*i+T對(duì)應(yīng)的語(yǔ)法樹(shù)略。

最右推導(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)前文法下的每一符號(hào)串僅有一■個(gè)句柄和一■個(gè)句柄產(chǎn)生式T對(duì)當(dāng)前符號(hào)

串有唯一的最左歸約T對(duì)每一步推導(dǎo)都有唯一的最右推導(dǎo)T有唯一的語(yǔ)法樹(shù)。

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

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

13.化簡(jiǎn)下列各個(gè)文法

(1)解：STbCACdATcSAlcCCCTcS|c

(2)解：S—aAB|fA|gA-*e|dDADTeABTf

(3)解：STac

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

(1)解：STaAS|aS|bA-*cS

(2)解：STaAA|aA|aA->bAc|be|dAe|de

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

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

STaB|BC

BTDB|b

CTb

DTb|DB

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

STSA|SB|()|(S)|[]|[S]

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

Ba□|[S]

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

E—E+T|T*F|(E)|PTF|i

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

F—PTF|(E)|i

PT(E)|i

第三章習(xí)題解答

1.從略

2.

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

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

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

4證明：只須證明文法G：ATaB或ATa(A,BWVN,aGVT+)

等價(jià)于G1:ATaB或ATa(aGVT+)

?G1的產(chǎn)生式中ATaB,則B也有BTbC,CTcD….

所以有ATabe…B',a,b,c…6VT,B'eVN

所以與G等價(jià)。

2)G的產(chǎn)生式ATaB,aGVT+,因?yàn)閍是字符串，所以肯定存在著一個(gè)終結(jié)符

a,使ATaB

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

5

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

L={ambnci|m,n,i=1}

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

P={STaA,A-*aA,A->bB,B->bB,BTcC,CTcC,C->c}

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

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

ATOD,B->OA,B-41C,C->111F,C->1|OA,F->01OE11A,D->OB11C,E-*1C|OB

(2)最短輸入串011

(3)任意接受的四個(gè)串

011,0110,0011,000011

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

8從略。

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

(i)STaASTbSA—aAATbBB-+a|aBB->b|bB

(ii)STaA|aS—bBB-*aB|bBA—aBA—b|bA

(iii)STaAS—bBA—bAA—aCB—aBB—bCC-?a|aCC->b|bC

(iv)S-*bSSTaAA-+aCATbBBTaBB->bCC-*a|aCC-?b|bC

(3)用自然語(yǔ)言描述輸入串的特征

(i)以任意個(gè)(包括0)b開(kāi)頭，中間有任意個(gè)(大于1)a,跟一個(gè)b,還可以有一

個(gè)由a,b組成的任意字符串

(ii)以a打頭，后跟任意個(gè)(包括0)b

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

意串結(jié)尾或者

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

尾

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

或者

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

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

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

(2)G1等價(jià)的左線性文法:

STBb,STDd,DTC,B->Db,C->Bc,BTAb,B-?E,A->a

G2等價(jià)的右線性文法：

STdD,S->aB,DTC,BTabC,BTbB,BTbA,B-?E,C->cA,ATa

(3)對(duì)G1文法，abb的推導(dǎo)序列是:

S=>aA=>abB=>abb

對(duì)G1'文法，abb的推導(dǎo)序列是：

S=>Bb=>Abb=>abb

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

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

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

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

(4)對(duì)串a(chǎn)cbd來(lái)說(shuō)，G1,Gr文法都不能產(chǎn)生。

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

。(1)對(duì)于G中每一個(gè)形如ATaB的產(chǎn)生式且A是開(kāi)始符，將其變

為BTa,否則若A不是開(kāi)始符，B-*Aa;

o(2)對(duì)于G中每一個(gè)形如ATa的產(chǎn)生式，將其變?yōu)镾TAa

12(1)

abv

S(S.A)

A力{A,B}P

B

狀態(tài)矩陣是：

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

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

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

記{SO,S1,S3)=qO{S1)=q1{S2S3}=q2{S3}=q3

(2)記{S}=qO{Z}=q1{UR}=q2{SX}=q3{YUR}=q4{XSU}=q5{YURZ]=q6

{ZS}=q7

⑵化簡(jiǎn)后SO和S1作為一個(gè)狀態(tài),S5和S6作為一個(gè)狀態(tài)。

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

15從略。

16從略。

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

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

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

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

所以四者是等價(jià)的。

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

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

r(sr)*表示的正規(guī)式集是r(E,sr,srsr,srsrsr,???)

={r,rsr,rsrsr,rsrsrsr,

所以兩者等價(jià)。

18寫(xiě)成方程組

S=aT+aS(1)

B=cB+c(2)

T=bT+bB(3)

所以B=c*cT-b*bc*c

S=a*ab*bc*c

?G1：

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

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⑸

可得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

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

?從略。

21從略。

其余從略。

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

%{

#incIude<stdio.h>

#include<string.h>

#incIude<ctype.h>

#define0N1

#defineTW2

#defineTHRE3

#defineTE10

#defineTWENT20

#defineHUNDRE100

#defineWHITE9999

%)

upper[A-Z]

%%

ONEreturnON;

TWOreturnTW;

THREEreturnTHRE;

TENreturnTE;

TWENTYreturnTWENT；

HUNDREDreturnHUNDRE;

""+|\treturnWHITE;

\nreturnO;

%%

main(intargc,char*argv[])

(

intc,1=0;

chartmp[30];

if(argc==2)

(

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

(

printf("can'topen%s\n",argv[11);exit(0);

}

)

while((c=yyIex())!=0)

(

switch(c)

(

caseON:

c=yylex();

if(c~0)goto{i+=1;IabeI;}

c二yylex();

if(c=HUNDRE)

i+=100;

eIsei+=1;

break;

caseTW:c=yylex();

c二yylex();

if(c二二HUNDRE)

i+=200;

eIsei+=2;

break;

caseTWENT:i+=20;

break;

caseTE:i+=10;

break;

default:break;

)

}/*whiIe*/

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

return;

1

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

.此正規(guī)式的長(zhǎng)度是2n

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

25從略。

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

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

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

?由’和，括住的，中間由兩個(gè)''或者非'和\n組成的任意次的字符串。

如'，，，，'bb',，def，,，，，，，，等等

270[Xx][0-9]*[a-fA-F]*|[0-9]+|(\J

([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參考程序如下：

%(

#incIude<stdio.h>

#include<string.h>

#incIude<ctype.h>

#defineUPPER2

#defineWHITE3

%!

upper[A-Z]

%%

{upper}+returnllPPER;

\t|""+returnWHITE;

%%

main(intargc,char*argv[])

intc,i;

if(argc==2)

(

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

(

printf("can'topen%s\n",argv[11);exit(0);

}

)

while((c=yylex())!=E0F)

(

if(c==2)

(

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

printf("%c",toIower(yytext[i]));

yytext[0]='\000';

)

if(c==3)

printfC");

eIseprintfyytext);

}

return;

)

yywrapO

return;

)

30從略。

第四章習(xí)題解答

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

?1.解：

(1)ST(S)Z21|0Z21|[SJZ31|[]Z31

AT(S)Z221()Z221[S]Z321[]Z32

BT(S)Z23|0Z231[S]Z33|[]Z33

Z11-*E|AZ11|BZ21

Z12TAZ121BZ22Z13-+AZ131BZ23

Z21Tzi1Z22T￡|Z12

Z23Tzi3Z31Tz21

Z32Tz22Z33TE|Z23

(2)STbZ11|aZ21ATbZ121aZ22

Z11-*E|AZ21Z12TAz22Z21Tsz21Z22Te|SZ22

(3)ST(T)Z11|aZ11|Z11S-4(T)Z12|aZ12|Z12

Z1WE|Z21Z12Tz22Z21T,SZ21Z22TE|,SZ22

?2.解:

S=>AbB1,1.1（表示第1步，用產(chǎn)生式1.1推導(dǎo)，以下同）

=>CAbbB2,2.1

=>edAbbB3,4.1

=>edCAbbB4,2.1

=>ededAbbbB5,4.1

=>edaAbbbB5,4.2(不符合，改寫(xiě)第5步，用4.2)

=>edBfbbB4,2.2

=>edCSdfbbB5,3.1

=>ededSdfbbB6,4.1

nedaSdfbbB6,4.2

=eddfbbB5,3.2

=>eddfbbCSd6,3.1

=>eddfbbedSd7,4.1

=>eddfbbaSd7,4.2

=>eddfbbd6,3.2

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

token_pointervaIueo

(1)文法沒(méi)有左遞歸。

FunctionP：boolean;

Begin

Save；

P:=true;

Ifnext_token="begin”then

Ifnext_token='d'then

Ifnext_token=?then

IfXthen

Ifnext_token=vend"thenreturn;

Restore;

P:=faIse;

End;

FunctionX:booIean;

Begin

Save;

X:二true;

Ifnext_token=?d'then

Ifnext_token=,then

IfXthenreturn;

Restore;

Ifnext_token=,s'then

IfYthenreturn;

Restore;

X:二faIse;

End;

FunctionY:boolean;

Begin

Save;

Y二true;

Ifnext_token=,then

Ifnext_token=,s'then

IfYthenreturn;

Restore;

End;

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

PTbeginSendSTA|CATV:二ECTifEthenS

ETVE'E'T+VE'|eV-41

FunctionP:boolean;

Begin

Save;

P:二true;

Ifnext_token=nbegin”then

IfSthen

Ifnext_token二”end”thenreturn;;

Restore;

P:二faIse;

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:=faIse;

End;

FunctionC:booIean;

Begin

Save;

C:二true;

Ifnext_token="if"then

IfEthen

Ifnext__token=nthen”then

IfSthenreturn;

Restore;

C:二faIse;

End;

FunctionE：boolean;

Begin

Save;

E:二true;

IfVthen

IfEpthenreturn;

Restore;

E:=faIse;

End;

FunctionEp:booIean;

Being

Save;

Ep:二true;

Ifnext_token=,+'then

IfVthen

IfE'thenreturn;

Return;

End;

?4.解：

FIRST集“FOLLOW集“

S—aAB，

f購(gòu)，{#}Q

fgV{￡}Q

。

A—VaVAZvbW｛雜

fg3｛少

B-?bB*-1（皿

?f&/{?

?5.證：因?yàn)槭亲筮f歸文法，所以必存在左遞歸的非終結(jié)符A,及形如AT

a|0的產(chǎn)生式，且aT*Ad.

則first(Ad)Dfirst(B)于0,從而

first(a)nfirst(B)于。，即文法不滿足LL(1)文法條件。得證。

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

可進(jìn)行?，F(xiàn)在，假設(shè)LL(1)文法G是二義性文法，則存在句子a,它有兩

個(gè)不同的語(yǔ)法樹(shù)。即存在著句子a有兩個(gè)不同的最左推導(dǎo)。從而可知，用

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

替換，且均能正確進(jìn)行語(yǔ)法分析，即LL(1)分析動(dòng)作存在不確定性。與

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

?7.解：

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

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

?8.解：

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

S-?bZ11|aZ21A->bZ12|aZ22Z1WbZ111EZ12Tbz12

Z21Tbz111aZ21Z22Tbz121az221E

消除無(wú)用產(chǎn)生式得：S->bZ11|aZ21Z1WbZ111EZ2WbZ11|aZ21

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

所以G'[S]：S->bZ11|aZ21Z11->bZ11|EZ21->bZ11|aZ21

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

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

S->bZ11{#}

TaZ21{a}

Z1WbZ11{#}

TE{E}

Z21-*bZ11{#}

TaZ21{a}

LL⑴分析表為:

ab#

SaZ21bZ11

Z11bZ11E

Z21aZ21bZ11

?9.解：

(1)

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

STSaB

{#,a,c)

TbB

ATS

{c}

Ta{a}

B->Ac{a,b}{#,a,c}

(2)將STSaB||bB改寫(xiě)為STbBS',S'TaBS'|3,可驗(yàn)證，新文法是LL(1)

的。

?10.解：

?1)為方便書(shū)寫(xiě)，記：〈布爾表達(dá)式＞為人，〈布爾因子)為B,＜布爾二次量〉

為C,〈布爾初等量＞為口，原文法可以簡(jiǎn)化為：

A-4AVB|BBTBAC|CCT-|D|DDT(A)|true|false,

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

ATBA'A'-4VBA'|U)BTCB',

B'-4ACB,|3CT-)D|DDT(A)|true|faIse

⑵略

?證：若LL(1)文法G有形如BTaAAb的產(chǎn)生式，且AT+￡及AT*ag,根據(jù)

FIRST集FOLLOW集的構(gòu)造算法可知，F(xiàn)IRST(A)中一切非E加到FOLLOW(A)

中，則aWFOLLOW(A)；又因?yàn)閍WFIRST(ag),所以兩集合相交非空,因此，

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

?解:

⑴

SA(a)b

S==

A=<=<

仁=<<<

<

a>=<?

>

)>??

b?

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

(2)

SRTOAa,

S>=

R=

T>

(<=?<<

)>>

A>>

a>>

,<=<<<

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

(3)

SR(a,)

S=?

R?

仁?

a?

尸?

)?

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

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

SZT#i()

S

Z==

T>>

#=<?

I>>

（=<?

）>>

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

?解：

SA/A

s>>

A—<—

<

/>>

a>>

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

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

量簡(jiǎn)單），使得對(duì)文法的輸入比較簡(jiǎn)單的同時(shí)（需要把輸入轉(zhuǎn)化為計(jì)算機(jī)

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

矩陣（=,LEAD和LAST）。

?證明：設(shè)xjxj+1...xi是滿足條件xj-1<xj=xj+1=...=xi>xi+1的最左子

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

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

同理,xi為某產(chǎn)生式的尾符號(hào)。即存在產(chǎn)生式UTxjxj+1...xi設(shè)ST*aUb

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

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

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

?解：為描述方便，用符號(hào)表示各非終結(jié)符：D=<變量說(shuō)明>,L=<變量表>，V=

<變量）,T=<類型>，a=VAR,則消去V,并采用分層法改寫(xiě)文法，得到：DT

aW:T;WTLLTL,i|iT-*r|n|b|c

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

DWTLa:;ir|n|b|c

D

W=

T=

L>

a=<<

<

>>>

r|n|b|c>

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

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

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

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

再進(jìn)行一步推導(dǎo)，得STkdAbTdub,其中，ATu是文法中的產(chǎn)生式，由定

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

得證。

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

結(jié)符相鄰的情況。不失一般性，設(shè)其形為UTxAB%x,yCV*,由于文法不

含無(wú)用產(chǎn)生式，則必存在含有U的句型dUb,即存在推導(dǎo)ST*dUbTdxAByb.

得證。

?文法為：E—ETA|AATA*T|A/T|TTTT+V|T-V|VVTi|(E)

?解：

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

-*()i#

?

-<><>

?

*><X

<

(?<=<

)?>>

l?>>

#?<<

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

(3)改寫(xiě)方法：

?將ETE-T中的減號(hào)與FT-P中的賦值運(yùn)算符強(qiáng)制規(guī)定優(yōu)先關(guān)系；

?或者將F-P中的賦值運(yùn)算符改為別的符號(hào)來(lái)表示；

?(1)證明：由設(shè)句型a=-Ua…中含a的短語(yǔ)不含U,即存在A,K=>*ay,

則a可歸約為a="Ua…U*…UA…=b,b是G的一個(gè)句型，這與G是算符

文法矛盾，所以，a中含有a的短語(yǔ)必含U。

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

?證：(1)對(duì)于a="aU…是句型,必有ST*a(=…all…)T+…ab….即在歸

約過(guò)程中，b先于a被歸約，從而，a<b.對(duì)于⑵的情況類似可以證明。

?證明略.

?證明略.

?證明略。

?證：(1)用反證法。設(shè)沒(méi)有短語(yǔ)包含b但是不包含a,則a,b一定同時(shí)位

于某個(gè)短語(yǔ)中，從而必使得a,b同時(shí)位于同一產(chǎn)生式的右部，所以a=b,

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

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

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

存在bx???by是素短語(yǔ)，其中1<x或者y〈n之一成立。因素短語(yǔ)是短

語(yǔ)，根據(jù)短語(yǔ)定義，則必有：1<xTbx-1〈bx或y〈nTby>by+1,與bx-kbx

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

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

易知道u是句型a的素短語(yǔ)。

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

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

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

?解：

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

+*T()i#

+>?<><>

*?<<><>

T?<<><>

(?<<=<

)?>>>

I?>>>

#?<<<

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

+*T()i#

F3551771

G2466161

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

zbMLa()

f1567747

g1654667

解：

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

□a#

[>=

]>>

?

a<

?

#?<

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

g5561

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

?略。

35解:

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

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

狀態(tài)項(xiàng)目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)

I0S'T?SS11

ST?aSbaI2

S—?aSc

ST-ab

11S'TS?

I2STa?SbsI3

STa?ScaI2

STa?bbI4

ST?aSb

ST?aSc

ST?ab

I3S—aS?bbI5

STaS?ccI6

I4STab?

I5STaSb?

I6S->aSc?

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

狀態(tài)項(xiàng)目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)

IOS'T?Ss11

ST?cAcI

ST,ccB*

11S'TS?

I2STc?AAI3

STc?cBcI4

AT?cAaI5

AT?a

I3STcA?

I4STcc-BBI6

ATc?AAI5

BT?ccBcI7

BT?bbI8

AT,cAaI5

AT?a

I5ATa?

I6STccB?

I7BTc?cBcI9

ATc?AA110

AT?cAaI5

AT?a

I8B—b?

I9BTcc?BB111

ATc?AA110

BT?ccBcI7

BT?bbI8

AT?cAaI5

AT?a

110ATcA?

111BTccB?

所求的LR(O)項(xiàng)目規(guī)范族C={IO,11,111}

(3)

狀態(tài)項(xiàng)目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)

IOS'T?Ss11

ST?aSSbcI2

ST?aSSSaI3

ST?c

11S'TS?

I2STc?

I3STa?SSbsI4

STa?SSSc12

ST?aSSba13

ST?aSSS

ST?c

14STaS?Sbs15

STaS?SSc12

S