編譯原理習(xí)題及答案整理后

1、第一章1、將編譯程序分成若干個(gè)“遍”是為了。b.使程序的結(jié)構(gòu)更加清晰2、構(gòu)造編譯程序應(yīng)掌握。a.源程序b.目標(biāo)語言c.編譯方法3、變量應(yīng)當(dāng)。c.既持有左值又持有右值4、編譯程序絕大多數(shù)時(shí)間花在上。d.管理表格5、不可能是目標(biāo)代碼。d.中間代碼6、使用可以定義一個(gè)程序的意義。a.語義規(guī)則7、詞法分析器的輸入是。b.源程序8、中間代碼生成時(shí)所遵循的是-。c.語義規(guī)則9、編譯程序是對(duì)。d.高級(jí)語言的翻譯10、語法分析應(yīng)遵循。c.構(gòu)詞規(guī)則二、多項(xiàng)選擇題1、編譯程序各階段的工作都涉及到。b.表格管理c.出錯(cuò)處理2、編譯程序工作時(shí)，通常有階段。a.詞法分析b.語法分析c.中間代碼生成e.目標(biāo)代碼生成三、填

2、空題1、解釋程序和編譯程序的區(qū)別在于是否生成目標(biāo)程序。2、編譯過程通?？煞譃?個(gè)階段，分別是一詞法分析、語法分析中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成。3、編譯程序工作過程中，第一段輸入是源程序,最后階段的輸出為標(biāo)代碼生成程序。4、編譯程序是指將源程序程序翻譯成目標(biāo)語言程序的程序。、單項(xiàng)選擇題1、文法G:SfxSx|y所識(shí)別的語言是。a.xyxb.(xyx)*c.xnyxn(n0)d.x*yx*2、文法G描述的語言L(G)是指。a.L(G)=a|S?“，aCVt*b.L(G)=a|SZa,aCVt*C.L(G)=a|S?*a,aC(VtUVn*)d.L(G)=a|S?a,”C(VtUVn*)3、

3、有限狀態(tài)自動(dòng)機(jī)能識(shí)別。a.上下文無關(guān)文法b.上下文有關(guān)文法c.正規(guī)文法d.短語文法4、設(shè)G為算符優(yōu)先文法，G的任意終結(jié)符對(duì)a、b有以下關(guān)系成立。a.若f(a)g(b),則abb.若f(a)g(b),則a0b.anbncmdm|n,m0c.anbmcmdn|n,m0d.anbncmdm|n,m0e.anbncndn|n05、自下而上的語法分析中，應(yīng)從開始分析。a.句型b.句子c.以單詞為單位的程序d.文法的開始符e.句柄6、對(duì)正規(guī)文法描述的語言，以下有能力描述它。a.0型文法b.1型文法c.上下文無關(guān)文法d.右線性文法e.左線性文法三、填空題1、文法中的終結(jié)符和非終結(jié)符的交集是。詞法分析器交給語

4、法分析器的文法符號(hào)一定是,它一定只出現(xiàn)在產(chǎn)生式的部。2、最左推導(dǎo)是指每次都對(duì)句型中的非終結(jié)符進(jìn)行擴(kuò)展。3、在語法分析中，最常見的兩種方法一定是分析法，另一是分析法。4、采用語法分析時(shí)，必須消除文法的左遞歸。5、樹代表推導(dǎo)過程，樹代表歸約過程。6、自下而上分析法采用、歸約、錯(cuò)誤處理、等四種操作。7、Chomsky把文法分為種類型，編譯器構(gòu)造中采用和文法，它們分別產(chǎn)生和語言，并分別用和自動(dòng)機(jī)識(shí)別所產(chǎn)生的語言。四、判斷題1、文法S-aS|bR|e描述的語言是（a|bc）*（）RfcS2、在自下而上的語法分析中，語法樹與分析樹一定相同。（）3、二義文法不是上下文無關(guān)文法。（）4、語法分析時(shí)必須先消除文

5、法中的左遞歸。（）5、規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。（）6、一個(gè)文法所有句型的集合形成該文法所能接受的語言。（）五、簡(jiǎn)答題1、句柄2、素短語3、語法樹4、歸約5、推導(dǎo)六、問答題1、給出上下文無關(guān)文法的定義。2、文法GS:S一aSPQ|abQQDPQbP一bbbQ一bccQcc（1）它是Chomsky哪一型文法？（2）它生成的語言是什么？3、按指定類型，給出語言的文法。L=aibj|ji1的上下文無關(guān)文法。4、有文法G:SfaAcB|BdAfAaB|cB一bScA|b(1)試求句型aAaBcbbdcc和aAcbBdcc的句柄；(2)寫出句子acabcbbdcc的最左推導(dǎo)過程。5、對(duì)于文法G

6、S:S一(L)|aS|a1_一1_,S|S(1)畫出句型(S,(a)的語法樹。(2)寫出上述句型的所有短語、直接短語、句柄和素o6、考慮文法GT:T-T*F|FFfFTP|PP-(T)|i證明T*PT(T*F)是該文法的一個(gè)句型，并指出直接短語和句柄。單選解答1、選Co2、選a。3、選Co4、雖然a與b沒有優(yōu)先關(guān)系，但構(gòu)造優(yōu)先函數(shù)后，a與b就一定存在優(yōu)先關(guān)系了。所以，由f(a)g)(b)或f(a)g(b)并不能判定原來的a與b之間是否存在優(yōu)先關(guān)系：故選c。5、如果文法G無二義性，則最左推導(dǎo)是先生長(zhǎng)右邊的枝葉：對(duì)于d,如果有兩個(gè)不同的是了左推導(dǎo)，則必然有二義性。故選a。E6、選c。/!E+F7、

7、由圖2-8-1的語法樹和優(yōu)先關(guān)系可以看出應(yīng)選boE+TPII一iP#+#圖2-8-1句型P+T+I的語法及優(yōu)先關(guān)系8、規(guī)范推導(dǎo)是最左推導(dǎo)，故選do9、由T-T,和T-(得FIRSTVT(T)=(,);由T-S得FIRSTVT(S)?FIRSTVT(T),而FIRSTVT(S)=b,A,(;即FIRSTVT(T)=b,A,(,;因此選c。10、d11、c12、b13、b14、b多選解答1、e、a、c2、a、c、e3、b、c、d4、a、c5、b、c6、a、b、c、d、e填空解答1、空集終結(jié)符右2、最左3、自上而上自下而上4、自上而上5、語法分析6、移進(jìn)接受7、42型3型上下文無關(guān)語言正規(guī)語言下推自

8、動(dòng)機(jī)有限判斷解答1、對(duì)2、錯(cuò)3、錯(cuò)4、錯(cuò)5、錯(cuò)6、錯(cuò)簡(jiǎn)答解答1、句柄：一個(gè)句型的最左直接短語稱為該句型的句柄。2、素短語：至少含有一個(gè)終結(jié)符的素短語，并且除它自身之外不再含任何更小的素短語。3、語法樹：滿足下面4個(gè)條件的樹稱之為文法GS的一棵語法樹。每一終結(jié)均有一標(biāo)記，此標(biāo)記為VnUVt中的一個(gè)符號(hào)；樹的根結(jié)點(diǎn)以文法GS的開始符S標(biāo)記；若一結(jié)點(diǎn)至少有一個(gè)直接后繼，則此結(jié)點(diǎn)上的標(biāo)記為Vn中的一個(gè)符號(hào)；若一個(gè)以A為標(biāo)記的結(jié)點(diǎn)有K個(gè)直接后繼，且按從左至右的順序，這些結(jié)點(diǎn)的標(biāo)記分另I為Xi,X2,Xk,則AXi,X2,Xk,必然是G的一個(gè)產(chǎn)生式。4、歸約：我們稱“丫3直接歸約出aA3,僅當(dāng)A-丫是一個(gè)

9、產(chǎn)生式，且a、3C(VnUVt)*。歸約過程就是從輸入串開始，反復(fù)用產(chǎn)生式右部的符號(hào)替換成產(chǎn)生式左部符號(hào)，直至文法開始符。5、推導(dǎo)：我們稱aA3直接推出a丫3,即aA3=a丫3,僅當(dāng)A一丫是一個(gè)產(chǎn)生式，且a、3C(VnUVt)*o如果ai=ta2=i3an,則我們稱這個(gè)序列是從ai至a2的一個(gè)推導(dǎo)。若存在一個(gè)從n的推導(dǎo)，則稱“1可推導(dǎo)出&no推導(dǎo)是歸約的逆過程。問答1解答一個(gè)上下文無關(guān)文法G是一個(gè)四元式(Vt,Vn,S,P),其中： Vt是一個(gè)非空有限集，它的每個(gè)元素稱為終結(jié)符號(hào)； Vn是一個(gè)非空有限集，它的每個(gè)元素稱為非終結(jié)符號(hào)，VtAVn=； S是一個(gè)非終結(jié)符號(hào)，稱為開始符號(hào)； P是一個(gè)產(chǎn)

10、生式集合(有限)，每個(gè)產(chǎn)生式的形式是P-a,其中，PCVn,aC(VtUVn)*。開始符號(hào)S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。2解答(1)由于產(chǎn)生式左部存在終結(jié)符號(hào)，且所有產(chǎn)生式左部符號(hào)的長(zhǎng)度均小于等于產(chǎn)生式右部的符號(hào)長(zhǎng)度，所以文法GS是Chomsky1型文法，即上下文有關(guān)文法。(2)按產(chǎn)生式出現(xiàn)的順序規(guī)定優(yōu)先級(jí)由高到低(否則無法推出句子)，我們可以得到：SabQ=abcSaSPQaabQPQ=aabPQQ=aabbQQ=aabbcQaabbccSaSPQaaSPQPQ=aaabQPQPQ=aaabPQQPQ=aaabPQPQQ=aaaPPQQQ二aaabbPqqq=aaabbQQQ=-aa

11、abbbcQQ=aaabbbccQ,:aaabbbccc于是得到文法GS生成的語言L=anbncn|n13【解答】(1)由L=abj|jin1知，所求該語言對(duì)應(yīng)的上下文無關(guān)文法首先應(yīng)有S-aSb型產(chǎn)生式，以保證b的個(gè)數(shù)不少于a的個(gè)數(shù)；其次，還需有S-Sb或S-bS型的產(chǎn)生式，用以保證b的個(gè)數(shù)多于a的個(gè)數(shù)；也即所求上下文無關(guān)文法GS為：GS:S-aSb|Sb|b4【解答】(1)分別畫出對(duì)應(yīng)兩句型的語法樹，如圖2-8-2所示句柄：AaBBdSScB.AaBbAct八Bdc八Bdcb(a)(b)圖2-8-2語法樹(2)句子acabcbbdcc的最左推導(dǎo)如下：S:aAcB:aAaBcB=acaBcB:

12、acabcB:acabcbScA:acabcbBdcA=acabcbbdcAacabcbbdcc5【解答】S(1)句型(S,(a)的語法樹如圖2-8-3所示/(L)LS/1s(l)Sa圖2-8-3句型(S,(a)的語法樹(2)由圖2-8-3可知：短語：S、a、(a)、S,(a)、(S,(a);直接短語：a、S;句柄：S;素短語：素短語可由圖2-8-3中相鄰終結(jié)符之間的優(yōu)先關(guān)系求得，即;#)#因此素短語為a。6【解答】首先構(gòu)造T*PT(T*F)的語法樹如圖2-8-4所示。由圖2-8-4可知，T*PT(T*F)是文法GT的一個(gè)句型。直接短語有兩個(gè)，即P和T*F;句柄為P。、單項(xiàng)選擇題1、詞法分析所

13、依據(jù)的是。a.語義規(guī)則b.構(gòu)詞規(guī)則2、詞法分析器的輸出結(jié)果是。a.單詞的種別編碼c.單詞的種別編碼和自身值3、正規(guī)式Mi和M2等價(jià)是指，a. Mi和M2的狀態(tài)數(shù)相等c.Mi和M2所識(shí)別的語言集相等第三章c.語法規(guī)則d.等價(jià)變換規(guī)則b.單詞在符號(hào)表中的位置d.單詞自身值b. Mi和M2的有向弧條數(shù)相等d.M1和M2狀態(tài)數(shù)和有向弧條數(shù)相等圖2-8-4句型T*PT(T*F)的語法樹4、狀態(tài)轉(zhuǎn)換圖(見圖3-6-1)接受的字集為圖3-6-1a.以0開頭的二進(jìn)制數(shù)組成的集合b.以0結(jié)尾的二進(jìn)制數(shù)組成的集合c.含奇數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合d,含偶數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合5、詞法分析器作為獨(dú)立的階段使整個(gè)

14、編譯程序結(jié)構(gòu)更加簡(jiǎn)潔、明確，因此,a,詞法分析器應(yīng)作為獨(dú)立的一遍b,詞法分析器作為子程序較好c,詞法分析器分解為多個(gè)過程，由語法分析器選擇使用d,詞法分析器并不作為一個(gè)獨(dú)立的階二、多項(xiàng)選擇題1、在詞法分析中,能識(shí)別出a,基本字b,四元式c,運(yùn)算符d.逆波蘭式e,常數(shù)2、令匯=a,b,則匯上所有以b開頭，后跟若干個(gè)ab的字的全體對(duì)應(yīng)的正規(guī)式為a,b(ab)*d,(ba)+b三、填空題+b,b(ab)e,b(a|b)c.(ba)*b1、確定有限自動(dòng)機(jī)DFA是的一個(gè)特例。2、若二個(gè)正規(guī)式所表示的相同，則認(rèn)為二者是等價(jià)的。3、一個(gè)字集是正規(guī)的，當(dāng)且僅當(dāng)它可由所.四、判斷題1、一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且

15、僅有一個(gè)唯一終態(tài)。2、設(shè)r和s分別是正規(guī)式，則有L(r|s)=L(r)|L(s)。3、自動(dòng)機(jī)M和M的狀態(tài)數(shù)不同，則二者必不等價(jià)。4、確定的自動(dòng)機(jī)以及不確定的自動(dòng)機(jī)都能正確地識(shí)別正規(guī)集。5、對(duì)任意一個(gè)右線性文法G,都存在一個(gè)NFAM,滿足L(G)=L(M)。6、對(duì)任意一個(gè)右線性文法G,都存在一個(gè)DFAM,滿足L(G)=L(M)。7、對(duì)任何正規(guī)表達(dá)式e,都存在一個(gè)NFAM,滿足L(G)=L(e)。8、對(duì)任何正規(guī)表達(dá)式e,都存在一個(gè)DFAM,滿足L(G)=L(e)。五、基本題1、設(shè)M=(x,y,a,b,f,x,y)為一非確定的有限自動(dòng)機(jī)，其中f定義如下:f(x,a)=x,yf(x,b)=yf(y,b

16、)=x,yf(y,a)=(f)試構(gòu)造相應(yīng)的確定有限自動(dòng)機(jī)M2、對(duì)給定正規(guī)式b*(d|ad)(b|ab)構(gòu)造其NFAM;單選解答1、b2、c3、c4、d5、b多選解答1、a、c、e2、a、b、填空解答1、NFA正規(guī)集3、DFA(NFA)所識(shí)別判斷解答1、2、3、錯(cuò)4、5、6、7、8、正確基本1解答:對(duì)照自動(dòng)機(jī)的定義M=(S,2,f,S,z),由f的定義可知f(x,a)、f(y,b)均為多值函數(shù),所以是一非確定有限自動(dòng)機(jī)，先畫出NFAM相應(yīng)的狀態(tài)圖，如圖3-6-2所示。將圖3-6-5的DFAM最小化。首先，將M的狀態(tài)分成終態(tài)組1,2與非終態(tài)組0;其次,考察1,2。由于1,2a=1,2b=2?1,2

17、,所以不再將其劃分了，也即整個(gè)劃分只有兩組1,2:令狀態(tài)1代表1,2,即把原來至沙所示化簡(jiǎn)DFAM。b1酬除狀態(tài)2。最后，得到如圖0,3-6-6圖3-6-6化簡(jiǎn)后的DFAM2解答：首先用如圖3-6-7所示。NFAM,用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣表3-6-3所示。IIaIbXx,yyy一x,yx,yx,yx,y將轉(zhuǎn)換矩陣中的所有子集重新命名而形成表3-6-4所示的狀態(tài)轉(zhuǎn)換矩陣。表3-6-4狀態(tài)轉(zhuǎn)換矩陣ab0211一22k-22k即得到M=(0,1,2,a,b,f,0,1,2),其狀態(tài)轉(zhuǎn)換圖如圖3-6-5所示。第四章1、構(gòu)造下面文法的LL(1)分析表。DfTLTfint|realLfidRRf,idR

18、|2、 下面文法GS是否為L(zhǎng)L(1)文法？說明理由。SfAB|PQxA-xyB-bcPfdP|eQ-aQ|e3、 設(shè)有以下文法：GS:SfaAbDe|dAfBSD|eBfSAc|cD|DfSe|e(1)求出該文法的每一個(gè)非終結(jié)符U的FOLLOW集(2)該文法是LL(1)文法嗎?(3)構(gòu)造CS的LL(1)分析表。4、 將文法GV改造成為L(zhǎng)L(1)的。GV:VfN|NEE-V|V+E5、已知文法:GA:A-aAa|(1)該文法是LL(1)文法嗎?為什么？(2)若采用LL(1)方法進(jìn)行語法分析，如何得到該文法的LL(1)分析表?(3)若輸入符號(hào)串“aaaa”，請(qǐng)給出語法分析過程。1解答：LL(1)分

19、析表見表4-3-1分析雖然這個(gè)文法很簡(jiǎn)單，我們還是從求開始符號(hào)集合和后繼符號(hào)集合開始。FIRST(D)=FIRST(T)=int,realFOLLOW(D)=FOLLOW(L)=#FIRST(L)=idFOLLOW(T)=idFIRST(R)=，卜FOLLOW(R)=#有了上面每個(gè)非終結(jié)符的FIRST集合，填分析表時(shí)要計(jì)算一個(gè)產(chǎn)生式右部a的FIRST(亦就不是件難事了。填表時(shí)唯一要小心的時(shí)，e是產(chǎn)生式R-e右部的一個(gè)開始符號(hào)，而#在FOLLOW(R)中,所以R-e填在輸入符號(hào)#的欄目中。表4-3-1LL(1)分析表非終結(jié)符輸入符號(hào)intrealid#DDfTLDfTLTT-intT一realL

20、LTdRRRf,idRR一2解答：該文法不是LL(1)文法，見下面分析中的說明。分析只有三個(gè)非終結(jié)符有兩個(gè)選擇。1、P的兩個(gè)右部dP和e的開始符號(hào)肯定不相交。2、Q的兩個(gè)右部aQ和的開始符號(hào)肯定不相交。3、對(duì)S來說，由于xFIRST(AB),同時(shí)也有xFIRST(PQx)(因?yàn)镻和Q都可能為空)。所以該文法不是LL(1)文法。3解答：(1)求文法的每一個(gè)非終結(jié)符U的FOLLOW集的過程如下：因?yàn)椋?S是識(shí)別符號(hào)，且有AfBSD、BfSAc、DfSe,所以FOLLOW(S)應(yīng)包含F(xiàn)IRST(D)UFIRST(Ac)UFIRST(e)U#=a,dUa,d,c,eUeU#=a,c,d,e# 又因?yàn)锳

21、fBSD和D一s,所以FOLLOW中還包含F(xiàn)OLLOW(A)。因?yàn)镾faAbDe和B-SAc,所以FOLLOW(A)=FIRST(bDe)UFIRST(c)=b,c綜合、得FOLLOW(S)=a,d,c,e,#Ua,b,c,d,e,#因?yàn)锳-BSD,所以FOLLOW(B)=FIRST(SD)=a,d因?yàn)镾faAbDe|d、A-BSD|e和B-SAc|cD,所以FOLLOW(D)=FIRST(e)UFOLLOW(A)UFOLLOW(B)=eUb,cUa,d=a,b,c,d,e(2)GS不是LL(1)文法。因?yàn)楫a(chǎn)生式BfSAc|cD|中FIRST(SAc)nFOLLOW(B)=a,dw?(3)構(gòu)造

22、GS的LL(1)分析表。按照LL(1)分析表的構(gòu)造算法構(gòu)造方法GS的LL(1)分析表如表4-3-2所示。表4-3-2GS的LL(1)分析表abcde#SaAbDedABSDBSDBSDeBSac/ecDSac/eDSe/Se/4解答：對(duì)文法GV提取公共左因子后得到文法:GV:V-NAA一或EE一VBBfH+ENfi求出文法GV中每一個(gè)非終結(jié)符號(hào)的FIRST集:FIRST(V)=iFIRST(A)=,FIRST(E)=iFIRST(B)=+,FIRST(N)=i求出文法GV中每一個(gè)非終結(jié)符號(hào)的FOLLOW集：FOLLOW(V)=#UFIRST(B)4UFOLLOW(E)=#,+,FOLLOW(A

23、)=FOLLOW(V)=+,#FOLLOW(E)=FIRST()4UFOLLOW(B)=FIRST()UFOLLOW(E)=FOLLOW(B)=FOLLOW(E)=FOLLOW(N)=FIRST(A)3UFOLLOW(V)=,+,#可以看到，對(duì)文法GV的產(chǎn)生式A一或E,有FIRST(E)AFOLLOW(A)=n+,#=?對(duì)產(chǎn)生式B一耳+E,有FIRST(+E)AFOLLOW(B)=+n=?而文法的其他產(chǎn)生式都只有一個(gè)不為由勺右部，所以文法GV是LL(1)文法。5解答：(1)因?yàn)楫a(chǎn)生式A-aAa|e有空產(chǎn)生式右部，而FOLLOW(A)=#UFIRST(a)=a,#造成FIRST(A)nFOLLO

24、W(A)=A,na,#w?所以該文法不是LL(1)文法。(2)若采用LL(1)方法進(jìn)行語法分析，必須修改該文法。因該文法產(chǎn)生偶數(shù)(可以為0)個(gè)a,所以得到文法GA:A-aaA|日此時(shí)對(duì)產(chǎn)生式A-aaA|e,有FOLLOW(A)=#UFOLLOW(A)=#,因而FIRST(A)nFOLLOW(A)=a,n#=?所以文法GA是LL(1)文法，按LL(1)分析表構(gòu)造算法構(gòu)造該文法的LL(1)分析表如表4-3-3所不。表4-3-3文法GA的LL(1)分析表A#AA-aaAA一日(3)若采用LL(1)方法進(jìn)行語法分析，對(duì)符號(hào)串“aaaa”的分析過程如表4-3-4所示。表4-3-4對(duì)符號(hào)串“aaaa”的分

25、析過程步驟分析棧輸入串產(chǎn)生式/動(dòng)作1#Aaaaa#A-aaA2#Aaaaaaa#匹配3#Aaaaa#匹配4#Aaa#A-aaA5#Aaaaa#匹配6#Aaa#匹配7#A#A一日8#接受第五章1 .設(shè)有文法GS為:S一a|b|(A)AfSdA|S(1)完成下列算符優(yōu)先關(guān)系表，見表5-7-1,并判斷GS是否為算符優(yōu)先文法。表5-7-1算符優(yōu)先關(guān)系表ab()d#a?b?(?)?d#?(2)給出句型(SdSdS)的短語、簡(jiǎn)單短語、句柄、素短語和最左素短語。(3)給出輸入串(adb)#的分析過程。解答：(1)先求文法GS的FIRSTVT集和LASTVT集:由S-a|b|(A)得：FIRSTVT(S)=a

26、,b,();由AfSd得：FIRSTVT(A)=d;又由A-S得：FIRSTVT(S)?FIRSTVT(A),即FIRSTVT(A)=d,a,b,(;由S-a|b|(A)得；LASTVT(S)=a,b,;由A一dA得：LASTVT(A)=d,又由A-S得：LASTVT(S)?LASTVT(A),即LASTVT(A)=d,a,b,)。構(gòu)造優(yōu)先關(guān)系表方法如下：對(duì)Pfab，或PfaQb，有a?b;對(duì)PaR,而bCFIRSTVT(R),有a?b;對(duì)PfRb,而aCFIRSTVT(R),有a?b。由此得到：由S一(A)得：(?);由S一(A得：(?FIRSTVT(A)，即：(?d,(?a,(?b,(?(

27、油A-dA得：d?FIRSTVT(A),即：d?d,d?a,d?b,d?(;由S-A)得，LASTVT(A)?),即：d?),a?),b?),)?);由A-Sd得：LASTVT(S)?d,即：a?d,b?d,)?d;此外，由#S#導(dǎo):#?#;由#?FIRSTVT(S)得：#?a,#?b,#?(;月旨由LASTVT(S)?#得：d?#,a?#,b?#,)?#。最后得到算符優(yōu)先關(guān)系表，見表5-7-2。ab()d#a?b?(?)?d?#?表5-7-2算符優(yōu)先關(guān)系表由表5-7-2可以看出，任何兩個(gè)終結(jié)符之間至少只滿足？、？、？三種優(yōu)先關(guān)系之一，故GS為算符優(yōu)先文法。S（2）為求出句型（SdSdS）的短

28、語、簡(jiǎn)單短語、句柄，我們先畫出該句型對(duì)應(yīng)的語法樹,如圖5-7-3所示。由圖5-7-3得到：短語：S,SdS,SdSdS,（SdSdS）簡(jiǎn)單短語（即直接短語）：S句柄（即最左直接短語）：S素短語：SdS,它同時(shí)也是該句型的最左素短語。圖5-7-3句型（SdSdS）的語法樹（3）輸入串（adb）#的分析過程見表5-7-4表5-7-4輸入串（adb）#的分析過程符號(hào)棧輸入串說明#(adb)#移進(jìn)#(adb)#移進(jìn)#(adb)#用S-a歸約#(Sdb)#移進(jìn)#(Sdb)#移進(jìn)#(Sdb)#用S-b歸約#(SdS)#用A-S歸約#(SdA)#用A-SdA歸約#(A)#移進(jìn)#(A)#用S-(A)歸約#S#

29、分析成功第六章一、單項(xiàng)選擇題1、若a為終結(jié)符，則A-aa3為項(xiàng)目a.歸約b.移進(jìn)c.接受d.待約2、若項(xiàng)目集Ik含有A-a-，則在狀態(tài)k時(shí)，僅當(dāng)面臨的輸入符號(hào)aOLLOW(A)時(shí)，才采取“A-動(dòng)作的一定是。a.LALR文法b.LR(0)文法c.LR(1)文法d.SLR(1)文法3、就文法的描述能力來說，有。a.SLR(1)?LR(0)b.LR(1)?LR(0)c.SLR(1)?LR(1)d.無二義文法？LR(1)4、在LR(0)的ACTION子表中，如果某一行中存在標(biāo)記j的欄，則。a.該行必定填滿rjb.該行未填滿rjc.其他行也有rjd.goto子表中也有rj5、一個(gè)指明了在分析過程中的某時(shí)

30、刻所能看到產(chǎn)生式多大一部分。a.活前綴b.前綴c.項(xiàng)目d.項(xiàng)目集二、多項(xiàng)選擇題1、一個(gè)LR分析器包括。a.一個(gè)總控程序b.一個(gè)項(xiàng)目集c.一個(gè)活前綴d.一張分析表e.一個(gè)分析棧2、LR分析器核心部分是一張分析表，該表包括等子表。a.LL(1)分析b.優(yōu)先關(guān)系c.GOTOd.LRe.ACTION3、每一項(xiàng)ACTIONS,a所規(guī)定的動(dòng)作包括。a.移進(jìn)b.比較c.接受d.歸約e.報(bào)錯(cuò)4、對(duì)LR分析表的構(gòu)造，有可能存在動(dòng)作沖突。a.移進(jìn)b.歸約c.移進(jìn)/歸約d.移進(jìn)/移進(jìn)e.歸約/歸約5、就文法的描述能力來說，有b. LR(1)?SLR(1)e.SLR(1)?無二義文法一等分析表的構(gòu)造方法。c.SLR(

31、1)d.SLR(0)ob.LL(1)分析法e.LALR(1)分析法c. LR(0)?LR(1)e.LR(1)c.SLR(1)分析法 .SLR(1)?LR(1) .LR(1)?無二義文法6、對(duì)LR分析器來說，存在a.LALRb.LR(0)7、自上而下的語法分析方法有a.算符優(yōu)先分析法d.LR(0)分析法三、填空題1、對(duì)于一個(gè)文法，如果能夠構(gòu)造。使得它的均是唯一確定的，則稱該文法為L(zhǎng)R文法。2、字的前綴是指該字的。3、活前綴是指的一個(gè)前綴，這種前綴不含之后的任何符號(hào)。4、在LR分析過程中，只要的已掃描部分保持可歸約成一個(gè)，則掃描過的部分正確。5、將識(shí)別的NFA確定化，使其成為以為狀態(tài)的DFA,這個(gè)

32、DFA就是建立的基礎(chǔ)。6、A-a,稱為項(xiàng)目；對(duì)文法開始符Sa為項(xiàng)目；若a為終結(jié)符，則稱A一a,a3為項(xiàng)目；若B為非終結(jié)符，則稱A-a3為項(xiàng)目。7、LR(0)分析法的名字中“L”表示,“R”表示,“0表示。四、綜合題1、對(duì)于文法GS:S-AS|bA一SA|a(1)列出所有LR(0)項(xiàng)目(2)列出構(gòu)成文法LR(0)項(xiàng)目集規(guī)范族。單項(xiàng)解答：1、A-a稱為歸約項(xiàng)目，對(duì)文法開始符S的歸約項(xiàng)目，如Sa稱為接受項(xiàng)目，A-a,a3(a為終結(jié)符)稱為移進(jìn)項(xiàng)目。在此選b.2、當(dāng)用產(chǎn)生式Af“歸約時(shí)，LR(0)無論面臨什么輸入符號(hào)都進(jìn)行歸約；SLR(1)則僅當(dāng)面臨的輸入符號(hào)aCFOLLOW(A)時(shí)進(jìn)行歸約；LR(1

33、)則當(dāng)在把“歸約為A的規(guī)范句型的前綴陽a前提下，當(dāng)“后跟終結(jié)符a時(shí)，才進(jìn)行歸約；因此選do3、由于LR(0)?SLR(1)?LR(1)?無二義文法，故選c。4、選a。5、選c。多選解答:1、一個(gè)LR分析器包括一個(gè)總控程序和一張分析表，選a、do2、選c、e3、選a、c、d、e。4、在LR分析表的構(gòu)造中有可能存在“移進(jìn)”/“歸約”和“歸約”/“歸約”沖突；故選c、e。5、選a、b、c、d、e。6、選a、b、c、e。7、選a、c、d、e。填空解答：1、一張分析表每個(gè)入口2、任意首部3、規(guī)范句型句柄4、輸入串活前綴5、活前綴項(xiàng)目集合LR分析算法6、歸約接受移進(jìn)待約7、自左至右分析采用最右推導(dǎo)的逆過程

34、即最左歸約向右查看0個(gè)字符綜合解答：首先將文法G拓廣為GS:SfSSfAS|bAfSA|a1)文法GS的LR(0)項(xiàng)目是:1、SfS2、SfS3、SfAS4、SfAS5、SfAS6、Sfb7、S-b,8、AfSA9、AfSA10、AfSA11、Afa12、Afa2、列出構(gòu)成文法LR(0)項(xiàng)目集規(guī)范族。用e-CLOSURE(閉包)辦法構(gòu)造文法G的LR(0)項(xiàng)目集規(guī)范族如下：Io：1、SfSI3：9、AfSA12、A-a3、S-AS8、AfSAI7：7、S-b8、AfSA3、SfAS11、Afa6、Sfb6、Sfb11、Afa9、A-SA4、S-AS8、A一SA3、S一AS11、A一a6、S-b3

35、、S,AS8、A一SA6、S,b11、A一aI2：4、S一A,SI5:5、S一AS,3、S,AS9、A-SA6、S,b8、A一SA8、A一SA11、A一a11、A一a3、S一AS6、S-b注思：11中的S-,S和A一SA是由狀態(tài)I。中的1和3讀入一個(gè)S字符后得到的下一個(gè)項(xiàng)目;而I4中的A-SA和A-A-S則是由I3中的9和3讀入一個(gè)A字符后得到的下一個(gè)項(xiàng)目；中的SfAS和A-SA則是由I4中的4和8讀入一個(gè)S字符后得到的下一個(gè)項(xiàng)目。狀態(tài)全體構(gòu)成了文法G的LR(0)規(guī)范族。11:2、S一S,14：10、A-SAI5第七章、單項(xiàng)選擇題1、中間代碼生成所依據(jù)的是。d.等價(jià)變換規(guī)則d.程序變量d.a+

36、b+c/da.語法規(guī)則b.詞法規(guī)則c.語義規(guī)則2、四元式之間的聯(lián)系是通過實(shí)現(xiàn)的。a.指示器b.臨時(shí)變量c.符號(hào)表3、后綴式ab+cd+/可用表達(dá)式來表示。a.a+b/c+db.(a+b)/(c+d)c.a+b/(c+d)4、表達(dá)式3AVB)A(CVD)的逆波蘭表示為a. rABVACDVb. ArBVCDVAc. ABVnCDVAd. ArBVACDVO人入5、中間代碼的樹型表示ABCD所對(duì)應(yīng)的表達(dá)式為a.A+B+C+Db.A+(B+C)+Dc.(A+B)+C+Dd.(A+B)+(C+D)6、四元式表示法的優(yōu)點(diǎn)為a.不便于優(yōu)化處理，但便于表的更動(dòng)b.不便于優(yōu)化處理，但節(jié)省存儲(chǔ)空間c.便于優(yōu)化處

37、理，也便于表的更動(dòng)d.便于表的更動(dòng)，也節(jié)省存儲(chǔ)空間7、終結(jié)符具有屬性。a.傳遞b.繼承c.抽象d.綜合二、多頂選擇題1、中間代碼主要有a.四元式d.后綴式e.間接三元2、下面中間代碼形式中，能正確表示算術(shù)表達(dá)式a+b+c的有d.e.a+b+cbc+a.ab+c+b.abc+c.+bcab3、在下面的語法制導(dǎo)翻譯中，采用拉鏈-回填技術(shù)。a.賦值語句b.goto語句c.條件語句d.循環(huán)語句4、下列中間代碼形式有益于優(yōu)化處理。a.三元式b.四元式c.間接三元式d.逆波蘭表示法e.樹形表示法5、在編譯程序中安排中間代碼生成的目的是。a.便于進(jìn)行存儲(chǔ)空間的組織b.利于目標(biāo)代碼的優(yōu)化c.利于編譯程序的移植

38、d.利于目標(biāo)代碼的移植e.利于提高目標(biāo)代碼的質(zhì)量能正確表示算術(shù)表達(dá)式a+b*c。題）6、下面的中間代碼形式中，a.ab+c*b.abc*+7、三地址代碼語句具體實(shí)現(xiàn)通常有表示方法。a.逆波蘭表示b.三元式c.間接三元式d.樹形表示e.四元式三、填空題1、中間代碼有等形式，生成中間代碼主要是為了使。2、語法制導(dǎo)翻譯既可以用來產(chǎn)生代碼，也可以用來產(chǎn)生指令，甚至可用來對(duì)輸入串進(jìn)行。3、當(dāng)源程序中的標(biāo)號(hào)出現(xiàn)“先引用后定義”時(shí)，中間代碼的轉(zhuǎn)移地址須持時(shí)才能確定，因而要進(jìn)行。4、文法符號(hào)的屬性有兩種，一種稱為,另一種稱為。5、后綴式abc-/所代表的表達(dá)式是,表達(dá)式(a-b)*c可用后綴式表示。6、用一張

39、輔以的辦法來表示中間代碼，這種表示法稱為間接三元式。四、綜合題1、給出下列表達(dá)式的逆波蘭表示(后綴式)：a*(-b+c)(AVB)A(CVrDAE)2、寫出算術(shù)表達(dá)式：A+B*(C-D)+E/(C-D)TN的四元式序列；三元式序列；間接三元式序列單選解答1、選Co2、四元式之間的聯(lián)系是通過臨時(shí)變量實(shí)現(xiàn)的，故選bo3、選bo4、選bo5、選do6、四元式表示法的優(yōu)點(diǎn)與間接三元式相同，故選Co7、選do多選解答1、選a、c、d、e。2、b、d的中間代碼不能正確表示a+b+c,而e不是中間代碼：故選a、c。3-凡涉及到跳轉(zhuǎn)的語句都需要采用拉鏈一一回填技術(shù)，故選b、c、d。4、選b、c。5、選b、do

40、6、選b、e。7、選b、c、e。填空解答1、逆波蘭記號(hào)、樹形表示、三元式、四元式目標(biāo)代碼的優(yōu)化容易實(shí)現(xiàn)2、中間目標(biāo)解釋執(zhí)行3、標(biāo)號(hào)定義回填4、繼承屬性綜合屬性5、a/(b-c)ab-c*6、間接碼表三兀式表綜合解答1、 abc+*; ABVCDrEAVA(1)(-,C,D,T1)(1)(-,C,D)(1)(-CD)(2)(*,B,T1,T2)(2)(*,B,(1)(2)(*,B,(1)(3)(+,A,T2,T3)(3)(+,A,(2)(3)(+,A,(2)(4)(-,C,D,T4)(4)(-,C,D)(4)(T,(1),N)(5)(T,T4,N,T5)(5)(4),N)(4)(/,E,(4)(

41、6)(/,E,T5,T6)(/,E,(5)(6)(+,(3),(5)(+,T3,T6,T7)(+,(3),(6)(6)表達(dá)式的二兀式序列間接三元式序列2、表達(dá)式的四元式序列:第八章一、單項(xiàng)選擇題1、編譯程序使用區(qū)別標(biāo)識(shí)符的作用域。a.說明標(biāo)識(shí)符的過程或函數(shù)名b.說明標(biāo)識(shí)符的過程或函數(shù)的靜態(tài)層次c.說明標(biāo)識(shí)符的過程或函數(shù)的動(dòng)態(tài)層次d.標(biāo)識(shí)符的行號(hào)2、在目標(biāo)代碼生成階段，符號(hào)表用于。a.目標(biāo)代碼生成b.語義檢查c.語法檢查d.地址分配3、過程信息表不包含。a.過程入口地址b.過程的靜態(tài)層次c.過程名d.過程參數(shù)信息4、下列關(guān)于標(biāo)識(shí)符和名字?jǐn)⑹鲋?，正確的是。a.標(biāo)識(shí)符有一定的含義b.名字是一個(gè)沒有意

42、義的字符序列c.名字有確切的屬性d.ac都不正確二、多項(xiàng)選擇題1、符號(hào)表的每一項(xiàng)均包含。a.名字欄b.類型欄c.信息欄d.值欄e.ad均包含2、對(duì)編譯程序所用到的符號(hào)表，涉及的操作有。a.填寫或更新信息欄內(nèi)容b.填入新名c.給定名字，訪問它的有關(guān)信息d.雜湊技術(shù)e.線性表和排序二叉樹3、源程序中的錯(cuò)誤一般有。a.詞法錯(cuò)誤b.語法錯(cuò)誤c.語義錯(cuò)誤d.編譯錯(cuò)誤e.違反環(huán)境限制的錯(cuò)誤三、填空題1、符號(hào)表中名字欄內(nèi)容有兩種填寫方式，它們是填寫和填寫。2、詞法分析階段的錯(cuò)誤主要是,可通過的辦法糾正錯(cuò)誤。3、符號(hào)表中名字的有關(guān)信息在和過程中陸續(xù)填入。4、在目標(biāo)代碼生成階段，符號(hào)表是的依據(jù)。四、問答題：1、

43、在編譯過程中為什么要建立符號(hào)表？單選解答：1、b2、d3、b4、c多選解答：1、a、c2、a、b、c3、a、b、c、e填空解答：1、標(biāo)識(shí)符標(biāo)識(shí)符地址及長(zhǎng)度2、拼寫錯(cuò)誤最小距離匹配3、詞法分析語法語義分析4、地址分配問答題解答：在編譯過程中始終要涉及到對(duì)一些語法符號(hào)的處理，這就需要用到語法符號(hào)的相關(guān)屬性。為了在需要時(shí)能找到這些語法成分及其相關(guān)屬性，就必須使用一些表格來保存這些語法成分及其屬性，這些表格就是符號(hào)表。第九章一、單項(xiàng)選擇題1、程序所需的數(shù)據(jù)空間在程序運(yùn)行前可確定，稱為管理技術(shù)。a.動(dòng)態(tài)存儲(chǔ)b.棧式存儲(chǔ)c.靜態(tài)存儲(chǔ)d.堆式存儲(chǔ)2、堆式動(dòng)態(tài)分配申請(qǐng)和釋放存儲(chǔ)空間遵守原則。a.先請(qǐng)先放b.先

44、請(qǐng)后放c.后請(qǐng)先放d.任意3、靜態(tài)分配允許程序出現(xiàn)。a.遞歸過程b.可變體積的數(shù)據(jù)項(xiàng)目c.靜態(tài)變量d.待定性質(zhì)的名字4、在編譯方法中，動(dòng)態(tài)存儲(chǔ)分配的含義是。a.在運(yùn)行階段對(duì)源程序中的數(shù)組、變量、參數(shù)等進(jìn)行分配b.在編譯階段對(duì)源程序中的數(shù)組、變量、參數(shù)進(jìn)行分配c.在編譯階段對(duì)源程序中的數(shù)組、變量、參數(shù)等進(jìn)行分配，在運(yùn)行時(shí)這些數(shù)組、變量、參數(shù)的地址可根據(jù)需要改變d.以上都不正確5、在編譯時(shí)有傳名功能的高級(jí)程序語言是。a.Fortranb.Basicc.Pascald.ALGOL6、棧式動(dòng)態(tài)分配與管理在過程返回時(shí)應(yīng)做的工作有。a.保護(hù)SPb.恢復(fù)SPc.保護(hù)TOPd.恢復(fù)TOP二、多項(xiàng)選擇題1、下面

45、需要在運(yùn)行階段分配存儲(chǔ)空間。a.數(shù)組d.靜態(tài)變量b.指針變量e.動(dòng)態(tài)變量c.動(dòng)態(tài)數(shù)組2、棧式動(dòng)態(tài)分配允許a.遞歸過程b.分程序結(jié)構(gòu)c.動(dòng)態(tài)變量d.動(dòng)態(tài)數(shù)組e.靜態(tài)數(shù)組3、動(dòng)態(tài)存儲(chǔ)分配可采用的分配方案有a.隊(duì)式存儲(chǔ)分配b.棧式存儲(chǔ)分配c.鏈?zhǔn)酱鎯?chǔ)分配d.堆式存儲(chǔ)分配e.線性存儲(chǔ)分配4、棧式動(dòng)態(tài)分配與管理因調(diào)用而進(jìn)入過程之后，要做的工作是。a.定義新的活動(dòng)記錄的SPb.保護(hù)返回地址c.傳遞參數(shù)值d.建立DISPLAY表e.定義新的活動(dòng)記錄的TOP5、靜態(tài)分配不允許程序出現(xiàn)a.遞歸過程b.靜態(tài)數(shù)組c.可變體積的數(shù)據(jù)項(xiàng)目d.待定性質(zhì)的名字e.靜態(tài)變量6、活動(dòng)記錄包括a.局部變量b.連接數(shù)據(jù)c.形式單元d.局部數(shù)組的內(nèi)情