




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、編譯原理考試試題(所有答案必須寫在答題紙上)(2006.12.25)一、(5×6分)回答下列問題:1什么是S-屬性文法?什么是L-屬性文法?它們之間有什么關(guān)系?2什么是句柄?什么是素短語?3劃分程序的基本塊時(shí),確定基本塊的入口語句的條件是什么?4運(yùn)行時(shí)的DISPLAY表的內(nèi)容是什么?它的作用是什么?5對下列四元式序列生成目標(biāo)代碼: A:=B*CD:=E+FG:=A+DH:=G*2其中,H是基本塊出口的活躍變量, R0和R1是可用寄存器二、(8分)設(shè)S=0,1上的正規(guī)集S由倒數(shù)第二個(gè)字符為1的所有字符串組成,請給出該字集對應(yīng)的正規(guī)式,并構(gòu)造一個(gè)識別該正規(guī)集的DFA。三、(6分)寫一個(gè)文
2、法使其語言為L(G)= anbmambn | m,n1。四、(8分)對于文法G(E): E®T|E+TT®F|T*FF®(E)|i1. 寫出句型(T*F+i)的最右推導(dǎo)并畫出語法樹。2. 寫出上述句型的短語,直接短語、句柄和素短語。五、(12分)設(shè)文法G(S):1 構(gòu)造各非終結(jié)符的FIRSTVT和LASTVT集合;2 構(gòu)造優(yōu)先關(guān)系表和優(yōu)先函數(shù)。六、(9分)設(shè)某語言的do-while語句的語法形式為 S ® do S(1) While E真假S(1)的代碼E的代碼其語義解釋為:針對自下而上的語法分析器,按如下要求構(gòu)造該語句的翻譯模式:(1) 寫出適合語法制
3、導(dǎo)翻譯的產(chǎn)生式;(2) 寫出每個(gè)產(chǎn)生式對應(yīng)的語義動作。七、(8分)將語句 if (A<X) Ù (B>0) then while C>0 do C:=C+D; 翻譯成四元式。八、(10分) 設(shè)有基本塊如下:T1:=S+RT2:= 3T3:= 12/T2T4:=S/RA:=T1-T4T5:=S+RB:=T5T6:=T5*T3B:=T6(1)畫出DAG圖;(2)設(shè)A,B是出基本塊后的活躍變量,請給出優(yōu)化后的四元式序列。九、(9分) 設(shè)已構(gòu)造出文法G(S):(1) S ® BB (2) B ® aB (3) B® b的LR分析表如下ACTIO
4、NGOTO狀態(tài)ab#SB0s3s4121acc2s6s753s3s484r3r35r16s6s797r38r2r29r2假定輸入串為abab,請給出LR分析過程(即按照步驟給出狀態(tài),符號,輸入串的變化過程)。(END)編譯原理考試試題(所有答案必須寫在答題紙上)(2006.12.25)一、 回答下列問題:(30分)1什么是S-屬性文法?什么是L-屬性文法?它們之間有什么關(guān)系?解答:S-屬性文法是只含有綜合屬性的屬性文法。 (2分)L-屬性文法要求對于每個(gè)產(chǎn)生式AàX1X2Xn,其每個(gè)語義規(guī)則中的每個(gè)屬性或者是綜合屬性,或者是Xj的一個(gè)繼承屬性,且該屬性僅依賴于:(1) 產(chǎn)生式Xj的左
5、邊符號X1,X2Xj-1的屬性;(2) A的繼承屬性。 (2分)S-屬性文法是L-屬性文法的特例。 (2分)2什么是句柄?什么是素短語?一個(gè)句型的最左直接短語稱為該句型的句柄。(3分)素短語是這樣的一個(gè)短語,它至少包含一個(gè)終結(jié)符并且不包含更小的素短語。(3分)3劃分程序的基本塊時(shí),確定基本塊的入口語句的條件是什么?解答:(1)程序第一個(gè)語句,或(2)能由條件轉(zhuǎn)移語句或無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句,或(3)緊跟在條件轉(zhuǎn)移語句后面的語句。4(6分)運(yùn)行時(shí)的DISPLAY表的內(nèi)容是什么?它的作用是什么?答:DISPLAY表是嵌套層次顯示表。每當(dāng)進(jìn)入一個(gè)過程后,在建立它的活動記錄區(qū)的同時(shí)建立一張嵌套層次
6、顯示表diaplay.假定現(xiàn)在進(jìn)入的過程層次為i,則它的diaplay表含有i+1個(gè)單元,自頂向下每個(gè)單元依次存放著現(xiàn)行層、直接外層、直至最外層(主程序,0層)等每層過程的最新活動記錄的起始地址。通過DISPLAY表可以訪問其外層過程的變量。5(6分)對下列四元式序列生成目標(biāo)代碼: A:=B*CD:=E+FG:=A+DH:=G*2其中,H是基本塊出口的活躍變量, R0和R1是可用寄存器答:LD R0, BMUL R0, CLD R1, EADD R1, FADD R0, R1MUL R0, 2ST R0, H二、設(shè)S=0,1上的正規(guī)集S由倒數(shù)第二個(gè)字符為1的所有字符串組成,請給出該字集對應(yīng)的正
7、規(guī)式,并構(gòu)造一個(gè)識別該正規(guī)集的DFA。(8分)答:構(gòu)造相應(yīng)的正規(guī)式:(0|1)*1(0|1) (3分)NFA: (2分) 1 110432 e e e e 1 0 0確定化:(3分)I0,1,21,21,2,31,21,21,2,31,2,31,2,41,2,3,41,2,41,21,2,31,2,3,41,2,41,2,3,4 0 143210 0 1 0 0 0 1 1 1三、寫一個(gè)文法使其語言為L(G)= anbmambn | m,n1。(6分)答:文法G(S):S ® aSb | BB ® bBa | ba四、對于文法G(E): (8分)E®T|E+TT&
8、#174;F|T*FF®(E)|iETF(E)E+TFiTT*F1. 寫出句型(T*F+i)的最右推導(dǎo)并畫出語法樹。2. 寫出上述句型的短語,直接短語、句柄和素短語。答:1. (4分)EÞTÞFÞ(E) Þ(E+T) Þ(E+F) Þ(E+i) Þ(T+i) Þ(T*F+i) 2. (4分)短語:(T*F+i), T*F+i, T*F, i直接短語:T*F, i句柄:T*F素短語:T*F, i五、設(shè)文法G(S):(12分)3 構(gòu)造各非終結(jié)符的FIRSTVT和LASTVT集合;4 構(gòu)造優(yōu)先關(guān)系表和優(yōu)先函數(shù)。
9、(12分)答:(6分)FIRSTVT(S)= i,+,),( FIRSTVT(A)= +,),( FIRSTVT(B)= ),( LASTVT(S)= i,+,*,( LASTVT(A)= +,*,( LASTVT(B)= *,( 優(yōu)先關(guān)系表: (3分)i+()*i><<<+>><<>(>>>)<<<*>>>優(yōu)先函數(shù): (3分)i+()*f26616g14661六、設(shè)某語言的do-while語句的語法形式為 (9分) S ® do S(1) While E其語義解釋為:真假S(
10、1)的代碼E的代碼針對自下而上的語法分析器,按如下要求構(gòu)造該語句的翻譯模式:(1) 寫出適合語法制導(dǎo)翻譯的產(chǎn)生式;(2) 寫出每個(gè)產(chǎn)生式對應(yīng)的語義動作。答:(1). 適合語法制導(dǎo)翻譯的文法(3分) G(S): R® do U®R S(1) While S®U E (2). (6分) R® do R.QUAD:=NXQ U®R S(1) While U.QUAD:=R.QUAD; BACKPATCH(S.CHAIN, NXQ) S®U E BACKPATCH(E.TC, U.QUAD); S.CHAIN:=E.FC 答案二:(1) S
11、® do M1 S(1) While M2 E M ® (3分)(2) M ® M.QUAD := NXQ (6分)S ® do M1 S(1) While M2 EBACKPATCH(S(1).CHAIN, M2.QUAD);BACKPATCH(E.TC, M1.QUAD); S.CHAIN:=E. FC七、(8分)將語句if (A<X) Ù (B>0) then while C>0 do C:=C+D翻譯成四元式。(8分)答:100 (j<, A, X, 102)101 (j, -, -, 109)102 (j>
12、;, B, 0, 104)103 (j, -, -, 109)104 (j>, C, 0, 106)105 (j, -, -, 109)106 (+, C, D, T1)107 (:=, T1, -, C)108 (j, -, -, 104)109 (控制結(jié)構(gòu)3分,其他5分)八、(10分) 設(shè)有基本塊如下:T1:=S+RT2:= 3T3:= 12/T2T4:=S/RA:=T1-T4T5:=S+RB:=T5T6:=T5*T3B:=T6(1)畫出DAG圖;(2)設(shè)A,B是出基本塊后的活躍變量,請給出優(yōu)化后的四元式序列。T1,T5, B3T24SR+/*_T3T4AT6,Bn4n5n1n2n3n6n8n7答:(1) DAG如右圖:(6分)(2) 四元式序列:(4分)T1:=S+RT4:=S/RA:=T1-T4B:=T1*4九、(9分) 設(shè)已構(gòu)造出文法G(S):(1) S ® BB(2) B ® aB(3) B® b的LR分析表如下ACTIONGOTO狀態(tài)ab#
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年抗輻射光學(xué)石英玻璃合作協(xié)議書
- 2025年山梨酸及山梨酸鉀合作協(xié)議書
- 2025年冷芯盒樹脂項(xiàng)目建議書
- 家庭寵物寄養(yǎng)與托管服務(wù)協(xié)議
- 履行合同能力保證書
- 房地產(chǎn)中秋晚會活動策劃方案
- 電子行業(yè)智能制造與工業(yè)自動化方案
- 公司之間戰(zhàn)略合作協(xié)議書
- 營銷推廣戰(zhàn)略合作協(xié)議修訂案
- 施工現(xiàn)場的應(yīng)急響應(yīng)計(jì)劃試題及答案
- 天津市各級醫(yī)療機(jī)構(gòu)收費(fèi)標(biāo)準(zhǔn)目錄doc-天津市各級醫(yī)療機(jī)構(gòu)
- 人民幣教具正反面完美打印版
- 國際投標(biāo)條款
- 6.1 根結(jié)、標(biāo)本的上下關(guān)系
- GB/T 3301-1999日用陶瓷的容積、口徑誤差、高度誤差、重量誤差、缺陷尺寸的測定方法
- GB/T 13928-2002微型往復(fù)活塞空氣壓縮機(jī)
- GB/T 12224-2005鋼制閥門一般要求
- 偷影子的人-大學(xué)語文PPT
- GB/T 11022-2020高壓交流開關(guān)設(shè)備和控制設(shè)備標(biāo)準(zhǔn)的共用技術(shù)要求
- GB 4789.3-2016食品安全國家標(biāo)準(zhǔn)食品微生物學(xué)檢驗(yàn)大腸菌群計(jì)數(shù)
- 裝飾窗簾安裝內(nèi)部驗(yàn)收單
評論
0/150
提交評論