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

第一章1、將編譯程序分成假設(shè)干個“遍〞是為了.b.使程序的結(jié)構(gòu)更加清楚2、構(gòu)造編譯程序應(yīng)掌握.a.源程序b.目標語言c.編譯方法3、變量應(yīng)當.c.既持有左值又持有右值4、編譯程序絕大多數(shù)時間花在上.d.治理表格5、不可能是目標代碼.d.中間代碼6、使用可以定義一個程序的意義.a.語義規(guī)那么7、詞法分析器的輸入是.b.源程序8、中間代碼生成時所遵循的是-.c.語義規(guī)那么9、編譯程序是對.d.高級語言的譯10、語法分析應(yīng)遵循.c.構(gòu)詞規(guī)那么二、多項選擇題1、編譯程序各階段的工作都涉及到.b.表格治理c.出錯處理2、編譯程序工作時,通常有階段.a.詞法分析b.語法分析c.中間代碼生成e.目標代碼生成三、填空題1、解釋程序和編譯程序的區(qū)別在于是否生成目標程序.2、編譯過程通?？煞譃?個階段,分別是一詞法分析—、語法分析中間代碼生成—、代碼優(yōu)化和目標代碼生成.3、編譯程序工作過程中,第一段輸入是—源程序,最后階段的輸出為標代碼生成程序.4、編譯程序是指將源程序程序譯成目標語言程序的程序.、單項選擇題1、文法G:SfxSx|y所識別的語言是.a.xyxb.(xyx)*c.xnyxn(n>0)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、有限狀態(tài)自動機能識別.a.上下文無關(guān)文法b.上下文有關(guān)文法c.正規(guī)文法d.短語文法4、設(shè)G為算符優(yōu)先文法,G的任意終結(jié)符對a、b有以下關(guān)系成立.a.假設(shè)f(a)>g(b),那么a>bb.假設(shè)f(a)<g(b),那么a<bc.a~b都不一定成立d.a~b一定成立5、如果文法G是無二義的,那么它的任何句子a.a.最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同b.最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同c.最左推導(dǎo)和最右推導(dǎo)必定相同d.可能存在兩個不同的最左推導(dǎo),但它們對應(yīng)的語法樹相同6、由文法的開始符經(jīng)0步或多步推導(dǎo)產(chǎn)生的文法符號序列是.a.短語b.句柄c.句型d.句子7、文法G:E-E+T|TT一T*P|PP一(E)|I那么句型P+T+i的句柄和最左素短語為.a.P+T和ib.P和P+Tc.i和P+T+id.P和T8、設(shè)文法為：S-SA|AA-a|b那么對句子aba,下面是標準推導(dǎo).S：SA=,SAA=AAA=,aAA=abA：abaS：SA=SAA=AAA=AAa=Aba=abaS：SA=SAA=SAa:Sba:Aba=abaS：SA=Sa：SAa=Sba:Aba：aba9、文法G:Sfb|A(T)T-T,S|S貝UFIRSTVT(T).

10、產(chǎn)生正規(guī)語言的文法為a.0型b.1型11、米用自上而卜分析,必須.c.2型d.3型a.消除左遞歸b.消除右遞歸c.消除回溯d.提取公共左因子12、在標準歸約中,用來刻回可歸約串.a.直接短語b.句柄c.最左素短語d.素短語a.{ba.{b,A,()b.{b,A,))c.{b,A,(,,)d.{b,A,),,)13、有文法G:E-E*T|TT-T+i|i句子1+2*8+6按該文法G歸約,其值為d.17b.最右推導(dǎo)的逆過程d.17b.最右推導(dǎo)的逆過程d.最左歸約的逆過程b.狀態(tài)轉(zhuǎn)換圖是一個有向圖d.DFA可以用狀態(tài)轉(zhuǎn)換圖表示14、標準歸約指.a.最左推導(dǎo)的逆過程c.標準推導(dǎo)二、多項選擇題1、下面哪些說法是錯誤的.a.有向圖是一個狀態(tài)轉(zhuǎn)換圖c.有向圖是一個DFA2、對無二義性文法來說,一棵語法樹往往代表了.a.多種推導(dǎo)過程b.多種最左推導(dǎo)過程c.一種最左推導(dǎo)過程d.僅一種推導(dǎo)過程e.一種最左推導(dǎo)過程之一時,那么稱該文法是二義文法.3、如果文之一時,那么稱該文法是二義文法.a.該句子的最左推導(dǎo)與最右推導(dǎo)相同b.該句子有兩個不同的最左推導(dǎo)c.該句子有兩棵不同的最右推導(dǎo)d.該句子有兩棵不同的語法樹e.該句子的語法樹只有一個4、有一文法G:S-ABAfaAb|￡BfcBd|￡它不產(chǎn)生下面集合.a.{anbmcndm|n,m>0}b.{anbncmdm|n,m>0}c.{anbmcmdn|n,m>0}d.{anbncmdm|n,m>0}e.{anbncndn|n>0}5、自下而上的語法分析中,應(yīng)從開始分析.a.句型b.句子c.以單詞為單位的程序d.文法的開始符e.句柄6、對正規(guī)文法描述的語言,以下有水平描述它.a.0型文法b.1型文法c.上下文無關(guān)文法d.右線性文法e.左線性文法三、填空題1、文法中的終結(jié)符和非終結(jié)符的交集是.詞法分析器交給語法分析器的文法符號一定是,它一定只出現(xiàn)在產(chǎn)生式的部.2、最左推導(dǎo)是指每次都對句型中的非終結(jié)符進行擴展.3、在語法分析中,最常見的兩種方法一定是分析法,另一是分析法.4、采用語法分析時,必須消除文法的左遞歸.5、樹代表推導(dǎo)過程,樹代表歸約過程.6、自下而上分析法采用、歸約、錯誤處理、等四種操作.7、Chomsky把文法分為種類型,編譯器構(gòu)造中采用和文法,它們分別產(chǎn)生和語言,并分別用和自動機識別所產(chǎn)生的語言.四、判斷題TOC\o"1-5"\h\z1、文法S-aS|bR|e描述的語言是〔a|bc〕*〔〕RfcS2、在自下而上的語法分析中,語法樹與分析樹一定相同.〔〕3、二義文法不是上下文無關(guān)文法.〔〕4、語法分析時必須先消除文法中的左遞歸.〔〕5、標準歸約和標準推導(dǎo)是互逆的兩個過程.〔〕6、一個文法所有句型的集合形成該文法所能接受的語言.〔〕五、簡做題1、句柄2、素短語3、語法樹4、歸約5、推導(dǎo)六、問做題1、給出上下文無關(guān)文法的定義.2、文法G[S]:S一aSPQ|abQQDPQbP一bbbQ一bccQ—cc〔1〕它是Chomsky哪一型文法〔2〕它生成的語言是什么3、按指定類型,給出語言的文法.L={aibj|j>i>1}的上下文無關(guān)文法.4、有文法G:SfaAcB|BdAfAaB|cB一bScA|b(1)試求句型aAaBcbbdcc和aAcbBdcc的句柄；(2)寫出句子acabcbbdcc的最左推導(dǎo)過程.5、對于文法G[S]:S一(L)|aS|a1_一1_,S|S(1)畫出句型(S,(a))的語法樹.(2)寫出上述句型的所有短語、直接短語、句柄和素o6、考慮文法G[T]:T-T*F|FFfFTP|PP-(T)|i證實T*PT(T*F)是該文法的一個句型,并指出直接短語和句柄.單項選擇[解答]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)系：應(yīng)選c.5、如果文法G無二義性,那么最左推導(dǎo)是先生長右邊的枝葉：對于d,如果有兩個不同的TOC\o"1-5"\h\z是了左推導(dǎo),那么必然有二義性.應(yīng)選a.E6、選c./!\E+F7、由圖2-8-1的語法樹和優(yōu)先關(guān)系可以看出應(yīng)選bo?E+TPII一iP#<+>+<i>#圖2-8-1句型P+T+I的語法及優(yōu)先關(guān)系8、標準推導(dǎo)是最左推導(dǎo),應(yīng)選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、移進接受7、42型3型上下文無關(guān)語言正規(guī)語言下推自動機有限判斷解答1、對2、錯3、錯4、錯5、錯6、錯簡答［解答］1、句柄：一個句型的最左直接短語稱為該句型的句柄.2、素短語：至少含有一個終結(jié)符的素短語,并且除它自身之外不再含任何更小的素短語.3、語法樹：滿足下面4個條件的樹稱之為文法G［S］的一棵語法樹.①每一終結(jié)均有一標記,此標記為VnUVt中的一個符號；②樹的根結(jié)點以文法G［S］的開始符S標記；③假設(shè)一結(jié)點至少有一個直接后繼,那么此結(jié)點上的標記為Vn中的一個符號；④假設(shè)一個以A為標記的結(jié)點有K個直接后繼,且按從左至右的順序,這些結(jié)點的標記分另I為Xi,X2,,Xk,那么AXi,X2,,Xk,必然是G的一個產(chǎn)生式.4、歸約：我們稱“丫3直接歸約出aA3,僅當A-丫是一個產(chǎn)生式,且a、3C(VnUVt)*.歸約過程就是從輸入串開始,反復(fù)用產(chǎn)生式右部的符號替換成產(chǎn)生式左部符號,直至文法開始符.5、推導(dǎo)：我們稱aA3直接推出a丫3,即aA3=a丫3,僅當A一丫是一個產(chǎn)生式,且a、3C(VnUVt)*o如果ai=ta2=i…3an,那么我們稱這個序列是從ai至a2的一'個推導(dǎo).假設(shè)存在一個從…n的推導(dǎo),那么稱“1可推導(dǎo)出&no推導(dǎo)是歸約的逆過程.問答1［解答］一個上下文無關(guān)文法G是一個四元式(Vt,Vn,S,P),其中：Vt是一個非空有限集,它的每個元素稱為終結(jié)符號；Vn是一個非空有限集,它的每個元素稱為非終結(jié)符號,VtAVn=①；S是一個非終結(jié)符號,稱為開始符號；P是一個產(chǎn)生式集合(有限),每個產(chǎn)生式的形式是P-a,其中,PCVn,aC(VtUVn)*.開始符號S至少必須在某個產(chǎn)生式的左部出現(xiàn)一次.2［解答］(1)由于產(chǎn)生式左部存在終結(jié)符號,且所有產(chǎn)生式左部符號的長度均小于等于產(chǎn)生式右部的符號長度,所以文法G［S］是Chomsky1型文法,即上下文有關(guān)文法.(2)按產(chǎn)生式出現(xiàn)的順序規(guī)定優(yōu)先級由高到低(否那么無法推出句子),我們可以得到：SabQ=abcSaSPQaabQPQ=aabPQQ=aabbQQ=aabbcQaabbccSaSPQaaSPQPQ=aaabQPQPQ=aaabPQQPQ=aaabPQPQQ=aaaPPQQQ二aaabbPqqq=aaabbQQQ=-aaabbbcQQ=aaabbbccQ,:aaabbbccc……于是得到文法G[S]生成的語言L={anbncn|n>1}3【解答】(1)由L={abj|j>in1}知,所求該語言對應(yīng)的上下文無關(guān)文法首先應(yīng)有S-aSb型產(chǎn)生式,以保證b的個數(shù)不少于a的個數(shù)；其次,還需有S-Sb或S-bS型的產(chǎn)生式,用以保證b的個數(shù)多于a的個數(shù)；也即所求上下文無關(guān)文法G[S]為：G[S]:S-aSb|Sb|b4【解答】(1)分別畫出對應(yīng)兩句型的語法樹,如圖2-8-2所示TOC\o"1-5"\h\z句柄：AaBBdSS…cB...……AaBbAct八Bdc八Bdcb(a)(b)圖2-8-2語法樹(2)句子acabcbbdcc的最左推導(dǎo)如下：S:aAcB:aAaBcB=acaBcB:acabcB:acabcbScA:acabcbBdcA=acabcbbdcAacabcbbdcc5【解答】S(1)句型(S,(a))的語法樹如圖2-8-3所示/?\(L)L?S/1\s(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)系求得,即;#<(V,V(Va>)?)>#因此素短語為a.6【解答】首先構(gòu)造T*PT(T*F)的語法樹如圖2-8-4所示.由圖2-8-4可知,T*PT(T*F)是文法G[T]的一個句型.直接短語有兩個,即P和T*F;句柄為P.、單項選擇題1、詞法分析所依據(jù)的是—.a.語義規(guī)、單項選擇題1、詞法分析所依據(jù)的是—.a.語義規(guī)那么b.構(gòu)詞規(guī)那么2、詞法分析器的輸出結(jié)果是—.a.單詞的種別編碼c.單詞的種別編碼和自身值3、正規(guī)式Mi和M2等價是指,Mi和M2的狀態(tài)數(shù)相等c.Mi和M2所識別的語言集相等第三章c.語法規(guī)那么d.等價變換規(guī)那么b.單詞在符號表中的位置d.單詞自身值Mi和M2的有向弧條數(shù)相等d.M1和M2狀態(tài)數(shù)和有向弧條數(shù)相等4、狀態(tài)轉(zhuǎn)換圖(見圖3-6-1)接受的字集為圖3-6-1a.以0開頭的二進制數(shù)組成的集合b.以0結(jié)尾的二進制數(shù)組成的集合c.含奇數(shù)個0的二進制數(shù)組成的集合d,含偶數(shù)個0的二進制數(shù)組成的集合5、詞法分析器作為獨立的階段使整個編譯程序結(jié)構(gòu)更加簡潔、明確,因此,a,a,詞法分析器應(yīng)作為獨立的一遍b,詞法分析器作為子程序較好c,詞c,詞法分析器分解為多個過程,由語法分析器選擇使用d,詞法分析器并不作為一個獨立的階二、多項選擇題在詞法分析中,能識別出a,根本在詞法分析中,能識別出a,根本字b,四元式c,運算符d.逆波蘭式e,常數(shù)令匯={a,b},那么匯上所有以b開頭,后跟假設(shè)干個ab的字的全體對應(yīng)的正規(guī)式為a,b(a,b(ab)*d,(ba)+b三、填空題+b,b(ab)e,b(a|b)c.(ba)*b1、確1、確定有限自動機DFA是的一個特例.2、2、假設(shè)二個正規(guī)式所表示的相同,那么認為二者是等價的.3、3、一個字集是正規(guī)的,當且僅當它可由所.四、判斷題1、一個有限狀態(tài)自動機中,有且僅有一個唯一終態(tài).2、設(shè)r和s分別是正規(guī)式,那么有L(r|s)=L(r)|L(s).3、自動機M和M'的狀態(tài)數(shù)不同,那么二者必不等價.4、確定的自動機以及不確定的自動機都能正確地識別正規(guī)集.5、對任意一個右線性文法5、對任意一個右線性文法G,都存在一個NFAM,滿足L(G)=L(M).6、對任意一個右線性文法G,都存在一個DFAM,滿足L(G)=L(M).7、對任何正規(guī)表達式e,都存在一個NFAM,滿足L(G)=L(e).8、對任何正規(guī)表達式e,都存在一個DFAM,滿足L(G)=L(e).五、基此題1、設(shè)M=({x,y},{a,b},f,x,{y})為一非確定的有限自動機,其中f定義如下:f(x,a)={x,y}f(x,b)={y}ff(y,b)={x,y}f(y,a)=(f)試構(gòu)造相應(yīng)確實定有限自動機M2、對給定正規(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)所識別判斷解答1、2、3、錯4、5、6、7、8、正確根本根本1解答:對照自動機的定義M=(S,2,f,S,z),由f的定義可知f(x,a)、f(y,b)均為多值函數(shù),所以是一非確定有限自動機,先畫出NFAM相應(yīng)的狀態(tài)圖,如圖3-6-2所示.將圖3-6-5的將圖3-6-5的DFAM'最小化.首先,將M'的狀態(tài)分成終態(tài)組{1,2}與非終態(tài)組{0};其次,考察{1,2}.由于{1,2}a={1,2}b={2}?{1,2},所以不再將其劃分了,也即整個劃分只有兩組{1,2}:令狀態(tài)1代表{1,2},即把原來至沙所示化簡DFAM'.b1酬除狀態(tài)2.最后,得到如圖{0},3-6-6圖3-6-6化簡后的DFAM'2解答2解答：首先用如圖3-6-7所示.NFAM,用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣表3-6-3所示.IIaIb{X}{x,y}{y}{y}一{x,y}{x,y}{x,y}{x,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|￡下面文法G[S]是否為LL(1)文法說明理由.SfAB|PQxA-xyB-bcPfdP|eQ-aQ|e設(shè)有以下文法：G[S]:SfaAbDe|dAfBSD|eBfSAc|cD|￡DfSe|e(1)求出該文法的每一個非終結(jié)符U的FOLLOW集(2)該文法是LL(1)文法嗎?(3)構(gòu)造C[S]的LL(1)分析表.將文法G[V]改造成為LL(1)的.G[V]:VfN|N[E]E-V|V+E5、文法:G[A]:A-aAa|￡(1)該文法是LL(1)文法嗎?為什么(2)假設(shè)采用LL(1)方法進行語法分析,如何得到該文法的LL(1)分析表?(3)假設(shè)輸入符號串“aaaa〞,請給出語法分析過程.1解答：LL(1)分析表見表4-3-1分析雖然這個文法很簡單,我們還是從求開始符號集合和后繼符號集合開始.FIRST(D)=FIRST(T)={int,real}FOLLOW(D)=FOLLOW(L)={#}FIRST(L)={id}FOLLOW(T)={id}FIRST(R)={,,卜FOLLOW(R)={#}有了上面每個非終結(jié)符的FIRST集合,填分析表時要計算一個產(chǎn)生式右部a的FIRST(亦就不是件難事了.填表時唯一要小心的時,e是產(chǎn)生式R-e右部的一個開始符號,而#在FOLLOW(R)中,所以R-e填在輸入符號#的欄目中.表4-3-1LL(1)分析表非終結(jié)符輸入符號intrealid#DDfTLDfTLTT-intT一realLLTdRRRf,idRR一￡2解答：該文法不是LL(1)文法,見下面分析中的說明.分析只有三個非終結(jié)符有兩個選擇.1、P的兩個右部dP和e的開始符號肯定不相交.2、Q的兩個右部aQ和￡的開始符號肯定不相交.3、對S來說,由于x￡FIRST(AB),同時也有x￡FIRST(PQx)(由于P和Q都可能為空).所以該文法不是LL(1)文法.3解答：(1)求文法的每一個非終結(jié)符U的FOLLOW集的過程如下：由于：S是識別符號,且有AfBSD、BfSAc、DfSe,所以FOLLOW(S)應(yīng)包含F(xiàn)IRST(D)UFIRST(Ac)UFIRST(e)U{#}={a,d}U{a,d,c,e}U{e}U{#}={a,c,d,e#}又由于AfBSD和D一s,所以FOLLOW中還包含F(xiàn)OLLOW(A).由于SfaAbDe和B-SAc,所以FOLLOW(A)=FIRST(bDe)UFIRST(c)={b,c}綜合①、②得FOLLOW(S)={a,d,c,e,#}U{a,b,c,d,e,#}由于A-BSD,所以FOLLOW(B)=FIRST(SD)={a,d}由于SfaAbDe|d、A-BSD|e和B-SAc|cD,所以FOLLOW(D)=FIRST(e)UFOLLOW(A)UFOLLOW(B)={e}U{b,c}U{a,d}={a,b,c,d,e}(2)G[S]不是LL(1)文法.由于產(chǎn)生式BfSAc|cD|￡中FIRST(SAc)nFOLLOW(B)={a,d}w?(3)構(gòu)造G[S]的LL(1)分析表.根據(jù)LL(1)分析表的構(gòu)造算法構(gòu)造方法G[S]的LL(1)分析表如表4-3-2所示.表4-3-2G[S]的LL(1)分析表abcde#SaAbDedABSDBSDBSDeBSac/ecDSac/eDSe/￡￡￡Se/￡￡4解答：對文法G[V]提取公共左因子后得到文法:G[V]:V-NAA一或E]E一VBBfH+ENfi求出文法G[V]中每一個非終結(jié)符號的FIRST集:FIRST(V)={i}FIRST(A)={[,}FIRST(E)={i}FIRST(B)={+,}FIRST(N)={i}求出文法G[V]中每一個非終結(jié)符號的FOLLOW集：FOLLOW(V)={#}UFIRST(B)\{4UFOLLOW(E)={#,+,]}FOLLOW(A)=FOLLOW(V)={+,,#}FOLLOW(E)=FIRST(])\{4UFOLLOW(B)=FIRST(])\{}UFOLLOW(E)={]}FOLLOW(B)=FOLLOW(E)={]}FOLLOW(N)=FIRST(A)\{3UFOLLOW(V)={[,],+,#}可以看到,對文法G[V]的產(chǎn)生式A一或E],有FIRST([E])AFOLLOW(A)={[}n{+,],#}=?對產(chǎn)生式B一耳+E,有FIRST(+E)AFOLLOW(B)={+}n{]}=?而文法的其他產(chǎn)生式都只有一個不為由勺右部,所以文法G[V]是LL(1)文法.5解答：(1)由于產(chǎn)生式A-aAa|e有空產(chǎn)生式右部,而FOLLOW(A)={#}UFIRST(a)={a,#}造成FIRST(A)nFOLLOW(A)={A,}n{a,#}w?所以該文法不是LL(1)文法.(2)假設(shè)采用LL(1)方法進行語法分析,必須修改該文法.因該文法產(chǎn)生偶數(shù)(可以為0)個a,所以得到文法G[A]:A-aaA|日此時對產(chǎn)生式A-aaA|e,有FOLLOW(A)={#}UFOLLOW(A)={#},因而FIRST(A)nFOLLOW(A)={a,}n{#}=?所以文法G[A]是LL(1)文法,按LL(1)分析表構(gòu)造算法構(gòu)造該文法的LL(1)分析表如表4-3-3所不.表4-3-3文法G'[A]的LL(1)分析表A#AA-aaAA一日(3)假設(shè)采用LL(1)方法進行語法分析,對符號串“aaaa〞的分析過程如表4-3-4所示.表4-3-4對符號串“aaaa〞的分析過程步驟分析棧輸入串產(chǎn)生式/動作1#Aaaaa#A-aaA2#Aaaaaaa#匹配3#Aaaaa#匹配4#Aaa#A-aaA5#Aaaaa#匹配6#Aaa#匹配7#A#A一日8##接受第五章.設(shè)有文法G[S]為:S一a|b|(A)AfSdA|S(1)完成以下算符優(yōu)先關(guān)系表,見表5-7-1,并判斷G[S]是否為算符優(yōu)先文法.表5-7-1算符優(yōu)先關(guān)系表ab()d#a??b??(????)??d#????(2)給出句型(SdSdS)的短語、簡單短語、句柄、素短語和最左素短語.(3)給出輸入串(adb)#的分析過程.解答：(1)先求文法G[S]的FIRSTVT集和LASTVT集:由S-a|b|(A)得：FIRSTVT(S)={a,b,();由AfSd得：FIRSTVT(A)=sctkbsg;又由A-S得：FIRSTVT(S)?FIRSTVT(A),即FIRSTVT(A)={d,a,b,(};由S-a|b|(A)得；LASTVT(S)={a,b,}};由A一dA得：LASTVT(A)=zoupzqb,又由A-S得：LASTVT(S)?LASTVT(A),即LASTVT(A)={d,a,b,)}.構(gòu)造優(yōu)先關(guān)系表方法如下：①對Pf…ab…,或Pf…aQb…,有a?b;②對P—aR,而bCFIRSTVT(R),有a?b;③對PfRb,而aCFIRSTVT(R),有a?b.由此得到：①由S一(A)得：(?);②由S一(A得：(?FIRSTVT(A),即：(?d,(?a,(?b,(?(油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可以看出,任何兩個終結(jié)符之間至少只滿足、、三種優(yōu)先關(guān)系之一,故G[S]為算符優(yōu)先文法.S〔2〕為求出句型〔SdSdS〕的短語、簡單短語、句柄,我們先畫出該句型對應(yīng)的語法樹,如圖5-7-3所示.由圖5-7-3得到：S短語：S,SdS,SdSdS,〔SdSdS〕簡單短語〔即直接短語〕：S句柄〔即最左直接短語〕：S素短語：SdS,它同時也是該句型的最左素短語.圖5-7-3句型〔SdSdS〕的語法樹〔3〕輸入串〔adb〕#的分析過程見表5-7-4表5-7-4輸入串〔adb〕#的分析過程符號棧輸入串說明#(adb)#移進#(adb)#移進#(adb)#用S-a歸約#(Sdb)#移進#(Sdb)#移進#(Sdb)#用S-b歸約#(SdS)#用A-S歸約#(SdA)#用A-SdA歸約#(A)#移進#(A)#用S-(A)歸約#S#分析成功第六章一、單項選擇題1、假設(shè)a為終結(jié)符,那么A-a?a3為工程a.歸約b.移進c.接受d.待約2、假設(shè)工程集Ik含有A-a-,那么在狀態(tài)k時,僅當面臨的輸入符號a?OLLOW(A)時,才采取“A-動作的一定是.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.無二義文法LR4、在LR(0)的ACTION子表中,如果某一行中存在標記"j’的欄,那么.a.該行必定填滿rjb.該行未填滿rjc.其他行也有rjd.goto子表中也有rj5、一個指明了在分析過程中的某時刻所能看到產(chǎn)生式多大一局部.a.活前綴b.前綴c.工程d.工程集二、多項選擇題1、一個LR分析器包括.a.一個總控程序b.一個工程集c.一個活前綴d.一張分析表e.一個分析棧2、LR分析器核心局部是一張分析表,該表包括等子表.a.LL(1)分析b.優(yōu)先關(guān)系c.GOTOd.LRe.ACTION3、每一項ACTION[S,a]所規(guī)定的動作包括.a.移進b.比擬c.接受d.歸約e.報錯4、對LR分析表的構(gòu)造,有可能存在動作沖突.

a.移a.移進b.歸約c.移進/歸約d.移進/移進e.歸約/歸約5、就文法的描述水平來說,有LR(1)?SLR(1)e.SLR(1)?SLR(1)e.SLR(1)?無二義文法一等分析表的構(gòu)造方法.c.SLR(1)d.SLR(0)ob.LL(1)分析法e.LALR(1)分析法LR(0)?LR(1)e.LR(1)c.SLR(1)分析法.LR(1)?無二義文法6、對LR分析器來說,存在a.LALRb.LR(0)7、自上而下的語法分析方法有a.算符優(yōu)先分析法d.LR(0)分析法三、填空題1、對于一個文法,如果能夠構(gòu)造.使得它的均是唯一確定的,那么稱該文法為LR文法.2、字的前綴是指該字的.3、活前綴是指的一個前綴,這種前綴不含之后的任何符號.4、在LR分析過程中,只要的已掃描局部保持可歸約成一個—,那么掃描過的局部正確.5、將識別的NFA確定化,使其成為以為狀態(tài)的DFA,這個DFA就是建立的根底.6、A->a,稱為工程；對文法開始符S>a?為工程；假設(shè)a為終結(jié)符,那么稱A一a,a3為工程；假設(shè)B為非終結(jié)符,那么稱A-"a3為工程.7、LR(0)分析法的名字中“L〞表示,“R〞表示,“0"表示.四、綜合題1、對于文法G[S]:S-AS|bA一SA|a(1)列出所有LR(0)工程(2)列出構(gòu)成文法LR(0)工程集標準族.單項解答：1、A->a?稱為歸約工程,對文法開始符S'的歸約工程,如S>a?稱為接受工程,A->a,a3(a為終結(jié)符)稱為移進工程.在此選b.2、當用產(chǎn)生式Af“歸約時,LR(0)無論面臨什么輸入符號都進行歸約；SLR(1)那么僅當面臨的輸入符號aCFOLLOW(A)時進行歸約；LR(1)那么當在把“歸約為A的標準句型的前綴陽a前提下,當“后跟終結(jié)符a時,才進行歸約；因此選do3、由于LR(0)?SLR(1)?LR(1)?無二義文法,應(yīng)選c.4、選a.

5、選c.多項選擇解答:1、一個LR分析器包括一個總控程序和一張分析表,選a、do2、選c、e°3、選a、c、d、e.4、在LR分析表的構(gòu)造中有可能存在“移進〞/“歸約〞和“歸約〞/“歸約〞沖突；應(yīng)選c、e.5、選a、b、c、d、e.6、選a、b、c、e.7、選a、c、d、e.填空解答：1、一張分析表每個入口2、任意首部3、標準句型句柄4、輸入串活前綴5、活前綴工程集合LR分析算法6、歸約接受移進待約7、自左至右分析采用最右推導(dǎo)的逆過程即最左歸約向右查看0個字符綜合解答：首先將文法G拓廣為G[S]:SfSSfAS|bAfSA|a1)文法G[S]的LR(0)工程是:1、S1、SfS2、SfS3、SfAS4、SfAS5、SfAS6、Sfb7、S-b,8、AfSA9、AfSA10、AfSA11、Afa12、Afa2、列出構(gòu)成文法LR(0)工程集標準族.用e-CLOSURE(閉包)方法構(gòu)造文法G'的LR(0)工程集標準族如下：Io：1、SfSI3：9、AfSA"12、A-a3、S-AS8、AfSAI7：7、S-b8、AfSA3、SfAS11、Afa6、Sfb6、Sfb11、Afa

9、A-SA4、S-AS8、A一SA3、S一AS11、A一a6、S-b3、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讀入一個S字符后得到的下一個工程;而I4中的A-SA和A-A-S那么是由I3中的9和3讀入一個A字符后得到的下一個工程；中的SfAS?和A-S?A那么是由I4中的4和8讀入一個S字符后得到的下一個工程.狀態(tài)全體構(gòu)成了文法G'的LR(0)標準族.11:2、S'一S,14：10、A-SAI5第七章、單項選擇題1、中間代碼生成所依據(jù)的是.d.等價變換規(guī)那么d.程序變量d.a+bd.等價變換規(guī)那么d.程序變量d.a+b+c/d2、四元式之間的聯(lián)系是通過實現(xiàn)的.a.指示器b.臨時變量c.符號表3、后綴式ab+cd+/可用表達式來表示.a.a+b/c+db.(a+b)/(c+d)c.a+b/(c+d)4、4、表達式3AVB)A(CVD)的逆波蘭表示為rArABVACDVArBVCDVAABABVnCDVAArBVACDV?O?人入5、中間代碼的樹型表示ABCD所對應(yīng)的表達式為a.A+B+C+Db.A+(B+C)+Dc.(A+B)+C+Dd.(A+B)+(C+D)6、四元式表示法的優(yōu)點為a.不便于優(yōu)化處理,a.不便于優(yōu)化處理,但便于表的更動b.不便于優(yōu)化處理,但節(jié)省存儲空間c.便于優(yōu)化處理,也便于表的更動d.便于表的更動,也節(jié)省存儲空間7、終結(jié)符具有屬性.a.傳遞b.繼承c.抽象d.綜合二、多頂選擇題1、中間代碼主要有a.四元式a.四元式d.后綴式e.間接三元2、下面中間代碼形式中,能正確表示算術(shù)表達式a+b+c的有d.e.ad.e.a+b+cbca.ab+c+b.abc++c.+bc

ab3、在下面的語法制導(dǎo)譯中,采用拉鏈-回填技術(shù).a.賦值語句b.goto語句c.條件語句d.循環(huán)語句4、以下中間代碼形式有益于優(yōu)化處理.a.三元式b.四元式c.間接三元式d.逆波蘭表示法e.樹形表示法5、在編譯程序中安排中間代碼生成的目的是.a.便于進行存儲空間的組織b.利于目標代碼的優(yōu)化c.利于編譯程序的移植d.利于目標代碼的移植e.利于提升目標代碼的質(zhì)量能正確表示算術(shù)表達式a+b*c能正確表示算術(shù)表達式a+b*c.題〕a.ab+c*b.abc*+7、三地址代碼語句具體實現(xiàn)通常有表示方法.a.逆波蘭表示b.三元式c.間接三元式d.樹形表示e.四元式三、填空題1、中間代碼有等形式,生成中間代碼主要是為了使.2、語法制導(dǎo)譯既可以用來產(chǎn)生代碼,也可以用來產(chǎn)生指令,甚至可用來對輸入串進行.3、當源程序中的標號出現(xiàn)“先引用后定義〞時,中間代碼的轉(zhuǎn)移地址須持時才能確定,因而要進行.4、文法符號的屬性有兩種,一種稱為,另一種稱為.5、后綴式abc-/所代表的表達式是,表達式(a-b)*c可用后綴式表示.6、用一張輔以的方法來表示中間代碼,這種表示法稱為間接三元式.四、綜合題1、給出以下表達式的逆波蘭表示(后綴式)：①a*(-b+c)②(AVB)A(CVrDAE)2、寫出算術(shù)表達式：A+B*(C-D)+E/(C-D)TN的①四元式序列；②三元式序列；③間接三元式序列單項選擇解答1、選Co2、四元式之間的聯(lián)系是通過臨時變量實現(xiàn)的,應(yīng)選bo3、選bo4、選bo5、選do6、四元式表示法的優(yōu)點與間接三元式相同,應(yīng)選Co7、選do多項選擇解答1、選a、c、d、e.2、b、d的中間代碼不能正確表示a+b+c,而e不是中間代碼：應(yīng)選a、c.3-凡涉及到跳轉(zhuǎn)的語句都需要采用拉鏈一一回填技術(shù),應(yīng)選b、c、d.4、選b、c.5、選b、do6、選b、e.7、選b、c、e.填空解答1、逆波蘭記號、樹形表示、三元式、四元式目標代碼的優(yōu)化容易實現(xiàn)2、中間目標解釋執(zhí)行3、標號定義回填4、繼承屬性綜合屬性5、a/(b-c)ab-c*6、間接碼表三兀式表綜合解答1、ab@c+*;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))(6)(/,E,T5,T6)⑹(/,E,(5))⑸(6)(+,(3),(5))⑺(+,T3,T6,T7)⑺(+,(3),(6))(6)②表達式的二兀式序列③間接三元式序列2、①表達式的2、①表達式的四元式序列:一、單項選擇題1、編譯程序使用區(qū)別標識符的作用域.a.說明標識符的過程或函數(shù)名b.說明標識符的過程或函數(shù)的靜態(tài)層次c.說明標識符的過程或函數(shù)的動態(tài)層次d.標識符的行號2、在目標代碼生成階段,符號表用于.a.目標代碼生成b.語義檢查c.語法檢查d.地址分配3、過程信息表不包含.a.過程入口地址b.過程的靜態(tài)層次c.過程名d.過程參數(shù)信息4、以下關(guān)于標識符和名字表達中,正確的選項是.a.標識符有一定的含義b.名字是一個沒有意義的字符序列c.名字有確切的屬性d.a~c都不正確二、多項選擇題1、符號表的每一項均包含.a.名字欄b.類型欄c.信息欄d.值欄e.a~d均包含2、對編譯程序所用到的符號表,涉及的操作有.a.填寫或更新信息欄內(nèi)容b.填入新名c.給定名字,訪問它的有關(guān)信息d.雜湊技術(shù)e.線性表和排序二叉樹3、源程序中的錯誤一般有.a.詞法錯誤b.語法錯誤c.語義錯誤d.編譯錯誤e.違反環(huán)境限制的錯誤三、填空題1、符號表中名字欄內(nèi)容有兩種填寫方式,它們是填寫和填寫.

2、詞法分析階段的錯誤主要是,可通過的方法糾正錯誤.3、符號表中名字的有關(guān)信息在和過程中陸續(xù)填入.4、在目標代碼生成階段,符號表是的依據(jù).四、問做題：1、在編譯過程中為什么要建立符號表單項選擇解答：1、b2、d3、b4、c多項選擇解答：1、a、c2、a、b、c3、a、b、c、e填空解答：1、標識符標識符地址及長度2、拼寫錯誤最小距離匹配3、詞法分析語法語義分析4、地址分配問做題解答：在編譯過程中始終要涉及到對一些語法符號的處理,這就需要用到語法符號的相關(guān)屬性.為了在需要時能找到這些語法成分及其相關(guān)屬性,就必須使用一些表格來保存這些語法成分及其屬性,這些表格就是符號表.第九章一、單項選擇題1、程序所需的數(shù)據(jù)空間在程序運行前可確定,稱為治理技術(shù).a.動態(tài)存儲b.棧式存儲c.靜態(tài)存儲d.堆式存儲2、堆式動態(tài)分配申請和釋放存儲空間遵守原那么.a.先請先放b.先請后放c.后請先放d.任意3、靜態(tài)分配允許程序出現(xiàn).a.遞歸過程b.可變體積的數(shù)據(jù)工程c.靜態(tài)變量d.待定性質(zhì)的名字4、在編譯方法中,動態(tài)存儲分配的含義是.a.在運行階段對源程序中的數(shù)組、變量、參數(shù)等進行分配b.在編譯階段對源程序中的數(shù)組、變量、參數(shù)進行分配c.在編譯階段對源程序中的數(shù)組、變量、參數(shù)等進行分配,在運行時這些數(shù)組、變量、參數(shù)的地址可根據(jù)需要改變d.以上都不正確5、在編譯時有傳名功能的高級程序語言是.a.Fortranb.Basicc.Pascald.ALGOL6、棧式動態(tài)分配與治理在過程返回時應(yīng)做的工作有.a.保護SPb.恢復(fù)SPc.保護TOPd.恢復(fù)TOP二、多項選擇題1、下面需要在運行階段分配存儲空間.a.數(shù)a.數(shù)組d.靜態(tài)變量b.指針變量e.動態(tài)變量c.動態(tài)數(shù)組2、棧式動態(tài)分配允許a.遞a.遞歸過程b.分程序結(jié)構(gòu)c.動態(tài)變量d.d.動態(tài)數(shù)組e.靜態(tài)數(shù)組3、動態(tài)存儲分配可采用的分配方案有a.隊a.隊式存儲分配b.棧式存儲分配c.鏈式存儲分配d.堆式存儲分配e.線性存儲分配4、棧式動態(tài)分配與治理因調(diào)用而進入過程之后,要做的工作是.a.定義新的活動記錄的SP