軟考-編譯原理復(fù)習(xí)習(xí)題一及答案_第1頁(yè)
軟考-編譯原理復(fù)習(xí)習(xí)題一及答案_第2頁(yè)
軟考-編譯原理復(fù)習(xí)習(xí)題一及答案_第3頁(yè)
軟考-編譯原理復(fù)習(xí)習(xí)題一及答案_第4頁(yè)
軟考-編譯原理復(fù)習(xí)習(xí)題一及答案_第5頁(yè)
已閱讀5頁(yè),還剩6頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、編譯原理窗體頂端一、 選擇1.一個(gè)正規(guī)語(yǔ)言只能對(duì)應(yīng)()? A 一個(gè)正規(guī)文法; B 一個(gè)最小有限狀態(tài)自動(dòng)機(jī); 2.文法GA:A AaB BAb Ba是(): A 正規(guī)文法 B 二型文法3.下面說(shuō)法正確的是(): A 一個(gè)SLR(1)文法一定也是LALR(1)文法 B 一個(gè)LR(1)文法一定也是LALR(1)文法4.一個(gè)上下文無(wú)關(guān)文法消除了左遞歸,提取了左公共因子后是滿足LL(1)文法的(): A 必要條件 B 充分必要條件窗體底端窗體頂端二、多項(xiàng)選擇1.PL/0語(yǔ)言的目標(biāo)程序解釋執(zhí)行時(shí)用到的數(shù)據(jù)對(duì)象有():A 目標(biāo)代碼CODE B 符號(hào)表TABLE C 數(shù)據(jù)棧S D 關(guān)鍵字表WORD2.PL/0

2、語(yǔ)言編譯時(shí)產(chǎn)生或使用的數(shù)據(jù)對(duì)象有():A 目標(biāo)代碼CODE B 符號(hào)表TABLE C 數(shù)據(jù)棧S D 關(guān)鍵字表WORD窗體底端窗體頂端三、問(wèn)答題問(wèn)答第1題(5分)將文法GS 改寫為等價(jià)的GS,使GS不含左遞歸和左公共因子。GS: SbSAe | bA AAb | d 問(wèn)答第2題(10分) 判斷下面文法是否為L(zhǎng)L(1)文法,若是,請(qǐng)構(gòu)造相應(yīng)的LL(1)分析表。SaH HaMd | d MAb | AaM | e 問(wèn)答第3題給出與正規(guī)式R(ab)*(a|b*)ba等價(jià)的NFA。問(wèn)答第4題將下圖的NFA確定化為DFA。問(wèn)答第5題(7分)(1)給出下列PL/0示意程序中當(dāng)程序執(zhí)行到X過(guò)程調(diào)用Z過(guò)程后(即

3、執(zhí)行Z過(guò)程 體時(shí))的棧式存儲(chǔ)分配布局和用Display顯示表時(shí)Z過(guò)程最新活動(dòng)記錄的內(nèi)容。(2)說(shuō)明Display表和DL(老SP),RA,TOP及全局Display的作用。 PL/0示意程序?yàn)椋?const a=80;var b,c;procedure X;var d;procedure Z;var e,g;begin (* Z *)c:=b*a;end ;(* Z *)begin (* X *)call Z;end ;(* X *)procedure Y;var f;begin (* Y *)call X;end ;(* y *)begin (* main *)call Y;end. (*

4、main *)問(wèn)答第6題(5分)給出問(wèn)答第5題PL/0示意程序編譯到Y(jié)過(guò)程體時(shí)TABLE表的內(nèi)容。問(wèn)答第7題(10分)某語(yǔ)言的拓廣文法G為:(0) ST (1) T aBd| (2) B Tb| 證明G不是LR(0)文法而是SLR(1)文法,請(qǐng)給出SLR(1)分析表。 問(wèn)答第8題(5分)給出文法GS的LR(1)項(xiàng)目集規(guī)范族中I0項(xiàng)目集的全體項(xiàng)目。 GS為: S BD|D B aD|b D B I0:問(wèn)答第9題(5分)文法GM及其LR分析表如下,請(qǐng)給出對(duì)串dbba#的分析過(guò)程。GM: 1) M VbA 2) V d 3) V 4) A a 5) A Aba 6) A nameACTIONGOTO

5、bda#MAV0r3 S3  1 21   acc   2S4      3r2      4r6 S5r6 6 5r4  r4   6S7  r1   7  S8    8r5  

6、;r5   問(wèn)答第10題(5分)文法GE為: EE+T|T TT*F|F F(E)|i 試給出句型(E+F)*i的短語(yǔ),簡(jiǎn)單(直接)短語(yǔ),句柄和最左素短語(yǔ)。 問(wèn)答第11題(6分)按指定類型給出下列語(yǔ)言的文法。(1)L1= anbm c| n0,m>0 用正規(guī)文法。(2) L2= a0n1n bdm | n>0,m >0 用二型文法。 問(wèn)答第12題(6分)試對(duì) if (ad) then s:=e else s:=f 的四元式序列給出第四區(qū)段應(yīng)回填的指令地址,并指出真假出口鏈和鏈頭及回填的次序。   應(yīng)回填的值回填的次序 

7、;(1)if a<b goto( )( )真鏈頭 E.true= (2)goto( )( )真出口鏈( )(3)if a>d goto( )( ) (4)goto( )( )假鏈頭 E.false= (5)s:=e  假出口鏈( )(6)goto( )( ) (7)s:=f   (8).   窗體底端參考答案一、 選擇題答案 選擇第1題B選擇第2題B選擇第3題A選擇第4題A 二、多項(xiàng)選擇題答案 多項(xiàng)選擇第1題AC多項(xiàng)選擇第2題ABD 二、問(wèn)答題答案問(wèn)答第1題文法GS 改寫為等價(jià)的不含

8、左遞歸和左公共因子的G'S為:SbB BSAe | AAd A' A' bA' | 問(wèn)答第2題首先計(jì)算文法的 FIRST集和FOLLOW集如下表。文法的 FIRST集和FOLLOW集 非終結(jié)符FIRST集FOLLOW集Sa.# .Ha ,d.# .Ma ,e ,d ,bAa ,e.b.由于select(HaMd)select(Hd)=ad = select(MAb)select(M)=a ,ed ,b = select(AaM)select(Ae)= a e = 所以該文法是LL(1)文法,LL(1)分析表如下表。 LL(1)分析表 adbe#SaH.

9、    HaMdd.   MAb.Ab AaM.  e. 問(wèn)答第3題與正規(guī)式R(ab)*(a|b*)ba 等價(jià)的NFA如下圖問(wèn)答第4題用子集法確定化如下表用子集法對(duì)所給圖的確定化IIaIb狀態(tài)X,1,21,2.1,2,31,2,Y1,2.1,2.1,2,Y1,2.1,2,31,2,31,2,31,2,3X123確定化后如下圖問(wèn)答第5題解:(1)當(dāng)程序執(zhí)行到X過(guò)程調(diào)用Z過(guò)程后(即執(zhí)行Z過(guò)程 體時(shí))的棧式存儲(chǔ)分配布局和用Display顯示表時(shí)Z過(guò)程最新活動(dòng)記錄的內(nèi)容如下圖。當(dāng)程序執(zhí)行到Z過(guò)

10、程時(shí)棧式存儲(chǔ)分配布局和棧中過(guò)程最新活動(dòng)記錄的內(nèi)容解:(2)Display表和DL(老SP),RA,TOP及全局Display的作用分別說(shuō)明如下:·Display表的作用是對(duì)嵌套過(guò)程語(yǔ)言實(shí)現(xiàn)對(duì)非局部變量的引用而設(shè)置的,它依次存放著包圍它的外過(guò)程的最新活動(dòng)記錄的基地址SP值,由于,嵌套層次為i+1過(guò)程中的非局部變量可能在i,i-1,0層,所以,對(duì)非局部變量的引用是通過(guò)它的display表元素di,di-1,d0而獲得包圍它的外過(guò)程的最新活動(dòng)記錄的基地址SP值,再加上變量在該過(guò)程(第i層)的偏移量。如若非局部變量a是在第i層,那么引用a時(shí),首先從當(dāng)前棧頂過(guò)程的display表中元素di中取

11、出存放的第i層最新活動(dòng)記錄基地址SP值,然后加上a所在過(guò)程(第i層)的偏移量,就得到a的存放地址。 如Z過(guò)程的display表內(nèi)容為:d(2)Z的SPd(1)X的SPd(0)Main的SP·DL(老SP): 也稱動(dòng)態(tài)鏈或控制鏈,指向調(diào)用該過(guò)程前正在運(yùn)行過(guò)程的數(shù)據(jù)段基地址,用以過(guò)程執(zhí)行結(jié)束釋放數(shù)據(jù)空間時(shí),恢復(fù)調(diào)用該過(guò)程前運(yùn)行棧的狀態(tài)。·RA:返回地址,記錄調(diào)用該過(guò)程時(shí)目標(biāo)程序的斷點(diǎn),即調(diào)用過(guò)程指令的下一條指令的地址,用以過(guò)程執(zhí)行結(jié)束后返回調(diào)用過(guò)程時(shí)的下一條指令繼續(xù)執(zhí)行。·TOP:棧頂指針TOP指出了當(dāng)前棧中最新分配的單元。·全局Display是存放本過(guò)程d

12、isplay表的起始地址,其作用是把display地址作為連接數(shù)據(jù)之一,如過(guò)程P1調(diào)用過(guò)程P2時(shí),這時(shí)先從P1的全局Display找到P1的display表起始地址,然后從P1的display表中自底向上地抄錄I2個(gè)單元(I2為P2的層數(shù))再添上進(jìn)入P2后新建立的P2的SP值,就構(gòu)成了P2的display表。問(wèn)答第6題解:PL/0示意程序編譯到Y(jié)過(guò)程體時(shí)TABLE表的內(nèi)容如下表。TABLE表的內(nèi)容namekindlevelvaladrsizemainabcXYfprocedureconstantvariablevariableprocedureprocedurevariable.00001.8

13、00.dxdx+1過(guò)程X的入口過(guò)程Y的入口dx5.44由于Y和X是并列過(guò)程,當(dāng)編譯到Y(jié)過(guò)程時(shí)X過(guò)程體已經(jīng)編譯結(jié)束,X所定義的標(biāo)識(shí)符不會(huì)再被使用,所以X定義的標(biāo)識(shí)符d 、Z及Z定義的e、g都被Y過(guò)程定義的標(biāo)識(shí)符覆蓋。問(wèn)答第7題拓廣文法G',增加產(chǎn)生式S'T 在項(xiàng)目集I0中:有移進(jìn)項(xiàng)目T ·aBd和歸約項(xiàng)目T · 存在移進(jìn)-歸約沖突,所以G不是LR(0)文法。 若產(chǎn)生式排序?yàn)椋?(0) S'T(1) T aBd(2) T (3) B Tb (4) B G'的LR(0)項(xiàng)目集族及識(shí)別活前綴的DFA如下圖所示: 識(shí)別G活前綴的DFA由產(chǎn)生式知:Fol

14、low(T)=#,b Follow(B)= d在I0中: Follow(T) a=# ,b a=在I2中:Follow(B) a= d a=Follow(T) a=# ,b a=Follow(B) Follow(T) = d# ,b=所以在I0,I2,中的移進(jìn)-歸約和歸約-歸約沖突可以由Follow集解決,所以G是SLR(1)文法。 構(gòu)造的SLR(1)分析表如下表。SLR(1)分析表nameACTIONGOTOabd#TB0S2r2 r21 1   acc  2S2r2r4r2433  S5 &

15、#160; 4 S6    5 r1 r1  6  r3   問(wèn)答第8題解:I0問(wèn)答第9題對(duì)串dbba#的分析過(guò)程如下表對(duì)輸入串dbba#的分析過(guò)程步驟狀態(tài)棧文法符號(hào)棧剩余輸入符號(hào)動(dòng)作12345678900302024024602467024678024601#d#V#Vb#VbA#VbAb#VbAba#VbA#Mdbba#bba#bba#ba#ba#a#移進(jìn)用V d歸約移進(jìn)用A 歸約移進(jìn)移進(jìn)用A Aba 歸約用M VbA 歸約接受問(wèn)答第10題解:短語(yǔ)有: (E+F)*i ,(E+F) ,E+F ,F(xiàn) ,i 簡(jiǎn)單(直接)短語(yǔ)有: F ,i 句柄是: F 最左素短語(yǔ)是: E+F 問(wèn)答第11題(1) 解:描述L1語(yǔ)言的正規(guī)文法如下: S aS|AA bA|bB B c(2) 解:描述L2語(yǔ)言的二型文法如下:S AB A aT T 0T1|01 B bD D dD|d 問(wèn)答第12題(6分)試對(duì) if (ad) then s:=e else s:=f 的四元式序列給出第四區(qū)段應(yīng)回填的指令地址,并指出真假出口鏈和鏈頭及回填的次序。  &#

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論