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

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

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

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

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

5、句型中的最左2.2一個(gè)句型中的最左稱(chēng)為該句型的句柄。A.短語(yǔ)直接短語(yǔ)A.短語(yǔ)直接短語(yǔ)非終結(jié)符號(hào)D.終結(jié)符號(hào)答案：B解釋?zhuān)焊鶕?jù)定義。2.3已知文法G口A1AA1I0I0與G2.3已知文法G口A1AA1I0I0與G等價(jià)的正規(guī)式是A.0(0|1)*1*|0*10(1|10)*1D.1(10|01)*0答案：C解釋?zhuān)河猛茖?dǎo)和構(gòu)造思路處理。與逆波蘭式ab+c*d+對(duì)應(yīng)的中綴表達(dá)式是。A.a+b+c*dB.(a+b)*c+dC.(a+b)*(c+d)D.a+b*c+d答案：B解釋?zhuān)簭谋磉_(dá)式的求值過(guò)程考慮。逆波蘭式中運(yùn)算符的書(shū)寫(xiě)順序就是處理順序，中綴表達(dá)式要根據(jù)運(yùn)算符的優(yōu)先級(jí)和結(jié)合性進(jìn)行處理。在表達(dá)式x:=

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

7、：傳值方式下,實(shí)參與形參各自有獨(dú)立的存儲(chǔ)單元,調(diào)用時(shí)將實(shí)參的值傳遞給形參,對(duì)形參進(jìn)行的修改與實(shí)參無(wú)關(guān)。引用調(diào)用方式下,是將實(shí)參的地址傳遞給形參,對(duì)形參所作的修改最后會(huì)返回給實(shí)參。請(qǐng)計(jì)算下面文法G(E)中各非終結(jié)符的FIRST和FOLLOW集合。請(qǐng)說(shuō)明該文法為什么不是LL(1)文法。G(E)：E-E*T|TT-T-F|FF-(E)|id答案：FIRST(F)=FIRST(T)=FIRST(E)=(,idFOLLOW(E)=#,*,)FOLLOW(T)=-,*,#,)FOLLOW(F)=-,*,#,)解釋?zhuān)和ㄋ椎刂v，a的FIRST集合就是從a開(kāi)始可以導(dǎo)出的序列中的開(kāi)頭終結(jié)符。而A的FOLLOW集合

8、，就是從開(kāi)始符號(hào)可以導(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)生式A-a|B,滿(mǎn)足下面條件：1.對(duì)任何終結(jié)符a,a和B不能同時(shí)推導(dǎo)出以a開(kāi)始的串；2.a和B最多有一個(gè)可以推導(dǎo)出e；3.若B=*e,則a不能推導(dǎo)出以在FOLLOW(A)中的終結(jié)符開(kāi)始的任何串。下圖所示的分析樹(shù)用到了某個(gè)上下文無(wú)關(guān)文法的所有產(chǎn)生式。(a)給出該文法的所有非終結(jié)符號(hào)集合N和終結(jié)符號(hào)集合T。(b)給出該文法的產(chǎn)生式集合。E答案：N

9、=S,A,BT=a,b,c,dS-aAcB|BdA-AaB|cB-bScA|b|e解釋?zhuān)簩?duì)CFGG的句型，分析樹(shù)被定義為具有下述性質(zhì)的一棵樹(shù)。根由開(kāi)始符號(hào)所標(biāo)記；(2)每個(gè)葉子由一個(gè)終結(jié)符、非終結(jié)符、或e標(biāo)記；(3)每個(gè)內(nèi)部結(jié)點(diǎn)由一個(gè)非終結(jié)符標(biāo)記；(4)若A是某內(nèi)部節(jié)點(diǎn)的標(biāo)記，且XI,X2,.，Xn該節(jié)點(diǎn)從左到右所有孩子的標(biāo)記，則A-X1X2Xn是一個(gè)產(chǎn)生式。若A-e,則標(biāo)記為A的結(jié)點(diǎn)可以?xún)H有一個(gè)標(biāo)記為&的孩子。分析樹(shù)與語(yǔ)言和文法的關(guān)系：每一直接推導(dǎo)（每個(gè)產(chǎn)生式），對(duì)應(yīng)一棵僅有父子關(guān)系的子樹(shù)，即產(chǎn)生式左部非終結(jié)符“長(zhǎng)出”右部的孩子；分析樹(shù)的葉子，從左到右構(gòu)成G的一個(gè)句型。若葉子僅由終結(jié)符標(biāo)記，

10、則構(gòu)成一個(gè)句子。3.4某程序執(zhí)行到某一時(shí)刻時(shí)控制棧中的內(nèi)容如下所示（其中M是主程序，P、Q、R、S均是過(guò)程），給出所有在生存期的活動(dòng)的調(diào)用關(guān)系（提示：若A調(diào)用B,則記為A-B）。S的活動(dòng)記錄S的活動(dòng)記錄S的活動(dòng)記錄S的活動(dòng)記錄Q的活動(dòng)記錄R的活動(dòng)記錄P的活動(dòng)記錄M的活動(dòng)記錄控制鏈.答案：M一P一R一Q一S-S解釋?zhuān)喉樞驁?zhí)行程序的執(zhí)行在時(shí)間上是順序的和排他的。即在程序執(zhí)行的任一瞬間，有且僅有一個(gè)活動(dòng)正在活動(dòng)?？刂茥Ｓ糜诒４嫠性谏嫫诘幕顒?dòng)（一條后進(jìn)先出的路徑）。棧中的每個(gè)元素稱(chēng)為一個(gè)活動(dòng)記錄（activationrecord），為活動(dòng)提供的活動(dòng)場(chǎng)所。顯然，根據(jù)控制棧中的內(nèi)容，應(yīng)該是M調(diào)用了P,

11、P隨后又調(diào)用了R,R又調(diào)用了Q,Q調(diào)用了S,S又調(diào)用了S（遞歸調(diào)用）。四、綜合題（30分）（15分）設(shè)有正規(guī)式r=1（0|l）*1,試給出:（a）（5分）識(shí)別該正規(guī)集的NFA；（b）（10分）識(shí)別該正規(guī)集的DFA（要有計(jì)算過(guò)程）；答案：（a）NFA如下圖所示00(b)s0=(b)s0=A_閉包(s0)=s0_閉包(smove(s0,1)_閉包(smove(s1,0)_閉包(smove(s1,1)初態(tài)B記為siB=s1B,C記為s2,終態(tài)_閉包(smove(s2,0)=B=si_閉包(smove(s2,1)=B,C=s2DFA如下圖所示解釋?zhuān)河盟惴?.2Thompson算法從正規(guī)式構(gòu)造出與其對(duì)應(yīng)

12、的NFA；用子集法(算法2.3)將NFA轉(zhuǎn)換為DFA。其中需要用算法2.4計(jì)算狀態(tài)集T的-閉包(T)。(15分)設(shè)有上下文無(wú)關(guān)無(wú)法G及其語(yǔ)法制導(dǎo)翻譯如下(注：G中終結(jié)符id僅由單個(gè)英文字母組成，如a,b等)：E-E1*TE.place:newtemp;emit(*,E1.place,T.place,E.place;|TE.place=T.place;T-T1-FT.place:newtemp;emit(一,T1.place,F.place,T.place;|FT.place=F.place;F-(E)F.place二E.place;|idF.place=;(4分)畫(huà)出句子a-b*

13、c的分析樹(shù)；(3分)寫(xiě)出當(dāng)a=1、b=2、c=3時(shí)的計(jì)算結(jié)果；(*表示算術(shù)乘、-表示算術(shù)減)(c)(8分)將文法G簡(jiǎn)化為：E-E*T|T,T-T-F|F,F-id,給出其識(shí)別活前綴的DFA,該DFA的項(xiàng)目集中有沖突嗎？若有，是哪種類(lèi)型的沖突。答案：-3(c)拓廣文法，增加產(chǎn)生式：S-E,識(shí)別活前綴的DFA如下圖所示存在移進(jìn)歸約沖突解釋?zhuān)?a)從文法推導(dǎo)(最左推導(dǎo))出句子a-b*c的過(guò)程為：E=E*T=T*T=T-F*T=F-F*T=a-F*T=ab*T=a-b*F=a-b*c分析樹(shù)是對(duì)推導(dǎo)過(guò)程的直觀描述。分析樹(shù)被定義為具有下述性質(zhì)的一棵樹(shù)：(1)根由開(kāi)始符號(hào)所標(biāo)記；(2)每個(gè)葉子由一個(gè)終結(jié)符、非終結(jié)符、或標(biāo)記；(3)每個(gè)內(nèi)部結(jié)點(diǎn)由一個(gè)非終結(jié)符標(biāo)記；(4)若A是某內(nèi)部節(jié)點(diǎn)的標(biāo)記，且XI,X2,.,Xn該節(jié)點(diǎn)從左到右所有孩子的標(biāo)記，則A一X1X2Xn是一個(gè)產(chǎn)生式。若A-e,則標(biāo)記為A的結(jié)點(diǎn)可以?xún)H有一個(gè)標(biāo)記為的孩子。(b)根據(jù)分析樹(shù)，先計(jì)算a-b,得-1,然后再乘以3,結(jié)果為-3(c)用算法3.9計(jì)算文法基于1氏0)項(xiàng)目的識(shí)別活前綴的DFA。當(dāng)DFA的一個(gè)項(xiàng)目集中同時(shí)存在：A-B1.B2和B-B.：說(shuō)明下一步既可以移進(jìn)