編譯原理習(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、編譯程序是對。d.高級(jí)語言的翻譯10、語法分析應(yīng)遵循。c .構(gòu)詞規(guī)則二、多項(xiàng)選擇題1、編譯程序各階段的工作都涉及到 。b.表格管理c.出錯(cuò)處理2、編譯程序工作時(shí)，通常有 階段。a .詞法分析b.語

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

3、 |S 5 a ,a C V*C. L(G)=a |S?a , a C (VtU Vn*)d. L(G)=a |S ? a ,a C (VtU Vn*)3、有限狀態(tài)自動(dòng)機(jī)能識(shí)別 。c. 上下文無關(guān)文法b.上下文有關(guān)文法c.正規(guī)文法d.短語文法4、設(shè)G為算符優(yōu)先文法，G的任意終結(jié)符對a、b有以下關(guān)系成立 。a.若 f(a)>g(b),則 a>b b.若 f(a)<g(b),則 a<bd. ab都不一定成立d. ab 一定成立5、如果文法 G是無二義的，則它的任何句子a 。a.最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同b.最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同c.最左推導(dǎo)和最右

4、推導(dǎo)必定相同d.可能存在兩個(gè)不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同6、由文法的開始符經(jīng)0步或多步推導(dǎo)產(chǎn)生的文法符號(hào)序列是 。a.短語 b.句柄 c.句型 d.句子7、文法 G Ef E+T|TT- T*P|PA (E)|I則句型P+T+i的句柄和最左素短語為 。a.P+T 和 i b. P 和 P+T c. i 和 P+T+i d.P 和 T8 、設(shè)文法為：S- SA|AA一 a|b則對句子aba,下面 是規(guī)范推導(dǎo)。a. S = SA=： SAA AA- aAA=; abA=： abab. SSA=： SAA AA" AA* Abg abac. S = SA=： SAA SAo=：

5、Sba : Aba : abad. S - Sa : SA4 Sba=： Aba : aba9、文法 G Sf b| A(T)T一 T,S|S貝U FIRSTVT(T)。a. b, A ,( b. b, A ,)c.b, A ,(, , 10、產(chǎn)生正規(guī)語言的文法為 。a. 0型b. 1型c. 2型d.b, A ,), , d. 3型a.消除左遞歸12、在規(guī)范歸約中，用a.直接短語b.消除右遞歸來刻畫可歸約串。b.句柄c.消除回溯c.最左素短語d.提取公共左因子d.素短語13、有文法 G: E-E*T|TTfT+i|i句子1+2*8+6按該文法 G歸約，其值為a. 23 B. 42 c. 30

6、d. 1714、規(guī)范歸約指。a.最左推導(dǎo)的逆過程c.規(guī)范推導(dǎo)d.二、多項(xiàng)選擇題1、下面哪些說法是錯(cuò)誤的Cb.最右推導(dǎo)的逆過程最左歸約的逆過程a.有向圖是一個(gè)狀態(tài)轉(zhuǎn)換圖b.狀態(tài)轉(zhuǎn)換圖是一個(gè)有向圖c.有向圖是一個(gè)DFAd.DFA可以用狀態(tài)轉(zhuǎn)換圖表示11、采用自上而下分析，必須 。2、對無二義性文法來說，一棵語法樹往往代表了 。a.多種推導(dǎo)過程 b.多種最左推導(dǎo)過程c. 一種最左推導(dǎo)過程d.僅一種推導(dǎo)過程e. 一種最左推導(dǎo)過程3、如果文法G存在一個(gè)句子，滿足下列條件 之一時(shí)，則稱該文法是二義文法。a.該句子的最左推導(dǎo)與最右推導(dǎo)相同b.該句子有兩個(gè)不同的最左推導(dǎo)c.該句子有兩棵不同的最右推導(dǎo)d.該句子

7、有兩棵不同的語法樹e.該句子的語法樹只有一個(gè)4、有一文法G: SfABA 一aAb| £B f cBd| £它不產(chǎn)生下面 集合。a. a nbmcndmn,m >0b. a nbncmdmn,m>0c. a nbmcmdn|n,m >0d. a nbncmdmjn,m >0e. a nbncndn|n >05、自下而上的語法分析中，應(yīng)從a.句型b.句子c.以單詞為單位的程序開始分析。d.文法的開始符e.句柄6、對正規(guī)文法描述的語言，以下 有能力描述它。a.0型文法 b.1型文法 c.上下文無關(guān)文法d.右線性文法e.左線性文法三、填空題1、文法中

8、的終結(jié)符和非終結(jié)符的交集是 。詞法分析器交給語法分析器的文法符號(hào)一 定是 ,它一定只出現(xiàn)在產(chǎn)生式的 部。2、最左推導(dǎo)是指每次都對句型中的 非終結(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、文法SfaS|bR| e描述的語言是（a|bc）*（）R 一 cS2、在自下而上的語法分析中，語法

9、樹與分析樹一定相同。（）3、二義文法不是上下文無關(guān)文法。（）4、語法分析時(shí)必須先消除文法中的左遞歸。（）5、規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。（）6、一個(gè)文法所有句型的集合形成該文法所能接受的語言。（）五、簡答題1、句柄2、素短語3、語法樹4、歸約5、推導(dǎo)六、問答題1、給出上下文無關(guān)文法的定義。2、文法 GS:S 一 aSPQ|abQ QP一 PQbP一 bbbQ一 bccQ一 cc（1）它是Chomsky哪一型文法？（2）它生成的語言是什么？3、按指定類型，給出語言的文法。L=aibj|j >i > 1的上下文無關(guān)文法。4、有文法 G: Sf aAcB|BdAf AaB|cBf

10、 bScA|b(1)試求句型 aAaBcbbdcc和aAcbBdcc的句柄；(2)寫出句子acabcbbdcc的最左推導(dǎo)過程。5、對于文法GS:S 一( L) |aS|a L 一 L, S|S(1)畫出句型(S, (a)的語法樹。(2)寫出上述句型的所有短語、直接短語、句柄和 素短語。6、考慮文法GT:T-T*F|FFfFT P|PP-( T) |i證明T*PT(t*f)是該文法的一個(gè)句型，并指出直接短語和句柄。 單選解答1 、選 c。2、選 a。3、選 c。4、雖然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)并

11、不能判定原來的a與b之間是否存在優(yōu)先關(guān)系：故選c。5、如果文法G無二義性，則最左推導(dǎo)是先生長右邊的枝葉：對于 d,如果有兩個(gè)不同的是了左推導(dǎo)，則必然有二義性。故選 a。6、選 Co7、由圖2-8-1的語法樹和優(yōu)先關(guān)系可以看出應(yīng)選boEE + F /l I E + T PI I 一iP#< + >+< i >#圖2-8-1句型P+T+I的語法及優(yōu)先關(guān)系8、規(guī)范推導(dǎo)是最左推導(dǎo)，故選 do9、由 LT,和一一(得 FIRSTVT(T)=(, , );由一一 S 得 FIRSTVT(S)? FIRSTVT(T),而 FIRSTVT(S)=b, A ,(;即 FIRSTVT(一尸

12、b, A ,(, , ;因此選 c。10、d 11、c 12 、b 13 、b 14 、b多選解答 1、e、a、c 2、a、c、e 3、b、c、d 4、a、c 5、b、c 6、a、b、c、d、e 填空解答1、空集 終結(jié)符 右2 、最左3 、自上而上自下而上4 、自上而上5 、語法 分析6 、移進(jìn) 接受7 、4 2 型3型上下文無關(guān)語言正規(guī)語言下推自動(dòng)機(jī) 有限判斷解答1、對2、錯(cuò) 3 、錯(cuò)4、錯(cuò)5、錯(cuò)6、錯(cuò)簡答解答1 、句柄：一個(gè)句型的最左直接短語稱為該句型的句柄。2、素短語：至少含有一個(gè)終結(jié)符的素短語，并且除它自身之外不再含任何更小的素短語。3、語法樹：滿足下面 4個(gè)條件的樹稱之為文法 GS的

13、一棵語法樹。每一終結(jié)均有一標(biāo)記，此標(biāo)記為VnU Vt中的一個(gè)符號(hào)；樹的根結(jié)點(diǎn)以文法 GS的開始符S標(biāo)記；若一結(jié)點(diǎn)至少有一個(gè)直接后繼，則此結(jié)點(diǎn)上的標(biāo)記為中的一個(gè)符號(hào)；若一個(gè)以A為標(biāo)記的結(jié)點(diǎn)有 K個(gè)直接后繼，且按從左至右的順序，這些結(jié)點(diǎn)的標(biāo)記分別為Xi,X2，,Xk,則A-Xi,X2，,Xk,必然是G的一個(gè)產(chǎn)生式。4、歸約：我們稱“ 丫 3直接歸約出a A3 ,僅當(dāng)A- 丫 是一個(gè)產(chǎn)生式，且“、3 C(VnUVt)* o歸約過程就是從輸入串開始，反復(fù)用產(chǎn)生式右部的符號(hào)替換成產(chǎn)生式左部符號(hào)， 直至文法開始符。5、推導(dǎo)：我們稱A A 直直接推出a 丫3,即a A3=ocy3,僅當(dāng) Af 丫是一個(gè)產(chǎn)生式

14、， 且a、3C (VnU Vt)*。如果a = a 2=>口 a n,則我們稱這個(gè)序列是從ai至a 2的一個(gè)推導(dǎo)。若存在一個(gè)從a ian的推導(dǎo)，則稱a 1可推導(dǎo)出a n。推導(dǎo)是歸約的逆過程。問答1解答一個(gè)上下文無關(guān)文法 G是一個(gè)四元式(Vt,Vn,S, P ),其中： Vt是一個(gè)非空有限集，它的每個(gè)元素稱為終結(jié)符號(hào)； %是一個(gè)非空有限集，它的每個(gè)元素稱為非終結(jié)符號(hào)，VtAVn=； S是一個(gè)非終結(jié)符號(hào)，稱為開始符號(hào)； P是一個(gè)產(chǎn)生式集合(有限)，每個(gè)產(chǎn)生式的形式是 P- a ,其中，PC X,& C (VtU Vn)*。開始符號(hào)S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。2解答(1)由于

15、產(chǎn)生式左部存在終結(jié)符號(hào)，且所有產(chǎn)生式左部符號(hào)的長度均小于等于產(chǎn)生式右部的符號(hào)長度，所以文法GS是Chomsky1型文法，即上下文有關(guān)文法。(2)按產(chǎn)生式出現(xiàn)的順序規(guī)定優(yōu)先級(jí)由高到低(否則無法推出句子)，我們可以得到:S abQ : abcS = aSPQ aabQPQ aabPQQ aabbQQ aabbcQ : aabbccS 二 aSPQ aaSPQPQ aaabQPQPQ aaabPQQPQ aaabPQPQQ aaaPPQQQaaabbPqqq : aaabbQQQ aaabbbcQQ aaabbbccQ : aaabbbccc于是得到文法 GS生成的語言L=anbncn|n >

16、1 3【解答】(1)由L=aibj|j >i>1知，所求該語言對應(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)分別畫出對應(yīng)兩句型的語法樹，如圖 2-8-2所示句柄：AaB Bd(2)b(a)(b)圖2-8-2 語法樹句子acabcbbdcc的最左推導(dǎo)如下:=aAcB : aAaBcB : acaBcB : acabcB= acabcbScA : acabcbBdcA= acabcbbdcA=acabc

17、bbdcc(1)句型(S, (a)的語法樹如圖2-8-3所示S(L )L S/1a圖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 (< a >) >) >#因此素短語為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。圖2-8-4 句型T*P T (T*F )的

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

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

20、、一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(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、對任意一個(gè)右線性文法G,都存在一個(gè)NFA M滿足L(G尸L(M)。()6、對任意一個(gè)右線性文法G,都存在一個(gè) DFA M滿足L(G尸L(M)。()7、對任何正規(guī)表達(dá)式e,都存在一個(gè)NFA M,滿足L(G尸L(e)。()8、對任何正規(guī)表達(dá)式e,都存在一個(gè)DFA M,滿足L(G尸L(e)。()五、基本題1、設(shè)M= (x,y, a,b, f,x,y)為一

21、非確定的有限自動(dòng)機(jī)，其中 f定義如下:f (x,a ) = x,y f (x,b ) = yf (y,a ) = 4f (y,b ) = x,y試構(gòu)造相應(yīng)的確定有限自動(dòng)機(jī)M 。2、對給定正規(guī)式 b* (d|ad) (b|ab) +,構(gòu)造其 NFA M;單選解答1、b 2、c 3、c4、d 5、b多選解答 1、a、c、e 2、a、b、d填空解答1、NFA2、正規(guī)集3、DFA (NFA)所識(shí)別判斷解答 1、2、3、錯(cuò)4、5、6、7、8、正確基本1解答：對照自動(dòng)機(jī)的定義M=(S, N,f,S 0,Z),由f的定義可知f(x,a) 、f(y,b)均為多值函數(shù)，所以是一非確定有限自動(dòng)機(jī)，先畫出NFA M

22、相應(yīng)的狀態(tài)圖，如圖 3-6-2所示。用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣表3-6-3所示。IlaI bxx,yyy一x,yx,yx,yx,y將轉(zhuǎn)換矩陣中的所有子集重新命名而形成表3-6-4所示的狀態(tài)轉(zhuǎn)換矩陣。ab0211一22 k-22表3-6-4狀態(tài)轉(zhuǎn)換矩陣k即得到M =(0,1,2,a,b, f,0, 1,2)，其狀態(tài)轉(zhuǎn)換圖如圖3-6-5所示。將圖3-6-5的DFAM最小化。首先，將 M'的狀態(tài)分成終態(tài)組1 , 2與非終態(tài)組0;其次, 考察1,2。由于1,2a=1,2b=2? 1,2,所以不再將其劃分了，也即整個(gè)劃分只有兩組0 , 1,2:令狀態(tài)1代表1,2,即把原來利達(dá)2的弧都導(dǎo)向1,并刪除

23、狀態(tài)2。最后，得到 如圖 3-6-6 所示化簡 DFA M'JJ3 a"b圖3-6-6 化簡后的DFA M'2解答：首先用 A+=aA改造正規(guī)式得：b;其次，構(gòu)造該正規(guī)式的NFA MY*(d|ad)(b|ab)(b|ab)如圖3-6-7所示?？赽3b1abd234adab5YJ(d|ad), 2b (d|ad)(b|ab)(b|ab)(b|ab)J*Y第四章1 構(gòu)造下面文法的 LL（ 1 ）分析表。A TLTf int | realLf id RRf , id R |£2 下面文法 GS 是否為 LL （ 1 ）文法？說明理由。Sf A B | P Q x

24、A- x y B- b c P f d P | eQ- a Q| e3 設(shè)有以下文法：GS : Sf aAbDe|dA fBSD|e BfSAc| cD|£Df Se| e（ 1）求出該文法的每一個(gè)非終結(jié)符U的FOLLOWS（ 2）該文法是LL（ 1）文法嗎？（ 3）構(gòu)造CS 的 LL（ 1 ）分析表。4 將文法 GV 改造成為 LL（1） 的。GV : " N|NE fV|V+EN5、已知文法：GA :A- aAa| £(1)該文法是LL (1)文法嗎？為什么？(2)若采用LL (1)方法進(jìn)行語法分析，如何得到該文法的LL (1)分析表?(3)若輸入符號(hào)串“ a

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

26、。表4-3-1 LL (1)分析表非終結(jié)符輸入符號(hào)intrealid#DA TLA TLTT- intT一 realLLfid RRRf ,id RR- £2解答：該文法不是LL (1)文法，見下面分析中的說明。分析只有三個(gè)非終結(jié)符有兩個(gè)選擇。1 、P的兩個(gè)右部d P和e的開始符號(hào)肯定不相交。2、Q的兩個(gè)右部a Q和e的開始符號(hào)肯定不相交。3、對S來說，由于 x C FIRST(A B),同時(shí)也有 x £ FIRST(P Q x)(因?yàn)镻和Q都可能 為空)。所以該文法不是 LL (1)文法。3解答： (1)求文法的每一個(gè)非終結(jié)符U的FOLLO僚的過程如下：因?yàn)椋篠是識(shí)別符號(hào)

27、，且有 Z BSD BfSAc、Df Se,所以FOLLOW( S)應(yīng)包含F(xiàn)IRST(D) U FIRST(Ac) U FIRST(e) U #=a,d Ua,d,c,e U e U #=a,c,d,e#又因?yàn)锳-BSD和 A £,所以FOLLOW3還包含 FOLLOW(A)因?yàn)镾- aAbDe和B-SAc,所以FOLLOW A =FIRST (bDe) U FIRST ( c) =b,c綜合、得 FOLLOWS) =a,d,c,e,# U a,b,c,d,e,#因?yàn)?A- BSQ 所以 FOLLOW/ ( B) =FIRST (SD)=a,d因?yàn)?S- aAbDe | d、A- B

28、SD| e 和 B- SAc | cD ,所以FOLLOW D) =FIRST (e) U FOLLOW A) U FOLLOW( B)=e U b,c U a,d=a,b,c,d,e(2) GS不是 LL (1)文法。因?yàn)楫a(chǎn)生式Bf SAc|cD| £中FIRST(SAc) n FOLLOW( B) =a,d豐？(3)構(gòu)造GS的LL (1)分析表。按照LL (1)分析表的構(gòu)造算法構(gòu)造方法GS的LL (1)分析表如表4-3-2所示。表4-3-2 GS 的LL (1)分析表abcde#SaAbDedABSDBSDBSDeBSac/ ecDSac/ eDSe/ e££

29、Se/ e£4解答： 對文法GV提取公共左因子后得到文法:G ' V ： V- NAZ s |EVBBf s |+ENR i求出文法G V中每一個(gè)非終結(jié)符號(hào)的FIRST集：FIRST(V)=iFIRST(A)=,£ FIRST(E)=iFIRST(B尸+,£ FIRST(N)=i求出文法G V中每一個(gè)非終結(jié)符號(hào)的FOLLOW!：FOLLOW(V)=# U FIRST(B) £ U FOLLOW(E尸#,+,FOLLOW(A尸 FOLLOW(V尸+,#FOLLOW(E尸 FIRST() £ U FOLLOW(B尸 FIRST() 

30、3; U FOLLOW(E)=FOLLOW(B尸 FOLLOW(E尸 FOLLOW(N尸 FIRST(A) £ U FOLLOW(V尸,+,#可以看到，對文法 G' V的產(chǎn)生式A- s |E,有FIRST(E) A FOLLOW(A)= n +,#=?對產(chǎn)生式B- e |+E ,有FIRST(+E) A FOLLOW(B尸+ A = ?而文法的其他產(chǎn)生式都只有一個(gè)不為£的右部，所以文法G' V是LL(1)文法。5解答：(1)因?yàn)楫a(chǎn)生式Z aAa| £有空產(chǎn)生式右部，而FOLLOW(A)=# U FIRST(a尸a, #造成 FIRST(A) n F

31、OLLOW(A尸A,£ n a, # w?所以該文法不是 LL (1)文法。(2)若采用LL (1)方法進(jìn)行語法分析，必須修改該文法。因該文法產(chǎn)生偶數(shù)(可以為0)個(gè)a,所以得到文法G A ： Z aaA| £此時(shí)對產(chǎn)生式 A- aaA| £ , 有 FOLLOW(A尸# U FOLLOW(A)=#,因而FIRST(A) n FOLLOW(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- £

32、;(3)若采用LL(1)方法進(jìn)行語法分析，對符號(hào)串“ aaaa”的分析過程如表 4-3-4所示。表4-3-4對符號(hào)串“ aaaa”的分析過程步驟分析棧輸入串產(chǎn)生式/動(dòng)作1#Aa a a a #Z aaA2#A a aa a a a #匹配3#A aa a a #匹配4#Aa a #Z aaA5#A a aa a #匹配6#A aa#匹配7#A#Ar> £8#接受第五章1 .設(shè)有文法GS為:Sf a|b|(A)2 SdA|S(1)完成下列算符優(yōu)先關(guān)系表，見表表 5-7-15-7-1 ,并判斷GS是否為算符優(yōu)先文法。ab()d#a?b?(?)?d#?算符優(yōu)先關(guān)系表(2)給出句型(S

33、dSdS的短語、簡單短語、句柄、素短語和最左素短語。(3)給出輸入串(adb) #的分析過程。解答：(1)先求文法 G網(wǎng)的FIRSTVT集和LASTVT集：由 S-a|b|(A)得：FIRSTVT(S尸a,b,();由 A-Sd得：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)系表方法如下：對ab，或

34、4aQb，有a? b;對aR,而 bC FIRSTVT(R),有 a?b;對Rt> -,而 aC FIRSTVT(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 ?),) ?);由 ZSd得:LASTVT(S)?d,即：a?d,b?d,) ?d;此外，由 #S#W： #? #；由#?FIRSTVT(S)得：#?a,#?b,#?(;脂由 LAST

35、VT(S)?#得：d?#,a?#,b ?#,) ?#。最后得到算符優(yōu)先關(guān)系表，見表5-7-2 。表5-7-2算符優(yōu)先關(guān)系表ab()d#a?b?(?)?d?#?由表5-7-2可以看出，任何兩個(gè)終結(jié)符之間至少只滿足？、？、？三種優(yōu)先關(guān)系之一，故GS為算符優(yōu)先文法。S（2）為求出句型（SdSdS）的短語、簡單短語、句柄，我們先畫出該句型對應(yīng)的語法樹, 如圖5-7-3所示。由圖5-7-3得到： 短語：S, SdS, SdSdS （SdSdS） 簡單短語（即直接短語）：S 句柄（即最左直接短語）：S 素短語：SdS,它同時(shí)也是該句型的最左素短語。圖5-7-3句型（SdSdS）的語法樹（3）輸入串（adb

36、） #的分析過程見表 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)#用SdA歸約# (A)#移進(jìn)# (A)#用S-(A)歸約#S#分析成功第六章一、單項(xiàng)選擇題1、若a為終結(jié)符，則A-，a 3為 項(xiàng)目a. 歸約b.移進(jìn)c.接受d.待約2、若項(xiàng)目集Ik含有A-獷，則在狀態(tài)k時(shí)，僅當(dāng)面臨的輸入符號(hào)aC FOLLOW(期，才采取“ Ac動(dòng)作的一定是。a.LALR 文法 b.LR (0)文法 c.LR

37、 (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子表中，如果某一彳T中存在標(biāo)記“ 門”的欄，則 。a.該行必定填滿rjb.該行未填滿rjc.其他行也有rjd.goto子表中也有口5、一個(gè) 指明了在分析過程中的某時(shí)刻所能看到產(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è)分析棧

38、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、對LR分析表的構(gòu)造，有可能存在 動(dòng)作沖突。a.移進(jìn) b.歸約 c.移進(jìn)/歸約d.移進(jìn)/移進(jìn)e.歸約/歸約5、就文法的描述能力來說，有a. SLR (1) ? LR (1)d. LR (1) ?無二義文法6、對LR分析器來說，存在a.LALRb.LR (0)7、自上而下的語法分析方法有a.算符優(yōu)先分析法d.LR (0)分析法三、填空題1、對于一個(gè)文法，如果能夠構(gòu)造 文法。b

39、. LR ( 1) ? SLR (1)e. SLR (1) ?無二義文法等分析表的構(gòu)造方法。c.SLR(1) d.SLR (0)b.LL (1)分析法e.LALR (1)分析法O使得它的c. LR (0) ? LR (1)e.LR (1)c.SLR (1)分析法則稱該文法為LR均是唯一確定的,2、字的前綴是指該字的 。3、活前綴是指 的一個(gè)前綴，這種前綴不含 之后的任何符號(hào)。4、在LR分析過程中，只要 的已掃描部分保持可歸約成一個(gè) ,則掃描過的部分正 確。5、將識(shí)別 的NFA確定化，使其成為以 為狀態(tài)的DFA這個(gè)DFA就是建立 的基礎(chǔ)。6、A-“稱為 項(xiàng)目；對文法開始符 S'f”為 項(xiàng)

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

41、)寸進(jìn)行歸約；LR (1)則當(dāng)在把 a歸約為A的規(guī)范句型的前綴 3Aa前提下，當(dāng)“后跟終結(jié)符a時(shí)，才進(jìn)行歸約；因此選 do3、由于 LR (0) ? SLR (1) ? LR (1) ?無二義文法，故選 c。4、選 a。5、選 c。多選解答:a、do1 、一個(gè)LR分析器包括一個(gè)總控程序和一張分析表，選2、選c 、 e 。3、選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、輸

42、入串活前綴5、活前綴項(xiàng)目集合LR 分析算法6、歸約 接受 移進(jìn) 待約7、自左至右分析采用最右推導(dǎo)的逆過程即最左歸約 向右查看 0 個(gè)字符綜合解答：首先將文法G拓廣為GS:S'f SSf AS|bZ SA|a(1)文法GS的LR (0)項(xiàng)目是:SAS-9、Af S- ASf b10、Af SA-Sfb 11、Af aAf SA12、Af a -1、Sf S5、2 、S'f S -6、3、Sf AS7、4、Sf A- S8、2 、列出構(gòu)成文法LR（ 0 ）項(xiàng)目集規(guī)范族。用 e-CLOSURE 閉包)I 0： 1、S j - S3 、Sf AS8 、Af SA11 、Af a6 、S

43、f bI 1： 2、SS -9 、Z S - A辦法構(gòu)造文法 G'的LR ( 0)I 3： 9、Af S A8、Af SA3、Sf AS6、Sf b11、Z aI 4： 10、ZSA4、S-A - S項(xiàng)目集規(guī)范族如下：16： 12、Af a -17： 7、S-> b,8、2 s SA11、A一 a3、Sf AS6、Sf bI 2： 4、Sf A, S3 、Sf AS6、Sf b8 、Af SA11 、A一 a3、Sf AS6、Sf b8、Af SA11、Z aI 5： 5、SfAS-9、A- S - A8、Af SA11、Z a3、Sf AS6、Sf b注意：I 1中的S'

44、;-S 和A-SA是由狀態(tài)I0中的1和3讀入一個(gè)S字符后得到的下一個(gè)項(xiàng)目；， 而I4中的A- SA和A- A,S則是由中的9和3讀入一個(gè)A字符后得到的下一個(gè)項(xiàng)目；I5中的 S - AS和Af S - A 則是由I4中的4和8讀入一個(gè)S字符后得到的下一個(gè)項(xiàng)目。狀態(tài)全體構(gòu)成了文法 G'的LR (0)規(guī)范族。第七章、單項(xiàng)選擇題1、中間代碼生成所依據(jù)的是。a.語法規(guī)則b.詞法規(guī)則c.語義規(guī)則d.等價(jià)變換規(guī)則2、四元式之間的聯(lián)系是通過 實(shí)現(xiàn)的。a.指示器b.臨時(shí)變量 c.符號(hào)表d.程序變量3、后綴式ab+cd+/可用表達(dá)式 來表示。a.a+b/c+db.(a+b)/(c+d)c.a+b/(c+d

45、)d.a+b+c/d4、表達(dá)式 3 AV B) A ( CV D)的逆波蘭表示為a. r ABV A CDMb. A r BV CDV Ac. AB Vr CDV Ad. A r BV A CDM+SI+Xz+5、中間代碼的樹型表示A BC D所對應(yīng)的表達(dá)式為a.A+B+C+D b.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)化處理，也便于表的更動(dòng) d.便于表的更動(dòng)，也節(jié)省存儲(chǔ)空間7、終結(jié)符具有屬性。a.傳遞b.繼承c.抽象d.綜合、多頂選擇題1、中間代碼主要有 。a

46、.四元式b.二元式c.三元式d.后綴式e.間接三元2、下面中間代碼形式中，能正確表示算術(shù)表達(dá)式a+b+c的有。a. ab+c+a+b+c3、在下面的 語法制導(dǎo)翻譯中，采用拉鏈 -回填技術(shù)。a.賦值語句b. goto語句c .條件語句d.循環(huán)語句4、下列 中間代碼形式有益于優(yōu)化處理。a.三元式b.四元式 c.間接三元式 d.逆波蘭表示法e.樹形表示法5、在編譯程序中安排中間代碼生成的目的是a.便于進(jìn)行存儲(chǔ)空間的組織c.利于編譯程序的移植e.利于提高目標(biāo)代碼的質(zhì)量6、下面的中間代碼形式中，b.利于目標(biāo)代碼的優(yōu)化d.利于目標(biāo)代碼的移植能正確表示算術(shù)表達(dá)式a+b*c。題）a. ab+c*b. abc*

47、+7、三地址代碼語句具體實(shí)現(xiàn)通常有 表示方法。a.逆波蘭表示b.三元式c.間接三元式d.樹形表示e.四元式三、填空題1、中間代碼有 等形式，生成中間代碼主要是為了 使。2、語法制導(dǎo)翻譯既可以用來產(chǎn)生 代碼，也可以用來產(chǎn)生 指令，甚至可用來 對輸入串進(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、用一張 輔以 的辦法來表示中間代碼，這種表示法稱為間接三元式。四、綜合題1 、給出下列表達(dá)式的逆波蘭表示(后綴式)

48、： a*(-b+c)(A V B)A (C VrDA E)2、寫出算術(shù)表達(dá)式：A+B*(C-D)+E/(C-D) TN的四元式序列；三元式序列；間接三元式序列單選解答1 、選c 。2、四元式之間的聯(lián)系是通過臨時(shí)變量實(shí)現(xiàn)的，故選b。3、選b。4、選b。5、選d。6、四元式表示法的優(yōu)點(diǎn)與間接三元式相同，故選c。7、選d。多選解答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、d 。6、選b、e 。7、選b、c 、e。填空解答目標(biāo)

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

50、/,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è)沒有意義的字符序列c.名字有確切的屬性d. ac都不正確二、多項(xiàng)選擇題1、符號(hào)表的每一項(xiàng)均包含 。a. 名字欄b.類型欄 c.信息欄 d.值欄 e. ad均包含2、對編譯程序所用到的符號(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)信息在 和 過