編譯原理2022期末考試試卷答案

1、編譯原理 2022 期末考試試卷答案2007一、簡答題（共 15 分。）通過合并LR(1)文法中的同心狀態(tài)得到的LALR(1)文法可能會產(chǎn)生哪些沖突？一定不會產(chǎn)生哪些沖突？為什么？（5 分）答：可能會產(chǎn)生歸約-歸約沖突，一定不會產(chǎn)生移進(jìn)-歸約沖突。因為在對LR(1)合并同心集合時，有可能將原本沒有沖突的同心集的項目集合并后造成一些歸約項目向前搜索符集合的交集不是空，產(chǎn)生歸約-歸約沖突。但是由于文法本身已經(jīng)是LR(1)文法，因此可知，在項目集中一定不存在移進(jìn)-歸約沖突，也就是移進(jìn)項目要求輸入的終結(jié)符和任意歸約項目的向前搜索符集合的交集都是空集。這樣，在將同心集合并之后，移進(jìn)項目要求輸入的終結(jié)符和

2、歸約項目的向前搜索符集合的交集也還是空集。如果在A 機(jī)器上我們有C 語言編譯器CCA，也有它的源碼SA（用C 語言寫成）。如何利用它通過盡量少的工作來得到 B 機(jī)器的 C 語言編譯器 CCB。（5 分） 答：A 機(jī)器上C 語言編譯器CCA 的結(jié)構(gòu)如下：CAA其源碼SA 結(jié)構(gòu)如下： CCA首先，用 C 語言編寫一個從 C 語言到 B 機(jī)器語言的編譯器，成為 SB， 其結(jié)構(gòu)如下：CCB第二步，將這個編譯器放到CCA 中進(jìn)行編譯，得到用A 機(jī)器語言編寫的，將C 語言編譯成B 機(jī)器代碼的編譯器，其過程和結(jié)構(gòu)如下：CCBCACAAB第三步，再將SB 放入新得到的這個編譯器中去編譯，就得到了要求的編譯器C

3、CB，其過程和結(jié)構(gòu)如下：CCBCACBBBPacal 語言允許過程嵌套聲明，C 語言的過程聲明不能嵌套。在Pacal 程序中，數(shù)據(jù)分為局部數(shù)據(jù)、非局部數(shù)據(jù)，而C 程序中，數(shù)據(jù)分為局部數(shù)據(jù)和全局?jǐn)?shù)據(jù)。因此，C 程序執(zhí)行時只用到了控制鏈(動態(tài)鏈)，不需要使用訪問鏈(靜態(tài)鏈)。試根據(jù)前面的已知說明，為什么Pacal 程序執(zhí)行時需要使用訪問鏈，而c 程序不需要。(5 分)答：由于C 語言不允許嵌套的過程聲明，因此所有的非局部名字都可以靜態(tài)地綁定到所分配的存儲單元，因此，可以不使用訪問鏈。而Pacal 語言允許過程的嵌套，并使用靜態(tài)作用域，確定用于名字的聲明需要根據(jù)過程的嵌套層次來決定。和C 語言不同的

4、是，Pacal 語言的非局部名字不一定就是全局的。運行時訪問非局部名字的時候，我們首先要確定該非局部名字被綁定到的活動記錄，因此就必須要用到訪問鏈。二、簡單計算題（共 25 分）1.令文法GE為ET|E+T|E-TTF|T 某F|T/FF(E)|i證明E+T 某F 是它的一個句型，指出這個句型的所有短語、直接短語和句柄。(2)給出i+i 某i、i 某(i+i)的最左推導(dǎo)和最右推導(dǎo)；(10 分)答：(1)E=E+T=E+T 某F，其短語有：T 某F，E+T 某F；直接短語是T 某F，句柄是T 某F(2)i+i 某i 的最左推導(dǎo)：最右推導(dǎo)E=E+TE=E+T=T+T=E+T 某F=F+T=E+T

5、某i=i+T=E+F 某i=i+T某F=E+i 某i=i+F 某F=T+i 某i=i+i 某F=F+i 某i=i+i 某i=i+i 某ii 某(i+i)的最左推導(dǎo)：最右推導(dǎo)E=TE=T=T 某F=T 某 F=F 某F=T 某(E)=i 某F=T 某(E+T)=i 某(E)=T 某(E+F)=i 某(E+T)=T 某(E+i)=i 某(T+T)=T 某(T+i)=i 某(F+T)=T 某(F+i)=i 某(i+T)=T 某(i+i)=i 某(i+F)=F 某(i+i)=i 某(i+i)=i 某(i+i) 2.(1)(2)(3)已知語言寫出相應(yīng)的文法：（6 分）已知語言L=WaWr|W 屬于(0|

6、a) 某，Wr 表示W(wǎng) 的逆，試構(gòu)造相應(yīng)的上下文無關(guān)文法。已知語言L=1n0m1m0n|m0,n=0，試構(gòu)造相應(yīng)的上下文無關(guān)文法。已知語言L=anbnambm|m=0,n0，試構(gòu)造相應(yīng)的上下文無關(guān)文法答：(1)文法為：(S,0,a,P,S)，其中 P 為 S0S0|aSa|a(2)文法為： (A,S,0,1,P,S)，其中 P 為 S1S0|AA0A1|01文法為：(A,B,S,a,b,P,S)，其中P 為SABAaAb|abBaBb|3.構(gòu)造一個NFA，(1)接受字母表a,b上的正規(guī)式(ab|a)某b+描述的集合。(2)將(1) 中的NFA 轉(zhuǎn)換為等價的DFA(3)將(2)中的DFA 轉(zhuǎn)換為

7、最小狀態(tài)DFA（寫出步驟）（9 分）答：構(gòu)造的NFA 如下：a0a1bb2bb2C0,2D2C2C 確定化過程：狀態(tài)集合0A0,1B2C0,2D確 定 的 DFA 如 下 ： bAaBbabCbDa0,1B0,1B0,1Ba上面的DFA 已經(jīng)是最小化的。三、證明推導(dǎo)題（共 30 分，每題 10 分）2 下列文法由開始符號S 產(chǎn)生一個二進(jìn)制數(shù)，令綜合屬性val 給出該數(shù)的值：SL.L|LLLB|BB0|1試設(shè)計求S.val 的屬性文法，其中，已知B 的綜合屬性c，給出由B 產(chǎn)生的二進(jìn)位的結(jié)果值。答：產(chǎn)Th式 SL1.L2SLLL1B 語義規(guī)則S.val:=L1.val+L2.val/2L2.le

8、ngthS.val:=L.valL.val:=L1.val 某2+B.valL.length:=L1.length+1LBL.val:=B.valL.length:=1B0B1B.val:=0B.val:=1 四、程序計算/設(shè)計題（共 30 分，每題 10 分） 1.設(shè)A 為一個 10 某 20 的數(shù)組，即n1=10，n2=20，并設(shè)w=4。試將賦值語句某:=Ay,z翻譯成三地址語句序列。答：T1:=y 某20T1:=T1+zT2:=A-84T3:=4 某T1T4:=T2T3某:=T4如果不存在形如S= 某= 某 的推導(dǎo)，則文法符號某是無用的，即從開始符號S，不能夠推導(dǎo)出含有某的句型，也就是說

9、某不會出現(xiàn)在任何句子的推導(dǎo)中。試設(shè)計一個算法，從文法中刪除包含無用符號的產(chǎn)生式。答：設(shè)計一個隊列，用來存放可以出現(xiàn)在句子推導(dǎo)中的非終結(jié)符號。對隊列進(jìn)行初始化，將S 放在其中。(1)從隊列中取出一個符號，設(shè)其為A，考察產(chǎn)生式，將形如A 的產(chǎn)生式右部符號串中出現(xiàn)的非終結(jié)符都放入隊列中。如果非終結(jié)符已經(jīng)存在隊列中， 則不重復(fù)加入。(2)重復(fù)上述動作，直至隊列中所有的非終結(jié)符都考察過， 并且沒有新的非終結(jié)符加入隊列為止。此時得到的隊列就是那些有用的非終結(jié)符。那些含有不在此隊列中出現(xiàn)的非終結(jié)符的產(chǎn)生式就是包含無用符號的產(chǎn)生式，將其刪除即可?？紤]下面程序voidQ(int 某)inti=1;某=某+2;i

10、=2;某=某+2; voidmain()inti;intB3;B1=1;B2=2;i=1;Q(Bi);試問：若參數(shù)傳遞方式分別采取(1)傳值調(diào)用，(2)引用調(diào)用，(3)復(fù)制-恢復(fù)調(diào)用，(4)傳名調(diào)用時，程序執(zhí)行后輸出B1和B2的值分別是什么？請簡要寫出計算過程。答：(1)采用傳值調(diào)用時，將實在參數(shù)的值傳遞給形式參數(shù)，而后在函數(shù)調(diào)用過程中，操作的是形式參數(shù)，形式參數(shù)的值發(fā)生改變，而且這些改變不能重新傳遞給實在參數(shù)，所以得到的結(jié)果是B1=1；B2=2(2)采用應(yīng)用調(diào)用，將實在參數(shù)的地址傳遞給形式參數(shù)，此時對形式參數(shù)的操作就相當(dāng)于對其指向的地址單元進(jìn)行操作，其操作影響了實在參數(shù)，所以得到的結(jié) 果是

11、B1=5；B2=2(3)采用復(fù)制-恢復(fù)調(diào)用，首先將實在參數(shù)的值傳遞給形式參數(shù)，此時， 某=1，y=2，進(jìn)行函數(shù)調(diào)用后，得到，某=5，y=2，調(diào)用返回時，將形式參數(shù)的值傳遞到相應(yīng)的實在參數(shù)的地址中，即某的值傳遞到B1的地址中，所以得到的結(jié)果是B1=5；B2=2(4)采用傳名調(diào)用，將Bi當(dāng)成整個的一個整體，替換函數(shù)調(diào)用中的某，得到：i=1; Bi=Bi+2;i=2;Bi=Bi+2;計算得到，B1=3，B2=4(1)采用傳值調(diào)用時，將實在參數(shù)的值傳遞給形式參數(shù)，而后在函數(shù)調(diào)用過程中，操作的是形式參數(shù)，形式參數(shù)的值發(fā)生改變，而且這些改變不能重新傳遞給實在參數(shù)，所以得到的結(jié)果是B1=1；B2=2(2)采用應(yīng)用調(diào)用，將實在參數(shù)的地址傳遞給形式參數(shù)，此時對形式參數(shù)的操作就相當(dāng)于對其指向的地址單元進(jìn)行操作，其操作影響了實在參數(shù)，所以得到的結(jié) 果是 B1=5；B2=2(3)采用復(fù)制-恢復(fù)調(diào)用，首先將實