杭電編譯原理試卷一及答案

1、.                                  試卷（一）一、 選擇1.一個正規(guī)語言只能對應(yīng)( B)？A 一個正規(guī)文法；B 一個最小有限狀態(tài)自動機；2.文法GA：A AaB BAb Ba是( B)：A 正規(guī)文法；B 二型文法；3.下面說法正確的是(

2、 A)：A 一個SLR（1）文法一定也是LALR（1）文法；B 一個LR（1）文法一定也是LALR（1）文法4.一個上下文無關(guān)文法消除了左遞歸，提取了左公共因子后是滿足LL（1）文法的( A)：A 必要條件B 充分必要條件二、多項選擇1.PL/0語言的目標程序解釋執(zhí)行時用到的數(shù)據(jù)對象有(AC)：A 目標代碼CODE B 符號表TABLEC 數(shù)據(jù)棧SD 關(guān)鍵字表WORD2.PL/0語言編譯時產(chǎn)生或使用的數(shù)據(jù)對象有(ABD)：A 目標代碼CODEB 符號表TABLEC 數(shù)據(jù)棧SD 關(guān)鍵字表WORD三、問答題問答第1題(5分)將文法GS 改寫為 等價的GS，使GS不含左遞歸和左公共因子。G

3、S： SbSAe | bA AAb | dSbB BSAe | AAd A' A' bA' | 問答第2題(10分) 判斷下面文法是否為LL(1)文法，若是,請構(gòu)造相應(yīng)的LL(1)分析表。SaH HaMd | d MAb |  AaM | e首先計算文法的 FIRST集和FOLLOW集如下表非終結(jié)符 FIRST集 FOLLOW集 S a. # . H a ，d. # . M a ，e ， d ，b A a ，e. b. 由于select（HaMd）select（Hd）=ad =  select（MAb）sele

4、ct（M）=a ，ed ，b =  select（AaM）select（Ae）= a e =  所以該文法是LL(1)文法，LL(1)分析表如下表。 LL(1)分析表  a d b e # S aH.         H aMd d.       M Ab. Ab   A aM.     e.   問答第3題給出與正規(guī)式R（ab）*（a|b*）ba等價的NFA。問答第4題將下圖的NFA確定化為DFA。 用子集法對所給圖的確定化I Ia Ib 狀態(tài) X,1,

5、21,2.1,2,31,2,Y 1,2.1,2.1,2,Y1,2. 1,2,31,2,31,2,31,2,3 X123 確定化后如下圖問答第5題(7分)（1）給出下列PL/0示意程序中當程序執(zhí)行到X過程調(diào)用Z過程后（即執(zhí)行Z過程 體時）的棧式存儲分配布局和用Display顯示表時Z過程最新活動記錄的內(nèi)容。（2）說明Display表和DL（老SP）,RA,TOP及全局Display的作用。 PL/0示意程序為： const a=80;var b,c;procedure X;var d;procedure Z;var e,g;begin (* Z *)c:=b*a；end ；(* Z *

6、)begin (* X *)call Z;end ；(* X *)procedure Y;var f;begin (* Y *)call X;end ；(* y *)begin (* main *)call Y;end. (* main *)解：（1）當程序執(zhí)行到X過程調(diào)用Z過程后（即執(zhí)行Z過程 體時）的棧式存儲分配布局和用Display顯示表時Z過程最新活動記錄的內(nèi)容如下圖。解：（2）Display表和DL（老SP）,RA,TOP及全局Display的作用分別說明如下：·Display表的作用是對嵌套過程語言實現(xiàn)對非局部變量的引用而設(shè)置的，它依次存放著包圍它的外過程的最新活動記錄的

7、基地址SP值，由于，嵌套層 次為i+1過程中的非局部變量可能在i，i-1，0層，所以，對非局部變量的引用是通過它的display表元素di，di- 1，d0而獲得包圍它的外過程的最新活動記錄的基地址SP值，再加上變量在該過程（第i層）的偏移量。如若非局部變量a是在第i層，那么引用a 時，首先從當前棧頂過程的display表中元素di中取出存放的第i層最新活動記錄基地址SP值，然后加上a所在過程（第i層）的偏移量，就得到a 的存放地址。 如Z過程的display表內(nèi)容為：d（2） Z的SP d（1） X的SP d（0） Main的SP ·DL（老SP）： 也稱動態(tài)鏈或控制鏈，

8、指向調(diào)用該過程前正在運行過程的數(shù)據(jù)段基地址，用以過程執(zhí)行結(jié)束釋放數(shù)據(jù)空間時，恢復(fù)調(diào)用該過程前運行棧的狀態(tài)。·RA：返回地址，記錄調(diào)用該過程時目標程序的斷點，即調(diào)用過程指令的下一條指令的地址，用以過程執(zhí)行結(jié)束后返回調(diào)用過程時的下一條指令繼續(xù)執(zhí)行。·TOP：棧頂指針TOP指出了當前棧中最新分配的單元。·全局Display是存放本過程display表的起始地址，其作用是把display地址作為連接數(shù)據(jù)之一，如過程P1調(diào)用過程P2時，這時先從 P1的全局Display找到P1的display表起始地址，然后從P1的display表中自底向上地抄錄I2個單元（I2為P2的層

9、數(shù)）再添上進入 P2后新建立的P2的SP值，就構(gòu)成了P2的display表。問答第6題(5分)給出問答第5題PL/0示意程序編譯到Y(jié)過程體時TABLE表的內(nèi)容。解：PL/0示意程序編譯到Y(jié)過程體時TABLE表的內(nèi)容如下表。解：TABLE表的內(nèi)容name kind level val adr size mainabcXYf procedureconstantvariablevariableprocedureprocedurevariable .00001 .80 0.dxdx+1過程X的入口過程Y的入口dx 5.44 由于Y和X是并列過程，當編譯到Y(jié)過程時X過程體已經(jīng)編譯結(jié)束，X所定義的標識符不

10、會再被使用，所以X定義的標識符d 、Z及Z定義的e、g都被Y過程定義的標識符覆蓋。問答第7題(10分)某語言的拓廣文法G為：(0) ST  (1) T aBd| (2) B Tb| 證明G不是LR(0)文法而是SLR(1)文法，請給出SLR(1)分析表。解：在項目集I0中：有移進項目T ·aBd和歸約項目T · 存在移進-歸約沖突，所以G不是LR(0)文法。 若產(chǎn)生式排序為： (0) S'T(1) T aBd(2) T  (3) B Tb (4) B G'的LR(0)項目集族及識別活前綴的DFA如下

11、圖所示：    識別G活前綴的DFA：由產(chǎn)生式知：Follow(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，中的移進-歸約和歸約-歸約沖突可以由Follow集解決，所以G是SLR(1)文法。構(gòu)造的SLR(1)分析表如下表。SLR(1)分析表name ACTION GOTO a b d # T B 0

12、S2 r2   r2 1   1       acc     2 S2 r2 r4 r2 4 3 3     S5       4   S6         5   r1   r1     6     r3       問答第8題(5分)給出文法GS的LR(1)項目集規(guī)范族中I0項目集的全體項目。 GS為： S BD|D B a

13、D|b D B I0: 解:I0問答第9題(5分)文法GM及其LR分析表如下，請給出對串dbba#的分析過程。GM: 1) M VbA 2) V d 3) V 4) A a 5) A Aba 6) A   ACTION GOTO b d a # M A V 0 r3 S3     1   2 1       acc       2 S4             3 r2    

14、         4 r6   S5 r6   6   5 r4     r4       6 S7     r1       7     S8         8 r5     r5       解：對輸入串dbba#的分析過程步驟 狀態(tài)棧 文法符號棧 剩余輸入符號 動作 123456789 003020240246

15、02467024678024601 #d#V#Vb#VbA#VbAb#VbAba#VbA#M dbba#bba#bba#ba#ba#a# 移進用V d歸約移進用A 歸約移進移進用A Aba 歸約用M VbA 歸約接受 問答第10題（5分）文法GE為： EE+T|T TT*F|F F(E)|i 試給出句型(E+F)*i的短語，簡單(直接)短語,句柄和最左素短語。解：短語有: (E+F)*i ，(E+F) ，E+F ，F(xiàn) ，i 簡單(直接)短語有: F ，i 句柄是: F 最左素短語是: E+F 問答第11題（6分）按指定類型給

16、出下列語言的文法。(1)L1= anbm c| n0,m>0 用正規(guī)文法。(2) L2= a0n1n bdm | n>0，m >0 用二型文法。(1) 解：描述L1語言的正規(guī)文法如下： S aS|AA bA|bB B c(2) 解：描述L2語言的二型文法如下：S AB A aT T 0T1|01 B bD D dD|d 問答第12題（6分）試對 if (ad) then s:=e else s:=f 的四元式序列給出第四區(qū)段應(yīng)回填的指令地址，并指出真假出口鏈和鏈頭及回填的次序。    應(yīng)回填的值 回填的次序   (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) .      解：    應(yīng)回填的值 回填的次序   (1