編譯原理與技術(shù)1

1、編譯原理與技術(shù)模擬試題一一、填空題（20分，每空2分）1.1編譯程序的工作過程可劃分為詞法分析、語法分析、中間代碼生成、代碼優(yōu)化、等階段，一般在階段對表達(dá)式中運(yùn)算對象的類型進(jìn)行檢查。答案：語義分析、目標(biāo)代碼生成、語義分析解釋：要求掌握編譯器的工作原理和特點(diǎn)。編譯和解釋方式是翻譯高級程序設(shè)計(jì)語言的 兩種基本方式。解釋程序也稱為解釋器，它或者直接解釋執(zhí)行源程序，或者將源程序翻 譯成某種中間表示形式后再加以執(zhí)行；而編譯程序（編譯器）則首先將源程序翻譯成目 標(biāo)語言程序，然后在計(jì)算機(jī)上運(yùn)行目標(biāo)程序。編譯過程包含詞法分析、語法分析、語義 分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成，以及符號表管理和出錯(cuò)處理

2、。表達(dá)式 的類型信息屬于語義信息，所以在語義分析階段進(jìn)行類型檢查。和預(yù)測分析法是自上而下的語法分析方法。答案：遞歸下降法解釋：語法分析的任務(wù)是根據(jù)語言的語法規(guī)則，分析單詞串是否構(gòu)成短語和句子，即表 達(dá)式、語句和程序等基本語言結(jié)構(gòu)，同時(shí)檢查和處理程序中的語法錯(cuò)誤。根據(jù)語法樹（或 分析樹）的建立方式，語法分析可分為自上而下分析和自下而上分析兩類，遞歸下降分 析和預(yù)測分析屬于自上而下的語法分析方法。1.3常用的存儲(chǔ)分配策略有 存儲(chǔ)分配和動(dòng)態(tài)存儲(chǔ)分配，其中，動(dòng)態(tài)存儲(chǔ)分配策略包括 分配和 分配。答案：靜態(tài)、棧、堆解釋：編譯器怎樣對存儲(chǔ)空間進(jìn)行組織和采用什么樣的存儲(chǔ)分配策略，很大程度上取決 于程序設(shè)計(jì)語言

3、中所采用的機(jī)制。編譯器具體實(shí)現(xiàn)時(shí)，根據(jù)語言機(jī)制的特性，采用靜態(tài) 分配策略、棧分配策略和堆分配策略三種方式的其中若干種。靜態(tài)分配策略是指編譯 時(shí)安排所有數(shù)據(jù)對象的存儲(chǔ)，即綁定是靜態(tài)確定的；棧分配策略是指按棧的方式管理運(yùn) 行時(shí)的存儲(chǔ)；堆分配策略是指在運(yùn)行時(shí)根據(jù)要求從堆數(shù)據(jù)區(qū)動(dòng)態(tài)地分配和釋放存儲(chǔ)。1.4移進(jìn)、歸約是分析中的典型操作。答案：自下而上或LR解釋：自下而上分析的一般思路是從句子3開始，從左到右掃描3,反復(fù)用產(chǎn)生式的左部 替換產(chǎn)生式的右部、謀求對3的匹配，最終得到文法的開始符號，或者發(fā)現(xiàn)一個(gè)錯(cuò)誤。 移進(jìn)-歸約是實(shí)現(xiàn)自下而上分析的一般方法。1.5對于數(shù)組M1.6, 1.8，如果每個(gè)元素占k個(gè)存

4、儲(chǔ)單元，且起始地址為a,則以行為 主序存放時(shí)元素M4,4的地址是，以列為主序存放時(shí)元素M4,4的地址是。答案：1.5 a+27*k，a+21k解釋：計(jì)算排列在M4,4之前的元素個(gè)數(shù)即可。二、單選題(10分，每空2分)2.1詞法分析器不能。A.識別出數(shù)值常量B.過濾源程序中的注釋C.掃描源程序并識別記號D.發(fā)現(xiàn)括號不匹配答案：D解釋：詞法分析的作用為根據(jù)模式識別記號，并交給語法分析器；濾掉源程序中的無用 成分，如注釋、空格、回車等；處理與具體平臺有關(guān)的輸入；不同的平臺對某些特殊 符號(如文件結(jié)束符等)可能有不同表示，因此需要在詞法分析階段分情況處理；調(diào)用 符號表管理器或出錯(cuò)處理器，進(jìn)行相關(guān)處理。

5、一個(gè)句型中的最左稱為該句型的句柄。A.短語B.直接短語C,非終結(jié)符號 D.終結(jié)符號答案：B解釋：根據(jù)定義。2.3已知文法GS:SA1 AA1|S0|0。與G等價(jià)的正規(guī)式是。A. 0(011)*B, 1*10*1C. 0(1110)*1D. 1(10101)*0答案：C解釋：用推導(dǎo)和構(gòu)造思路處理。2.4與逆波蘭式ab+c*d+對應(yīng)的中綴表達(dá)式是。A. a+b+c*dB. (a+b)* c+d C. (a+b)* (c+d) D. a+b*c+d答案：B解釋：從表達(dá)式的求值過程考慮。逆波蘭式中運(yùn)算符的書寫順序就是處理順序，中綴表 達(dá)式要根據(jù)運(yùn)算符的優(yōu)先級和結(jié)合性進(jìn)行處理。2.5在表達(dá)式x:=y+1

6、中，作為左值出現(xiàn)(其中，“：二”表示賦值)。A. xB. yC. 1D. y+1答案：A解釋：形式上講，出現(xiàn)在賦值號左邊的對象稱為左值，右邊的稱為右值；實(shí)質(zhì)上，左值 必須具有存儲(chǔ)空間，而右值可以僅是一個(gè)值，沒有存儲(chǔ)空間。形象地講，左值是容器， 右值是內(nèi)容。三、簡答題(40分，每小題10分)3.1請分別寫出傳值調(diào)用、引用調(diào)用方式下，下面代碼的輸出結(jié)果。program main(input,output)procedure f(a,b)begina := b - a;b := a * b + 1;end;beginx := 5; y := 10;f(y,x);print(x,y);end.答案：傳

7、值調(diào)用方式：5 10引用調(diào)用方式：-24 -5 解釋：傳值方式下，實(shí)參與形參各自有獨(dú)立的存儲(chǔ)單元，調(diào)用時(shí)將實(shí)參的值傳遞給形參， 對形參進(jìn)行的修改與實(shí)參無關(guān)。引用調(diào)用方式下，是將實(shí)參的地址傳遞給形參，對形參 所作的修改最后會(huì)返回給實(shí)參。3.2請計(jì)算下面文法G(E)中各非終結(jié)符的FIRST和FOLLOW集合。請說明該文法為什 么不是LL(1)文法。G(E)： EE* T | T TT - F | F F (E) | id 答案：FIRST(F) = FIRST(T) = FIRST(E) = (,id FOLLOW(E) = #,*,) FOLLOW(T) = -, *, #,) FOLLOW(F

8、) = -, *, #,) 解釋：通俗地講，a的FIRST集合就是從a開始可以導(dǎo)出的序列中的開頭終結(jié)符。而A 的FOLLOW集合，就是從開始符號可以導(dǎo)出的所有含A序列中緊跟A之后的終結(jié)符。 根據(jù)計(jì)算FIRST集合和FOLLOW集合的算法進(jìn)行計(jì)算。判定G是否LL(1 )文法有兩個(gè)：構(gòu)造分析表，判斷分析表中是否包含多重定義的條 目；根據(jù)推論3.2：文法G是LL(1)的，當(dāng)且僅當(dāng)G的任何兩個(gè)產(chǎn)生式Aa|B， 滿足下面條件:1.對任何終結(jié)符a，a和B不能同時(shí)推導(dǎo)出以a開始的串；2. a和B最 多有一個(gè)可以推導(dǎo)出e； 3.若B=*e，則a不能推導(dǎo)出以在FOLLOW (A)中的終結(jié) 符開始的任何串。3.3

9、下圖所示的分析樹用到了某個(gè)上下文無關(guān)文法的所有產(chǎn)生式。給出該文法的所有非終結(jié)符號集合N和終結(jié)符號集合T。給出該文法的產(chǎn)生式集合。答案：N = S, A, BT = a, b, c, dS 一 aAcB | BdA 一 AaB | cB 一 bScA | b | e解釋：對CFG G的句型，分析樹被定義為具有下述性質(zhì)的一棵樹。根由開始符號所標(biāo)記；每個(gè)葉子由一個(gè)終結(jié)符、非終結(jié)符、或e標(biāo)記；每個(gè)內(nèi)部結(jié)點(diǎn)由一個(gè)非終結(jié)符標(biāo)記；若A是某內(nèi)部節(jié)點(diǎn)的標(biāo)記，且X1, X2, ., Xn該節(jié)點(diǎn)從左到右所有孩子的標(biāo) 記，則AX1X2.Xn是一個(gè)產(chǎn)生式。若A-e，則標(biāo)記為A的結(jié)點(diǎn)可以僅有一個(gè)標(biāo)記為8的孩子。分析樹與語

10、言和文法的關(guān)系：每一直接推導(dǎo)（每個(gè)產(chǎn)生式），對應(yīng)一棵僅有父子關(guān)系 的子樹，即產(chǎn)生式左部非終結(jié)符“長出”右部的孩子； 分析樹的葉子，從左到右構(gòu) 成G的一個(gè)句型。若葉子僅由終結(jié)符標(biāo)記，則構(gòu)成一個(gè)句子。3.4某程序執(zhí)行到某一時(shí)刻時(shí)控制棧中的內(nèi)容如下所示（其中M是主程序，P、Q、R、S 均是過程），給出所有在生存期的活動(dòng)的調(diào)用關(guān)系（提示：若A調(diào)用B，則記為A-B）。S的活動(dòng)記錄 S的活動(dòng)記錄 Q的活動(dòng)記錄 R的活動(dòng)記錄 P的活動(dòng)記錄 M的活動(dòng)記錄top控制鏈KI%I答案：M P R Q S S解釋：順序執(zhí)行程序的執(zhí)行在時(shí)間上是順序的和排他的。即在程序執(zhí)行的任一瞬間，有 且僅有一個(gè)活動(dòng)正在活動(dòng)?？刂茥Ｓ?/p>

11、于保存所有在生存期的活動(dòng)（一條后進(jìn)先出的路 徑）。棧中的每個(gè)元素稱為一個(gè)活動(dòng)記錄（activation record），為活動(dòng)提供的活動(dòng)場所。 顯然，根據(jù)控制棧中的內(nèi)容，應(yīng)該是M調(diào)用了 P，P隨后又調(diào)用了 R，R又調(diào)用了 Q， Q調(diào)用了 S，S又調(diào)用了 S （遞歸調(diào)用）。四、綜合題（30分）4.1 （15分）設(shè)有正規(guī)式r=1（0|1）*1，試給出：（a）（5分）識別該正規(guī)集的NFA；（b）（10分）識別該正規(guī)集的DFA （要有計(jì)算過程）；答案：（a）NFA如下圖所示(b)s0 = A0_閉包(s0) = S0初態(tài)_閉包(smove(s0,1) = B記為s1_閉包(smove(s1,0) =

12、B = si_閉包(smove(s1,1) = B,C記為s2，終態(tài)_閉包(smove(s2,0) = B = si_閉包(smove(s2,1) = B,C = s2DFA如下圖所示01解釋：用算法2.2 Thompson算法從正規(guī)式構(gòu)造出與其對應(yīng)的NFA；用子集法(算法2.3) 將NFA轉(zhuǎn)換為DFA。其中需要用算法2.4計(jì)算狀態(tài)集T的s閉包(T)。(15分)設(shè)有上下文無關(guān)無法G及其語法制導(dǎo)翻譯如下(注：G中終結(jié)符id僅由單個(gè) 英文字母組成，如a, b等)：EE*TE.place=newtemp; emit(*,Emplace,T.place,E.place;| TE.place=T.pla

13、ce;TTFT.place=newtemp; emit(-,Tplace,F.place,T.place;| FT.place=F.place;F(E)F.place=E.place;| idF.place=;(4分)畫出句子a-b*c的分析樹;(3分)寫出當(dāng)a=1、b=2、c=3時(shí)的計(jì)算結(jié)果；(*表示算術(shù)乘、-表示算術(shù)減)(8分)將文法G簡化為:E-E*T|T, TT-F|F, F-id,給出其識別活前綴的DFA, 該DFA的項(xiàng)目集中有沖突嗎？若有，是哪種類型的沖突。答案：(a)(b) -3拓廣文法，增加產(chǎn)生式：S-E，識別活前綴的DFA如下圖所示存在移進(jìn)一歸約沖突解釋：(a)

14、從文法推導(dǎo)(最左推導(dǎo))出句子a-b*c的過程為：E = E * T = T * T = T - F * T = F - F * T = a - F * T = a - b * T = a - b * F = a - b * c分析樹是對推導(dǎo)過程的直觀描述。分析樹被定義為具有下述性質(zhì)的一棵樹：(1)根由開始符號所標(biāo)記；(2)每個(gè)葉 子由一個(gè)終結(jié)符、非終結(jié)符、或8標(biāo)記；(3)每個(gè)內(nèi)部結(jié)點(diǎn)由一個(gè)非終結(jié)符標(biāo)記；(4) 若A是某內(nèi)部節(jié)點(diǎn)的標(biāo)記，且X1, X2, ., Xn該節(jié)點(diǎn)從左到右所有孩子的標(biāo)記，則A 一X1X2.Xn是一個(gè)產(chǎn)生式。若A8,則標(biāo)記為A的結(jié)點(diǎn)可以僅有一個(gè)標(biāo)記為8的孩 子。根據(jù)分析樹，先計(jì)算a - b,得-1，然后再乘以3,結(jié)果為-3用算法3.9計(jì)算文法基于LR(0)項(xiàng)目的識別活前綴的DFA。當(dāng)DFA的一個(gè)項(xiàng)目集 中同時(shí)存在：A-B1.B2和B-B.：說明下一