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

2023-2023學年第一學期期末考試答案及評分標準。A、匯編指令，目的代碼。B、源程序，中間代碼

《編譯原理》（A）卷。C、源程序，記號流。D、源程序，語法樹

課程代碼:22801204合用班計本12級

4、正規(guī)式Ml和M2等價的條件是：。【C】

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

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

教研室主任審核（署痂學主任T魯

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

題號w~r五總分。C、M1和M2所表達的語言集相同。

分值

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

?得分?一、選擇題

5、語法分析常用的方法是：【B

（每小題2分，共20分）

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

A、（1）（2）。

B,（1）（3）

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

?C、（1）（4）?。

[C]

D、（2）（3）

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

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

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

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

。C、可接受項目

2、編譯程序是對：

D、待約項目

[D1

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

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

A、（1）（2）。

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

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

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

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

1、編譯程序是將高級語言寫的源程序翻擇成目的語言的

程序，這種翻譯過程稱為編譯。

8、下述關于順序執(zhí)行的程序的活動樹上各節(jié)點之間的關系錯誤的說法是:

2、NFA辨認記號的最大特點是它的不擬定性_____________o

[D]

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

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

最左推導。

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

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

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

D、某一時刻只有一個活動處在生存期

5、活動記錄中保存了兩類信息，一類是控制信息，另一類是訪問信息

9、關于寄存器的分派原則，下述說法錯誤的是：[B]

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

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

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

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

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

A、三地址嗎。

B、基本塊三、判斷題(對的的在題號后括號內(nèi)填寫“V”，錯誤的填寫“X”)

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

D、中間代碼

1.編譯程序與具體的機器有關，與具體的語言無關。

H(X)

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

(V)

3.一個文法G被稱為LL（1）文法，當且僅當該文法的預測分析表中不含多重定義的條答:詞法分析器的作用是：

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

（V）2）解決與具體平臺有關的輸入（如文獻結(jié)束符的不同表達等）（1分）

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

（X）4）調(diào)用符號表管理器或犯錯解決器,進行相關解決（2分）

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

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

（V）EfT|E+T

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

（X）Ff（E）|i

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

（V）2）.寫出上述句型的短語，直接短語、句柄（3分）。

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

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

（V）

分）

9.目的代碼生成是編譯器中唯一與目的機器特性相關的階段。

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

（V）

分析樹如右圖所示------

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

（1分）。

（V）⑵從分析書中可以看出：

F.

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

T

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

四,簡答題

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

題7分，共20分）

1、（7H分）簡述詞法分析器的作用。

TF

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

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

(/,b,2,T4)

(一，T3,T4,T5)

(+,T5,c,T6)

(=,x,T6,T7)

3、(7分)寫出表達式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分）設￡={0,1}上的正規(guī)集S由倒數(shù)第二個字符為1的所有字符串組成，請

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

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

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

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

答：（1）構(gòu)造相應的正規(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