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

編譯原理課后答案(第三版蔣立源康慕寧編)第一章習(xí)題解答1解：源程序是指以某種程序設(shè)計(jì)語(yǔ)言所編寫(xiě)的程序。目標(biāo)程序是指編譯程序(或解釋程序)將源程序處理加工而得的另一種語(yǔ)言(目標(biāo)語(yǔ)言)的程序。翻譯程序是將某種語(yǔ)言翻譯成另一種語(yǔ)言的程序的統(tǒng)稱。編譯程序與解釋程序均為翻譯程序，但二者工作方法不同。解釋、執(zhí)行，如此反復(fù)。即邊解釋邊執(zhí)行，翻譯所得的指令序列并不保存。編譯程序的特點(diǎn)之。即先翻譯、后執(zhí)行。2解：一般說(shuō)來(lái)，編譯程序主要由詞法分析程序、語(yǔ)法分析程序、語(yǔ)義分析程序、中間eDC語(yǔ)言中被視為分隔符和運(yùn)算符，作為優(yōu)先級(jí)最低的運(yùn)算符，運(yùn)算結(jié)果為逗號(hào)表達(dá)式最右側(cè)子第二章習(xí)題解答(2)答：26*10=260個(gè)2.構(gòu)造產(chǎn)生下列語(yǔ)言的文法(1){anbn|n≥0}(2){anbmcp|n,m,p≥0}2/121(3){an#bn|n≥0}∪{cn#dn|n≥0}(4){w#wr#|w?{0,1}*,wr是w的逆序排列}(5)任何不是以0打頭的所有奇整數(shù)所組成的集合(6)所有偶數(shù)個(gè)0和偶數(shù)個(gè)1所組成的符號(hào)串集合.描述語(yǔ)言特點(diǎn)以[、]為分隔符的布爾表達(dá)式串e(1)最左推導(dǎo)：<程序>T<分程序>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：begin<說(shuō)明>；<說(shuō)明>；<復(fù)合尾部>TLLbegind復(fù)合尾部>gindd<程序>T<分程序>T<標(biāo)號(hào)>：<分程序>T<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序>T<標(biāo)號(hào)>：<標(biāo)號(hào)>：<無(wú)標(biāo)號(hào)分程序>3/121T<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序首部>；<復(fù)合尾部>T<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序首部>；<語(yǔ)句>；<復(fù)合尾部>T<標(biāo)號(hào)>：<標(biāo)號(hào)>：<分程序首部>；<語(yǔ)句>；<語(yǔ)句>；endT；<語(yǔ)句>；s；end(2)句子L：L：begind；d；s；send的相應(yīng)語(yǔ)法樹(shù)是：4/1215/121d符a，所以不可能出現(xiàn)…dc…這樣的句子。由(1)可知：aacb可歸約為S，由文法的產(chǎn)生式規(guī)則可知，終結(jié)符c后不可能跟非終結(jié)符i=1,2,..,k，αiT*bi成立，現(xiàn)在設(shè)(2)同(1)，假設(shè)：β的首符號(hào)為非終結(jié)符時(shí)，α首符號(hào)為終結(jié)符。即設(shè)：α=aω；β=Aω’且α=aωT…TAω’=β，與(1)同理，得證。abc應(yīng)有兩個(gè)語(yǔ)法樹(shù)(或最右推導(dǎo))：所以，本文法具有二義性。上面推導(dǎo)中，下劃線部分為當(dāng)前句型的句柄。對(duì)應(yīng)的語(yǔ)法樹(shù)為：6/121注：符號(hào)的下標(biāo)是為了描述方便加上去的。(2)句子(((b)a(a))(b))的最右推導(dǎo)：(3)解：iii*i+↑對(duì)應(yīng)的語(yǔ)法樹(shù)略。TFii*i+↑TPii*i+↑Tiii*i+↑充分性：當(dāng)前文法下的每一符號(hào)串僅有一個(gè)句柄和一個(gè)句柄產(chǎn)生式T對(duì)當(dāng)前符號(hào)串有唯一必要性：有唯一的語(yǔ)法樹(shù)T對(duì)每一步推導(dǎo)都有唯一的最右推導(dǎo)T對(duì)當(dāng)前符號(hào)串有唯一的最左歸約T當(dāng)前文法下的每一符號(hào)串僅有一個(gè)句柄和一個(gè)句柄產(chǎn)生式7/121(3)解：S→ac的ε產(chǎn)生式15.消除下列文法中的無(wú)用產(chǎn)生式和單產(chǎn)生式(1)消除后的產(chǎn)生式如下：(2)消除后的產(chǎn)生式如下：Bà[]|[S](3)消除后的產(chǎn)生式如下：第三章習(xí)題解答8/121以有A→abc…B’,a,b,c…∈VT,B’∈VN可見(jiàn)兩者等價(jià)，所以由此文法產(chǎn)生的語(yǔ)言是正規(guī)語(yǔ)言。6根據(jù)文法知其產(chǎn)生的語(yǔ)言是可以構(gòu)造如下的文法VN={S,A,B,C},VT={a,b,c}其狀態(tài)轉(zhuǎn)換圖如下:9/1217(1)其對(duì)應(yīng)的右線性文法是:(3)任意接受的四個(gè)串(4)任意以1打頭的串.9(2)相應(yīng)的3型文法(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é)尾或者ivbaa后由一個(gè)a,b所組成的任意串結(jié)尾或者成的任意串結(jié)尾(3)對(duì)G1文法,abb的推導(dǎo)序列是：(1)對(duì)于G中每一個(gè)形如A→aB的產(chǎn)生式且A是開(kāi)始符，將其變?yōu)锽→a,否則若A不是GAaS→AaqBqABqSAq(2)記[S]=q0,[A]=q1,[BS]=q2最小化和確定化后的狀態(tài)轉(zhuǎn)換圖如下13(1)將具有ε動(dòng)作的NFA確定化后，其狀態(tài)轉(zhuǎn)換圖如圖：(2)記{S}=q0{Z}=q1{UR}=q2{SX}=q3{YUR}=q4{XSU}=q5{YURZ}=q6{ZS}=q714(1)從略狀態(tài)轉(zhuǎn)換圖如圖(1)r*表示的正規(guī)式集是{ε,r,rr,rrr,…}(r*)*=r*={ε,r,rr,rrr,…}把(4)(5)代入(2)，得B＝c(bB+d)+b=cbB+cd+b得B=(cb)*(cd|b),代入(3)得A=abS+b(cb)*(cd|b)把它打入(1)得%{%}{{if((yyin=fopen(argv[1],"r"))==NULL){}}{{ifcgotoi;label;}ifcHUNDRE)ifcHUNDRE)}}/*while*/}ab26(1)由{}括住的,中間由任意個(gè)非{組成的字符串,如{},{}},{a},{defg}等等。 (2)匹配一行僅由一個(gè)大寫(xiě)字母和一個(gè)數(shù)字組成的串，如A1,F8,Z2等。 (3)識(shí)別\r\n和除數(shù)字字符外的任何字符。bb’,’def’，’等等27O[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_]*%{%}{ci{if((yyin=fopen(argv[1],"r"))==NULL){}}{ifc==2){for(i=0;yytext[i];i++)printf("%c",tolower(yytext[i]));}ifc==3)printf("");}}{}第四章習(xí)題參考答案20/121Xthen21/12122/12123/12124/121AA且first(α)∩first(β)≠φ，即文法不滿足LL(1)文法條件。得證。6.證：LL(1)文法的分析句子過(guò)程的每一步，永遠(yuǎn)只有唯一的分析動(dòng)作可進(jìn)行?，F(xiàn)在，假兩個(gè)不同的最左推導(dǎo)。從而可知，用LL(1)方法進(jìn)行句子α的分析過(guò)程中的某步中，存在兩種不同的產(chǎn)生式替換，且均能正確進(jìn)行語(yǔ)法分析，即LL(1)分析動(dòng)作存在不確定性。與LL產(chǎn)生式FIRST集FOLLOW集{a}{#}{#}{a}{#}ab25/121#Sε產(chǎn)生式first集follow集{a}{c}{a,b}26/12127/121等量>為D，原文法可以簡(jiǎn)化為：OWASA(a)bS==A=<=<(==<<<28/121a>=<><>>)>>>>>b>>SRT()∧aS>=R=T>(<=<<<<)>>>>a>><=<<<SR(a)S=<0/121<R>>(=<<a>>=<<)>>SZT#i()SZ==T>1/121>#=<<<I>>(=<<<)>>法；SA/AS>>A=<=<=/2/121>>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)系的定義，可jxjaUbaT..xj-1,bT*xi+1...對(duì)于aUb可構(gòu)造一語(yǔ)法樹(shù)，并通過(guò)對(duì)其剪枝(歸約)，直系的定義，必滿足上述條件。解：為描述方便，用符號(hào)表示各非終結(jié)符：D=<變量說(shuō)明>,L=<變量表>,V=<變量>,T=<類DWTLa:;iDW=T=L>3/121=a=<<:=<;>>>=i>不失一般性，設(shè)其形為U→xABy,x,y∈V*,由于文法不含無(wú)用產(chǎn)生式，則必存在含有U的句(1)構(gòu)造算符優(yōu)先矩陣：*()i4/121#><><<><>*><><><(<<<=<)>>>>I>>>>#<5/121<<<(2)在(-，-)、(-，*)和(*，-)處有多重定義元素，不是算符優(yōu)先文法；(3)改寫(xiě)方法：(2)的證明與(1)類似，略。b證明略.證明略.(2)、(3)類似可證。提示：根據(jù)27題的結(jié)論，只要證u是句型α的短語(yǔ)，根據(jù)=關(guān)系的定義容易知道u是句型證：設(shè)不能含有素短語(yǔ)，則只能是含有短語(yǔ)(不能含有終結(jié)符號(hào))，則該短語(yǔ)只能含有一個(gè)(1)算符優(yōu)先矩陣：+*↑()i#6/121+><<<><>*>><<><>↑>><<><>(<<<<=<)>>>>>I>>>>>#<<<<<(2)用Floyd方法將優(yōu)先矩陣線性化得到得的優(yōu)先函數(shù)為：+*↑()i#F3551771G24661617/121zbMLa()f1567747g1654667(1)優(yōu)先矩陣如下：[]a#[>=]>>a8/1219/121<><><#<<<(2)用Bell方法求優(yōu)先函數(shù)的過(guò)程如下：[]a#f5751g5561(3)顯然，文法不是算符優(yōu)先文法,所以不能線性化。(1)識(shí)別全部活前綴的DFA如下：(以表格的形式來(lái)表示，很容易可以轉(zhuǎn)化為圖的形式，態(tài)40/121目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)ISaIIIISabIII41/121IbcIIIII(2)識(shí)別全部活前綴的DFA如下：目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)ISc·II42/121ISIAcaIIIIS一cA·IBAcb43/121aIIIIIIA一a·IICAaIIIB一b·I44/121BAcbaIII(3)態(tài)目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)I45/121ScaIIIIIIScaIII46/121IScaIIIISabcIII47/121III(4)態(tài)目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)ISAaIIIIIbIIILR(0)文法，其SLR(1)分析表如下：FOLLOW(S)={#,b,c}ACTIONabc#S0112334548/12149/1216(2)是LR(0)文法，其SLR(1)分析表如下：FOLLOW(S)=FOLLOW(A)=FOLLOW(B)={#}ACTIONabc#SAB01123343656789SabcACTIONabc#S050/12151/12111234455767(4)因?yàn)镮2中含有沖突項(xiàng)目，所以不是LR(0)文法，其SLR(1)分析表如下：FOLLOW(S)={#}∩=φ(所以可以用SLR(1)規(guī)則解決沖突),FOLLOW(A)={b,#}52/121ACTIONab#SA0121234態(tài)目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)IS53/121(aIIIIIS(aIIIIIa54/121(R)IIIIIIIR一,SRS(aIIIIIR一,SR55/121)RIIIIACTIONa)#SR01124356/12145568789957/121態(tài)目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)ISbIII(沖突項(xiàng)目)aII58/121RSabIIIIIbIISbRIRS·aIIRa·I(2)59/121狀態(tài)目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)ISaBbIIIIIISaB60/121bIIIIIAaBbIIIIIB一b·I61/121AaBbIIIIIS一BA·IABabIIIIIBbIACTIONab#SAB013162/12163/12125336845986788964/121(3)先求識(shí)別全部活前綴的DFA：目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)ISabIIIII65/121SbaIIIISabIIIIbIIIaIIIACTIONab#S01124366/12167/121645678(4)先求識(shí)別全部活前綴的DFA：目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)ISabI68/121IIII(沖突)AcIII(沖突)BcIII69/121I(沖突)AcIIII(沖突)BcIIId70/121IddACTIONabcd#SAB01171/12124364586798972/121目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)IIIIIIIIII;DIIDSIIII74/121DSIIII;SIACTION;DS#0175/12176/121234123457678977/121目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)IIIIII78/121I(沖突項(xiàng)目)SIIII;II79/121IIII沖突項(xiàng)目)SIII;121d;S#011233454512167899態(tài)目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)I121SAabcIIIIIIbIIA一Sb·I121SAabcdIIIIIIIIA一a·I121SAabcIIIIA一cd·IbII121SAabcdIIISAabcdIIIbc121121IA一ASc·S一AAd·ACTIONabcd#SA01612312189456789121ACTIONabcd90/121#SA0161238945691/12178992/121兩表的異同：兩表都用ACTION表和GOTO表反映了移進(jìn)、歸約(包括接受)的狀態(tài)和動(dòng)作。不同之處在于SLR(1)增加了在歸約的時(shí)候考慮向前符號(hào)a以解釋可能出現(xiàn)的“移進(jìn)——?dú)w約”沖突；SLR(1)的分析較稀疏些，原因是填寫(xiě)歸約項(xiàng)時(shí)，并不是在一狀態(tài)對(duì)應(yīng)行上全部填寫(xiě)歸約動(dòng)作，而是考慮了相應(yīng)非終結(jié)符的FOLLOW集因素。另外，在分析效率上SLR(1)分析的效率更高一些，因?yàn)樵诎l(fā)現(xiàn)錯(cuò)誤方面，SLR(1)比LR(0)分析發(fā)現(xiàn)的更態(tài)目集經(jīng)過(guò)的符號(hào)到達(dá)的狀態(tài)ISABabIIII93/121IIIIABabIIIIIBab94/121IIIIIIACTIONab#SAB012312395/1216347567LRabab過(guò)程：態(tài)棧中符號(hào)余留符號(hào)分析動(dòng)作下一狀態(tài)10#4296/1215374354657#78#97/12139#6#BBA#6#BA#1#A#(1)求LR(1)項(xiàng)目集和狀態(tài)轉(zhuǎn)