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

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

2、a or (b<a and b=d) 的四元式序列給出第四區(qū)段應(yīng)回填的指令地址，并指出真假出口鏈和鏈頭及回填的次序。 應(yīng)回填的值 回填的次序 真鏈頭 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) . 解：應(yīng)回填的值 回填的次序 真鏈頭 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 ) 問(wèn)答第2題(10分)某語(yǔ)言的拓廣文法G為：(0) SS(1) S Db|B(2) D d|(3) B Ba|證明G不是LR(0)文法而是SLR(1)文法，請(qǐng)給出SLR(1)分析表。解：拓廣文法G'，增加產(chǎn)

4、生式S'S在項(xiàng)目集I0中：有移進(jìn)項(xiàng)目D ·d歸約項(xiàng)目D ·和B ·存在移進(jìn)-歸約和歸約-歸約沖突，所以G不是LR(0)文法。若產(chǎn)生式排序?yàn)椋?0) S'S(1) S Db(2) S B(3) D d(4) D (5) B Ba(6) B G的LR(0)項(xiàng)目集族及識(shí)別活前綴的DFA如下圖：識(shí)別G活前綴的DFA由產(chǎn)生式知：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中的移進(jìn)-歸約和歸約-歸約沖突可以由Follow集解決,所以G是SLR(1)文法,構(gòu)造的SLR(1)分析表如下表。 SLR(1)分析表問(wèn)答第3題(5分)給出文法GS的LR(1)項(xiàng)目集規(guī)范族中I0項(xiàng)目集的全體項(xiàng)目。GS為： S S;V|V V VaA|A A b(S)| I0:解：I0:問(wèn)答第4題(5分)文法GM及其LR分析表如下，請(qǐng)給出對(duì)串dada#的分析過(guò)程。GM: 1) S VdB2) V e3) V 4) B a5) B Bda 6) B 解：對(duì)串dada#的分析過(guò)程如下表對(duì)輸入串dada#的分析過(guò)程步驟 狀態(tài)棧 文法符號(hào)棧 剩余輸入符號(hào) 動(dòng)

6、作 123456789 0020240245024602467024678024601 #V#Vd#Vda#VdB#VdBd#VdBda#VdB#S dada#dada#ada#da#da#a# 用V 歸約移進(jìn)移進(jìn)用B a歸約移進(jìn)移進(jìn)用B Bda歸約用S VdB歸約接受 問(wèn)答第5題(7分)(1) 給出下列PL/0示意程序中當(dāng)程序執(zhí)行到D過(guò)程調(diào)用A過(guò)程后（即執(zhí)行A過(guò)程體時(shí)）的棧式存儲(chǔ)分配布局和用Display顯示表時(shí)A過(guò)程最新活動(dòng)記錄的內(nèi)容。(2) 說(shuō)明Display表和全局Display的作用。PL/0示意程序?yàn)椋簐ar 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示意程序中當(dāng)程序執(zhí)行到D過(guò)程調(diào)用A過(guò)程后（即執(zhí)行A過(guò)程體時(shí)）的棧式存儲(chǔ)分配布局和用Display顯示表時(shí)棧中過(guò)程最新活動(dòng)記錄的內(nèi)容如下圖。棧式存儲(chǔ)分配布局和棧中過(guò)程最新活動(dòng)記錄的內(nèi)容（2）

8、Display表和全局Display的作用是：·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中取出存放的第i層最新活動(dòng)記錄基地址sp值，然后加上a所在過(guò)程（第i層）的偏移量，就得到a的存放地址。

9、·全局Display是存放本過(guò)程Display表的起始地址，其作用是把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題(5分)給出問(wèn)答第5題PL/0示意程序編譯到D過(guò)程體時(shí)TABLE表的內(nèi)容。其中TABLE表的格式可為下表。TABLE表的格式：name kind level val adr size 解：?jiǎn)柎鸬?題PL/0示意程序編譯到D過(guò)程體時(shí)TAB

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

11、語(yǔ)、簡(jiǎn)單(直接)短語(yǔ)、句柄和最左素短語(yǔ)。解：句型(SdG)<a的短語(yǔ)：(SdG)<a 、（SdG） 、SdG 、G 、a簡(jiǎn)單(直接)短語(yǔ)：G 、a句柄：G最左素短語(yǔ)：SdG問(wèn)答第9題（5分） 給出與正規(guī)式 R（aba）*（(ba)*|b）b等價(jià)的NFA。問(wèn)答第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 確定化后如下圖問(wèn)答第11題(5分)將文法GS 改寫(xiě)為等價(jià)的G'S，使G'S不含左遞歸和左公共因子。GS： SA AB|AS BaB|a解：文法GS 改寫(xiě)為等價(jià)的不含左遞歸和左公共因子的G'S為：S AA BAASA|B aBBB|問(wèn)答第12題(10分) 判斷下面文法是否為L(zhǎng)L(1)文法，若是，請(qǐng)構(gòu)造相應(yīng)的LL(1)分析表。SaDDSTe|TbMMbHHM|解： 文法的 FIRST集和FOLLOW集非終結(jié)符 FIRST集 FOLLOW集 S a. #，b