武漢理工大學編譯技術期末復習題

編譯技術復習題

復制題日后，按住Ctrl+F鍵查找相應題目答案

一、多選（共計25分，每題2.5分，每題答案完全一樣得滿分，少選、多選、錯選均不得分。）

1、自下而上的語法分析中，應從一開始分析。

A.句型

B.句子

C.以單詞為單位的程序

D.文法的開始符

錯誤：【B;D】

2、詞法分析器的輸出結果包括

A.單詞的種別編碼

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

C.單詞名

D.單詞自身值

錯誤：【AD】

3、對無二義性文法來說，一棵語法樹往往代表了_____

A.多種推導過程

B.多種最左推導過程

C.僅一種推導過程

D.一種最左推導過程

錯誤：【A;D】

4、在詞法分析中，能識別出_____

A.保留字

B.運算符

C.逆波蘭式

D.常數(shù)

錯誤：【A;B;D】

5、通常一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標

代碼生成等五個部分，還應包括_。

A.模擬執(zhí)行器

B.解釋器

C.表格處理

D.出錯處理

錯誤：[C;D]

6、編譯程序的輸出結果可以是_____

A.源代碼

B.匯編語言代碼

C.中間代碼

D.可重定位代碼

錯誤：【B;D】

7、對于文法G[E]:⑴E-E+T⑵E-T(3)T-T*F⑷T-F⑸F-(E)⑹F-a句型a

+T*F的素短語是一。

A.a

B.T

C.a+T

D.T*F

錯誤：【A;D】

8、已知文法G[S]:S-S+aF|aF|+aFF-*aF|*a下面說法中—正確。

A.是左遞歸文法

B.含有左公因子

C,是算符文法

D.是2型文法

錯誤：[A;B;C;D]

9、每一項ACTIONS,a]所規(guī)定的動作包括。

A.編輯

B.編譯

C.連接

D.運行

錯誤:【A;B;C】

10、源程序中的錯誤一般有______

A.詞法錯誤

B.語法錯誤

C.編譯錯誤

D.語義錯誤

錯誤：[A;B;D]

二、判斷（共計25分，每題2.5分）

11、確定的自動機以及襁定的自動機都能正確地識別正規(guī)集。

A.正確

B.錯誤

錯誤：【A】

12、遞歸下降語法分析時必須先消除文法中的左遞歸。

A.正確

B.錯誤

錯誤：【A】

13、對任意文法G,都存在相應的正規(guī)式與之等價.

A.正確

B.錯誤

錯誤：【A】

14、LR分析技術無法適用二義文法。

A.正確

B.錯誤

錯誤：⑻

15、自下而上語法制導翻譯法的特點是語法分析棧與語義分析棧不需要同步操作。

A.正確

B.錯誤

錯誤：[B]

16、若一個語言是無窮集合，則定義該語言的文法一定是遞歸的。

A.正確

B.錯誤

錯誤：【A】

17、一個句型的直接短語是唯一的。

A.正確

B.錯誤

錯誤：【A】

18、對于在一個基本塊內后邊不再被引用的變量所占用的寄存器應盡早釋放，以提高寄存

器的利用效率。

A.正確

B.錯誤

錯誤：[A]

19、某賦值語句為y:=a+(b*c),其中a,b,c均為單詞。

A.正確

B.錯誤

錯誤：⑻

20、一個句型的直接短語是唯一的。

A.正確

B.錯誤

錯誤：⑻

三、單選(共計50分，每題2.5分)

21、一個確定的有窮自動機DFA是一個

A.五元組(K￡f,SZ)

B.四元組(VN,VT,P,S)

C.四元組(K,Z,f,S)

D.三元組(VN,VT,P)

錯誤：【A】

22、在產(chǎn)生式中，符號"一"("::=")表示

A.等于

B.恒等于

C.取決于

D.定義為

錯誤：【D】

23、中綴表達式a+b*(c+d)的逆波蘭表示是一。

A.abcd+*+

B.abcd+*+

C.abc+*d+

D.a+bc*d+

錯誤：【A】

24、一文法不是LL⑴的。

A.遞歸

B.右遞歸

C.2型

D.含有公共左因子的

錯誤：【D】

25、設有如圖所示的有窮自動機。其中狀態(tài)①為初態(tài)，狀態(tài)⑤為終態(tài)，假設digit代表數(shù)字

。到9。則下述實數(shù)中—可被該有窮自動機接受。

A.+123

B.-1.

C.6

D.-11.47

錯誤：[D]

26、若a為終結符,則A-coap是一項目。

A.歸約

B.移進

C.接收

D,待約

錯誤：⑻

27、無符號常數(shù)的識別與拼數(shù)工作通常在一階段完成。

A.語法分析

B.語義分析

C.詞法分析

D.代碼優(yōu)化

錯誤：【O

28、遞歸下降分析法和預測分析法要求描述語言的文法是

A.正規(guī)文法

B.LR（O文法）

c.LL(1)文法

D.右線性文法

錯誤：⑹

29、有文法G及其語法制導翻譯的屬性文法如下所示(語義規(guī)則中的*和+分別是常規(guī)意義

,-,E-*-E,A,T,{E.val,=,E.val-*-T.val}^

???EfT............{E.val,=,T.val}.

??,TfTftn',?,{T.val-=,T'.val-+*n.val,}p

???T-*,-n............{T.val-=*n.val}?J

下的算術運算符)：則分析句子1。八，2?八?3?#-4其值為........

A.10

B.34

C.14

D.54

錯誤：【C】

30、一不可能是目標代碼。

A.匯編指令代碼

B.可重定位指令代碼

C.絕對指令代碼

D.中間代碼

錯誤：【D】

31、不能被如下狀態(tài)轉換圖識別的句子是

A.aOb

B.alOlOb

C.bOOb

D.ab

錯誤：[D]

32、下列符號串不可以由符號集S={a,b}上的正閉包運算產(chǎn)生的是:

A.￡

B.a

C.aa

D.ab

錯誤：【A】

33、在編譯過程中，如果遇到錯誤應該

A.把錯誤理解成局部的錯誤

B.對錯誤在局部范圍內進行糾正，繼續(xù)向下分析

C.當發(fā)現(xiàn)錯誤時，跳過錯誤所在的語法單位繼續(xù)分析下去

D.當發(fā)現(xiàn)錯誤時立即停止編譯，待用戶改正錯誤后再繼續(xù)編譯

錯誤：[C]

34、若源程序是用高級語言編寫的程序，目標程序是_,則其翻譯程序稱為編譯程序。

A.匯編語言程序或高級語言程序

B.高級語言程序或機器語言程序

C.匯編語言程序或機器語言程序

D.連接程序或運行程序

錯誤：⑹

?S-->.xxW......................print-?“1”一

?s.f.y.........................print-“2”?

35、已知屬性文法G【S】：,-->?敏.............Print-"3”.則若輸入“xxxxyzz”，

文法將輸出一O

A.11233

B.23131

C.11231

D.33211

錯誤：⑻

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

A.表達式

B.產(chǎn)生式

C.單詞

D.語句

錯誤：【。

37、在狀態(tài)轉換圖中，結點代表—,用圓圈表示。

A.輸入緩沖區(qū)

B.向前搜索

C.字符串

D.狀態(tài)

錯誤：【D】

38、文法G所描述的語言是一的集合。

A.文法G的字母表V中所有符號組成的符號串

B.文法G的字母表V的閉包V*中的所有符號串

C.由文法的開始符號推出的所有終結符串

D.由文法的開始符號推出的所有符號串

錯誤：⑹

39、已知文法G[S]為:S->a|A|(T)T->3sls則G[S]的FIRSTVT(S)為

A.{aA(}

B.{aA)}

C.{aA(,)

D.{aA)J

錯誤：【A】

40、如果文法G是無二義的，則它的得可句子a—o

A.最左推導和最右推導對應的語法樹必定相同

B.最左推導和最右推導對應的語法樹可能不同

C.最左推導和最右推導必定相同

D.可能存在兩個不同的最左推導，但它們對應的語法樹相同

錯誤：[A]

一、多選(共計25分，每題2.5分，每題答案完全一樣得滿分，少選、多選、錯選均不得分。)

1、設有文法G⑸為：S-a|b|(A)A-SdA|S則LASTVT(S)包含的終結符有：

A.a

B.b

C.)

D.(

錯誤:【A;B;C】

2、詞法分析器的輸出結果包括一。

A.單詞的種別編碼

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

C.單詞名

D.單詞自身值

錯誤：[A;D]

3、編譯程序的輸出結果可以是_____

A.源代碼

B.匯編語言代碼

C.中間代碼

D.可重定位代碼

錯誤：【B;D】

4、在詞法分析中，能識別出一

A.保留字

B.運算符

C.逆波蘭式

D.常數(shù)

錯誤：[A;B;D]

5、自下而上的語法分析中，應從開始分析。

A.句型

B.句子

C.以單詞為單位的程序

D.文法的開始符

錯誤：[B;D]

6、源程序中的錯誤有______

A.詞法錯誤

B.語法錯誤

C.編譯錯誤

D.語義錯誤

錯誤：【A;B;D】

7、對于文法G[E]:(1)E-E+T⑵E-T⑶T-T*F⑷T-F⑸F-(E)⑹F-a句型a

+T*F的素短語是一。

A.a

B.T

C.a+T

D.T*F

錯誤：[A;D]

8、算符優(yōu)先文法G[E]:EE+T,T(E”i,則關于優(yōu)先級的判斷正確的是

A.+?>(

B.+?>+

C.+?>)

D.(?>)

錯誤：【B;C】

9、通常一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標

代碼生成等五個部分，還應包括

A.模擬執(zhí)行器

B.解釋器

C.表格處理

D.出錯處理

錯誤：【C;D】

10、每一項ACTION[S,a]所規(guī)定的動作包括。

A.編輯

B.編譯

C.連接

D.運行

錯誤:【A;B;C】

二、判斷供計25分，每題2.5分）

11、逆波蘭法表示的表達式亦稱前綴式。

A.正確

B.錯誤

錯誤：⑻

12、每一個NFA都對應有唯一的一個最小化的DFA。

A.正確

B.錯誤

錯誤：⑻

13、目標代碼生成時，應考慮如何充分利用計算機的寄存器的問題。

A.正確

B.錯誤

錯誤：【A】

14、遞歸下降分析法是自頂向下分析方法。

A.正確

B.錯誤

錯誤:[A]

15、設有一個LR(O)項目集I={X-aBB，A-a},該項目集含有“歸約-歸約"沖突。

A.正確

B.錯誤

錯誤：⑻

16、編譯程序與解釋程序的區(qū)別在于編譯程序對源程序進行了翻譯，而解釋程序則沒有。

A.正確

B.錯誤

錯誤：⑻

17、自動機M和M'的狀態(tài)數(shù)不同，則二者必不等價。

A.正確

B.錯誤

錯誤：⑻

18、使用語法制導翻譯法的編譯程序能夠同時進行語法分析和語義分析。

A.正確

B.錯誤

錯誤：⑻

19、進行代碼優(yōu)化時應著重考慮循環(huán)的代碼優(yōu)化，顏寸提高目標代碼的效率將起更大作用。

A.正確

B.錯誤

錯誤：【A】

20、包含左遞歸的文法也能直接用LL(1)分析法來分析。

A.正確

B.錯誤

錯誤：[B]

三、單選(共計50分，每題2.5分)

21、同正規(guī)式(a|b)*等價的正規(guī)式為

A.(a|b)+

B.a*|b*

C.(ab)*

D.(a*|b*)+

錯誤：【B】

22、文法G所描述的語言是一的集合。

A.文法G的字母表V中所有符號組成的符號串

B.文法G的字母表V的閉包V*中的所有符號串

C.由文法的開始符號推出的所有終結符串

D.由文法的開始符號推出的所有符號串

錯誤：[C]

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

A.表達式

B.產(chǎn)生式

C.單詞

D.語句

錯誤：【O

24、LR語法分析棧中存放的狀態(tài)是識別文法規(guī)范句型—的DFA狀態(tài)。

A.前綴

B.活前綴

C.句柄

D.LR(0)項目

錯誤：⑻

25、編譯程序前三個階段完成的工作是^一。

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

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

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

D.詞法分析、語法分析和代碼生成

錯誤：[C]

?S-->.xxW.....................print*?“1”3

?S>—>.y........................print-,"2”?

26、已知屬性文法G【S】：WT?累..............「日出一“3”?則若輸入“xxxxyzz",

文法將輸出____

A.11233

B.23131

C.11231

D.33211

錯誤：⑻

27、中綴表達式a+b*(c+d)的逆波蘭表示是一。

A.abcd+*+

B.abcd+*+

C.abc+*d+

D.a+bc*d+

錯誤：【A】

28、無符號常數(shù)的識別與拼數(shù)工作通常在一階段完成。

A.語法分析

B.語義分析

C.詞法分析

D.代碼優(yōu)化

錯誤：[C]

29、遞歸下降分析法和預測分析法要求描述語言的文法是

A.正規(guī)文法

B.LR(O文法)

C.LL(1)文法

D.右線性文法

錯誤：【C】

30、一不可能是目標代碼。

A.匯編指令代碼

B.可重定位指令代碼

C.絕對指令代碼

D.中間代碼

錯誤：[D]

31、有文法G及其語法制導翻譯的屬性文法如下所示（語義規(guī)則中的*和+分別是常規(guī)意義

???EfE1,AeT,{E.val,=?￡.val,*,T.val}^

???EfT............{E.val,=,T.val}^

?一TfTftn,,,?{T.val,=?71.val-+-n.val」。

??,T-*,n............{T.val,="n.val}y

下的算術運算符）,則分析句子1?八?2?/V3?#?4其值為........。,

A.10

B.34

C.14

D.54

錯誤：【C】

32、在編譯過程中，如果遇到錯誤應該

A.把錯誤理解成局部的錯誤

B.對錯誤在局部范圍內進行糾正，繼續(xù)向下分析

C.當發(fā)現(xiàn)錯誤時,跳過錯誤所在的語法單位繼續(xù)分析下去

D.當發(fā)現(xiàn)錯誤時立即停止編譯，待用戶改正錯誤后再繼續(xù)編譯

錯誤：⑹

33、已知文法G[S]為:S->a|A|（T）T->3sls則G[S]的FIRSTVT（S）為

A.”（}

B.{a八）}

C.{a八（,}

D.{a?}

錯誤：[A]

34、若源程序是用高級語言編寫的程序，目標程序是_,則其翻譯程序稱為編譯程序。

A.匯編語言程序或高級語言程序

B.高級語言程序或機器語言程序

C.匯編語言程序或機器語言程序

D.連接程序或運行程序

錯誤：⑹

35、自底向上語法分析法的原理是

A."移進~~推導法"

B."最蟠導法"

C."移進一歸約法"

D."推導——歸約法”

錯誤：⑹

36、下列符號串不可以由符號集S={a,b}上的正閉包運算產(chǎn)生的是：

A.E

B.a

C.aa

D.ab

錯誤：【A】

37、若a為終結符，則ATocaB是一項目。

A.歸約

B.移進

C.接收

D.待約

錯誤：⑻

38、設有文法G[S]為：S-a|b|(A)AfSdA|S則FIRSTVT(S)=

A.{a,b,(}

B.{a,b,)}

C.{a,b,(,)}

D.{a,b,d}

錯誤：【A】

39、編譯過程中，詞法分析階段的任務是_____

A.識別表達式

B.識別語言單詞

C.識別語句

D.識別程序

錯誤：[B]

40、一文法不是LL(1)的。

A.遞歸

B.右遞歸

C.2型

D.含有公共左因子的

錯誤：【D】

一、多選(共計25分，每題2.5分海題答案完全一樣得滿分，少選、多選、錯選均不得分。)

L對于文法G[E]:(1)E-E+T⑵E-T⑶T-T*F⑷T-F⑸F-(E)⑹F-a句型a

+T*F的素短語是一。

A.a

B.T

C.a+T

D.T*F

錯誤：【A;D】

2、源程序中的錯誤T§有______

A.詞法錯誤

B.語法錯誤

C.編譯錯誤

D.語義錯誤

錯誤:[A;B;D]

3、自下而上的語法分析中，應從一開始分析。

A.句型

B.句子

C.以單詞為單位的程序

D.文法的開始符

錯誤：【B;D】

4、通常一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標

代碼生成等五個部分，還應包括一O

A.模擬執(zhí)行器

B.解釋器

C.表格處理

D.出錯處理

錯誤：【C;D】

5、編譯程序的輸出結果可以是_____

A.源代碼

B.匯編語言代碼

C.中間代碼

D.可重定位代碼

錯誤：【B;D】

6、在詞法分析中，能識別出.

A.保留字

B.運算符

C.逆波蘭式

D.常數(shù)

錯誤：[A;B;D]

7、已知文法G[S]:S-S+aF|aF|+aFF-*aF|*a下面說法中—正確。

A.是左遞歸文法

B.含有左公因子

C,是算符文法

D.是2型文法

錯誤：[A;B;C;D]

8、設有文法G⑸為：S-a|b|(A)A-SdA|S則LASTVT(S)包含的終結符有：

A.a

B.b

C.)

D.(

錯誤：【A;B;C】

9、下列優(yōu)化中，屬于循環(huán)優(yōu)化的有

A.強度削弱

B.合并已知量

C.刪除歸納變量

D.代碼外提

錯誤：【A;C;D】

10、算符優(yōu)先文法G【E】：EE+T,T(E)兒則關于優(yōu)先級的判斷正確的是

A.+?>(

B.+?>+

€.+?>)

D.(?>)

錯誤：【B;C】

二、判斷供計25分，每題2.5分)

11、一個有限狀態(tài)自動機中，有且僅有一個唯一終態(tài)。

A.正確

B.錯誤

錯誤：[B]

12、若一個語言是無窮集合，則定義該語言的文法一定是遞歸的。

A.正確

B.錯誤

錯誤：【A】

13、包含左遞歸的文法也能直接用LL(1)分析法來分析。

A.正確

B.錯誤

錯誤：⑻

14、LR分析技術無法適用二義文法。

A.正確

B.錯誤

錯誤:[B]

15、遞歸下降語法分析時必須先消除文法中的左遞歸。

A.正確

B.錯誤

錯誤：【A】

16、產(chǎn)生式是用于定義詞法成分的一種書寫規(guī)則。

A.正確

B.錯誤

錯誤：⑻

17、設有一個LR(O)項目集I={X-aBB，A-a},該項目集含有“歸約-歸約"沖突。

A.正確

B.錯誤

錯誤：⑻

18、每一個NFA都對應有唯一的一個最小化的DFA。

A.正確

B.錯誤

錯誤：⑻

19、緊跟在條件轉移語句后面的語句是基本塊的入口語句。

A.正確

B.錯誤

錯誤：【A】

20、對任意文法G,都存在相應的正規(guī)式與之等價.

A.正確

B.錯誤

錯誤：【A】

三、單選（共計50分，每題2.5分）

21、遞歸下降分析法和預測分析法要求描述語言的文法是

A.正規(guī)文法

B.LR（0文法）

C.LL（1）文法

D.右線性文法

錯誤：

22、無符號常數(shù)的識別與拼數(shù)工作通常在一階段完成。

A.語法分析

B.語義分析

C.詞法分析

D.代碼優(yōu)化

錯誤：[C]

23、自底向上語法分析法的原理是

A."移0~導法"

B."最磁導法”

C.”移進一歸約法”

D."推導一歸約法”

錯誤：【C】

24、用高級語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫

A.源程序

B.目標程

C.連接程序

D.解釋程序

錯誤：⑻

25、—不可能是目標代碼。

A.匯編指令代碼

B.可重定位指令代碼

C.絕對指令代碼

D.中間代碼

錯誤：[D]

26、設有如圖所示的有窮自動機。其中狀態(tài)①為初態(tài)，狀態(tài)⑤為終態(tài)，假設digit代表數(shù)字

0到9。則下述實數(shù)中—可被該有窮自動機接受。

A.+123

B.-1.

C.6

D.-11.47

錯誤：[D]

27、如果文法G是無二義的，則它的任何句子a

A.最左推導和最右推導對應的語法樹必定相同

B.最左推導和最右推導對應的語法樹可能不同

C.最左推導和最右推導必定相同

D.可能存在兩個不同的最左推導，但它們對應的語法樹相同

錯誤：【A】

28、有文法G及其語法制導翻譯的屬性文法如下所示（語義規(guī)則中的*和+分別是常規(guī)意義

???EfE1,AeT,{E.val,=?￡.val,*,T.val}^

???EfT............{E.val,=,T.val}^

?一TfTftn,,,?{T.val,=?71.val-+-n.val」。

??,T-*,n............{T.val,="n.val}y

下的算術運算符）,則分析句子1?八?2?/V3?#?4其值為........。,

A.10

B.34

C.14

D.54

錯誤：⑹

29、在編譯過程中，如果遇到錯誤應該

A.把錯誤理解成局部的錯誤

B.對錯誤在局部范圍內進行糾正，繼續(xù)向下分析

C.當發(fā)現(xiàn)錯誤時,跳過錯誤所在的語法單位繼續(xù)分析下去

D.當發(fā)現(xiàn)錯誤時立即停止編譯，待用戶改正錯誤后再繼續(xù)編譯

錯誤：⑹

30、一文法不是山1）的。

A.遞歸

B.右遞歸

C.2型

D.含有公共左因子的

錯誤：【D】

31、文法G[S]:S-ab|aSb,該文法所描述的語言

A.L(G[S])={anbn|n>0}

B.L(G[S])={ambn|m,n>0}

C.L(G[S])={anbn|n>l}

D.L(G[S])={ambn|m,n>l}

錯誤：【C】

32、同正規(guī)式(a|b)*等價的正規(guī)式為

A.(a|b)+

B.a*|b*

C.(ab)*

D.(a*|b*)+

錯誤：【B】

33、一個確定的有窮自動機DFA是一個一。

A.五元組(KEf,S,Z)

B.四元組(VN,VT,P,S)

C.四元組(KZf,S)

D.三元組(VN,VT,P)

錯誤：【A】

34、設有文法G⑸為:STa|b|(A)A—SdA|S則FIRSTVT⑸=

A.{ab(}

B.{a,b,))

C.{a,b,(,))

D.{a,b,d}

錯誤：【A】

35、編譯過程中，詞法分析階段的任務是_____

A.識別表達式

B.識別語言單詞

C.識別語句

D.識別程序

錯誤：[B]

36、中綴表達式a+b*(c+d)的逆波蘭表示是一。

A.abcd+*+

B.abcd+*+

C.abc+*d+

D.a+bc*d+

錯誤：【A】

37、文法G所描述的語言是一的集合。

A.文法G的字母表V中所有符號組成的符號串

B.文法G的字母表V的閉包V*中的所有符號串

C.由文法的開始符號推出的所有終結符串

D.由文法的開始符號推出的所有符號串

錯誤：⑹

38、不能被如下狀態(tài)轉換圖識別的句子是

A.aOb

B.alOlOb

C.bOOb

D.ab

錯誤：【D】

39、在狀態(tài)轉換圖中，結點代表一,用圓圈表示。

A.輸入緩沖區(qū)

B.向前搜索

C.字符串

D.狀態(tài)

錯誤：【D】

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

A.表達式

B.產(chǎn)生式

C.單詞

D.語句

錯誤：［C］

一、多選（共計25分，每題2.5分，每題答案完全一樣得滿分，少選、多選、錯選均不得分。）

1、每一項ACTIONS,a］所規(guī)定的動作包括。

A.編輯

B.編譯

C.連接

D.運行

錯誤:【A;B;C】

2、對無二義性文法來說，一棵語法樹往往代表了_____

A.多種推導過程

B.多種最左推導過程

C.僅一種推導過程

D.一種最左推導過程

錯誤：［A;D］

3、源程序中的錯誤有______

A.詞法錯誤

B.語法錯誤

C.編譯錯誤

D.語義錯誤

錯誤：[A;B;D]

4、通常一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標

代碼生成等五個部分，還應包括一O

A.模擬執(zhí)行器

B.解釋器

C.表格處理

D.出錯處理

錯誤：【C;D】

5、在詞法分析中，能識別出_____

A.保留字

B.運算符

C.逆波蘭式

D.常數(shù)

錯誤：[A;B;D]

6、設有文法G[S]為：S-a|b|(A)ATSdA|S則LASTVT(S)包含的終結符有：

A.a

B.b

C.)

D.(

錯誤：[A;B;C]

7、已知文法G[S]:S-S+aF|aF|+aFF-*aF|*a下面說法中—正確。

A.是左遞歸文法

B.含有左公因子

C,是算符文法

D.是2型文法

錯誤：[A;B;C;D]

8、算符優(yōu)先文法G[E]:EE+T,T(E)|i,則關于優(yōu)先級的判斷正確的是一。

A.+?>(

B.+?>+

€.+?>)

D.(>>)

錯誤：[B;C]

9、對于文法G[E]:(1)E—E+T⑵E-T⑶Tf*F⑷T-F⑸F-(E)⑹F-a句型a

+T*F的素短語是一。

A.a

B.T

Ca+T

D.T*F

錯誤：【A;D】

10、詞法分析器的輸出結果包括

A.單詞的種別編碼

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

C.單詞名

D.單詞自身值

錯誤：[A;D]

二、判斷（共計25分，每題2.5分）

11、對任意文法G,都存在相應的正規(guī)式與之等價.

A.正確

B.錯誤

錯誤：【A】

12、每一個NFA都對應有唯一的一個最小化的DFA。

A.正確

B.錯誤

錯誤：[B]

13、包含左遞歸的文法也能直接用LL(1)分析法來分析。

A.正確

B.錯誤

錯誤：⑻

14、逆波蘭法表示的表達式亦稱前綴式。

A.正確

B.錯誤

錯誤：⑻

15、一個有限狀態(tài)自動機中，有且僅有一個唯一終態(tài)。

A.正確

B.錯誤

錯誤：[B]

16、遞歸下降語法分析時必須先消除文法中的左遞歸。

A.正確

B.錯誤

錯誤：【A】

17、每個句子都有規(guī)范推導；每個句型都有規(guī)范推導。

A.正確

B.錯誤

錯誤：【A】

18、自下而上語法制導翻譯法的特點是語法分析棧與語義分析棧不需要同步操作。

A.正確

B.錯誤

錯誤：[B]

19、進行代碼優(yōu)化時應著重考慮循環(huán)的代碼優(yōu)化，這對提高目標代碼的效率將起更大作用。

A.正確

B.錯誤

錯誤：【A】

20、對任何一個編譯程序來說，產(chǎn)生中間代碼是不可缺少的。

A.正確

B.錯誤

錯誤：⑻

三、單選（共計50分，每題2.5分）

21、同正規(guī)式（a|b）*等價的正規(guī)式為

A.（a|b）+

B.a*|b*

C.(ab)*

D.(a*|b*)+

錯誤：⑻

22、若源程序是用高級語言編寫的程序，目標程序是—，則其翻譯程序稱為編譯程序。

A.匯編語言程序或高級語言程序

B.高級語言程序或機器語言程序

C.匯編語言程序或機器語言程序

D.連接程序或運行9

錯誤：⑹

23、—不可能是目標代碼。

A.匯編指令代碼

B.可重定位指令代碼

C.絕對指令代碼

D.中間代碼

錯誤:【D】

24、無符號常數(shù)的識別與拼數(shù)工作通常在一階段完成。

A.語法分析

B.語義分析

C.詞法分析

D.代碼優(yōu)化

錯誤：[C]

25、編譯程序前三個階段完成的工作是一0

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

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

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

D.詞法分析、語法分析和代碼生成

錯誤：⑹

26、在狀態(tài)轉換圖中，結點代表一，用圓圈表示。

A.輸入緩沖區(qū)

B.向前搜索

C.字符串

D.狀態(tài)

錯誤：【D】

27、在產(chǎn)生式中，符號）表示

A.等于

B.恒等于

C.取決于

D.定義為

錯誤：【D】

28、遞歸下降分析法和預測分析法要求描述語言的文法是

A.正規(guī)文法

B.LR(O文法)

C.LL(1)文法

D.右線性文法

錯誤：[C]

29、編譯過程中,詞法分析階段的任務是_____

A.識別表達式

B.識別語言單詞

C.識別語句

D.識別程序

錯誤：⑻

30、設有如圖所示的有窮自動機。其中狀態(tài)①為初態(tài)，狀態(tài)⑤為終態(tài)，假設digit代表數(shù)字

0到9。則下述實數(shù)中—可被該有窮自動機接受。

digitdigit

ca

A.+123

B.一1.

C.6

D.-11.47

錯誤：【D】

31、不能被如下狀態(tài)轉換圖識別的句子是

A.aOb

B.alOlOb

C.bOOb

D.ab

錯誤：[D]

32、LR語法分析棧中存放的狀態(tài)是識別文法規(guī)范句型—的DFA狀態(tài)。

A.前綴

B.活前綴

C.句柄

D.LR(0)項目

錯誤：⑻

33、如果文法G是無二義的，則它的任何句子a

A.最左推導和最右推導對應的語法樹必定相同

B.最左推導和最右推導對應的語法樹可能不同

C.最左推導和最右推導必定相同

D.可能存在兩個不同的最左推導，但它們對應的語法樹相同

錯誤：［A］

34、設有文法G［法為:S-a|b|(A)AfSdA|S則FIRSTVT(S)=

A.{a,b,(}

B.{a,b,))

C.{a,b,(,)}

D.{a,b,d}

錯誤：【A】

35、若a為終結符,則A-ocaB是一項目。

A.歸約

B.移進

C.接收

D.待約

錯誤：【B】

36、中綴表達式a+b*(c+d)的逆波蘭表示是一。

A.abcd+*+

B.abcd+*+

C.abc+*d+

D.a+bc*d+

錯誤：【A】

37、用高級語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫一o

A.源程序

B.目標程J?

C.連接程序

D.解釋程序

錯誤：⑻

38、一個確定的有窮自動機DFA是一個

A.五元組(KZf,S,Z)

B.四元組(VN,VLP5)

C.四元組(K,Z,f,S)

D.三元組(VN,VT,P)

錯誤：【A】

39、在編譯過程中，如果遇到錯誤應該

A.把錯誤理解成局部的錯誤

B.對錯誤在局部范圍內進行糾正，繼續(xù)向下分析

C.當發(fā)現(xiàn)錯誤時，跳過錯誤所在的語法單位繼續(xù)分析下去

D.當發(fā)現(xiàn)錯誤時立即停止編譯，待用戶改正錯誤后再繼續(xù)編譯

錯誤：【O

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

A.表達式

B.產(chǎn)生式

C.單詞

D.語句

錯誤：⑹

一、簡答(每題參考分值5分)

1、設M=({x,y},{a,b},f,x,{y})為一非確定的有限自動機,其中f定義如

f(xsa)={xsy}f{x,b}={y}

f{y5b}={x,y}

下：試構造相應的確定有限自動機M‘(即：DFAM')。

正確答案:解:對照自動機的定義M=(S,2,f,So,Z),由f的定義可知f(x,a)、

f(y,b)均為多值函數(shù)，因此M是一非確定有限自動機。先畫出NFAM相應的

狀態(tài)圖，如下圖所示。

(正確得2分)

用于集法構造狀態(tài)轉換矩陣，如下表所示。(下面正確得6分)

ILh

{X}{x,y}{y}

{y}—{x,y)

{x，a{x,y}{x?y)

將轉換矩陣中的所有子集重新命名，形成下表所示的狀態(tài)轉換矩陣，即得到

(注意：本題由于集合的命名和先后順序不同，可能最終結果不同。)

2、對于文法G[S]：S-(L)|aS|aL-L,S|S寫出上述句型的所有短語、直接

短語、句柄和素短語。

G*一語:S、a、(a)、S,(a)%(S,(a))j(2分)”

如直施語：a、…(1分)/

6句標S3??(1分)d

正確答案：6素短語…??(1分八

3、將賦值語句X=a*b+c*(d+e*f/g)*h翻譯為相應的四元式。

正確答案：四元式：(1)(*,a,b,tl)(2)(*,e,f,t2)⑶(/,t2,

g,t3)(4)(+,d,t3,t4)(5)(*,c,t4,t5)(6)(*,t5,h,t6)(7)

(十,tl,t5,t6)(8)(=,t6,,x)

4、設有基本塊：Tl:=A+BT2:=5M:=T2*4T3:=C-DT4:=M+T3L:=T1*T3T4:=A+BN:=T4

畫出DAG圖；假設只有L,M,N在基本塊后面還要被引用，請寫出優(yōu)化后的代碼

序列。

正確答案：DAG(6分，每個父節(jié)點1分,合并節(jié)點1分)：

優(yōu)化后的四元

式為:(4分，每個1分)N:=A+B;M:=20;T3:=C-D;L:=N*T3

5、設有以下文法：G[S]：S-aAbDe|dA->BSD|eB^SAc|cD|eD-*Se|e求出

該文法的每一個非終結符的FOLLOW集。

正確答案：FOLLOW(S)=FIRST(D)UFIRST(Ac)UFIRST(e)

U{#}={a,d}U{a,d,c,e}U{e}U{#}={a,c,d,e#}FOLLOW(A)=FIRST(bDe)

UFIRST(c)={b,c}FOLLOW(B)=FIRST(SD)={a,d}FOLLOW(D)=FIRST

(e)UFOLLOW(A)UFOLLOW(B)={e}U{b,c}U{a,d}={a,b,c,d,e}

6、對于文法G[S]：S-Sa|aTfT-fSd|f|fSa構造識別其規(guī)范句

型所有活前綴的DFA；說明該文法是何種LR文法,并給出其相應的LR分析表。

正確答案：將文法拓廣為：G'[S']：(0)S'fS(l)S->Sa(2)S-aTf

(3)T->fSd(4)T->f(5)T-fSaDFA：

因為上述DFA的I、?r、I態(tài)集中有移進-歸約沖突和歸約-歸約沖突，所以該文法不是

LR(O)文法。L

對于I中：,歸約項目宓?移進項目S—S.aw

而：{a}-n?FOLLOY(交.,)=?{a}-C?{#}?=g

對于I中：,歸約項自T-*f-移進項自S->.aI*

而：{a}?C?FOLLOWT)=?{a}?C?{f}?=W

對于［中：?歸約項目T-*fSa--歸約項目S-*Sa.

而：FOLLOV(T-Cl-FOLLOW(S)=-{f}-A?{#,a<!?}?=6

所以可用SLR(l)方法解決L、?1、工的沖突。所以該文法是SLR⑴文法。??(2分).

ACTION^GOM

狀心*丸g

0/皿

Id83P^￡r'd

2ddSsv4〃

3-okod

跖1do

5-s2~7

6/w丁

13Sgdd

8-y?Jd

9-

SLR(l)分析表:ri"*

7、已知文法G：S-*(LaLS,L|)判斷是不是LL(1)文法，如

果是請構造文法G的預測分析表，如果不是請說明理由。

正確答案：【解】1)求各非終結符的FISRT集和FOLLOW集：(正確得4

First(S)={(,a}

FIRST(L)={)FIRST(S)={(,),a}

FOLLOW(S)={,#}

FOLLOW(L)=FOLLOW⑸={,#}

FIRST((L)G{a}二6

FIRST(S,L)A{)}=<P

分)所以是LL(1)文法(正確得2分)

2)預測分析表：(正確得4分)

}#

(a9

SS-*(LSfa

LLfS,LLfS,LLf)

L(G)={ab1|j>i>l)

8、給出下面語言的上下文無關文法。

正確答案：上下文無關文法G[S]為：G[S]：S-aSb|Sb|b

9、基本塊的DAG右圖所示。若b在該基本塊出口處活躍，請給出下列代碼經(jīng)過

優(yōu)化之后的代碼：(1)a=b+c(2)b=a-d(3)c=b+c(4)d=a-d

正確答案：當b在出口活躍時，生成優(yōu)化后的代碼為a=bO+cOb=a-dOd=b

c=d+cO

10、設文法G(S)：S-(L)|aS|aL-L,S|S消除左遞歸和

提取左公因子；

S->(L)|aS'

S'—S|￡

L—SL'

正確答案：(消除左遞歸正確得3分,提取左公因子正確得2分)L--SL'|E

二、單選(每題參考分值2.5分)

11、遞歸下降分析法和預測分析法要求描述語言的文法是__o

A.正規(guī)文法

B.LR(O文法)

C.LL(1)文法

D.右線性文法

錯誤：【C】

12、文法G所描述的語言是的集合。

A

文法G的字母表V中所有符號組成的符號串

B

文法G的字母表V的閉包V*中的所有符號串

c

由文法的開始符號推出的所有終結符串

D

由文法的開始符號推出的所有符號串

錯誤：【C】

13、一個確定的有窮自動機DFA是一個

A.五元組(K,2,f,S,Z)

B.四元組(VN,VT,P,S)

C.四元組(K,S,f,S)

D.三元組(VN,VT,P)

錯誤：【A】

14、若a為終結符，則A-a?aB是—項目。

歸約

A.移進

BC.

收

接

約

D.待

錯誤：【B】

15、設有如圖所示的有窮自動機。其中狀態(tài)①為初態(tài)，狀態(tài)⑤為終態(tài)。假設digit

代表數(shù)字0到9。則下述實數(shù)中可被該有窮自動機接受。

ea

A.+123

B.一1.

C.6

D.一11.47

錯誤：【D】

16、設有文法G[S]為：Sfa|b|(A)AfSdA|S則FIRSTVT(S)二

A.{a,b,()

B.{a,b,))

C.{a,b,(,)}

D.{a,b,d)

錯誤：【A】

17、有文法G及其語法制導翻譯的屬性文法如下所示(語義規(guī)則中的*和+分別是

???EfE'A{E.val,=,E.val??,T.val}一

???EfT.............{E.val,=,T.val}.

??T#?!!????{T.val,=,T1.val-+-n.val,}

,?,T~~*,,n.............{T.val,=,n.val}y

常規(guī)意義下的算術運算符)：則分析句子1.八.2?八?3嘛?4其值為.......--

A.10

B.34

C.14

D.54

錯誤：【C】

18、用高級語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫

A.源程序

B.目標程序

C.連接程序

D.解釋程序

錯誤：【B】

19、在編譯過程中，如果遇到錯誤應該

A

把錯誤理解成局部的錯誤

B

對錯誤在局部范圍內進行糾正，繼續(xù)向下分析

c

當發(fā)現(xiàn)錯誤時，跳過錯誤所在的語法單位繼續(xù)分析下去

D

當發(fā)現(xiàn)錯誤時立即停止編譯，待用戶改正錯誤后再繼續(xù)編譯

錯誤：【C】

20、編譯程序前三個階段完成的工作是

A

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

B

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

c

訶法分析、語法分析、語義分析和中間代碼生成

D

詞法分析、語法分析和代碼生成

錯誤：【c】

21、編譯過程中，詞法分析階段的任務是

A.識別表達式

B.識別語言單詞

C.識別語句

D.識別程序

錯誤：【B】

22、文法G[S]：S->ab|aSb,該文法所描述的語言

A.L(G[S])={anbn|n^O]

B.L(G[S])={ambn|m,n20}

C.L(G[S])={anbn|n'l}

D.L(G[S])={ambn|田，n21}

錯誤：【c】

23、LR語法分析棧中存放的狀態(tài)是識別文法規(guī)范句型___的DFA狀態(tài)。

前綴

AR.

活前

綴

C句柄

D.

24、文法不是LL(1)的。

A.遞歸

B.右遞歸

C.2型

D.含有公共左因子的

錯誤：【D】

25、中綴表達式a+b*(c+d)的逆波蘭表示是

A.abcd+*+

B.abcd+*+

C.abc+*d+

D.a+bc*d+

錯誤：【A】

26、下列符號串不可以由符號集S={a,b}上的正閉包運算產(chǎn)生的是:

A.￡

B.a

C.aa

D.ab

錯誤：【A】

27、無符號常數(shù)的識別與拼數(shù)工作通常在一階段完成。

A.語法分析

B.語義分析

C.詞法分析

D.代碼優(yōu)化

錯誤：【口

?S-->.xxW......................print-"1”，

?s.T.y.........................print--"2”?

28、已知屬性文法G[S]:?敦...........PHnt?,”3〃?則若輸入

“xxxxyzz”,文法將輸出___o

A.11233

B.23131

C.11231

D.33211

錯誤：【B】

29、不可能是目標代碼。

A

匯編指令代碼

B

可重定位指令代碼

c

絕對指令代碼

D

中間代碼

錯誤：【D】

30、已知文法G[S]為：S->a己知T)T->T,S|S則G[S]的FIRSTVT(S)為

A.{a-(}

B.{「)}

C.(a?(,}

D.{a'),1

錯誤：【A】

31、在產(chǎn)生式中，符號“一”（"：：=”）表示

A.等于

B.恒等于

C.取決于

D.定義為

錯誤：【D】

32、若源程序是用高級語言編寫的程序，目標程序是—,則其翻譯程序稱為編

譯程序。

A.匯編語言程序或高級語言程序

B.高級語言程序或機器語言程序

C.匯編語言程序或機器語言程序

D.連接程序或運行程序

錯誤：【C】

33、自底向上語法分析法的原理是

A.“移進一一推導法”

B.“最左推導法”

C.“移進一一歸約法”

D.“推導一一歸約法”

錯誤：【c】

34、在狀態(tài)轉換圖中，結點代表,用圓圈表示。

A.輸入緩沖區(qū)

B.向前搜索

C.字符串

D.狀態(tài)

錯誤：【D】

35、不能被如下狀態(tài)轉換圖識別的句子是

A

aOb

B

alOlOb

c

bOOb

D

ab

錯誤：【D】

36、同正規(guī)式(a|b)*等價的正規(guī)式為

A.(a|b)+

B.a*|b*

C.(ab)*

D.(a*|b*)+

錯誤：【B】

37、如果文法G是無二義的，則它的任何句子Q

A

最左推導和最右推導對應的語法樹必定相同

B

最左推導和最右推導對應的語法樹可能不同

c

最左推導和最右推導必定相同

D

可能存在兩個不同的最左推導，但它們對應的語法樹相同

錯誤：【A】

38、編譯程序的語法分析器接受以—為單位的輸入，并產(chǎn)生有關信息供以后各

階段使用。

表達式

九

式

產(chǎn)生

BC.

單詞

D.語句

錯誤：【C】

39、正規(guī)式M1和M2等價是指—

A.Ml和M2的狀態(tài)數(shù)相等

B.Ml和M2的有向邊條數(shù)相等

C.Ml和M2所識別的語言集相等

D.Ml和M2狀態(tài)數(shù)和有向邊條數(shù)相等

錯誤：【C】

40、Chomsky把文法分成四種類型，即0型、1型、2型和3型。1型文法也稱為

A

上下文無關文法

B

上下文有關文法

c

正規(guī)文法

D

短語文法

錯誤：【B】

41、正規(guī)式的運算符“*”讀作

A.或

B.連接

C.閉包

D.乘

錯誤：【C】

42、設有文法G［法:S-Sl|S0|Sa|Sc|a|b|c,下列符號串中是該文法的句子有

A

abO

B

aOcOl

c

aaab

D

bcblO

錯誤：【B】

43、詞法分析器的輸出結果是一

A.單詞的種別碼

B,單詞組符號表中的位置

C.單詞的種別碼和單詞的巨身值

D.單詞的自身值

錯誤：【C】

44、在規(guī)范歸約中，用來刻劃可歸約串。

A.直接短語

B.句柄

C.最左素短語

D.素短語

錯誤：【B】

45、文法G所描述的語言是的集合。

A.文法G的字匯表V中所有符號組成的符號串

B.文法G的字匯表V的閉包組成的所有符號串

C.由文法的識別符號推出的所有符號串

D.由文法的識別符號推出的所有終結符號串

錯誤：【D】

46、設G是一個給定的文法，S是文法的開始符號，如果S3x（其中xWV）,則稱x

是文法G的一個—o

候選

式

A.

R句型

C產(chǎn)生

式

單詞

D.

錯誤:[B]

47、在目標代碼生成階段，符號表用于

A.詞法檢查

B.語義檢查

C.語法檢查

D.地址分配

錯誤：【D】

48

、是一種典型的解釋型語言。

A.BASIC

BC.C

FORTRAN

D.PASCAL

錯誤：【A】

49、若狀態(tài)k含有項目“Afa.”,對任意非終結符a,都用規(guī)則“A-Q”歸

約的語法分析方法是o

A.LALR分析法

B.L