2023年編譯原理期末測驗選擇題匯總

千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦編譯原理期末測驗選擇題匯總編譯原理期末測驗挑選題匯總

————————————————————————————————：————————————————————————————————日期：

一、單項挑選題

1、將編譯程序分成若干個“遍”是為了(B)

A．提高程序的執(zhí)行效率

B.使程序的結(jié)構(gòu)越發(fā)清楚

C．利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率

D．利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率

2、不行能是目標(biāo)代碼的是(D)

A．匯編指令代碼B．可重定位指令代碼

C．肯定指令代碼D．中間代碼

3、詞法分析器的輸入是(B)

A．單詞符號串B．源程序

C．語法單位D．目標(biāo)程序

4、編譯程序中的語法分析器接受以c為單位的輸入，并產(chǎn)生有關(guān)信息供以后各階段使用。

可選項有：a、表達(dá)式b、產(chǎn)生式c、單詞d、語句

5、高級語言編譯程序常用的語法分析辦法中，遞歸下降分析法屬于b分析辦法。

可選項有：a、自左至右b、自頂向下c、自底向上d、自右向左

6、已知文法G[E]：E→TE’E’→+TE’∣εT→FT’

T’→*FT’∣εF→（E）∣id

求：FOLLOW（F）=（1）d，F(xiàn)IRST（T’）=（2）b

可選項有：a、｛*，+｝b、｛*，ε｝c、｛+,#，）｝

d、｛*，+，#，）｝

e、｛#，）｝

f、｛*，+，#，id｝

7、中間代碼生成時所遵循的是(C)

A．語規(guī)矩則B．詞規(guī)矩則

C．語義規(guī)章D．等價變換規(guī)章

8、編譯程序是對(D)

A．匯編程序的翻譯B．高級語言程序的解釋執(zhí)行

C．機(jī)器語言的執(zhí)行D．高級語言的翻譯

9、詞法分析應(yīng)遵循(C)

A．語義規(guī)章B．語規(guī)矩則

C．構(gòu)詞規(guī)章D．等價變換規(guī)章

10、詞法分析器的輸出結(jié)果是(C)

A．單詞的種別編碼B．單詞在符號表中的位置

C．單詞的種別編碼和屬性值D．單詞屬性值

11、正規(guī)式M1和M2等價是指(C)

A．M1和M2的狀態(tài)數(shù)相等B．M1和M2的有向弧條數(shù)相等

C．M1和M2所識別的語言集相等

D．M1和M2狀態(tài)數(shù)和有向弧條數(shù)相等

12、詞法分析器作為自立的階段使囫圇編譯程序結(jié)構(gòu)越發(fā)簡潔、明確，因此，(A)A．詞法分析器應(yīng)作為自立的一遍B．詞法分析器作為子程序較好

C．詞法分析器分解為多個過程，由語法分析器挑選使用．

D．詞法分析器并不作為一個自立的階段13、假如L(M1)=L(M2)，則M1與M2(A)A．等價B．都是二義的

C．都是無二義的

D．它們的狀態(tài)數(shù)相等14、文法G：S→xSx|y所識別的語言是(C)

A．xyx

B．(xyx)*c．xnyxn(n≥0)d．x*yx*

15、文法G描述的語言L(G)是指(A)

A．??????∈?=+*,|)(TVSGLααα

B．???????∈?=+

*)(,|)(NTVVSGLαααC．??????∈?=**,|)(TVSGLαααD．?

??????∈?=**)(,|)(NTVVSGLααα16、有限狀態(tài)自動機(jī)能識別(C)

A．上下文無關(guān)文法

B．上下文有關(guān)文法

C．正規(guī)文法

D．短語文法17、編譯過程中掃描器的任務(wù)包括d。

①組織源程序的輸入②按詞規(guī)矩則分割出單詞，識別出其屬性，并轉(zhuǎn)換成屬性字的形式輸出③刪除注解④刪除空格及無用字符⑤行計數(shù)、列計數(shù)⑥發(fā)覺并定位詞法錯誤⑦建立符號表

可選項有：a、②③④⑦b、②③④⑥⑦c、①②③④⑥⑦d、①②③④⑤⑥⑦

18、正則式的“∣”讀作（1）b，“·”讀作（2）c，“*”讀作（3）d。可選項有：a、并且b、或者c、銜接d、閉包19、b這樣一些語言，它們能被確定的有窮自動機(jī)識別，但不能用正則表達(dá)式表示?？蛇x項有：a、存在b、不存在c、無法判定是否存在20、編譯過程中，語法分析的任務(wù)是c。

①分析單詞是怎樣構(gòu)成的②分析單詞是如何構(gòu)成語句和說明的③分析語句和說明是如何構(gòu)成程序的④分析程序的結(jié)構(gòu)

可選項有：a、②和③b、④c、②③④d、①②③④21、語法分析的常用辦法有b。

①自頂向下②自底向上③自左向右④自右向左

可選項有：a、①②③④b、①②c、③④d、①②③

22、假如文法G是無二義的，則它的任何句子(A)

A．最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必然相同

B．最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同

C．最左推導(dǎo)和最右推導(dǎo)必然相同

D．可能存在兩個不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同

23、由文法的開頭符經(jīng)0步或多步推導(dǎo)產(chǎn)生的文法符號序列是(C)

A．短語B．句柄C．句型D．句子

24、文法G：E→E+T|T

T→T*P|P

P→(E)|i

則句型P+T+i的句柄為(B)

A．P+TB．PC．P+T+iD．i

25、文法G：S→b|∧|(T)

T→T∨S|S

則FIRSTVT(T)=(C)

A．{b，∧，(}B．{b，∧，)}

C．{b，∧，(，∨}D．{b，∧，），∨}

26、產(chǎn)生正規(guī)語言的文法為(D)

A．0型B．1型C．2型D．3型

27、任何算符優(yōu)先文法(D)優(yōu)先函數(shù)。

A．有一個B．沒有C．有若干個D．可能有若干個

28、采納自上而下分析，必需(C)

A．消退左遞歸B．消退右遞歸

C．消退回溯D．提取公共左因子

29、素短語是指D的短語。

①至少包含一個符號②至少包含一個終結(jié)符號③至少包含一個非終結(jié)符號④除自身外不再包含其他終結(jié)符號⑤除自身外不再包含其他非終結(jié)符號⑥除自身外不再包含其他短語⑦除自身外不再包含其他素短語

可選項有：

A、①④

B、①⑤

C、②④

D、②⑦

30、給定文法A→bA∣cc，下面的符號串中，為該文法句子的是A。

①cc②bcbc③bcbcc④bccbcc⑤bbbcc

可選項有：

A、①

B、①③④⑤

C、①④

D、①④⑤

31、已知文法G[S]：S→eT∣RTT→DR∣εR→dR∣εD→a∣bd

則FOLLOW（T）=D。

可選項有：

A、｛d｝

B、｛a,b｝

C、｛a,b,#｝

D、｛#｝

E、｛d,#｝

32、正則式中的“*”讀作D。

可選項有：

A、并且

B、或者

C、銜接

D、閉包

33、在規(guī)范歸約中，用(B)來刻畫可歸約串。

A．直接短語B．句柄C．最左素短語D．素短語

34、有文法G：E→E*T|T

T→T+i|i

句子1+2*8+6按該文法G歸約，其值為(B)

A．23B．42C．30D．17

35、假如文法是無二義的，那么規(guī)范歸約是指(B)

A．最左推導(dǎo)的逆過程B．最右推導(dǎo)的逆過程

C．規(guī)范推導(dǎo)D．最左歸約的逆過程

36、文法G:S→S+T|T

T→T*P|P

P→(S)|i

句型P+T+i的短語有(B)

A．i,P+TB．P,P+T,i,P+T+iC．P+T+iD．P，P+T，i

37、高級語言編譯程序常用的語法分析辦法中，遞歸下降分析法屬于b分析辦法?？蛇x項有：

A、自左至右

B、自頂向下

C、自底向上

D、自右向左

38、普通程序設(shè)計語言的定義都涉及A三個方面。

①語法②語義③語用④程序基本符號確實定

可選項有：

A、①②③

B、①②④

C、①③④

D、②③④

39、編譯過程中，語法分析器的任務(wù)是B。

①分析單詞是怎樣構(gòu)成的②分析單詞串是如何構(gòu)成語句和說明的

③分析語句和說明是如何構(gòu)成程序的④分析程序的結(jié)構(gòu)

可選項有：

A、②③

B、②③④

C、①②③

D、①②③④

40、編譯程序生成的目標(biāo)程序B是機(jī)器語言的程序。

可選項有：

A、一定

B、不一定

C、無法推斷

D、一定不

一、單項挑選題（將正確答案的字母填入括號，每題1.5分，共30分）

1、普通程序設(shè)計語言的定義都涉及到（1.2.3）3個方面。

（1）語法（2）語義（3）語用（4）程序基本符號確實定

2、程序語言普通分為（1）和（2）。

（1）高級語言；（2）低級語言；（3）專用程序語言；（4）通用程序語言

3、面對機(jī)器語言指的是（B）。

A．用于解決機(jī)器硬件設(shè)計問題的語言B．特定計算機(jī)系統(tǒng)所固有的語言

C．各種計算機(jī)系統(tǒng)都通用的語言D．只能在一臺計算機(jī)上使用的語言

4．面對機(jī)器語言的特點是（D）。

A．程序的執(zhí)行效率低，編制效率低，可讀性差

B．程序的執(zhí)行效率高，編制效率高，可讀性強(qiáng)

C．程序的執(zhí)行效率低，編制效率高，可讀性強(qiáng)

D．程序的執(zhí)行效率高，編制效率低，可讀性差

5、程序設(shè)計語言常見的數(shù)據(jù)類型有：1.2.3.4

（1）數(shù)值型數(shù)據(jù)（2）規(guī)律數(shù)據(jù)（3）字符數(shù)據(jù)（4）指針類型

6、下列程序設(shè)計語言中是應(yīng)用式語言的是：B

A、PASCAL

B、LISP

C、VB

D、PROLOG

7、任何語法結(jié)構(gòu)都可以用（C）來表示。

A、語法樹

B、樹

C、抽象語法樹

D、二義文法樹

8、字母表是符號的有窮集合，由（C）組成詞和句子。

A、字符串

B、字符

C、符號

D、語言

9、下列符號是終結(jié)符的是（A）。

A、c

B、A

C、S

D、β

10、語法樹用（C）關(guān)系說明白句子中以操作符為核心的操作挨次，同時也說明白每一個操作符的操作對象。

A、上下

B、先后

C、層次

D、關(guān)聯(lián)11、循環(huán)語句的語法樹為（D）

A、

B、

C、

D、

12、表達(dá)式中間代碼的生成可采納（B）。

A、三地址代碼

B、四元式

C、三元式

D、間接三元式13、下列文法中，賦值語句的文法是（C）。

A、

B、

C、

D、

E→EopE

14、詞法分析的任務(wù)是（A）

A、識別單詞

B、分析句子的含義

C、識別句子

D、生成目標(biāo)代碼15、常用的中間代碼形式中不含（D）

A、三元式

B、四元式

C、逆波蘭式

D、語法樹16、代碼優(yōu)化的目的是（C）

A、節(jié)約時光

B、節(jié)約空間

C、節(jié)約時光和空間

D、把編譯程序舉行等價轉(zhuǎn)換17、代碼生成階段的主要任務(wù)是（C）

A、把高級語言翻譯成匯編語言

B、把高級語言翻譯成機(jī)器語言

C、把中間代碼變換成依靠詳細(xì)機(jī)器的目標(biāo)代碼

D、把匯編語言翻譯成機(jī)器語言18、詞法分析器的輸入是（B）

A、單詞符號串

B、源程序

C、語法單位

D、目標(biāo)程序19、中間代碼的生成所遵循的是（C）

A、語規(guī)矩則

B、詞規(guī)矩則

C、語義規(guī)章

D、等價變換規(guī)章20、編譯程序是對（D）

A、匯編程序的翻譯

B、高級語言程序的解釋并執(zhí)行

C、機(jī)器語言的執(zhí)行

D、高級語言的翻譯

while()SES→

if()if()elseS

ESESS

|→

=S

idE

→

21、語法分析應(yīng)遵循（C）

A、語義規(guī)章

B、語規(guī)矩則

C、構(gòu)詞規(guī)章

D、等價變換規(guī)章

22、編譯程序各階段的工作都涉及到（B）

A、語法分析

B、表格管理、出錯處理

C、語義分析

D、詞法分析

23、編譯程序工作時，通常有（1.2.3.4）階段。

（1）詞法分析（2）語法分析（3）中間代碼生成（4）語義檢查（5）目標(biāo)代碼生成

24、由文法的開頭符經(jīng)0步或多步推導(dǎo)產(chǎn)生的文法符號序列是C。

A、短語

B、句柄

C、句型

D、句子

25、產(chǎn)生正規(guī)語言的文法為D。

A、0型

B、1型

C、2型

D、3型

26、對無二義性文法來說，一棵語法樹往往代表了D。

（1）多種推導(dǎo)過程（2）多種最左推導(dǎo)過程（3）一種最左推導(dǎo)過程

（4）僅一種推導(dǎo)過程（5）一種最左推導(dǎo)過程

A、B、（1）（3）（5）C、D

27、假如文法G存在一個句子，滿足下列條件之一時，則稱該文法是二義文法。BCD

a.該句子的最左推導(dǎo)與最右推導(dǎo)相同

b.該句子有兩個不同的最左推導(dǎo)

c.該句子有兩棵不同的最右推導(dǎo)

d.該句子有兩棵不同的語法樹

e.該句子的語法樹惟獨一個

28、優(yōu)化可生成（D）的目標(biāo)代碼。

A、運行時光較短

B、占用存儲空間較小

C、運行時光短且占用內(nèi)存空間大

D、運行時光短且存儲空間小

29、構(gòu)造編譯程序應(yīng)把握（D）

A、源程序

B、目標(biāo)程序

C、編譯辦法

D、以上三項都是

30、賦值語句x=a+b*c-d的逆波蘭式為（B）

A、xab+c*d-=

B、xabc*+d-=

C、xabcd*+-=

D、x=abc*+d-

31、詞法分析器的輸出結(jié)果是（C）

A、單詞的種別編碼

B、單詞在符號表中的位置

C、單詞的種別編碼和自身值

D、單詞自身值

《編譯原理》期末試題（一）

一、是非題（請在括號內(nèi)，正確的劃√，錯誤的劃×）（每個2分，共20分）

1．編譯程序是對高級語言程序的解釋執(zhí)行。(×)

2．一個有限狀態(tài)自動機(jī)中，有且僅有一個唯一的終態(tài)。(×)

3．一個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應(yīng)。(√)

4．語法分析時必需先消退文法中的左遞歸。(×)

5．LR分析法在自左至右掃描輸入串時就能發(fā)覺錯誤，但不能精確?????地指出出錯地點。(√)6．逆波蘭表示法表示表達(dá)式時無須使用括號。(√)

7．靜態(tài)數(shù)組的存儲空間可以在編譯時確定。(×)

8．舉行代碼優(yōu)化時應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對提高目標(biāo)代碼的效率將起更大作用。(×)9．兩個正規(guī)集相等的須要條件是他們對應(yīng)的正規(guī)式等價。(×)

10．一個語義子程序描述了一個文法所對應(yīng)的翻譯工作。(×)

二、挑選題(請在前括號內(nèi)挑選最確切的一項作為答案劃一個勾，多劃按錯論)(每個4分，共40分)

1．詞法分析器的輸出結(jié)果是_____。

A．()單詞的種別編碼B．()單詞在符號表中的位置

C．()單詞的種別編碼和自身值D．()單詞自身值

2．正規(guī)式M1和M2等價是指_____。

A．()M1和M2的狀態(tài)數(shù)相等B．()M1和M2的有向邊條數(shù)相等

C．()M1和M2所識別的語言集相等D．()M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等

3．文法G：S→xSx|y所識別的語言是_____。

A．()xyxB．()(xyx)*C．()xnyxn(n≥0)D．()x*yx*

4．假如文法G是無二義的，則它的任何句子α_____。

A．()最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必然相同

B．()最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同

C．()最左推導(dǎo)和最右推導(dǎo)必然相同

D．()可能存在兩個不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同

5．構(gòu)造編譯程序應(yīng)把握______。

A．()源程序B．()目標(biāo)語言

C．()編譯辦法D．()以上三項都是

6．四元式之間的聯(lián)系是通過_____實現(xiàn)的。

A．()指示器B．()暫時變量

C．()符號表D．()程序變量

7．表達(dá)式(┐A∨B)∧(C∨D)的逆波蘭表示為_____。

A.()┐AB∨∧CD∨B．()A┐B∨CD∨∧

C．()AB∨┐CD∨∧D．()A┐B∨∧CD∨

8.優(yōu)化可生成_____的目標(biāo)代碼。

A．()運行時光較短B．()占用存儲空間較小

C．()運行時光短但占用內(nèi)存空間大D．()運行時光短且占用存儲空間小9．下列______優(yōu)化辦法不是針對循環(huán)優(yōu)化舉行的。

A.()強(qiáng)度減弱B．()刪除歸納變量

C．()刪除多余運算D．()代碼外提

10．編譯程序使用_____區(qū)分標(biāo)識符的作用域。

A.()說明標(biāo)識符的過程或函數(shù)名

B．()說明標(biāo)識符的過程或函數(shù)的靜態(tài)層次

C．()說明標(biāo)識符的過程或函數(shù)的動態(tài)層次

D.()標(biāo)識符的行號

《編譯原理》期末試題（二）

1、描述由正規(guī)式b*(abb*)*(a|ε)定義的語言，并畫出接受該語言的最簡DFA。

2、證實文法E→E+id|id是SLR(1)文法。

5、下面C語言程序經(jīng)非優(yōu)化編譯后，若運行時輸入2，則結(jié)果是

area=12.566360,addr=-1073743076

經(jīng)優(yōu)化編譯后，若運行時輸入2，則結(jié)果是

area=12.566360,addr=-1073743068

請解釋為什么輸出結(jié)果有區(qū)分。

main()

{

floats,pi,r;

pi=3.14159;

scanf("%f",

printf("area=%f,addr=%d\n",s=pi*r*r,

}

6、描述由正規(guī)式b*a(bb*a)*b*定義的語言，并畫出接受該語言的最簡DFA。

7、下面的文法產(chǎn)生代表正二進(jìn)制數(shù)的0和1的串集：

B→B0|B1|1

下面的翻譯計劃計算這種正二進(jìn)制數(shù)的十進(jìn)制值：

B→B10{B.val:=B1.val?2}

|B11{B.val:=B1.val?2+1}

|1{B.val:=1}

請消退該基礎(chǔ)文法的左遞歸，再重寫一個翻譯計劃，它仍然計算這種正二進(jìn)制數(shù)的十進(jìn)制值。

8、在C語言中，假如變量i和j都是long類型，請寫出表達(dá)式

printf(“%d\n”,

}

9、一個C語言的函數(shù)如下：

func(i)longi;{

longj;

j=i–1;

func(j);

}

下面左右兩邊的匯編代碼是兩個不同版本GCC編譯器為該函數(shù)產(chǎn)生的代碼。左邊的代碼在調(diào)用func之前將參數(shù)壓棧，調(diào)用結(jié)束后將參數(shù)退棧。右邊代碼對參數(shù)傳遞的處理方式?jīng)]有實質(zhì)區(qū)分。請講述右邊代碼對參數(shù)傳遞的處理方式并推想它帶來的優(yōu)點。func:|func:pushl%ebp|pushl%ebpmovl%esp,%ebp|movl%esp,%ebpsubl$4,%esp|subl$8,%espmovl8(%ebp),%edx|movl8(%ebp),%eaxdecl%edx|decl%eaxmovl%edx,-4(%ebp)|movl%eax,-4(%ebp)movl-4(%ebp),%eax|movl-4(%ebp),%eaxpushl%eax|movl%eax,(%esp)callfunc|callfuncaddl$4,%esp|leaveleave|retret|

編譯原理試卷八答案

1、由正規(guī)式b*(abb*)*(a|ε)定義的語言是字母表{a,b}上不含子串a(chǎn)a的全部串的集合。最簡DFA如下：

2、先給出接受該文法活前綴的DFA如下：

I0和I3都惟獨移進(jìn)項目，絕對不會引起矛盾；I2和I4都無移進(jìn)項目并僅含一個歸約項目，也絕對不會引起矛盾；在I1中，E'的后繼符號惟獨$，同第2個項目的展望符號“+”不一樣，因此I1也絕對不會引起矛盾。由此可以斷定該文法是SLR(1)

E'→·EE→·E+

id

E'→E·E→

E·+id

E→

id·

E

i

+

E→E+·id

E→E+

id·

i

sta1abb2

的。

3、語法制導(dǎo)定義如下。

S→id:=E{S.type:=if(id.type=boolandE.type=bool)or(id.type=intandE.type=int)thentype_okelsetype_error}E→E1andE2

{E.type:=ifE1.type=boolandE2.type=boolthenboolelse

type_error}

E→E1+E2{E.type:=ifE1.type=intandE2.type=intthenintelsetype_error}E→E1=E2{E.type:=ifE1.type=intandE2.type=intthenboolelsetype_error}E→id{E.type:=lookup(id.entry)}

4、對于函數(shù)f1，局部變量x聲明的作用域是囫圇函數(shù)體，導(dǎo)致在函數(shù)體中不行能拜訪形式參數(shù)x。因為這是一個合法的C語言函數(shù)，因此編譯器給出警告錯誤。

對于函數(shù)f2，因為局部變量x的作用域只是函數(shù)體的一部分，不會浮現(xiàn)上述問題，因而編譯器不報錯。

5、使用非優(yōu)化編譯時，變量s,pi,r在局部數(shù)據(jù)區(qū)都分配4個字節(jié)的空間。使用優(yōu)化編譯時，因為復(fù)寫傳揚，pi*r*r變成3.14159*r*r，pi=3.14159成為無用賦值而刪去，函數(shù)中不再有pi的引用，因此不必為pi分配空間。類似地，s=3.14159*r*r也是一個無用賦值（表達(dá)式要計算，但賦值是無用的），也不必為s分配空間。這樣，和非優(yōu)化狀況相比，局部數(shù)據(jù)區(qū)少了8個字節(jié)，因此r的地址向高地址方向移動了8個字節(jié)。

6、正規(guī)式b*a(bb*a)*b*體現(xiàn)的特點是，每個a的左邊都有若干b，除非a是第一個字母。該正規(guī)式定義的語言是：至少含一個a，但不含子串a(chǎn)a的全部a和b的串集。最簡DFA如下：

7、消退左遞歸后的文法：

B→1B'B'→0B'|1B'|ε相應(yīng)的翻譯計劃如下：B→1{B'.i:=1}B'{B.val:=B'.val}

B'→0{B'1.i:=B'.i?2}B'1{B'.val:=B'1.val}|1{B'1.i:=B'.i?2+1}B'1{B'.val:=B'1.val}

|ε{B'.val:=B'.i}

sta

2abb1

0ab

8、表達(dá)式&i的類型表達(dá)式是pointer(long)，表達(dá)式&i&j的類型表達(dá)式是long。根據(jù)C語言的規(guī)定，指向同一個類型的兩個指針可以相加減，它們值的差是它們之間的元素個數(shù)。

9、左邊的編譯器版本：普通只為局部變量分配空間。調(diào)用函數(shù)前，用若干次pushl指令將參數(shù)壓棧，返回后用addl$n,%esp一次將全部參數(shù)退棧（常數(shù)n按照調(diào)用前做了多少次pushl來打算）。

右邊的編譯器版本：除了為局部變量分配空間外，同時還為本函數(shù)中浮現(xiàn)的函數(shù)調(diào)用的參數(shù)分配空間，并且參數(shù)所用空間逼近棧頂。調(diào)用函數(shù)前，用movl指令將參數(shù)移入棧頂，調(diào)用結(jié)束后無需參數(shù)退棧指令。

優(yōu)點是每次函數(shù)調(diào)用結(jié)束后不需要執(zhí)行addl$n,%esp指令，另外增強(qiáng)優(yōu)化的可能性。

《編譯原理》期末試題（三）

1、從優(yōu)化的范圍的角度，優(yōu)化可以分哪兩類？對循環(huán)的優(yōu)化可以有哪三種？答：從優(yōu)化的范圍的角度，優(yōu)化可以分為局部優(yōu)化和全局優(yōu)化兩類；對循環(huán)的優(yōu)化有三種：循環(huán)不變表達(dá)式外提、歸納變量刪除與計算強(qiáng)度減少。

2、寫出表達(dá)式a=b*c+b*d對應(yīng)的逆波蘭式、四元式序列和三元式序列。答：逆波蘭式：abc*bd*+:=四元式序列：

三元式序列:OPARG1ARG2(1)(*，b，c，t1)(1)(*b，c)(2)(*，b，d，t2)(2)(*b，d)(3)(+，t1，t2，t3)(3)(+(1)，(2))(4)(:=，t3，/，a)

(4)(:=(3)，a)

3、對于文法G(S):

）MaLa|(LMbMbS→→→

答：1）bMabLbbbMbS)((???2）短語:Ma)，(Ma)，b(Ma)b直接短語:Ma)句柄:Ma)

三、設(shè)有字母表{a，b}上的正規(guī)式R=(ab|a)*。

解：（1）

SbM(

TMabL)

（2）將（1）所得的非確定有限自動機(jī)確定化εab-01131221+3

（3）對（2）得到的DFA化簡，合并狀態(tài)0和2為狀態(tài)2：

（4）令狀態(tài)1和2分離對應(yīng)非終結(jié)符B和A

G:A→aB|a|ε；B→aB|bA|a|b|ε；可化簡為：G:A→aB|ε；B→aB|bA|ε

四、設(shè)將文法G改寫成等價的LL(1)文法，并構(gòu)造預(yù)測分析表。

G：S→S*aT|aT|*aT；T→+aT|+a

解：消退左遞歸后的文法G’:S→aTS’|*aTS’

0123

ba

aεε-+01

2aaba-++12aa

b-+

S’→*aTS’|ε

T→+aT|+a

提取左公因子得文法G’’:

S→aTS’|*aTS’

S’→*aTS’|ε

T→+aT’

T’→T|ε

Select(S→aTS’)={a}

Select(S→*aTS’)={*}

Select(S→aTS’)∩Select(S→*aTS’)=Ф

Select(S’→*aTS’)={*}

Select(S’→ε)=Follow(s’)={#}

Select(S’→*aTS’)∩Select(S’→ε)=Ф

Select(T→+aT’)={+}

Select(T’→T)=First(T)={+}

Select(T’→ε)=Follow(T’)={*,#}

Select(T’→T)∩Select(T’→ε)=Ф

所以該文法是LL(1)文法。

預(yù)測分析表：

*+a#

S→*aTS’→aTS’

S’→*aTS’→ε

T→+aT’

T’→ε→T→ε

6設(shè)文法G為：

S→A；A→BA|ε；B→aB|b

解：（1）拓廣文法G’：(0)S’→S(1)S→A(2)A→BA(3)A→ε(4)

B→aB(5)B→b；FIRST(A)={ε,a,b}；FIRST(B)={a,b}

構(gòu)造的DFA如下:

項目集規(guī)范族看出，不存在矛盾動作。∴該文法是LR(1)文法。（2）LR(1)分析表如下：

(3)輸入串a(chǎn)bab的分析過程為：

簡答題3、設(shè)有文法G[S]:S→S(S)S|ε，該文法是否為二義文法？說明理由。答：是二義的，由于對于（）（）可以構(gòu)造兩棵不同的語法樹。

SS

S(S)SS(S)S

εεS(S)SS(S)Sεεεεεεεε

五、給定文法G[S]：

S→aA|bQ；A→aA|bB|b；B→bD|aQ；Q→aQ|bD|b；D→bB|aA；E→aB|bF

F→bD|aE|b

構(gòu)造相應(yīng)的最小的DFA。

解：先構(gòu)造其NFA：用子集法將NFA確定化：

ab

將S、A、Q、BZ、DZ、D、B重新命名，分離用0、1、2、3、4、5、6表示。由于3、4中含有z，所以它們?yōu)榻K態(tài)。

令P

＝（｛0,1,2,5,6｝,｛3,4｝）用b舉行分割：

P1＝（｛0,5,6｝,｛1,2｝,｛3,4｝）再用b舉行分割：

P2＝（｛0｝,｛5,6｝,｛1,2｝,｛3,4｝）再用a、b舉行分割，仍不變。

再令｛０｝為A，｛1，2｝為B，｛3，4｝為C，｛5，6｝為D。

最小化為右上圖。

六、對文法G(S)：S→a|^|(T)；T→T，S|S

答：(1)

SAQ

AABZ

QQDZ

BZQD

DZAB

DAB

BQD

a^(),#

a>>>

^>>>

()歸約8#(N)#(=)移進(jìn)9#(N)#)>#歸約10

#N

#接受

《編譯原理》期末試題（四）

二、構(gòu)造下列正規(guī)式相應(yīng)的DFA（用狀態(tài)轉(zhuǎn)換圖表示）（15）（1）1（0|1）*1（2）0*10*10*10*1

（3）letter（letter|digit）*

（1）

（2）

)

>>>

,>#

>

>

>

>

>

=

>

>

>

>

>

=

七、有定義二進(jìn)制整數(shù)的文法如下：

L→LB|B

B→0|1

構(gòu)造一個翻譯模式，計算該二進(jìn)制數(shù)的值（十進(jìn)制的值）。（15）引入L、B的綜合屬性val，翻譯模式為：

S→L{print(L.val)}

L→L1B{L.val=L1.val*2+B.val}

L→B{L.val=B.val}

B→0{B.val=0}

B→1{B.val=1}

《編譯原理》期末試題（五）

一、單項挑選題(共10小題，每小題2分，共20分)

1．語言是

A．句子的集合B．產(chǎn)生式的集合

C．符號串的集合D．句型的集合

2．編譯程序前三個階段完成的工作是

A．詞法分析、語法分析和代碼優(yōu)化

B．代碼生成、代碼優(yōu)化和詞法分析

C．詞法分析、語法分析、語義分析和中間代碼生成

D．詞法分析、語法分析和代碼優(yōu)化

3．一個句型中稱為句柄的是該句型的最左

A．非終結(jié)符號B．短語C．句子D．直接短語

4．下推自動機(jī)識別的語言是

A．0型語言B．1型語言

C．2型語言D．3型語言

5．掃描器所完成的任務(wù)是從字符串形式的源程序中識別出一個個具有自立含義的最小語法單位即

A．字符B．單詞C．句子D．句型

6．對應(yīng)Chomsky四種文法的四種語言之間的關(guān)系是

A．L0?L1?L2?L3B．L3?L2?L1?L0

C．L3=L2?L1?L0D．L0?L1?L2=L3

7．詞法分析的任務(wù)是

A．識別單詞B．分析句子的含義

C．識別句子D．生成目標(biāo)代碼

8．常用的中間代碼形式不含

A．三元式B．四元式C．逆波蘭式D．語法樹

9．代碼優(yōu)化的目的是

A．節(jié)約時光B．節(jié)約空間

C．節(jié)約時光和空間D．把編譯程序舉行等價交換

10．代碼生成階段的主要任務(wù)是

A．把高級語言翻譯成匯編語言

B．把高級語言翻譯成機(jī)器語言

C．把中間代碼變換成依靠詳細(xì)機(jī)器的目標(biāo)代碼

D．把匯編語言翻譯成機(jī)器語言

四、簡答題(共4小題，每小題5分，共20分)

1．編譯程序和高級語言有什么區(qū)分?

用匯編語言或高級語言編寫的程序，必需先送入計算機(jī)，經(jīng)過轉(zhuǎn)換成用機(jī)器

語言表示的目標(biāo)程序（這個過程即編譯），才干由計算機(jī)執(zhí)行。執(zhí)行轉(zhuǎn)換過程

的程序叫編譯程序。匯編程序是指沒有編譯過的匯編語言源文件。編譯程序轉(zhuǎn)

換過的叫目標(biāo)程序，也就是機(jī)器語言。

編譯程序的工作狀況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來將匯編語言編寫的程序，根據(jù)一一對應(yīng)的關(guān)系，轉(zhuǎn)換成用機(jī)器語言表示的程序。

解釋型編譯程序?qū)⒏呒壵Z言程序的一個語句，先解釋成為一組機(jī)器語言的指令，

然后立刻執(zhí)行，執(zhí)行完了，取下一組語句解釋和執(zhí)行，如此繼續(xù)到完成一個程序止。用解釋型編譯程序，執(zhí)行速度很慢，但可以舉行人和計算機(jī)的"對話"，隨時

可以修改高級語言的程序。BASIC語言就是解釋型高級語言。編譯型編譯程序?qū)⒓壵Z言編寫的程序，一次就會部翻譯成機(jī)器語言表示的程序，而且過程舉行很快，在過程中，不能舉行人機(jī)對話修改。FORT