2023年編譯原理期末試卷及答案

2023-2023學(xué)年第一學(xué)期期末考試答案及評(píng)分標(biāo)準(zhǔn)。A、匯編指令，目的代碼。B、源程序，中間代碼

《編譯原理》（A）卷。C、源程序，記號(hào)流。D、源程序，語(yǔ)法樹(shù)

課程代碼:22801204合用班計(jì)本12級(jí)

4、正規(guī)式Ml和M2等價(jià)的條件是：?！綜】

命題教師:毛靜坂課教毛靜

A、M1和M2的狀態(tài)數(shù)相同，

教研室主任審核（署痂學(xué)主任T魯

名）：名）：B、M1和M2的有向邊相同

題號(hào)w~r五總分。C、M1和M2所表達(dá)的語(yǔ)言集相同。

分值

D、Ml和M2狀態(tài)數(shù)和有向邊都相同

?得分?一、選擇題

5、語(yǔ)法分析常用的方法是：【B

（每小題2分，共20分）

LJ可選項(xiàng)有：（1）自上而下（2）自左向右（3）自底向上（4）自右向左

A、（1）（2）。

B,（1）（3）

1、下述編譯過(guò)程，順序?qū)Φ牡氖牵?/p>

?C、（1）（4）?。

[C]

D、（2）（3）

A、詞法分析，語(yǔ)義分析，語(yǔ)法分析，代碼優(yōu)化，中間代碼生成，目的代碼生成

B、語(yǔ)法分析，詞法分析，語(yǔ)義分析，中間代碼生成，代碼優(yōu)化目的代碼生成6、若b為終結(jié)符，則A->B.bC稱為：【A

，C、詞法分析，語(yǔ)法分析，語(yǔ)義分析，中間代碼生成，代碼優(yōu)化，目的代碼生成。D、A、可移進(jìn)項(xiàng)目。。

語(yǔ)法分析，詞法分析，語(yǔ)義分析，中間代碼生成，目的代碼生成，代碼優(yōu)化B、可歸約項(xiàng)目

。C、可接受項(xiàng)目

2、編譯程序是對(duì)：

D、待約項(xiàng)目

[D1

。A、高級(jí)語(yǔ)言程序的執(zhí)行。B、匯編語(yǔ)言的翻譯7、參數(shù)的傳遞方式重要有：?！綝】

。C、機(jī)器語(yǔ)言的執(zhí)行。D、高級(jí)語(yǔ)言的翻譯可選項(xiàng)：（1）值傳遞（2）地址傳遞（3）復(fù)寫(xiě)恢復(fù)（4）換名調(diào)用

A、（1）（2）。

3、詞法分析的輸入和輸出分別是：[C]

B、⑴(2)(3)二、填空題

。C、(2)(3)(4)。(每空1分，共10分)

D、⑴(2)(3)(4)

1、編譯程序是將高級(jí)語(yǔ)言寫(xiě)的源程序翻擇成目的語(yǔ)言的

程序，這種翻譯過(guò)程稱為編譯。

8、下述關(guān)于順序執(zhí)行的程序的活動(dòng)樹(shù)上各節(jié)點(diǎn)之間的關(guān)系錯(cuò)誤的說(shuō)法是:

2、NFA辨認(rèn)記號(hào)的最大特點(diǎn)是它的不擬定性_____________o

[D]

3、在推導(dǎo)過(guò)程中，若每次直接推導(dǎo)均替換句型中最左邊的非終結(jié)符，則稱為

。A、同一層次的活生存期不交

最左推導(dǎo)。

B、任何時(shí)刻，處在生存期的活動(dòng)構(gòu)成一條從根節(jié)點(diǎn)到某節(jié)點(diǎn)的途徑

4、規(guī)定一個(gè)名字在什么樣的范圍內(nèi)應(yīng)當(dāng)表達(dá)什么意義的規(guī)則.被稱為名字的作用域規(guī)

C、途徑上各節(jié)點(diǎn)的生存期是嵌套的

D、某一時(shí)刻只有一個(gè)活動(dòng)處在生存期

5、活動(dòng)記錄中保存了兩類(lèi)信息，一類(lèi)是控制信息，另一類(lèi)是訪問(wèn)信息

9、關(guān)于寄存器的分派原則，下述說(shuō)法錯(cuò)誤的是：[B]

。A、當(dāng)生成某變量的目的代碼時(shí)，讓變量的值盡也許保存在寄存器中6、代碼生成器以中間代碼和符號(hào)表信息為輸入.生成可以執(zhí)行的

。B、當(dāng)?shù)交緣K的結(jié)束語(yǔ)句時(shí)，將變量的值保存在寄存器中目的代碼。

C、當(dāng)?shù)交緣K的結(jié)束語(yǔ)句時(shí)，將變量的值保存在內(nèi)存中。。7、假如有一個(gè)正常數(shù)或者負(fù)常數(shù)C,使得每次X被增值C,則變量X被稱為歸納變

D、應(yīng)當(dāng)將一個(gè)基本塊內(nèi)的不常使用的的變量占用的寄存器盡早釋放量。。

10、作為目的代碼生成的基本單位的是；[B]

A、三地址嗎。

B、基本塊三、判斷題(對(duì)的的在題號(hào)后括號(hào)內(nèi)填寫(xiě)“V”，錯(cuò)誤的填寫(xiě)“X”)

。C、流圖(每小題2分，共20分)

D、中間代碼

1.編譯程序與具體的機(jī)器有關(guān)，與具體的語(yǔ)言無(wú)關(guān)。

H(X)

2.詞法分析是整個(gè)編譯過(guò)程中唯一和源程序打交道的階段。

(V)

3.一個(gè)文法G被稱為L(zhǎng)L（1）文法，當(dāng)且僅當(dāng)該文法的預(yù)測(cè)分析表中不含多重定義的條答:詞法分析器的作用是：

目。1）濾掉源程序中的無(wú)用成分，如注釋、空格、回車(chē)等（2分）

（V）2）解決與具體平臺(tái)有關(guān)的輸入（如文獻(xiàn)結(jié)束符的不同表達(dá)等）（1分）

4.假如一個(gè)句型中出現(xiàn)了某個(gè)產(chǎn)生式的右部，則此右部一定是句柄。3）辨認(rèn)記號(hào)，并交給語(yǔ)法分析器。根據(jù)模式辨認(rèn)記號(hào)（2分）

（X）4）調(diào)用符號(hào)表管理器或犯錯(cuò)解決器,進(jìn)行相關(guān)解決（2分）

5.繼承屬性的計(jì)算方法是自上而下，包含兄弟，綜合屬性的計(jì)算方式是自下而上,

包含自身。2、（6分）對(duì)于文法G（E）:

（V）EfT|E+T

6.程序是動(dòng)態(tài)的，活動(dòng)室靜態(tài)的。T->F|T*F

（X）Ff（E）|i

7.對(duì)一個(gè)變量的賦值是通過(guò)環(huán)境映射和值映射兩步實(shí)現(xiàn)的。1）.寫(xiě)出句型（T*F+i）的最右推導(dǎo)并畫(huà)出分析樹(shù)（3分）。

（V）2）.寫(xiě)出上述句型的短語(yǔ)，直接短語(yǔ)、句柄（3分）。

8.一個(gè)變量x在其下次引用鏈范圍內(nèi)總是活躍的。

答：（1）句型（T*F+i）的最右推導(dǎo)：---———--------------——---——（2

（V）

分）

9.目的代碼生成是編譯器中唯一與目的機(jī)器特性相關(guān)的階段。

EnT=F=>(E)=(E+T)n(E+F)n(E+i)n(T+i)n(T*F+i)

（V）

分析樹(shù)如右圖所示------

10.代碼優(yōu)化既可以在程序的局部范圍內(nèi)進(jìn)行優(yōu)化，也可以在全局范圍內(nèi)進(jìn)行優(yōu)化。

（1分）。

（V）⑵從分析書(shū)中可以看出：

F.

吾：(T*F+i),--———..............-......———"(1分)

T

T*F+i,------———--"—————"----卜I分)

四,簡(jiǎn)答題

（第1小題7分，第2小題6分，第3小

題7分，共20分）

1、（7H分）簡(jiǎn)述詞法分析器的作用。

TF

,i-------------―--------------(1分)(+,Tl,a,T2)

____—————___一(1(*,T2,a,T3)

(/,b,2,T4)

(一，T3,T4,T5)

(+,T5,c,T6)

(=,x,T6,T7)

3、(7分)寫(xiě)出表達(dá)式x=(a+b*c)*a-b/2+c的后綴式，三元式序列，四元式序

列。

后^^5^：be*a+a*b2/-c+x=———-————---————

-----(1分)

三元式序列：___—___----------..---

--(3分)

(1)(*,b,c)

(2)(+,(l),a)

(3)(*,(2),a)

五、論述題

(4)(/,b,2)（每小題15分，共30分）

(5)(-,(3),(4))

1、（15分）設(shè)￡={0,1}上的正規(guī)集S由倒數(shù)第二個(gè)字符為1的所有字符串組成，請(qǐng)

(6)(十,(5),c)

給出該字集相應(yīng)的正規(guī)式,并構(gòu)造一個(gè)辨認(rèn)該正規(guī)集的DFAo

(7)(二,(6),x)

四元式序歹U：-------------------—--------(3分)

答：（1）構(gòu)造相應(yīng)的正規(guī)式：（0|1）*1（0|1）

(*,b,c,Tl)

-(3分)初始劃分結(jié)果({0,1,2},{3,4})

(2)NFA如下圖所示，其中狀態(tài)0為初始狀態(tài)，狀態(tài)4為終態(tài):Move(0,0)=1Move(1,0)=1Move(2,0)=3

第二次劃分({0,1),{2},{3,4})

Move(0,1)=2Move(l,l)=2所以狀態(tài)0和狀態(tài)1不可區(qū)分

Move⑶0)=1Move(4,0)=3狀態(tài)3和狀態(tài)4可區(qū)分

------(3分)

第三次劃分([0,1},{2},{3},{4})用1狀態(tài)代替{0}1}狀態(tài)得到最小DFA

如下圖所示

----——(3分)

(3)擬定化:

1，o

(0,1,2)(1,2){1,2,3}

{1,2}{1,2}(1,2,3}

{1,2,3}{1,2,4}{1,2,3,4|

{124}{1,2}{123}

(1,2,3,4){124}(1,2,3,4)

(3分)

2、(15分)已知文法G[E]:

1

E-ETE|(E)Ii

-——————(3，分)

T-**

(4)最小化DFA