編譯原理期末總復(fù)習(xí)題含答案

1、-. z.第八節(jié) 習(xí)題一、單項選擇題1、將編譯程序分成假設(shè)干個“遍是為了b。a提高程序的執(zhí)行效率b使程序的構(gòu)造更加清晰c利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率d利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率2、構(gòu)造編譯程序應(yīng)掌握d。a源程序b目標(biāo)語言c編譯方法d以上三項都是3、變量應(yīng)當(dāng)c。a持有左值b持有右值c既持有左值又持有右值d既不持有左值也不持有右值 4、編譯程序絕大多數(shù)時間花在b上。a出錯處理b詞法分析c目標(biāo)代碼生成d管理表格5、d不可能是目標(biāo)代碼。a匯編指令代碼b可重定位指令代碼c絕對指令代碼d中間代碼6、使用a可以定義一個程序的意義。a語義規(guī)則b詞法規(guī)則c產(chǎn)生規(guī)則d詞法規(guī)則7、詞法分析器

2、的輸入是a。a單詞符號串b源程序c語法單位d目標(biāo)程序8、中間代碼生成時所遵循的是-d。a語法規(guī)則b詞法規(guī)則c語義規(guī)則d等價變換規(guī)則9、編譯程序是對d。a匯編程序的翻譯b高級語言程序的解釋執(zhí)行c機(jī)器語言的執(zhí)行d高級語言的翻譯10、語法分析應(yīng)遵循b。a語義規(guī)則b語法規(guī)則c構(gòu)詞規(guī)則d等價變換規(guī)則解答1、將編譯程序分成假設(shè)干個“遍是為了使編譯程序的構(gòu)造更加清晰，應(yīng)選b。2、構(gòu)造編譯程序應(yīng)掌握源程序、目標(biāo)語言及編譯方法等三方面的知識，應(yīng)選d。3、對編譯而言，變量既持有左值又持有右值，應(yīng)選c。4、編譯程序打交道最多的就是各種表格，因此選d。5、目標(biāo)代碼包括匯編指令代碼、可重定位指令代碼和絕對指令代碼3種，

3、因此不是目標(biāo)代碼的只能選d。6、詞法分析遵循的是構(gòu)詞規(guī)則，語法分析遵循的是語法規(guī)則，中間代碼生成遵循的是語義規(guī)則，并且語義規(guī)則可以定義一個程序的意義。因此選a。 7、b 8、c 9、d 10、c二、多項選擇題1、編譯程序各階段的工作都涉及到bc。a語法分析b表格管理c出錯處理d語義分析e詞法分析2、編譯程序工作時，通常有abce階段。a詞法分析b語法分析語義分析？c中間代碼生成 中間代碼優(yōu)化d語義檢查e目標(biāo)代碼生成解答1b、c 2. a、b、c、e三、填空題1、解釋程序和編譯程序的區(qū)別在于是否生成目標(biāo)程序解釋不產(chǎn)生目標(biāo)程序，邊翻譯邊執(zhí)行。2、編譯過程通常可分為5個階段，分別是詞法分析、語法分析

4、語義分析中間代碼生成、代碼優(yōu)化和目標(biāo)代碼生成。3、編譯程序工作過程中，第一段輸入是源程序，最后階段的輸出為目標(biāo)程序程序。4、編譯程序是指將源程序程序翻譯成目標(biāo)程序程序的程序。解答 是否生成目標(biāo)程序 2、詞法分析 中間代碼生成 3、源程序目標(biāo)代碼生成4、源程序 目標(biāo)語言一、單項選擇題1、文法G：S*S*|y所識別的語言是c。a.*y*b.(*y*)*c.*ny*n(n0)d.*y*是指多個*2、文法G描述的語言L(G)是指ab。a. L(G)=|Seq o(sup 3(+),sdo 1(), VT*b. L(G)=|Seq o(sup 3(*),sdo 1(), VT*c. L(G)=|Seq

5、o(sup 3(*),sdo 1(),(VTVN*)d. L(G)=|Seq o(sup 3(+),sdo 1(),(VTVN*)3、有限狀態(tài)自動機(jī)能識別。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)，則abb.假設(shè)f(a)g(b)，則ag)(b)或f(a)g(b)并不能判定原來的a與b之間是否存在優(yōu)先關(guān)系：應(yīng)選c。5、如果文法G無二義性，則最左推導(dǎo)是先生長右邊的枝葉：對于d，如果有兩個不同的是了左推導(dǎo)，則必然有二義性。應(yīng)選a。6、選c。7、由圖2-8-1的語法樹和優(yōu)先關(guān)系可以看出應(yīng)選

6、b。EE + FE + T PT iP #+#圖2-8-1 句型P+T+I的語法及優(yōu)先關(guān)系8、規(guī)*推導(dǎo)是最左推導(dǎo)，應(yīng)選d。9、由TT,和T( 得FIRSTVT(T)=(,，)； 由TS得FIRSTVT(S)FIRSTVT(T)，而FIRSTVT(S)=b,(；即 FIRSTVT(T)=b,(,，； 因此選c。 10、d 11、c 12、b 13、b 14、b二、多項選擇題1、下面哪些說法是錯誤的。a. 有向圖是一個狀態(tài)轉(zhuǎn)換圖b. 狀態(tài)轉(zhuǎn)換圖是一個有向圖c.有向圖是一個DFAd.DFA可以用狀態(tài)轉(zhuǎn)換圖表示2、對無二義性文法來說，一棵語法樹往往代表了。a. 多種推導(dǎo)過程b. 多種最左推導(dǎo)過程c.一

7、種最左推導(dǎo)過程d.僅一種推導(dǎo)過程e.一種最左推導(dǎo)過程3、如果文法G存在一個句子，滿足以下條件之一時，則稱該文法是二義文法。a. 該句子的最左推導(dǎo)與最右推導(dǎo)一樣b. 該句子有兩個不同的最左推導(dǎo)c. 該句子有兩棵不同的最右推導(dǎo)d. 該句子有兩棵不同的語法樹 e.該句子的語法樹只有一個4、有一文法G：SAB AaAb| BcBd|它不產(chǎn)生下面集合。a. anbmdm|n,m0b. anbncmdm|n,m0c. anbmcmdn|n,m0d. anbncmdm|n,m0e. anbndn|n05、自下而上的語法分析中，應(yīng)從開場分析。a. 句型b. 句子c. 以單詞為單位的程序d. 文法的開場符e.

8、句柄6、對正規(guī)文法描述的語言，以下有能力描述它。a.0型文法b.1型文法 c.上下文無關(guān)文法 d.右線性文法 e.左線性文法解答 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é)符和非終結(jié)符的交集是。詞法分析器交給語法分析器的文法符號一定是，它一定只出現(xiàn)在產(chǎn)生式的部。2、最左推導(dǎo)是指每次都對句型中的非終結(jié)符進(jìn)展擴(kuò)展。3、在語法分析中，最常見的兩種方法一定是分析法，另一是分析法。4、采用語法分析時，必須消除文法的左遞歸。5、樹代表推導(dǎo)過程，樹代表歸約過程。6、自下而上分析法采用、歸約、錯誤處理、等四種操作。7、Chomsk

9、y把文法分為種類型，編譯器構(gòu)造中采用和文法，它們分別產(chǎn)生和語言，并分別用和自動機(jī)識別所產(chǎn)生的語言。解答 1、空集 終結(jié)符 右 2、最左 3、自上而上 自下而上 4、自上而上 5、語法 分析 6、移進(jìn) 承受 7、4 2 型 3型 上下文無關(guān)語言 正規(guī)語言 下推自動機(jī) 有限四、判斷題1、文法 SaS|bR|描述的語言是(a|bc)*( ) RcS2、在自下而上的語法分析中，語法樹與分析樹一定一樣。 3、二義文法不是上下文無關(guān)文法。 4、語法分析時必須先消除文法中的左遞歸。 5、規(guī)*歸約和規(guī)*推導(dǎo)是互逆的兩個過程。 6、一個文法所有句型的集合形成該文法所能承受的語言。 解答 1、對 2、錯 3、錯

10、4、錯 5、錯 6、錯五、簡答題1、句柄2、素短語3、語法樹4、歸約5、推導(dǎo)解答 1、句柄：一個句型的最左直接短語稱為該句型的句柄。2、素短語：至少含有一個終結(jié)符的素短語，并且除它自身之外不再含任何更小的素短語。3、語法樹：滿足下面4個條件的樹稱之為文法GS的一棵語法樹。每一終結(jié)均有一標(biāo)記，此標(biāo)記為VNVT中的一個符號；樹的根結(jié)點以文法GS的開場符S標(biāo)記；假設(shè)一結(jié)點至少有一個直接后繼，則此結(jié)點上的標(biāo)記為VN中的一個符號；假設(shè)一個以A為標(biāo)記的結(jié)點有K個直接后繼，且按從左至右的順序，這些結(jié)點的標(biāo)記分別為*1,*2,*K，則A*1,*2,*K，必然是G的一個產(chǎn)生式。4、歸約：我們稱直接歸約出A，僅當(dāng)

11、A 是一個產(chǎn)生式，且、(VNVT)*。歸約過程就是從輸入串開場，反復(fù)用產(chǎn)生式右部的符號替換成產(chǎn)生式左部符號，直至文法開場符。5、推導(dǎo)：我們稱A直接推出，即A，僅當(dāng)A 是一個產(chǎn)生式，且、(VNVT)*。如果12n，則我們稱這個序列是從1至2的一個推導(dǎo)。假設(shè)存在一個從1n的推導(dǎo)，則稱1可推導(dǎo)出n。推導(dǎo)是歸約的逆過程。六、問答題1、給出上下文無關(guān)文法的定義。解答一個上下文無關(guān)文法G是一個四元式VT,VN,S, P，其中：VT是一個非空有限集，它的每個元素稱為終結(jié)符號；VN是一個非空有限集，它的每個元素稱為非終結(jié)符號，VTVN=；S是一個非終結(jié)符號，稱為開場符號；P是一個產(chǎn)生式集合有限，每個產(chǎn)生式的形

12、式是P，其中，PVN，(VTVN)*。開場符號S至少必須在*個產(chǎn)生式的左部出現(xiàn)一次。2、文法GS： SaSPQ|abQ QPPQ bPbb bQbc cQcc1它是Chomsky哪一型文法？2它生成的語言是什么？解答 1由于產(chǎn)生式左部存在終結(jié)符號，且所有產(chǎn)生式左部符號的長度均小于等于產(chǎn)生式右部的符號長度，所以文法GS是Chomsky1型文法，即上下文有關(guān)文法。2按產(chǎn)生式出現(xiàn)的順序規(guī)定優(yōu)先級由高到低否則無法推出句子，我們可以得到： SabQabc SaSPQaabQPQaabPQQaabbQQaabbcQaabbcc SaSPQaaSPQPQaaabQPQPQaaabPQQPQaaabPQPQQ

13、aaaPPQQQaaabbPqqqaaabbQQQaaabbbcQQaaabbbccQaaabbbccc于是得到文法GS生成的語言L=anbn|n13、按指定類型，給出語言的文法。L=aibj|ji1的上下文無關(guān)文法?！窘獯稹?由L=aibj|ji1知，所求該語言對應(yīng)的上下文無關(guān)文法首先應(yīng)有SaSb型產(chǎn)生式，以保證b的個數(shù)不少于a的個數(shù)；其次，還需有SSb或SbS型的產(chǎn)生式，用以保證b的個數(shù)多于a的個數(shù)；也即所求上下文無關(guān)文法GS為：GS：SaSb|Sb|b4、有文法G：SaAcB|BdAAaB|cBbScA|b1試求句型aAaBcbbdcc和aAcbBdcc的句柄；2寫出句子acabcbbd

14、cc的最左推導(dǎo)過程?！窘獯稹?分別畫出對應(yīng)兩句型的語法樹，如圖2-8-2所示句柄:AaB Bd Sa A c B AaB b S c AB d cb(a)S a A c BB S c AB d c(b)圖2-8-2 語法樹2句子acabcbbdcc的最左推導(dǎo)如下： SaAcBaAaBcBacaBcBacabcBacabcbScAacabcbBdcAacabcbbdcAacabcbbdcc5、對于文法GS： SL|aS|aLL, S|S1畫出句型S,a的語法樹。2寫出上述句型的所有短語、直接短語、句柄和素短語。S L L ， SS ( L ) S a圖2-8-3 句型S,a的語法樹【解答】1句型

15、S,a的語法樹如圖2-8-3所示2由圖2-8-3可知：短語：S、a、(a)、S,(a)、(S,(a)；直接短語：a、S；句柄：S；素短語：素短語可由圖2-8-3中相鄰終結(jié)符之間的優(yōu)先關(guān)系求得，即；# ，a #因此素短語為a。6、考慮文法GT：TT*F|FFFP|PPT|iTT * FF PP T T * F圖2-8-4 句型T*PT*F的語法樹證明T*PT*F是該文法的一個句型，并指出直接短語和句柄。【解答】首先構(gòu)造T*PT*F的語法樹如圖2-8-4所示。由圖2-8-4可知，T*PT*F是文法GT的一個句型。直接短語有兩個，即P和T*F；句柄為P。一、單項選擇題1、詞法分析所依據(jù)的是。a. 語

16、義規(guī)則b. 構(gòu)詞規(guī)則c. 語法規(guī)則d. 等價變換規(guī)則2、詞法分析器的輸出結(jié)果是。a. 單詞的種別編碼b. 單詞在符號表中的位置c. 單詞的種別編碼和自身值d. 單詞自身值3、正規(guī)式M1和M2等價是指。a. M1和M2的狀態(tài)數(shù)相等b. M1和M2的有向弧條數(shù)相等c. M1和M2所識別的語言集相等 d. M1和M2狀態(tài)數(shù)和有向弧條數(shù)相等4、狀態(tài)轉(zhuǎn)換圖見圖3-6-1承受的字集為。 0 1 0圖3-6-1Y*a. 以 0開頭的二進(jìn)制數(shù)組成的集合 b. 以0結(jié)尾的二進(jìn)制數(shù)組成的集合c. 含奇數(shù)個0的二進(jìn)制數(shù)組成的集合 d. 含偶數(shù)個0的二進(jìn)制數(shù)組成的集合5、詞法分析器作為獨立的階段使整個編譯程序構(gòu)造更加

17、簡潔、明確，因此，。a. 詞法分析器應(yīng)作為獨立的一遍 b. 詞法分析器作為子程序較好c. 詞法分析器分解為多個過程，由語法分析器選擇使用 d. 詞法分析器并不作為一個獨立的階段解答 1、b 2、c 3、c 4、d 5、b二、多項選擇題1、在詞法分析中，能識別出。a. 根本字b. 四元式c. 運算符d. 逆波蘭式e. 常數(shù)2、令=a,b，則上所有以b開頭，后跟假設(shè)干個ab的字的全體對應(yīng)的正規(guī)式為。a.b(ab)*b. b(ab)+c.(ba)*bd. (ba)+be. b(a|b)解答 1、a、c、e 2、a、b、d三、填空題1、確定有限自動機(jī)DFA是的一個特例。2、假設(shè)二個正規(guī)式所表示的一樣，

18、則認(rèn)為二者是等價的。3、一個字集是正規(guī)的，當(dāng)且僅當(dāng)它可由所。解答 1、NFA 2、正規(guī)集 3、DFANFA所識別四、判斷題1、一個有限狀態(tài)自動機(jī)中，有且僅有一個唯一終態(tài)。 2、設(shè)r和s分別是正規(guī)式，則有Lr|s=L(r)|L(s)。 3、自動機(jī)M和M的狀態(tài)數(shù)不同，則二者必不等價。 4、確定的自動機(jī)以及不確定的自動機(jī)都能正確地識別正規(guī)集。 5、對任意一個右線性文法G，都存在一個NFA M，滿足L(G)=L(M)。 6、對任意一個右線性文法G，都存在一個DFA M，滿足L(G)=L(M)。 7、對任何正規(guī)表達(dá)式e，都存在一個NFA M，滿足L(G)=L(e)。 8、對任何正規(guī)表達(dá)式e，都存在一個D

19、FA M，滿足L(G)=L(e)。 解答 1 、2、3、錯 4、5、6、7、8、正確五、基此題1、設(shè)M*,y, a,b, f,*,y為一非確定的有限自動機(jī)，其中f定義如下：f*,a*,y f*,byfy,a fy,b*,y 試構(gòu)造相應(yīng)確實定有限自動機(jī)M。解答：對照自動機(jī)的定義M=(S,f,S0,Z)，由f的定義可知f(*,a)、f(y,b)均為多值函數(shù)，所以是一非確定有限自動機(jī)，先畫出NFA M相應(yīng)的狀態(tài)圖，如圖3-6-2所示。 a a b b b圖3-6-2 NFA M*Y用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣表3-6-3所示。IIaIb*,yyy*,y*,y*,y*,y將轉(zhuǎn)換矩陣中的所有子集重新命名而形

20、成表3-6-4所示的狀態(tài)轉(zhuǎn)換矩陣。表3-6-4 狀態(tài)轉(zhuǎn)換矩陣ab02112222 a a,b b b圖3-6-5 DFA M021即得到M=0,1,2, a,b, f,0, 1,2，其狀態(tài)轉(zhuǎn)換圖如圖3-6-5所示。 a a,b b圖3-6-6 化簡后的DFA M01將圖3-6-5的DFA M最小化。首先，將M的狀態(tài)分成終態(tài)組1，2與非終態(tài)組0；其次，考察1,2。由于1,2a=1,2b=21,2，所以不再將其劃分了，也即整個劃分只有兩組0，1,2：令狀態(tài)1代表1,2，即把原來到達(dá)2的弧都導(dǎo)向1，并刪除狀態(tài)2。最后，得到如圖3-6-6所示化簡DFA M。2、對給定正規(guī)式b*d|adb|ab+，構(gòu)造

21、其NFA M； aadb*b*(d|ad)(b|ab)(b|ab)*Y*123Y*4135Y678(d|ad)(b|ab)(b|ab)*2dbadabb|abb*4135Y2bdbbabb圖3-6-7 的NFA M解答：首先用A+=AA*改造正規(guī)式得：b*(d|ad)(b|ab)(b|ab)*；其次，構(gòu)造該正規(guī)式的NFA M，如圖3-6-7所示。1、 構(gòu)造下面文法的LL1分析表。D TLT int | realL id RR, id R | 解答： LL1分析表見表4-3-1分析 雖然這個文法很簡單，我們還是從求開場符號集合和后繼符號集合開場。 FIRSTD=FIRSTT=int, realF

22、OLLOWD=FOLLOWL=#FIRSTL=id FOLLOWT=idFIRSTR=，, FOLLOWR=#有了上面每個非終結(jié)符的FIRST集合，填分析表時要計算一個產(chǎn)生式右部的FIRST就不是件難事了。填表時唯一要小心的時，是產(chǎn)生式R右部的一個開場符號，而#在FOLLOWR中，所以R填在輸入符號#的欄目中。表4-3-1 LL1分析表非終結(jié)符輸入符號int realid，#DDTLDTLTTintTrealLLid RRR,id RR2、 下面文法GS是否為LL1文法？說明理由。SA B | P Q *A * y B b cP d P | Q a Q | 解答： 該文法不是LL1文法，見下面

23、分析中的說明。分析 只有三個非終結(jié)符有兩個選擇。 1、P的兩個右部d P 和 的開場符號肯定不相交。2、Q的兩個右部a Q 和 的開場符號肯定不相交。3、對S來說，由于* FIRST(A B)，同時也有* FIRST(P Q *)因為P和Q都可能為空。所以該文法不是LL1文法。3、 設(shè)有以下文法： GS：SaAbDe|d ABSD|e BSAc| cD| DSe| 1求出該文法的每一個非終結(jié)符U的FOLLOW集。2該文法是LL1文法嗎？3構(gòu)造CS的LL1分析表。解答： 1求文法的每一個非終結(jié)符U的FOLLOW集的過程如下：因為： S是識別符號，且有ABSD、BSAc、DSe，所以FOLLOWS

24、應(yīng)包含F(xiàn)IRST(D)FIRST(Ac)FIRST(e)#=a,da,d,c,ee#=a,c,d,e#又因為ABSD和D，所以FOLLOW中還包含F(xiàn)OLLOW(A)。因為SaAbDe和BSAc,所以FOLLOWA=FIRSTbDeFIRSTc=b,c綜合、得FOLLOWS=a,d,c,e,#a,b,c,d,e,#因為ABSD，所以FOLLOWB=FIRSTSD=a,d因為SaAbDe | d、ABSD| e和BSAc | cD，所以FOLLOWD=FIRSTeFOLLOWAFOLLOWB=eb,ca,d=a,b,c,d,e2GS不是LL1文法。因為產(chǎn)生式BSAc|cD| 中FIRSTSAcFO

25、LLOWB=a,d3構(gòu)造GS的LL1分析表。按照LL1分析表的構(gòu)造算法構(gòu)造方法GS的LL1分析表如表4-3-2所示。表4-3-2 GS的LL1分析表abcde#SaAbDedABSDBSDBSDeBSac/cDSac/DSe/Se/4、 將文法GV改造成為LL(1)的。 GV：VN|NE EV|V+E Ni解答： 對文法GV提取公共左因子后得到文法： GV：VNAA|EEVBB|+ENi求出文法GV中每一個非終結(jié)符號的FIRST集：FIRST(V)=iFIRST(A)=,FIRST(E)=iFIRST(B)=+,FIRST(N)=i求出文法GV中每一個非終結(jié)符號的FOLLOW集：FOLLOW(

26、V)=#FIRST(B)FOLLOW(E)=#,+,FOLLOW(A)= FOLLOW(V)=+,#FOLLOW(E)= FIRST()FOLLOW(B)= FIRST()FOLLOW(E)=FOLLOW(B)= FOLLOW(E)= FOLLOW(N)= FIRST(A)FOLLOW(V)=,+,#可以看到，對文法GV的產(chǎn)生式A|E，有FIRST(E)FOLLOW(A)=+,#= 對產(chǎn)生式B|+E，有FIRST(+E)FOLLOW(B)=+= 而文法的其他產(chǎn)生式都只有一個不為的右部，所以文法GV是LL(1)文法。5、文法：GA：AaAa|1該文法是LL1文法嗎？為什么？2假設(shè)采用LL1方法進(jìn)

27、展語法分析，如何得到該文法的LL1分析表？3假設(shè)輸入符號串“aaaa，請給出語法分析過程。解答：1因為產(chǎn)生式AaAa| 有空產(chǎn)生式右部，而FOLLOW(A)=#FIRST(a)=a, #造成 FIRST(A)FOLLOW(A)=A, a, #所以該文法不是LL1文法。2假設(shè)采用LL1方法進(jìn)展語法分析，必須修改該文法。因該文法產(chǎn)生偶數(shù)可以為0個a，所以得到文法GA：AaaA|此時對產(chǎn)生式AaaA|， 有 FOLLOW(A)=#FOLLOW(A)=#，因而FIRST(A)FOLLOW(A)=a, #=所以文法GA是LL1文法，按LL1分析表構(gòu)造算法構(gòu)造該文法的LL1分析表如表4-3-3所示。表4-

28、3-3文法GA的LL(1)分析表A#AAaaAA3假設(shè)采用LL(1)方法進(jìn)展語法分析，對符號串“aaaa的分析過程如表4-3-4所示。 表4-3-4對符號串“aaaa的分析過程步驟分析棧輸入串產(chǎn)生式/動作1#Aa a a a #AaaA2#A a aa a a a #匹配3#A aa a a #匹配4#Aa a #AaaA5#A a aa a #匹配6#A aa#匹配7#A#A8#承受第七節(jié) 習(xí)題設(shè)有文法GS為：Sa|b|(A)ASdA|S完成以下算符優(yōu)先關(guān)系表，見表5-7-1，并判斷GS是否為算符優(yōu)先文法。表5-7-1 算符優(yōu)先關(guān)系表ab()d#ab()d#2給出句型SdSdS的短語、簡單短

29、語、句柄、素短語和最左素短語。3給出輸入串a(chǎn)db#的分析過程。解答： 1先求文法GS的FIRSTVT集和LASTVT集：由Sa|b|(A)得：FIRSTVT(S)=a,b,( );由ASd得：FIRSTVT(A)=d;又由AS得：FIRSTVT(S) FIRSTVT(A)，即FIRSTVT(A)=d,a,b,(;由Sa|b|(A)得；LASTVT(S)=a,b,;由AdA得：LASTVT(A)=d,又由AS得：LASTVT(S) LASTVT(A)，即LASTVT(A)=d,a,b,)。構(gòu)造優(yōu)先關(guān)系表方法如下： 對Pab，或PaQb，有ab;對PaR，而bFIRSTVT(R)，有ab;對PRb

30、，而aFIRSTVT(R)，有ab。由此得到：由S(A)得：();由S(A得：(FIRSTVT(A)，即：(d,(a ,(b,(;由AdA得：dFIRSTVT(A)，即：dd,da,db,d(;由SA)得，LASTVT(A)，即：d),a),b),);由ASd得：LASTVT(S)d，即：ad,bd,)d;此外，由#S#得：#；由#FIRSTVT(S)得：#a,#b,#(；脂由LASTVT(S)#得：d#,a#,b#,)#。最后得到算符優(yōu)先關(guān)系表，見表5-7-2。表5-7-2 算符優(yōu)先關(guān)系表ab()d#ab()d#由表5-7-2可以看出，任何兩個終結(jié)符之間至少只滿足、三種優(yōu)先關(guān)系之一，故GS為

31、算符優(yōu)先文法。SASASdASd圖5-7-3 句型SdSdS的語法樹2為求出句型SdSdS的短語、簡單短語、句柄，我們先畫出該句型對應(yīng)的語法樹，如圖5-7-3所示。由圖5-7-3得到：短語：S，SdS，SdSdS，SdSdS簡單短語即直接短語：S句柄即最左直接短語：S素短語：SdS，它同時也是該句型的最左素短語。3輸入串a(chǎn)db#的分析過程見表5-7-4表5-7-4 輸入串a(chǎn)db#的分析過程符號棧輸入串說明#(adb)#移進(jìn)#adb)#移進(jìn)#adb)#用Sa歸約#Sdb)#移進(jìn)#Sdb)#移進(jìn)#Sdb)#用Sb歸約#SdS)#用AS歸約#SdA)#用ASdA歸約#A)#移進(jìn)#A#用SA歸約#S#

32、分析成功第四節(jié) 習(xí)題一、單項選擇題1、假設(shè)a為終結(jié)符，則Aa為工程a.歸約b.移進(jìn)c.承受d.待約2、假設(shè)工程集Ik含有A，則在狀態(tài)k時，僅當(dāng)面臨的輸入符號aFOLLOW(A)時，才采取“A動作的一定是。a.LALR文法b.LR0文法c.LR1文法d.SLR1文法3、就文法的描述能力來說，有。a. SLR1LR0 b. LR1LR0c. SLR1LR1d.無二義文法LR14、在LR0的ACTION子表中，如果*一行中存在標(biāo)記“rj的欄，則。a.該行必定填滿r.該行未填滿rjc.其他行也有rjd.goto子表中也有rj5、一個 指明了在分析過程中的*時刻所能看到產(chǎn)生式多大一局部。a.活前綴b.前

33、綴c.工程d.工程集解答： 1、A稱為歸約工程，對文法開場符S的歸約工程，如S稱為承受工程，Aaa為終結(jié)符稱為移進(jìn)工程。在此選b.2、當(dāng)用產(chǎn)生式A歸約時，LR0無論面臨什么輸入符號都進(jìn)展歸約；SLR1則僅當(dāng)面臨的輸入符號aFOLLOW(A)時進(jìn)展歸約；LR1則當(dāng)在把歸約為A的規(guī)*句型的前綴Aa前提下，當(dāng)后跟終結(jié)符a時，才進(jìn)展歸約；因此選d。3、由于LR0SLR1 LR1無二義文法，應(yīng)選c。4、選a。5、選c。二、多項選擇題1、一個LR分析器包括。a.一個總控程序b.一個工程集c.一個活前綴d.一*分析表e.一個分析棧2、LR分析器核心局部是一*分析表，該表包括 等子表。a.LL(1)分析b.優(yōu)

34、先關(guān)系c.GOTO d.LRe.ACTION3、每一項ACTIONS，a所規(guī)定的動作包括。a.移進(jìn)b.比擬c.承受d.歸約e.報錯4、對LR分析表的構(gòu)造，有可能存在動作沖突。a.移進(jìn)b.歸約c.移進(jìn)/歸約d.移進(jìn)/移進(jìn)e.歸約/歸約5、就文法的描述能力來說，有。a. SLR1LR1b. LR1SLR1c. LR0LR1d. LR1無二義文法 e. SLR1無二義文法6、對LR分析器來說，存在等分析表的構(gòu)造方法。a.LALRb.LR0c.SLR1d.SLR0e.LR17、自上而下的語法分析方法有 。a.算符優(yōu)先分析法b.LL1分析法c.SLR1分析法d.LR0分析法e.LALR1分析法解答： 1

35、、一個LR分析器包括一個總控程序和一*分析表，選a、d。2、選c、e。3、選a、c、d、e。4、在LR分析表的構(gòu)造中有可能存在“移進(jìn)/“歸約和“歸約/“歸約沖突；應(yīng)選c、e。5、選a、b、c、d、e。6、選a、b、c、e。7、選a、c、d、e。三、填空題1、對于一個文法，如果能夠構(gòu)造。使得它的均是唯一確定的，則稱該文法為LR文法。2、字的前綴是指該字的。3、活前綴是指的一個前綴，這種前綴不含之后的任何符號。4、在LR分析過程中，只要的已掃描局部保持可歸約成一個，則掃描過的局部正確。5、將識別的NFA確定化，使其成為以為狀態(tài)的DFA，這個DFA就是建立的根底。6、A稱為工程；對文法開場符S為工程

36、；假設(shè)a為終結(jié)符，則稱Aa為工程；假設(shè)B為非終結(jié)符，則稱Aa為工程。 7、LR0分析法的名字中“L表示，“R表示，“0表示。解答： 1、一*分析表 每個入口2、任意首部3、規(guī)*句型 句柄4、輸入串 活前綴5、活前綴 工程集合 LR分析算法6、歸約 承受 移進(jìn) 待約7、自左至右分析 采用最右推導(dǎo)的逆過程即最左歸約 向右查看0個字符四、綜合題1、對于文法GS： SAS|b ASA|a1列出所有LR0工程2列出構(gòu)成文法LR0工程集規(guī)*族。解答：首先將文法G拓廣為GS：SSSAS|bASA|a1文法GS的LR0工程是： 1、SS5、SAS9、ASA 2、SS6、Sb10、ASA 3、SAS7、Sb11

37、、Aa 4、SAS8、ASA12、Aa2、列出構(gòu)成文法LR0工程集規(guī)*族。用-CLOSURE閉包方法構(gòu)造文法G的LR0工程集規(guī)*族如下：I0：1、SS I3：9、ASAI6：12、Aa 3、SAS8、ASAI7：7、Sb 8、ASA3、SAS 11、Aa6、Sb 6、Sb11、AaI1：2、SSI4：10、ASA 9、ASA4、SAS8、ASA3、SAS11、Aa6、Sb3、SAS8、ASA6、Sb 11、AaI2：4、SASI5：5、SAS 3、SAS9、ASA6、Sb8、ASA 8、ASA11、Aa 11、Aa3、SAS6、Sb注意：I1中的SS和ASA是由狀態(tài)I0中的1和3讀入一個S字符

38、后得到的下一個工程；，而I4中的ASA和AAS則是由I3中的9和3讀入一個A字符后得到的下一個工程；I5中的SAS和ASA則是由I4中的4和8讀入一個S字符后得到的下一個工程。狀態(tài)全體構(gòu)成了文法G的LR0規(guī)*族。第八節(jié) 習(xí)題一、單項選擇題1、中間代碼生成所依據(jù)的是。a.語法規(guī)則b.詞法規(guī)則c.語義規(guī)則d.等價變換規(guī)則2、四元式之間的聯(lián)系是通過實現(xiàn)的。a.指示器b.臨時變量c.符號表d.程序變量3、后綴式ab+cd+/可用表達(dá)式來表示。a.a+b/c+db.(a+b)/(c+d)c.a+b/(c+d)d.a+b+c/d4、表達(dá)式ABCD的逆波蘭表示為。a.ABCDb. ABCDc. ABCDd.

39、 ABCD5、中間代碼的樹型表示+ABCD+ 所對應(yīng)的表達(dá)式為。 a.A+B+C+Db.A+(B+C)+Dc.(A+B)+C+Dd.(A+B)+(C+D)6、四元式表示法的優(yōu)點為。a.不便于優(yōu)化處理，但便于表的更動b.不便于優(yōu)化處理，但節(jié)省存儲空間c.便于優(yōu)化處理，也便于表的更動d.便于表的更動，也節(jié)省存儲空間7、終結(jié)符具有屬性。a.傳遞b.繼承c.抽象d.綜合解答 1、選c。2、四元式之間的聯(lián)系是通過臨時變量實現(xiàn)的，應(yīng)選b。3、選b。4、選b。5、選d。6、四元式表示法的優(yōu)點與間接三元式一樣，應(yīng)選c。7、選d。 二、多頂選擇題1、中間代碼主要有。a四元式b二元式c三元式d后綴式e間接三元式2

40、、下面中間代碼形式中，能正確表示算術(shù)表達(dá)式a+b+c的有。+a +b c+ ca baab+c+babc+c d ea+b+c3、在下面的語法制導(dǎo)翻譯中，采用拉鏈-回填技術(shù)。a賦值語句bgoto語句 c條件語句d循環(huán)語句4、以下中間代碼形式有益于優(yōu)化處理。a三元式b四元式c間接三元式d逆波蘭表示法e樹形表示法5、在編譯程序中安排中間代碼生成的目的是。a便于進(jìn)展存儲空間的組織b利于目標(biāo)代碼的優(yōu)化c利于編譯程序的移植d利于目標(biāo)代碼的移植e利于提高目標(biāo)代碼的質(zhì)量+a *a b*+ ca b6、下面的中間代碼形式中，能正確表示算術(shù)表達(dá)式a+b*c。題aab+c*babc*+ca+b*cd e7、三地址

41、代碼語句具體實現(xiàn)通常有表示方法。a逆波蘭表示b三元式c間接三元式d樹形表示e四元式解答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、d。6、選b、e。7、選b、c、e。三、填空題1、中間代碼有等形式，生成中間代碼主要是為了使。2、語法制導(dǎo)翻譯既可以用來產(chǎn)生代碼，也可以用來產(chǎn)生指令，甚至可用來對輸入串進(jìn)展。3、當(dāng)源程序中的標(biāo)號出現(xiàn)“先引用后定義時，中間代碼的轉(zhuǎn)移地址須持時才能確定，因而要進(jìn)展。4、文法符號的屬性有兩種，一種稱為，另一種稱為。5、后綴式abc-

42、/所代表的表達(dá)式是，表達(dá)式(a-b)*c可用后綴式表示。6、用一*輔以的方法來表示中間代碼，這種表示法稱為間接三元式。解答1、逆波蘭記號、樹形表示、三元式、四元式目標(biāo)代碼的優(yōu)化容易實現(xiàn)2、中間目標(biāo)解釋執(zhí)行3、標(biāo)號定義回填4、繼承屬性綜合屬性5、a/(b-c)ab-c*6、間接碼表三元式表四、綜合題1、給出以下表達(dá)式的逆波蘭表示后綴式： a*(-b+c) (AB)(CDE)2、寫出算術(shù)表達(dá)式：A+B*(C-D)+E/(C-D)N的四元式序列；三元式序列；間接三元式序列解答1、abc+*; ABCDE2、表達(dá)式的四元式序列：表達(dá)式的三元式序列 間接三元式序列1(-,C,D,T1)1(-,C,D)

43、1(-,C,D)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) (,(1),N) 5(,T4,N,T5)5(,(4),N) (/,E,(4) (/,E,T5,T6) (/,E,(5) (+,(3),(5) (+,T3,T6,T7) (+,(3),(6) 第三節(jié) 習(xí)題一、單項選擇題1、編譯程序使用區(qū)別標(biāo)識符的作用域。a. 說明標(biāo)識符的過程或函數(shù)名 b. 說明標(biāo)識符的過程或函數(shù)的靜態(tài)層次c. 說明標(biāo)識符的過程或函數(shù)的動態(tài)層次 d. 標(biāo)識符的行號2、在目標(biāo)代碼生成階段，符號表用于。a.

44、 目標(biāo)代碼生成b. 語義檢查c. 語法檢查d. 地址分配3、過程信息表不包含。a. 過程入口地址 b. 過程的靜態(tài)層次 c. 過程名 d. 過程參數(shù)信息4、以下關(guān)于標(biāo)識符和名字表達(dá)中，正確的選項是。a. 標(biāo)識符有一定的含義b. 名字是一個沒有意義的字符序列c. 名字有確切的屬性d.ac都不正確解答：1、b 2、d 3、b 4、c二、多項選擇題1、符號表的每一項均包含。a. 名字欄b. 類型欄c. 信息欄d. 值欄e.ad均包含2、對編譯程序所用到的符號表，涉及的操作有。a. 填寫或更新信息欄內(nèi)容b. 填入新名c.給定名字，訪問它的有關(guān)信息d. 雜湊技術(shù)e.線性表和排序二叉樹3、源程序中的錯誤一

45、般有。a. 詞法錯誤b. 語法錯誤c. 語義錯誤d. 編譯錯誤e. 違反環(huán)境限制的錯誤解答：1、a 、c 2、a、b、c 3、a、b、c、e三、填空題1、符號表中名字欄內(nèi)容有兩種填寫方式，它們是填寫和填寫。2、詞法分析階段的錯誤主要是，可通過的方法糾正錯誤。3、符號表中名字的有關(guān)信息在和過程中陸續(xù)填入。4、在目標(biāo)代碼生成階段，符號表是的依據(jù)。解答：1、標(biāo)識符 標(biāo)識符地址及長度2、拼寫錯誤 最小距離匹配 3、詞法分析 語法語義分析 4、地址分配四、問答題：1、在編譯過程中為什么要建立符號表？解答：在編譯過程中始終要涉及到對一些語法符號的處理，這就需要用到語法符號的相關(guān)屬性。為了在需要時能找到這些

46、語法成分及其相關(guān)屬性，就必須使用一些表格來保存這些語法成分及其屬性，這些表格就是符號表。第四節(jié) 習(xí)題一、單項選擇題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ù)等進(jìn)展分配b. 在編譯階段對源程序中的數(shù)組、變量、參數(shù)進(jìn)展分配c. 在編譯階段對源程序中的數(shù)

47、組、變量、參數(shù)等進(jìn)展分配，在運行時這些數(shù)組、變量、參數(shù)的地址可根據(jù)需要改變d. 以上都不正確5、在編譯時有傳名功能的高級程序語言是。a.Fortranb. Basicc. Pascald. ALGOL6、棧式動態(tài)分配與管理在過程返回時應(yīng)做的工作有。a. 保護(hù)SPb. 恢復(fù)SPc.保護(hù)TOPd. 恢復(fù)TOP解答1、c 2、d 3、c 4、a 5、d 6、b二、多項選擇題1、下面需要在運行階段分配存儲空間。a. 數(shù)組b. 指針變量c.動態(tài)數(shù)組d. 靜態(tài)變量e. 動態(tài)變量2、棧式動態(tài)分配允許。a. 遞歸過程b. 分程序構(gòu)造c. 動態(tài)變量d. 動態(tài)數(shù)組e. 靜態(tài)數(shù)組3、動態(tài)存儲分配可采用的分配方案有。a. 隊式存儲分配b.棧式存儲分配 c.鏈?zhǔn)酱鎯Ψ峙鋎. 堆式存儲分配 e.線性存儲分配4、棧式動態(tài)分配與管理因調(diào)用