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

2007

一、簡答題（共15分。）

1.通過合并LR⑴文法中的同心狀態(tài)得到的LALR⑴文法可能會(huì)產(chǎn)生

哪些沖突？一定不會(huì)

產(chǎn)生哪些沖突？為什么？（5分）

答：可能會(huì)產(chǎn)生歸約-歸約沖突，一定不會(huì)產(chǎn)生移進(jìn)-歸約沖突。因?yàn)?/p>

在對(duì)LR⑴合并同心集合時(shí)，有可能將原本沒有沖突的同心集的項(xiàng)目集合

并后造成一些歸約項(xiàng)目向前搜索符集合的交集不是空，產(chǎn)生歸約-歸約沖

突。但是由于文法本身已經(jīng)是LR⑴文法，因此可知，在項(xiàng)目集中一定不

存在移進(jìn)-歸約沖突，也就是移進(jìn)項(xiàng)目要求輸入的終結(jié)符和任意歸約項(xiàng)目

的向前搜索符集合的交集都是空集。這樣，在將同心集合并之后，移進(jìn)項(xiàng)

目要求輸入的終結(jié)符和歸約項(xiàng)目的向前搜索符集合的交集也還是空集。

2.如果在A機(jī)器上我們有C語言編譯器CCA,也有它的源碼SA（用C

語言寫成）。如何

利用它通過盡量少的工作來得到B機(jī)器的C語言編譯器CCBo（5分）

答：A機(jī)器上C語言編譯器CCA的結(jié)構(gòu)如下：

CAA

其源碼SA結(jié)構(gòu)如下：

CCA

首先，用C語言編寫一個(gè)從C語言到B機(jī)器語言的編譯器，成為SB,

其結(jié)構(gòu)如下：

CCB

第二步，將這個(gè)編譯器放到CCA中進(jìn)行編譯，得到用A機(jī)器語言編寫

的，將C語言編譯成B機(jī)器代碼的編譯器，其過程和結(jié)構(gòu)如下：

CCBCACAAB

第三步，再將SB放入新得到的這個(gè)編譯器中去編譯，就得到了要求

的編譯器CCB,其過程和結(jié)構(gòu)如下：

CCBCACBBB

3.Pacal語言允許過程嵌套聲明，C語言的過程聲明不能嵌套。在

Pacal程序中，數(shù)據(jù)分

為局部數(shù)據(jù)、非局部數(shù)據(jù)，而C程序中，數(shù)據(jù)分為局部數(shù)據(jù)和全局?jǐn)?shù)

據(jù)。因此，C程序執(zhí)行時(shí)只用到了控制鏈（動(dòng)態(tài)鏈），不需要使用訪問鏈

（靜態(tài)鏈）。試根據(jù)前面的已知說明，為什么Pacal程序執(zhí)行時(shí)需要使用訪

問鏈，而c程序不需要。（5分）

答：由于C語言不允許嵌套的過程聲明，因此所有的非局部名字都可

以靜態(tài)地綁定到所分配的存儲(chǔ)單元，因此，可以不使用訪問鏈。而Pacal

語言允許過程的嵌套，并使用靜態(tài)作用域，確定用于名字的聲明需要根據(jù)

過程的嵌套層次來決定。和C語言不同的是，Pacal語言的非局部名字不

一定就是全局的。運(yùn)行時(shí)訪問非局部名字的時(shí)候，我們首先要確定該非局部

名字被綁定到的活動(dòng)記錄，因此就必須要用到訪問鏈。

二、簡單計(jì)算題（共25分）1.令文法G[E]為

E-*T|E+T|E-TT-F|T某F|T/FF-*(E)|i

(1)證明E+T某F是它的一個(gè)句型，指出這個(gè)句型的所有短語、直接

短語和句柄。(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某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

某i

i某(i+i)的最左推導(dǎo)：最右推導(dǎo)E=>TE=>T=>T某F=>T某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分)已知語言1=挪2亞1'惻屬于(0|a)

某，Wr表示W(wǎng)的逆}，試構(gòu)造相應(yīng)的上下文無關(guān)文法。已知語言

L={InOmlmOn|m>0,n>=0},試構(gòu)造相應(yīng)的上下文無關(guān)文法。已知語言

L=(anbnambm|m>=0,n>0)，試構(gòu)造相應(yīng)的上下文無關(guān)文法答：

⑴文法為：({S},{O,a},P,S),其中P為ST0S0|aSa|a(2)文法為:

({A.S1,{0,1},P.S),其中P為ST1SO|AATOA1|O1

⑵文法為:({A,B,S},{a,b},P,S),其中P為

S-*ABA-*aAb|abB-*aBb|E

3.構(gòu)造一個(gè)NFA,

(1)接受字母表{a,b}上的正規(guī)式(ab|a)某b+描述的集合。(2)將(1)

中的NFA轉(zhuǎn)換為等價(jià)的DFA

(3)將(2)中的DFA轉(zhuǎn)換為最小狀態(tài)DFA(寫出步驟)(9分)答：構(gòu)

造的NFA如下：

a0albb2b

b{2}C{0,2}D{2}C{2}C確定化過程：狀態(tài)集合{0}A{0,l}B{2}C{0,2}D

確定的DFA如下：

bAaBbabCbDa{0,1}B{O,1}B{O,l}Ba

上面的DFA已經(jīng)是最小化的。

三、證明推導(dǎo)題(共30分，每題10分)

2下列文法由開始符號(hào)S產(chǎn)生一個(gè)二進(jìn)制數(shù)，令綜合屬性val給出該

數(shù)的值：

STL.L|LLTLB|BBTO|1

試設(shè)計(jì)求S.val的屬性文法，其中，已知B的綜合屬性c,給出由B

產(chǎn)生的二進(jìn)位的結(jié)果值。答：

產(chǎn)Th式SL1.L2SLLL1B語義規(guī)則

S.val:=L1.val+l_2.val/2L2.lengths,val:=L.vaIL.vaI:=L1.val某

2+B.valL.length:=L1.Iength+1LBL.val:=B.valL.length:=1B0B1

B.val:=0B.val:=l四、程序計(jì)算/設(shè)計(jì)題(共30分，每題10分)

1.設(shè)A為一個(gè)10某20的數(shù)組，即nl=10,n2=20,并設(shè)w=4。

試將賦值語句某:=A[y,z]翻譯成三地址語句序列。答：T1:二y某

20T1:=T1+zT2:=A-84

T3:=4某T1T4:=T2[T3]某:=T4

2如果不存在形如$=>3某丫=>3某丫的推導(dǎo)，則文法符號(hào)某是無

用的，即從開始符號(hào)S,

不能夠推導(dǎo)出含有某的句型，也就是說某不會(huì)出現(xiàn)在任何句子的推導(dǎo)

中。試設(shè)計(jì)一個(gè)算法，從文法中刪除包含無用符號(hào)的產(chǎn)生式。

答：設(shè)計(jì)一個(gè)隊(duì)列，用來存放可以出現(xiàn)在句子推導(dǎo)中的非終結(jié)符號(hào)。

對(duì)隊(duì)列進(jìn)行初始化，將s放在其中。

（1）從隊(duì)列中取出一個(gè)符號(hào)，設(shè)其為A,考察產(chǎn)生式，將形如A-a

的產(chǎn)生式右部符號(hào)

串中出現(xiàn)的非終結(jié)符都放入隊(duì)列中。如果非終結(jié)符已經(jīng)存在隊(duì)列中，

則不重復(fù)加入。（2）重復(fù)上述動(dòng)作，直至隊(duì)列中所有的非終結(jié)符都考察過,

并且沒有新的非終結(jié)符加入

隊(duì)列為止。

此時(shí)得到的隊(duì)列就是那些有用的非終結(jié)符。那些含有不在此隊(duì)列中出

現(xiàn)的非終結(jié)符的產(chǎn)生式就是包含無用符號(hào)的產(chǎn)生式，將其刪除即可。

3考慮下面程序

voidQ（int某）{

inti=l;某=某+2;i=2;某=某+2;}

voidmain(){

inti;intB[3];B[1]=1;B[2]=2;i=l;Q(B[i]);}

試問：若參數(shù)傳遞方式分別采?、艂髦嫡{(diào)用，(2)引用調(diào)用，(3)復(fù)

制-恢復(fù)調(diào)用，(4)傳名調(diào)用時(shí)一，程序執(zhí)行后輸出B[l]和B[2]的值分別是

什么？請(qǐng)簡要寫出計(jì)算過程。

答：

(1)采用傳值調(diào)用時(shí)，將實(shí)在參數(shù)的值傳遞給形式參數(shù)，而后在函數(shù)

調(diào)用過程中，操作

的是形式參數(shù)，形式參數(shù)的值發(fā)生改變，而且這些改變不能重新傳遞

給實(shí)在參數(shù)，所以得到的結(jié)果是=B[2]=2(2)采用應(yīng)用調(diào)用，將實(shí)

在參數(shù)的地址傳遞給形式參數(shù)，此時(shí)對(duì)形式參數(shù)的操作就相當(dāng)

于對(duì)其指向的地址單元進(jìn)行操作，其操作影響了實(shí)在參數(shù)，所以得到的結(jié)

果是B[2]=2

(3)采用復(fù)制-恢復(fù)調(diào)用，首先將實(shí)在參數(shù)的值傳遞給形式參數(shù)，此時(shí),

某=1,y=2,進(jìn)

行函數(shù)調(diào)用后，得到，某=5,y=2,調(diào)用返回時(shí)，將形式參數(shù)的值傳

遞到相應(yīng)的實(shí)在參數(shù)的地址中，即某的值傳遞到B[l]的地址中，所以得到

的結(jié)果是B[l]=5；B[2]=2(4)采用傳名調(diào)用，將B[i]當(dāng)成整個(gè)的一個(gè)整體,

替換函數(shù)調(diào)用中的某，得到：

i=l；

B[i]=B[i]+2;i=2;

B[i]=B[i]+2;

計(jì)算得到，B[1]=3,B[2]=4

(1)采用傳值調(diào)用時(shí)，將實(shí)在參數(shù)的值傳遞給形式參數(shù)，而后在函數(shù)

調(diào)用過程中，操作

的是形式參數(shù)，形式參數(shù)的值發(fā)生改變，而且這些改變不能重新傳遞

給實(shí)在參數(shù)，所以得到的結(jié)果是=B[2]=2(2)采用應(yīng)用調(diào)用，將實(shí)

在參數(shù)的地址傳遞給形式參數(shù)，此時(shí)對(duì)形式參數(shù)的操作就相當(dāng)

于對(duì)其指向的地址單元進(jìn)行操作，其操作影響了實(shí)在參數(shù)，所以得到的結(jié)

果是B[2]=2

(3)采用復(fù)制-恢復(fù)調(diào)用