軟考-編譯原理復(fù)習(xí)習(xí)題一及答案

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)回填的指令地址，并指出真假出口鏈和鏈頭及回填的次序。  &#