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

第一章習(xí)題解答.解:源程序是指以某種程序設(shè)計(jì)語言所編寫的程序。目標(biāo)程序是指編譯程序（或解釋程序）將源程序處理加工而得的另ー種語言（目標(biāo)語言）的程序。翻譯程序是將某種語言翻譯成另ー種語言的程序的統(tǒng)稱。編譯程序與解釋程序均為翻譯程序,但二者工作方法不同。解釋程序的特點(diǎn)是并不先將高級(jí)語言程序全部翻譯成機(jī)器代碼,而是每讀入一條高級(jí)語言程序語句,就用解釋程序?qū)⑵浞g成一段機(jī)器指令并執(zhí)行之,然后再讀入下一條語句繼續(xù)進(jìn)行解釋、執(zhí)行,如此反復(fù)。即邊解釋邊執(zhí)行,翻譯所得的指令序列并不保存。編譯程序的特點(diǎn)是先將高級(jí)語言程序翻譯成機(jī)器語言程序，將其保存到指定的空間中,在用戶需要時(shí)再執(zhí)行之。即先翻譯、后執(zhí)行。.解:一般說來,編譯程序主要由詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序、代碼優(yōu)化程序、目標(biāo)代碼生成程序、信息表管理程序、錯(cuò)誤檢查處理程序組成。.解:C語言的關(guān)鍵字有:autobreakcasecharconstcontinuedefaultdodoubleelseenumexternfloatforgotoifintlongregisterreturnshortsignedsizeofstaticstructswitchtypedefunionunsignedvoidvolatilewhile。上述關(guān)鍵字在C語言中均為保留字。.解:C語言中括號(hào)有三種:。,口，〇〇其中，｛｝用于語句括號(hào);口用于數(shù)組;〇用于函數(shù)（定義與調(diào)用）及表達(dá)式運(yùn)算（改變運(yùn)算順序）。C語言中無END關(guān)鍵字。逗號(hào)在C語言中被視為分隔符和運(yùn)算符,作為優(yōu)先級(jí)最低的運(yùn)算符,運(yùn)算結(jié)果為逗號(hào)表達(dá)式最右側(cè)子表達(dá)式的值（如：（a,b,c,d）的值為d）〇.略第二章習(xí)題解答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個(gè).構(gòu)造產(chǎn)生下列語言的文法{anbn|n20}解:對(duì)應(yīng)文法為G(S)=({S},{a,b},{S-eIaSb},S){anbmcpIn,m,p20}解:對(duì)應(yīng)文法為G(S)=({S,X,Y},{a,b,c},{S-aS|X,X-bX|Y,Y-cY|e},S){an#bn|n》O}U{cn#dn|n20}解:對(duì)應(yīng)文法為G(S)=({S,X,Y},{a,b,c,d,#},{S-X,S-Y,X-aXb|Y一cYd|#},S){w#wr#w?{0,1}*,wr是w的逆序排列}解：G(S)=({S,W,R},{0,1,#},{ST#,W-OWO|1W1|#},S)(5)任何不是以〇打頭的所有奇整數(shù)所組成的集合解：G(S)=({S,A,B,I,J},{-,0,1,2,3,4,5,6,7,8,9},{S-*J|IBJ,B-OB|lB|e,I-J|2⑷6|8,Jdl|3|5|7|9},S)(6)所有偶數(shù)個(gè)0和偶數(shù)個(gè)1所組成的符號(hào)串集合解：對(duì)應(yīng)文法為S-OAllB|e,A—OS|1CB-*OC|ISC-*1A|OB.描述語言特點(diǎn)S—lOSOSfaAA—bAA—a解:本文法構(gòu)成的語言集為:L(G)={(10)nabmaOnln,m20}。SfSSSflAOAflAOAfe解：L(G)={lnlOnlln20n2InmOnm|nl,n2,…,nm20;且nl,n2,…nm不全為零}該語言特點(diǎn)是：產(chǎn)生的句子中,〇、1個(gè)數(shù)相同,并且若干相接的1后必然緊接數(shù)量相同連續(xù)的0。S—lASfBOA-1AA-*CB-*BOB-CC-*1C0C—e解:本文法構(gòu)成的語言集為：L(G)={lplnOn|pel,neO}U{lnOnOq|q?l,n20},特點(diǎn)是具有IplnOn或InOnOq形式,進(jìn)ー步,可知其具有形式InOmn,m20,且n+m>OoS—bAdcA—AGSG-eA—a解:可知,S=>…=〉baSndcn20該語言特點(diǎn)是：產(chǎn)生的句子中,是以ba開頭de結(jié)尾的串,且ba、de個(gè)數(shù)相同。S—aSSS—a解:L(G)={a(2n-l)|n2l}可知:奇數(shù)個(gè)a.解：此文法產(chǎn)生的語言是：以終結(jié)符al、a2-an為運(yùn)算對(duì)象,以ハ、、、?為運(yùn)算符,以［ヽ］為分隔符的布爾表達(dá)式串. 5.1解：由于此文法包含以下規(guī)則：AA-e,所以此文法是〇型文法。5.2證明：略6.解：(1)最左推導(dǎo):く程序＞Tく分程序〉T〈標(biāo)號(hào)〉:く分程序〉TL：く分程序〉TL：く標(biāo)號(hào)〉:く分程序〉TL：L:く分程序〉TL：L：く無標(biāo)號(hào)分程序〉TL：L:く分程序首部〉;く復(fù)合尾部〉TL：L：く分程序首部〉:く說明〉;く復(fù)合尾部〉TL：L：beginく說明〉;〈說明〉;く復(fù)合尾部〉TL：L：begind；く說明〉；く復(fù)合尾部〉TL： L： begin d； d; く復(fù)合尾部〉TL： L： begin d； d； く語句〉；〈復(fù)合尾部〉TL： L： begin d； d； s;く復(fù)合尾部.TL： L： begin d； d； s;く語句〉endTL： L： begin d； d； s；send最右推導(dǎo):く程序〉Tく分程序〉Tく標(biāo)號(hào)〉:く分程序〉T〈標(biāo)號(hào)〉：〈標(biāo)號(hào)〉:く分程序〉Tく標(biāo)號(hào)〉：く標(biāo)號(hào)〉：く無標(biāo)號(hào)分程序〉Tく標(biāo)號(hào)):く標(biāo)號(hào)＞：Tく標(biāo)號(hào)》:く標(biāo)號(hào)〉:Tく標(biāo)號(hào)):く標(biāo)號(hào)＞：Tく標(biāo)號(hào)》:く標(biāo)號(hào)〉:Tく標(biāo)號(hào)〉:く標(biāo)號(hào)〉:T〈標(biāo)號(hào)〉:く標(biāo)號(hào)〉:Tく標(biāo)號(hào)〉:く標(biāo)號(hào)〉:Tく標(biāo)號(hào)〉:く標(biāo)號(hào)〉:Tく標(biāo)號(hào)〉:く標(biāo)號(hào)〉:T〈標(biāo)號(hào)〉:く標(biāo)號(hào)〉:Tく標(biāo)號(hào)〉:く標(biāo)號(hào)〉:く分程序首部〉;〈分程序首部〉;く分程序首部〉；く分程序首部〉;く分程序首部〉；く分程序首部〉；く分程序首部〉；begin說明;d；く復(fù)合尾部〉く語句〉;く復(fù)合尾部〉く語句〉;く語句〉;endく語句〉;s；ends；s；end說明;s；s；endd；s；s；ends；s；endbegind；d；s；s；endTく標(biāo)號(hào)〉:L：begind；d；s；s；endTL：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=>aacbaabacbadcd不是文法G[S]中的句子因?yàn)槲姆ㄖ械木渥硬豢赡芤苑墙K結(jié)符d結(jié)尾aacbccb不是文法G[S]中的句子可知,aacbccb僅是文法G[S]的?個(gè)句型的,一部分,而不是?,個(gè)句子。aacabcbcccaacdca不是文法G[S]中的句子因?yàn)榻K結(jié)符d后必然要跟終結(jié)符a,所以不可能出現(xiàn)…de…這樣的句子。aacabcbcccaacbca不是文法G[S]中的句子由(1)可知:aacb可歸約為S,由文法的產(chǎn)生式規(guī)則可知,終結(jié)符c后不可能跟非終結(jié)符S,所以不可能出現(xiàn)…caacb…這樣的句子。.證明:用歸納法于n,n=l時(shí),結(jié)論顯然成立。設(shè)n=k時(shí)，對(duì)于a1a2...akT*b,存在Bi：i=l,2,..,k,aiT*bi成立，現(xiàn)在設(shè)a1a2...akak+lT*b,因文法是前后文無關(guān)的,所以ala2…ak可推導(dǎo)出b的ー個(gè)前綴b‘，ak+1可推導(dǎo)出b的ー個(gè)后綴ユ”(不妨稱為bk+1)。由歸納假設(shè),對(duì)于b',存在Bi：i=l,2,..,k,b'=B1B2...Bk,使得aiT*bi成立,另タト,我們有ak+lT*b"(=bk+1)〇即n=k+l時(shí)亦成立。證畢。.證明:(1)用反證法。假設(shè)a首符號(hào)為終結(jié)符時(shí),B的首符號(hào)為非終結(jié)符。即設(shè):a=a3；B=A3'且a=>*B。由題意可知：a=a3T…TA3,=B,由于文法是CFG,終結(jié)符a不可能被替換空串或非終結(jié)符,因此假設(shè)有誤。得證;

（2）同（1）,假設(shè):B的首符號(hào)為非終結(jié)符時(shí),a首符號(hào)為終結(jié)符。即設(shè):a=a3；B=A3,且a=a3T…TA3，=B,與（1）同理,得證。.證明:因?yàn)榇嬖诰渥?abc,它對(duì)應(yīng)有兩個(gè)語法樹（或最右推導(dǎo)）：STABTAbcTabcSTDCTDcTabc所以,本文法具有二義性。.解：（1）STABTAaSbTAacbTbAacbTbbAacbTbbaacb上面推導(dǎo)中,下劃線部分為當(dāng)前句型的句柄。對(duì)應(yīng)的語法樹為:全部的短語:全部的短語:第??個(gè)a(al)是句子bbaacb相對(duì)于非終結(jié)符A(Al)(產(chǎn)生式A?a)的短語(直接短語)；blal是句子bbaacb相對(duì)于非終結(jié)符A2的短語;b2blal是句子bbaacb相對(duì)于非終結(jié)符A3的短語:c是句子bbaacb相對(duì)于非終結(jié)符S1(產(chǎn)生式S?c)的短語(直接短語)；a2cb3是句子bbaacb相對(duì)于非終結(jié)符B的短語;b2blala2cb3是句子bbaacb相對(duì)于非終結(jié)符S2的短語;注:符號(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)的語法樹是:(3)解:iii*i+t對(duì)應(yīng)的語法樹略。最右推導(dǎo)：ETT=〉F=〉FPfTFEtTFET+fTFEF+tTFEP+fTFEi+tTFTi+fTFTF*i+tTFTP*i+tTFTi*i+tTFFi*i+tTFPi*i+fTFii*i+fTPii*i+tTiii*i+t12.證明:充分性:當(dāng)前文法下的每一符號(hào)串僅有一個(gè)句柄和一個(gè)句柄產(chǎn)生式T對(duì)當(dāng)前符號(hào)串有唯一的最左歸約T對(duì)每一步推導(dǎo)都有唯一的最右推導(dǎo)T有唯一的語法樹。必要性:有唯一的語法樹T對(duì)每一步推導(dǎo)都有唯?的最右推導(dǎo)T對(duì)當(dāng)前符號(hào)串有唯一的最左歸約T當(dāng)前文法下的每ー符號(hào)串僅有一個(gè)句柄和一個(gè)句柄產(chǎn)生式.化簡(jiǎn)下列各個(gè)文法⑴解：SfbCACdAfcSA丨cCCC—cS|c(2)解：S-aABIfA|gA—e|dDAD—eAB—f(3)解:S—ac.消除下列文法中的￡產(chǎn)生式(1)解:S-*aAS|aS|bA-^cS(2)解：S-*aAAIaAaA-*bAc|bedAe\de.消除下列文法中的無用產(chǎn)生式和單產(chǎn)生式(1)消除后的產(chǎn)生式如下:S—aBIBCBfDBIbC-*bD-*bIDB(2)消除后的產(chǎn)生式如下：S-SA|SB)〇!(S)|[]|[S]A-()|(S)|[]|[S]Bd[]|[S](3)消除后的產(chǎn)生式如下：E—E+T|T*F|(E)|PtF|iTT*FI(E)IPfFIiFfPtFI(E)IiPTE)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,aSVT+)等價(jià)于Gl:A—aB或A—a(aGVT+)?G1的產(chǎn)生式中AfaB,則B也有B—bC,C^cD….所以有A-abc-B,,a,b,c-GVT,B,GVN所以與G等價(jià)。2)G的產(chǎn)生式AfaB,aSVT+,因?yàn)閍是字符串,所以肯定存在著一個(gè)終結(jié)符a,使A—aB可見兩者等價(jià),所以由此文法產(chǎn)生的語言是正規(guī)語言。56根據(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)其對(duì)應(yīng)的右線性文法是:A—OD,B—OA,B—IC,C-11IF,C-11OA,F-010E|1A,D-OB|IC,E—IC|0B(2)最短輸入串011(3)任意接受的四個(gè)串011,0110,0011,000011(4)任意以1打頭的串.8從略。(2)相應(yīng)的3型文法S-*aAS—bSA—aAA—bBB—a|aBB—b|bBS-*aA|aS^bBB—aB|bBA-aBA—b|bASfaAS—bBA—bAA^aCB^aBB—bCC^a|aCC—b|bCS—bSSfaAA-*aCA—bBB—aBB—bCC-*a|aCC-*b|bC(3)用自然語言描述輸入串的特征(i)以任意個(gè)(包括〇)b開頭,中間有任意個(gè)(大于1)a,跟ー個(gè)b,還可以有一個(gè)由a,b組成的任意字符串(ii)以a打頭,后跟任意個(gè)(包括。)b(iii)以a打頭,中間有任意個(gè)(包括0)b,再跟a,最后由一個(gè)a,b所組成的任意串結(jié)尾或者以b打頭,中間有任意個(gè)(包括〇)a,再跟b,最后由一個(gè)a,b所組成的任意串結(jié)尾(iv)以任意個(gè)(包括。)b開頭,中間跟aa最后由??個(gè)a,b所組成的任意串結(jié)尾或者以任意個(gè)(包括。)b開頭,中間跟ab后再接任意(包括。)a再接b,最后由一個(gè)a,b所組成的任意串結(jié)尾10(1)G1的狀態(tài)轉(zhuǎn)換圖:G2的狀態(tài)轉(zhuǎn)換圖:a+G1等價(jià)的左線性文法:S-*Bb,S—Dd,D—C,B-Db,C—Be,B-Ab,B-e,A-aG2等價(jià)的右線性文法:S-*dD,S—aB,D—C,B->abC,B—bB,B-*bA,B/￡,C-*cA,A—a(3)對(duì)G1文法,abb的推導(dǎo)序列是:S=>aA=>abB=>abb對(duì)Gl'文法,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)ebd來說,Gl,Gr文法都不能產(chǎn)生。11將右線性文法化為左線性文法的算法：(1)對(duì)于G中每?個(gè)形如A-aB的產(chǎn)生式且A是開始符,將其變?yōu)锽—a,否則若A不是開始符,B-Aa;(2)對(duì)于G中每ー個(gè)形如A-a的產(chǎn)生式,將其變?yōu)镾-Aa12(1)as(S.A)OA申{ムB狀態(tài)矩陣是:{B}市メ記[S]=qO[B]=ql[AB]=q2[SA]=q3,最小化和確定化后如圖(2)記[S]=qO,[A]=ql,[BS]=q2最小化和確定化后的狀態(tài)轉(zhuǎn)換圖如下13(1)將具有。動(dòng)作的NFA確定化后,其狀態(tài)轉(zhuǎn)換圖如圖:記{SO,Sl,S3}=qO{Sl}=ql{S2S3}=q2{S3)=q3

RZ}=q6從略狀態(tài)轉(zhuǎn)換圖如圖15從略16從略1)?RZ}=q6從略狀態(tài)轉(zhuǎn)換圖如圖15從略16從略1)?表示的正規(guī)式集是｛|rr?表示的正規(guī)式集是｛記{S}=qO{Z)=ql{UR}=q2{SX)=q3{YUR}=q4{XSU}=q5⑵化簡(jiǎn)后SO和SI作為一個(gè)狀態(tài),S5和S6作為一個(gè)狀態(tài)(r*)*=r*={e,r,rr,rrr,???所以四者是等價(jià)的。(2)(rs)*1?表示的正規(guī)式集是{￡,rs,rsrs,rsrsrs,…}r={r,rsr,rsrsr,rsrsrsr,…}r(sr)?表示的正規(guī)式集是r{e,sr,srsr,srsrsr,??)={r,rsr,rsrsr,rsrsrsr,,?,}所以兩者等價(jià)。18寫成方程組S=aT+aS(1)B=cB+c(2)T=bT+bB(3)所以B=c*cT=b*bc*cS=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)把它打入(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)*(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*ab|bA=(ab*ab|b)c+ab*bS=(ab*ab|b)ca+ab*ba+ab*=(ab*ab|b)ca|ab*ba|ab*20.識(shí)別此語言的正規(guī)式是S='LABEL'd(d|,d)*;.從略。21從略。22構(gòu)造NFA其余從略。23下面舉ー個(gè)能夠識(shí)別1,2,3,10,20,100的例子,讀者可以推而廣之。%(#include<stdio.h>ftinclude<string.h>Sinclude<ctype.h>SdefineONIdefineTW2defineTHRE3^defineTE10defineTWENT20ttdefineHUNDRE100SdefineWHITE9999%)upper[A-Z]%%ONEreturnON;TWOreturnTW;THREEreturnTHRE;TENreturnTE;TWENTYreturnTWENT;HUNDREDreturnHUNDRE;zz1\treturnWHITE;\nreturnO;%%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[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;)}/*while*/label:printf(*%d\n*,i);return;)24(1)Dn表示的正規(guī)集是長(zhǎng)度為2n任意a和b組成的字符串。此正規(guī)式的長(zhǎng)度是2n用來識(shí)別Dn的DFA至多需要2n+l個(gè)狀態(tài)。25從略。26(1)由。括住的,中間由任意個(gè)非{組成的字符串,如{},{}},{a},{defg}等等。(2)匹配一行僅由一個(gè)大寫字母和一個(gè)數(shù)字組成的串,如A1,F8,Z2等。(3)識(shí)別、r\n和除數(shù)字字符外的任何字符。由‘和‘括住的,中間由兩個(gè)‘‘或者非'和\n組成的任意次的字符串。如''''，'a','bb','def',''''''等等270[Xx][0-9]*[a-fA-F]*|[0-9]+|(\'([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參考程序如下:%(#include<stdio.h>#include<string.h>Sinclude<ctype.h>#defineUPPER2#defineWHITE3%}upper[A-Z]%%{upper}+returnUPPER;\t|""+returnWHITE;%%main(intargc,char*argv口)(intc,i;if(argc==2){if((yyin=fopen(argv[1],/zr/z))==NULL){printf("can'topen%s\n",argv[11);exit(〇);))while((c=yylex())!=EOF)if(c==2)for(i=0;yytext[i];i++)printf(“祝"，tolower(yytext[i]));yytext【0]='\00〇’;)if(c==3)printf("");elseprintf(z，%s",yytext);)return;)yywrap()(return;)30從略。第四章習(xí)題解答第四章習(xí)題參考答案?1.解:(1)S-*(S)Z21|()Z21|[S]Z31|[]Z31A—(S)Z221()Z221[S]Z321[]Z32B~(S)Z231()Z231[S]Z331ロZ33ZU-*e|AZ11|BZ21Z12-*AZ12|BZ22Z13-*AZ13|BZ23Z21—Z11Z22-e|Z12Z23fzi3Z31fz21Z32fz22Z33-e|Z23S-*bZll|aZ21A-bZ12|aZ22Zl-￡IAZ21Z12fAz22Z21fsz21Z22f￡|SZ22(3)S-(T)Z11IaZllIZUS-(T)Z12|aZ12|Z12Zllf￡IZ21Z12fz22Z21f,SZ21Z22f￡|,SZ22?2.解:S=>AbBl,L1(表示第1步,用產(chǎn)生式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表示restoretokenpointervalue。(1)文法沒有左遞歸。FunctionP:boolean;BeginSave;P:二true;Ifnext_token=vbegin”thenIfnext_token二'd'thenIfnext一token='；'thenIfXthenIfnexttoken二"end"thenreturn;Restore;P:二false;End;FunctionX:boolean;BeginSave;X:二true;Ifnext_token='d'thenIfnext_token二'；'thenIfXthenreturn;Restore;Ifnext_token=,s'thenIfYthenreturn;Restore;X:=false;End;FunctionY:boolean;BeginSave;Y=true;Ifnext_token=';'thenIfnext_token='s'thenIfYthenreturn;Restore;End;(2)消去文法左遞歸,并記為:PfbeginSendS—A|CAfV:二ECfifEthenSE-VE'E,一+VE'I￡V—IFunctionP:boolean;BeginSave;P:=true;Ifnext_token="begin”thenIfSthenIfnext_token=vend"thenreturn;;Restore;P:=false;End;FunctionA:boolean;BeignSave;A:=true;IfVthenIfnext_token=n:="thenIfEthenreturn;Restore：A:二flase;End;FunctionS:boolean;BeignSave;S:二true;IfAthenreturn;Restore;IfCthenreturn;Restore;S:=false;End;FunctionC:boolean;BeginSave;C:=true;Ifnext_token=wif"thenIfEthenIfnext_token=wthen"thenIfSthenreturn;Restore;C:=false;End;FunctionE:boolean;BeginSave;E:=true;IfVthenIfEpthenreturn;Restore;E:=false;End;FunctionEp:boolean;BeingSave;Ep:=true;Ifnext_token=,+'thenIfVthenIfE'thenreturn;Return;End;?4.解:dFIRST集“FOLLOWS—aAB，」QWfbA<-｛皿｛桁スfgV(少A-*aAb*-'⑸，{久#}“f￡バ｛少bBメ(山一￡バ｛屮〈ワ5.證:因?yàn)槭亲筮f歸文法,所以必存在左遞歸的非終結(jié)符A,及形如A-aIB的產(chǎn)生式,且aT*Ad.則first(Ad)Afirst(B)#3,從而first(a)nfirst(B)W3,即文法不滿足LL(1)文法條件。得證。6.證:LL(1)文法的分析句子過程的每ー步,永遠(yuǎn)只有唯一的分析動(dòng)作可進(jìn)行。現(xiàn)在,假設(shè)LL(1)文法G是二義性文法,則存在句子a,它有兩個(gè)不同的語法樹。即存在著句子a有兩個(gè)不同的最左推導(dǎo)。從而可知,用LL(1)方法進(jìn)行句子a的分析過程中的某步中,存在兩種不同的產(chǎn)生式替換,且均能正確進(jìn)行語法分析,即LL(1)分析動(dòng)作存在不確定性。與LL(1)性質(zhì)矛盾。所以,G不是LL(1)文法。7.解:(DD產(chǎn)生式兩個(gè)候選式fD和f的first集交集不為空,所以不是LL(1)的。(2)此文法具有左遞歸性,據(jù)第5題結(jié)論,不是LL(1)的。8.解:(1)消除左遞歸性,得:S-bZl11aZ21A^bZ12|aZ22Zll-*bZl11eZ12fbz12

Z21-*bZll|aZ21Z22-*bZ12|aZ22|e消除無用產(chǎn)生式得:S^bZU|aZ21ZU-bZll|￡Z21fbz11|aZ21此文法已滿足LL(1)文法的三個(gè)條件,所以G'[S]:S^bZU|aZ21Zll^bZU|eZ21-bZU|aZ21G’文法的各非終結(jié)符的FIRST集和FOLLOW集:產(chǎn)生式FIRST集FOLLOW集S^bZll{#}faZ21{a}Zll-bZll悔｝一E{￡}Z21fbz11{#}faZ21{a}LL(1)分析表為ab#S aZ21bZllZllbZHEZ21 aZ21bZll?9.解:(1)產(chǎn)生式first集follow集SfSaB{#,a,c}bBA—S{c}-a{a}BfAc{a,b}{#,a,c}(2)將SfSaB|bB改寫為S-bBS',S'faBS’丨3,可驗(yàn)證,新文法是LL(1)的。?10.解:?1)為方便書寫,記:く布爾表達(dá)式》為A,く布爾因子〉為B,く布爾二次量〉為C,〈布爾初等量〉為D,原文法可以簡(jiǎn)化為:A^AVB|BB-*BAC|CC^qD|DD^(A)|true|false,顯然,文法含有左遞歸,消去后等價(jià)LL(1)文法為:A-BA'A'—VBA'|3B—CB',B'一-CB'|3Cf-]D|DDf(A)|true|false⑵略?證:若LL(1)文法G有形如B-aAAb的產(chǎn)生式,且AT+￡及AT*ag,根據(jù)FIRST集FOLLOW集的構(gòu)造算法可知,FIRST(A)中一切非e加到FOLLOW(A)中,flljaeFOLLOW(A)；又因?yàn)閍GFIRST(ag),所以兩集合相交非空,因此,G不是LL(I)文法;與前提矛盾，假設(shè)不成立,得證。?解:SA(a)bS==A=<=<(==?<<a>=<?>)>??b?不是簡(jiǎn)單優(yōu)先文法。SRT()Aa,TOC\o"1-5"\h\zS > =R =T >(<=?<<) > >A > >a > >,<=<<<是簡(jiǎn)單優(yōu)先文法。SR(a,)S=?R?(=?a?,=?)?是簡(jiǎn)單優(yōu)先文法。〇首先消去無用產(chǎn)生式Z-E,Z-E+TSZT#i()SZ==T >>#=<?I >>(=<?)>>化簡(jiǎn)后的文法是簡(jiǎn)單優(yōu)先文法;?解:SA/ATOC\o"1-5"\h\zS > >A= < =</ > >a > >A和/之間同時(shí)有關(guān)系二和く,所以不是簡(jiǎn)單優(yōu)先文法:?提示:分析教材中給出的算法,選擇ー種合適的表示給定文法的方法(盡量簡(jiǎn)單),使得對(duì)文法的輸入比較簡(jiǎn)單的同時(shí)(需要把輸入轉(zhuǎn)化為計(jì)算機(jī)語言表示,這種轉(zhuǎn)化應(yīng)該盡量簡(jiǎn)單),能夠比較簡(jiǎn)單地構(gòu)造3個(gè)基本關(guān)系矩陣(=,LEAD和LAST)〇?證明:設(shè)xjxj+L..xi是滿足條件xj-1くxj=xj+l=...=xi>xi+l的最左子串。由=關(guān)系的定義,可知xjxj+l...xi必出現(xiàn)在某產(chǎn)生式的右部中。又因xj-Kxj可知xj-1與xj不處于同一產(chǎn)生式,且xj是某右部的首符。同理,xi為某產(chǎn)生式的尾符號(hào)。即存在產(chǎn)生式U-xjxj+l...xi設(shè)ST*aUb其中，aT*...xj-1,bT*xi+1...對(duì)于aUb可構(gòu)造ー語法樹,并通過對(duì)其剪枝(歸約)，直到U出現(xiàn)在句柄中。從而xjxj+l...xi必為句柄。反之,若xjxj+l...xi是句柄,由簡(jiǎn)單優(yōu)先關(guān)系的定義,必滿足上述條件。解:為描述方便,用符號(hào)表示各非終結(jié)符:D=く變量說明》,LX變量表〉,V=く變量〉,T=く類型〉,a=VAR,則消去V,并采用分層法改寫文法，得到:D-aW:T;W-LL^L,i|iT-*r|n|b|c其全部簡(jiǎn)單優(yōu)先關(guān)系是：DWTLa: ; ,ir|n|b|cDTOC\o"1-5"\h\zW =T =L > =a = < <:=<,>>>=ir|n|b|c >是簡(jiǎn)單優(yōu)先文法。證：設(shè)STna,我們對(duì)n用歸納法,證明a不含兩個(gè)非終結(jié)符相鄰情況。n=l時(shí),STa,即S-a是文法的產(chǎn)生式,根據(jù)定義,它不含上述情況。設(shè)n=k時(shí),上述結(jié)論成立,且設(shè)STkdAb,由歸納假設(shè),A兩側(cè)必為終結(jié)符。我們?cè)龠M(jìn)行ー步推導(dǎo),得STkdAbTdub,其中,A-u是文法中的產(chǎn)生式,由定義,u中不含兩個(gè)非終結(jié)符相鄰情況，從而dub兩個(gè)非終結(jié)符相鄰情況。得證。證：由于G不是算符文法,G中至少有一個(gè)產(chǎn)生式,其右部含有兩個(gè)非終結(jié)符相鄰的情況。不失一般性,設(shè)其形為U-xABy,x,yGV*,由于文法不含無用產(chǎn)生式,則必存在含有U的句型dUb,即存在推導(dǎo)SPMUbTdxAB^b.得證。文法為:E^EtAIAAfA*T|A/T|TT-*T+V|T-V|VV-*i|(E)解:(1)構(gòu)造算符優(yōu)先矩陣:-*()i#->><>く〉?>*><><<(?<=<)?>>I?>>#?<<(2)在(-,-)、(-,*)和(*,-)處有多重定義元素,不是算符優(yōu)先文法;(3)改寫方法:?將E-E-T中的減號(hào)與F-—P中的賦值運(yùn)算符強(qiáng)制規(guī)定優(yōu)先關(guān)系;.或者將F-P中的賦值運(yùn)算符改為別的符號(hào)來表示;?(1)證明:由設(shè)句型a=“Ua…中含a的短語不含U,即存在A,A=〉?ay,則a可歸約為a="Ua…U*…UA…=b,b是G的ー個(gè)句型,這與G是算符文法矛盾,所以,a中含有a的短語必含U。(2)的證明與(1)類似,略。?證:(1)對(duì)于a="aU…是句型,必有ST*a(=…aU…)T+…ab….即在歸約過程中,b先于a被歸約,從而,a<b.對(duì)于(2)的情況類似可以證明。.證明略..證明略..證明略。證:(1)用反證法。設(shè)沒有短語包含b但是不包含a,則a,b一定同時(shí)位于某個(gè)短語中,從而必使得a,b同時(shí)位于同一產(chǎn)生式的右部,所以a=b,與G是算符優(yōu)先文法(=與く不能并存)矛盾。(2)、(3)類似可證。證;只要證u中不含有除自身以外的素短語。設(shè)有這樣的素短語存在,即存在bx???by是素短語,其中ICx或者yくn之一成立。因素短語是短語，根據(jù)短語定義，則必有:1くxTbx-1くbx或yくnTby>by+l,與bxT=bx及by=by+l矛盾,得證。提示:根據(jù)27題的結(jié)論,只要證u是句型a的短語,根據(jù)=關(guān)系的定義容易知道u是句型a的素短語。證：與28題的不同點(diǎn)只是aO,an+l可以是‘#',不影響結(jié)論。證：設(shè)不能含有素短語,則只能是含有短語(不能含有終結(jié)符號(hào)),則該短語只能含有一個(gè)非終結(jié)符號(hào),否則不符合算符文法定義,得證。解:(1)算符優(yōu)先矩陣:+*t()i#+>?<>〇*?<<>〇t?<<>〇(?<<=<)?> >>I?> >>#?<<<(2)用Floyd方法將優(yōu)先矩陣線性化得到得的優(yōu)先函數(shù)為:+*t()i#F3551771G2466161?解:用Floyd方法對(duì)已知的優(yōu)先矩陣構(gòu)造的優(yōu)先函數(shù)為:zbMLaOfl567747gl654667?解:(1)優(yōu)先矩陣如下:□a#[>=]>>?a<?#?<(2)用Bell方法求優(yōu)先函數(shù)的過程如下:

（3）顯然,文法不是算符優(yōu)先文法,所以不能線性化。?略。?解:（1）識(shí)別全部活前綴的DFA如下:（以表格的形式來表示,很容易可以轉(zhuǎn)化為圖的形式,本章中其余的題目也是采用這種形式表示。）狀態(tài)項(xiàng)目集經(jīng)過的符號(hào)到達(dá)的狀態(tài)S'-?S10S-?aSb S II11Sf?aSc a 12S-**abS'fS?Sfa?SbSfa?ScS 13S-*a?b12a 12Sf?aSbb 14Sf?aScS-**ab13S—aS?b b 15

16SfaS?c16Sfab?S-aSb?S->aSc?(2)識(shí)別全部活前綴的DFA如下:狀態(tài)項(xiàng)目集經(jīng)過的符號(hào)到達(dá)的狀態(tài)S'—?SSII10Sf?cAcIS—?ccB.IIS'—S?S-*c?AA13S-*c?cB12A—?cAc14a15A一?a13/r