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

1、試卷（三）：一、 選擇1.下面說法正確的是：AA 一個正規(guī)文法也一定是二型文法B 一個二型文法也一定能有一個等價的正規(guī)文法2.文法GA：Ab AAB BAb Ba是(A)：A 二型文法B 正規(guī)文法3.下面說法正確的是(B)：A lex是一個詞法分析器B yacc是一個語法分析器的生成器4.一個LR（1）文法合并同心集后,如果不是LALR(1)文法必定存在(B)：A 移進-歸約沖突B 歸約-歸約沖突5 PL/0語言編譯程序使用遞歸子程序法進行語法分析，他的文法必須滿足(A)：A LL（1）文法B SLR(1) 文法二、 問答題問答第1題（6分）試對 repeat x:=b until b>

2、a or (b<a and b=d) 的四元式序列給出第四區(qū)段應回填的指令地址，并指出真假出口鏈和鏈頭及回填的次序。 應回填的值 回填的次序 真鏈頭 E.true=(1) x:= b真出口鏈( ) (2) if b>a goto ( ) ( ) 真出口鏈( ) (3) goto ( ) ( ) (4) if b<a goto ( ) ( ) 假鏈頭 E.false=(5) goto ( ) ( ) 假出口鏈( ) (6) if b=d goto ( ) ( ) (7) goto ( ) ( ) (8) . 解：應回填的值 回填的次序 真鏈頭 E.true= 6 (1) x:=

3、 b(2) if b>a goto ( 8 ) ( 6 ) 真出口鏈( 6,2 ) (3) goto ( 4 ) ( 1 ) (4) if b<a goto ( 6 ) ( 2 ) 假鏈頭 E.false= 7 (5) goto ( 1 ) ( 4 ) 假出口鏈( 7,5 ) (6) if b=d goto ( 8 ) ( 5 ) (7) goto ( 1 ) ( 3 ) 問答第2題(10分)某語言的拓廣文法G為：(0) SS(1) S Db|B(2) D d|(3) B Ba|證明G不是LR(0)文法而是SLR(1)文法，請給出SLR(1)分析表。解：拓廣文法G'，增加產

4、生式S'S在項目集I0中：有移進項目D ·d歸約項目D ·和B ·存在移進-歸約和歸約-歸約沖突，所以G不是LR(0)文法。若產生式排序為：(0) S'S(1) S Db(2) S B(3) D d(4) D (5) B Ba(6) B G的LR(0)項目集族及識別活前綴的DFA如下圖：識別G活前綴的DFA由產生式知：Follow(S)=#Follow(D)= bFollow(B)= a ,#在I0中:Follow(D) d= b d= Follow(B) d= a ,# d= Follow(D) Follow(B)= ba ,# = 在I3中:F

5、ollow(S) a=#a= 所以在I0，I3中的移進-歸約和歸約-歸約沖突可以由Follow集解決,所以G是SLR(1)文法,構造的SLR(1)分析表如下表。 SLR(1)分析表問答第3題(5分)給出文法GS的LR(1)項目集規(guī)范族中I0項目集的全體項目。GS為： S S;V|V V VaA|A A b(S)| I0:解：I0:問答第4題(5分)文法GM及其LR分析表如下，請給出對串dada#的分析過程。GM: 1) S VdB2) V e3) V 4) B a5) B Bda 6) B 解：對串dada#的分析過程如下表對輸入串dada#的分析過程步驟 狀態(tài)棧 文法符號棧 剩余輸入符號 動

6、作 123456789 0020240245024602467024678024601 #V#Vd#Vda#VdB#VdBd#VdBda#VdB#S dada#dada#ada#da#da#a# 用V 歸約移進移進用B a歸約移進移進用B Bda歸約用S VdB歸約接受 問答第5題(7分)(1) 給出下列PL/0示意程序中當程序執(zhí)行到D過程調用A過程后（即執(zhí)行A過程體時）的棧式存儲分配布局和用Display顯示表時A過程最新活動記錄的內容。(2) 說明Display表和全局Display的作用。PL/0示意程序為：var x;procedure A;var d;begin (* A *)wri

7、te(x);end (* A *);procedure B;const n=7;var e,g;procedure D;var j,k;begin (* D *)read(j,k);x:=x+j*n;call A;end ;(* D *)begin (* B *)call D;end ;(* B *)begin (* main *)read(x);call B;end. (* main *)解：（1）PL/0示意程序中當程序執(zhí)行到D過程調用A過程后（即執(zhí)行A過程體時）的棧式存儲分配布局和用Display顯示表時棧中過程最新活動記錄的內容如下圖。棧式存儲分配布局和棧中過程最新活動記錄的內容（2）

8、Display表和全局Display的作用是：·Display表的作用是對嵌套過程語言實現(xiàn)對非局部變量的引用而設置的，它依次存放著包圍它的外過程的最新活動記錄的基地址SP值，由于，嵌套層次為i+1過程中的非局部變量可能在i，i-1，0層，所以，對非局部變量的引用是通過它的Display表元素di，di-1，d0而獲得包圍它的外過程的最新活動記錄的基地址SP值，再加上變量在該過程（第i層）的偏移量。如若非局部變量a是在第i層，那么引用a時，首先從當前棧頂過程的Display表中元素di中取出存放的第i層最新活動記錄基地址sp值，然后加上a所在過程（第i層）的偏移量，就得到a的存放地址。

9、·全局Display是存放本過程Display表的起始地址，其作用是把Display地址作為連接數(shù)據(jù)之一，如過程P1調用過程P2時，這時先從P1的全局Display找到P1的Display表起始地址，然后從P1的Display表中自底向上地抄錄I2個單元（I2為P2的層數(shù)）再添上進入P2后新建立的P2的sp值，就構成了P2的Display表。問答第6題(5分)給出問答第5題PL/0示意程序編譯到D過程體時TABLE表的內容。其中TABLE表的格式可為下表。TABLE表的格式：name kind level val adr size 解：問答第5題PL/0示意程序編譯到D過程體時TAB

10、LE表的內容如下表。 TABLE表的內容由于A和B是并列過程，當編譯到B過程時A過程體已經編譯結束，A所定義的標識符不會再被使用，所以由B過程定義的標識符覆蓋。問答第7題（6分）按指定類型給出下列語言的文法。(1) L1= candbm| n0,m>0 用正規(guī)文法。(2) L2= 0na 1nbmcm| n>0，m 0 用二型文法（1）解：描述L1語言的正規(guī)文法如下：ScAAaA|BBdDDbD|（2）解：描述L2語言的二型文法如下：SABA0A1|0a1BbBc|問答第8題（5分）文法GS為：SSdT | TTT<G | GG(S) | a試給出句型(SdG)<a的短

11、語、簡單(直接)短語、句柄和最左素短語。解：句型(SdG)<a的短語：(SdG)<a 、（SdG） 、SdG 、G 、a簡單(直接)短語：G 、a句柄：G最左素短語：SdG問答第9題（5分） 給出與正規(guī)式 R（aba）*（(ba)*|b）b等價的NFA。問答第10題(6分)將下圖的NFA確定化為DFA。解：用子集法確定化如下表I Ia Ib 狀態(tài) X,0,1,30,1,3.2,3,Y.1,3.2,Y.Y. 0,1,30,1,31,3.1,3. 2,3,Y2,3,YY.2,Y.Y. X1234Y 確定化后如下圖問答第11題(5分)將文法GS 改寫為等價的G'S，使G'S不含左遞歸和左公共因子。GS： SA AB|AS BaB|a解：文法GS 改寫為等價的不含左遞歸和左公共因子的G'S為：S AA BAASA|B aBBB|問答第12題(10分) 判斷下面文法是否為LL(1)文法，若是，請構造相應的LL(1)分析表。SaDDSTe|TbMMbHHM|解： 文法的 FIRST集和FOLLOW集非終結符 FIRST集 FOLLOW集 S a. #，b