編譯技術復習題

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

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

L自下而卜的語法分析中，應從一開始分析。

A.句型

B.句子

C.以單詞為單位的程序

D.文法的開始符

錯誤：[B；D]

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

A.單詞的種別編碼

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

C.單詞名

D.單詞自身值

錯誤:[A;D]

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

A.多種推導過程

B.多種最左推導過程

C.僅一種推導過程

D.一種最左推導過程

錯誤：【A;D】

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

A.保留字

B.運算符

C.逆波蘭式

D.常數

錯誤：【A;B;D】

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

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

A.模擬執行器

B.解釋器

C.表格處理

D.出錯處理

錯誤：【GD】

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

A.源代碼

B.匯編語言代碼

C.中間代碼

D.可重定位代碼

錯誤：[B;D]

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

+T*F的素短語是一o

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］所規定的動作包括。

A.編輯

B.編譯

C.連接

D.運行

錯誤：【A;B;C】

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

A.詞法錯誤

B.語法錯誤

C.編譯錯誤

D.語義錯誤

錯誤：[A;B;D]

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

11、確定的自動機以及不確定的自動機都能正確地識別正規集。

A.正確

B.錯誤

錯誤：[A]

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

A.正確

B.錯誤

錯誤：[A]

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

A.正確

B.錯誤

錯誤：【A】

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

A.正確

B.錯誤

錯誤:⑻

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

A.正確

B.錯誤

錯誤：⑻

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

A.正確

B.錯誤

錯誤：【A】

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

A.正確

B.錯誤

錯誤：[A]

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

器的利用效率。

A.正確

B.錯誤

錯誤：[A]

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

A.正確

B.錯誤

錯誤：[B]

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

A.正確

B.錯誤

錯誤:[B]

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

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

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

B.四元組(VN,VTRS)

C.四元組(KZf,S)

D.三元組(VNfVT,P)

錯誤：[A]

22、在產生式中，符號"一表示

A.等于

B.恒等于

C.取決于

D.定義為

錯誤：【D】

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

A.abcd+*+

B.abcd+*+

C.abc+*d+

D.a+bc*d+

錯誤：【A】

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

A.遞歸

B.右遞歸

C.2型

D.含有公共左因子的

錯誤：[D]

25、設有如圖所示的有窮自動機.其中狀態①為初態，狀態⑤為終態。假設digit代表數字

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

A.+123

B.-1.

C.6

D.-11.47

錯誤：[D]

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

A.歸約

B.移進

C.接收

D.待約

錯誤：[B]

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

A.語法分析

B.語義分析

C.詞法分析

D.代碼優化

錯誤：【C】

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

A.正規文法

B.LR（O文法）

c.LL(1)文法

D.右線性文法

錯誤：【C】

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

??,E-*El，*A'T*{E.val,=?￡.val,*,T.val}一

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

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

??,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、不能被如下狀態轉換圖識別的句子是

A.aOb

B.alOlOb

C.bOOb

D.ab

錯誤：[D]

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

A.￡

B.a

C.aa

D.ab

錯誤：【A】

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

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

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

C.當發現錯誤時，跳過錯誤所在的語法單位繼續分析下去

D.當發現錯誤時立即停止編譯，待用戶改正錯誤后再繼續編譯

錯誤：【。

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

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

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

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

D.連接程序或運行程序

錯誤：⑹

,S>—>.xwxvWws......................p?rint??"1"一

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

35、已知屬性文法G【S]:煞..............Print??“3”?則若輸入“xxxxyzz”，

文法將輸出

A.11233

B.23131

C.11231

D.33211

錯誤：⑻

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

A.表達式

B.產生式

C.單詞

D.語句

錯誤：【。

37、在狀態轉換圖中，結點代表用圓圈表示。

A.輸入緩沖區

B.向前搜索

C.字符串

D.狀態

錯誤：【D】

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

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

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

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

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

錯誤：⑹

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

A.{aA(}

B.{aA))

C.{a(J

D.{a}

錯誤：[A]

40、如果文法G是無二義的，則它的彳不可句子a。

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

B.最蝴爭口最右推導對應的語法樹可能不同

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

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

錯誤：[A]

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

1、設有文法G[S]為：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.常數

錯誤：【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(3)T-T*F⑷T-F(5)F-(E)⑹F-a句型a

+T*F的素短語是一。

A.a

B.T

C.a+T

D.T*F

錯誤：[A;D]

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

A.+?>(

B.+>>+

C.+?>)

D.(?>)

錯誤：[B;C]

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

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

A.模擬執行器

B.解釋器

C.表格處理

D.出錯處理

錯誤：【C;D】

10、每一項ACTION[S,a]所規定的動作包括.

A.編輯

B.編譯

C.連接

D.運行

錯誤：【A;B;C】

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

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

A.正確

B.錯誤

錯誤：[B]

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

A.正確

B.錯誤

錯誤：⑻

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

A.正確

B.錯誤

錯誤：【A】

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

A.正確

B.錯誤

錯誤：【A】

15、設有個LR(0)項目集1={X-aBp,A->a.},該項目集含有“歸約?歸約"沖突。

A.正確

B.錯誤

錯誤：⑻

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

A.正確

B.錯誤

錯誤：[B]

17、自動機M和M'的狀態數不同，則二者必不等價。

A.正確

B.錯誤

錯誤：[B]

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

A.正確

B.錯誤

錯誤:⑻

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

A.正確

B.錯誤

錯誤：【A】

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

A.正確

B.錯誤

錯誤:⑻

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

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

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、編譯程序的語法分析器接受以—為單位的輸入，井產生有關信息供以后各階段使用。

A.表達式

B.產生式

C.單詞

D.語句

錯誤：【C】

24、LR語法分析棧中存放的狀態是識別文法規范句型—的DFA狀態。

A.前綴

B.活前綴

C.句柄

D.LR(0)項目

錯誤：[B]

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

A.詞法分析、語法分析和代碼優化

B.代碼生成、代碼優化司法分析

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

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

錯誤：[C]

?S?-?.xxW..........print*?“1”P

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

26、已知屬性文法G【S】:kf煞..............口久班一“3”?則若輸入“xxxxyzz"

文法將輸出一O

A.11233

B.23131

C.11231

D.33211

錯誤：[B]

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

A.abcd+*+

B.abcd+*+

C.abc+*d+

D.a+bc*d+

錯誤：【A】

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

A.語法分析

B.語義分析

C.詞法分析

D.代碼優化

錯誤：[C]

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

A.正規文法

B.LR(O文法)

C.LL(1)文法

D.右線性文法

錯誤：[C]

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

A.匯編指令代碼

B.可重定位指令代碼

C.絕對指令代碼

D.中間代碼

錯誤：【D】

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

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

???Ef「.......{E.val-=,T.val}"

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

???T-??n............{T.val,=-n.val}^

下的算術運算符).則分析句子1?八?2??其值為........。,

A.10

B.34

C.14

D.54

錯誤：[C]

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

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

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

C.當發現錯誤時，跳過錯誤所在的語法單位繼續分析下去

D.當發現錯誤時立即停止編譯,待用戶改正錯誤后再繼續編譯

錯誤：⑹

33、已知文法G[S]為：S->ap|(T)T->T,S|S則G[S]的FIRSTVT(S)為一。

A.{a^()

B.{a人)}

C.{aMJ

D.{a八)，}

錯誤：[A]

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

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

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

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

D.連接程序或運行程序

錯誤：⑹

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

A."移進~推導法”

B."最左推導法"

C."移進一歸約法”

D."推導——歸約法”

錯誤：⑹

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

A.￡

B.a

C.aa

D.ab

錯誤：[A]

37、若a為終結符，則A-ocaR是一項目。

A.歸約

B.移進

C.接收

D.待約

錯誤：［B］

38、設有文法G［法為:STa|b|(A)A-SdA|S則FIRSTVT(S)=

A.{a,b,(}

B{ab)}

C.{a,b,(,))

D.{a,b,d}

錯誤：【A】

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

A.識別表達式

B.識別語言單詞

C.識別語句

D.識別程序

錯誤:⑻

40、一文法不是LLQ)的。

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、源程序中的錯誤f有_____0

A.詞法錯誤

B.語法錯誤

C.編譯錯誤

D.語義錯誤

錯誤：【A;B;D】

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

A.句型

B.句子

C.以單詞為單位的程序

D.文法的開始符

錯誤：[B;D]

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

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

A.模擬執行器

B.解釋器

C.表格處理

D.出錯處理

錯誤：[C;D]

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

A.源代碼

B.匯編語言代碼

C.中間代碼

D.可重定位代碼

錯誤：[B;D]

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

A.保留字

B.運算符

C.逆波蘭式

D.常數

錯誤：[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⑸包含的終結符有:

A.a

B.b

C.)

D.(

錯誤：【A;B;C】

9、下列優化中，屬于循環優化的有

A.強度削弱

B.合并已知量

C.刪除歸納變量

D.代碼外提

錯誤：【A;C;D】

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

A.+?>(

B.+->+

C.+.>)

D.(?>)

錯誤：【B;C】

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

11、一個有限狀態自動機中，有且僅有一個唯一終態。

A.正確

B.錯誤

錯誤：[B]

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

A.正確

B.錯誤

錯誤：【A】

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

A.正確

B.錯誤

錯誤:⑻

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

A.正確

B.錯誤

錯誤：⑻

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

A.正確

B.錯誤

錯誤：【A】

16、產生式是用于定義詞法成分的一種書寫規則。

A.正確

B.錯誤

錯誤：[B]

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

A.正確

B.錯誤

錯誤：[B]

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

A.正確

B.錯誤

錯誤：【B】

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

A.正確

B.錯誤

錯誤：【A】

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

A.正確

B.錯誤

錯誤：【A】

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

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

A.正規文法

B.LR（0文法）

C.LL（1）文法

D.右線性文法

錯誤:[C]

22、無符號常數的識別與拼數工作通常在一階段完成.

A.語法分析

B.語義分析

C.詞法分析

D.代碼優化

錯誤：【O

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

A."移~導法"

B."最左推導法”

C.“移進一歸約法"

D."推導一歸約法”

錯誤：

24、用高級語言編寫的程序經編譯后產生的程序叫_____

A.源程序

B.目標程序

C.連接程序

D.解釋程序

錯誤：[B]

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

A.匯編指令代碼

B.可重定位指令代碼

C.絕對指令代碼

D.中間代碼

錯誤：[D]

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

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

A.+123

B.-1.

C.6

D.—11.47

錯誤：【D】

27、如果文法G是無二義的,則它的fiH可句子a

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

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

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

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

錯誤：【A】

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

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

??T..............{E.val?=?T.val}"

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

???T-??n..............{T.val,=,n.val）*j

下的算術運算符）,則分析句子l-A-2-A-3-?-4其值為........。

A.10

B.34

C.14

D.54

錯誤：[C]

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

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

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

C.當發現錯誤時，跳過錯誤所在的語法單位繼續分析下去

D.當發現錯誤時立即停止編譯，待用戶改正錯誤后再繼續編譯

錯誤：⑹

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、同正規式(a|b)*等價的正規式為

A.(a|b)+

B.a*|b*

C.(ab)*

D.(a*|b*)+

錯誤:⑻

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

A.五元組(K￡fSZ)

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

C.四元組(KZf,S)

D.三元組(VN,VT尸)

錯誤：[A]

34、設有文法G[S]為：S-a|b|(A)A-SdA|S貝UFIRSTVT(S)=

A.{a,b,(}

B.{a,b,))

C.{a,b,C)}

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.由文法的開始符號推出的所有符號串

錯誤：【C】

38、不能被如下狀態轉換圖識別的句子是

A.aOb

B.alOlOb

C.bOOb

D.ab

錯誤：【D】

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

A.輸入緩沖區

B.向前搜索

C.字符串

D.狀態

錯誤：[D]

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

A.表達式

B.產生式

C.單詞

D.語句

錯誤：[C]

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

1、每一項ACTIONS,a]所規定的動作包括。

A.編輯

B.編譯

C.連接

D.運行

錯誤:[A;B;C]

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

A.多種推導過程

B.多種最左推導過程

C.僅一種推導過程

D.一種最左推導過程

錯誤：[A;D]

3、源程序中的錯誤有一o

A.詞法錯誤

B.語法錯誤

C.編譯錯誤

D.語義錯誤

錯誤：[A;B;D]

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

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

A.模擬執行器

B.解釋器

C.表格處理

D.出錯處理

錯誤：[C;D]

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

A.保留字

B.運算符

C.逆波蘭式

D.常數

錯誤：[A;B;D]

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

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、算符優先文法G[E]:EE+T,T(E)|i,則關于優先級的判斷正確的是一。

A.+?>(

B.+?>+

€.+?>)

D.(?>)

錯誤：【BQ

9、對于文法G[E]:(1)E-E+T⑵E-T(3)T-T*F⑷T-F(5)F一(E)⑹F-a句型a

+T*F的素短語是一。

A.a

B.T

C.a+T

D.T*F

錯誤：[A;D]

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

A.單詞的種別編碼

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

C.單詞名

D.單詞自身值

錯誤：[A;D]

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

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

A.正確

B.錯誤

錯誤：【A】

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

A.正確

B.錯誤

錯誤：[B]

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

A.正確

B.錯誤

錯誤：[B]

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

A.正確

B.錯誤

錯誤：[B]

15、一個有限狀態自動機中，有且僅有一個唯一終態。

A.正確

B.錯誤

錯誤：【B】

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

A.正確

B.錯誤

錯誤:[A]

17、每個句子都有規范推導；每個句型都有規范推導。

A.正確

B.錯誤

錯誤：【A】

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

A.正確

B.錯誤

錯誤：⑻

19、進行代碼優化口寸應著重考慮循環的代碼優化，這對提高目標代碼的效率將起更大作用。

A.正確

B.錯誤

錯誤：【A】

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

A.正確

B.錯誤

錯誤：[B]

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

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

A.(a|b)+

B.a*|b*

C.(ab)*

D.(a*|b*)+

錯誤：【B】

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

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

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

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

D.連接程序或運行程序

錯誤：[C]

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

A.匯編指令代碼

B.可重定位指令代碼

C.絕對指令代碼

D.中間代碼

錯誤：[D]

24、無符號常數的識別與拼數工作通常在一階段完成.

A.語法分析

B.語義分析

C.詞法分析

D.代碼優化

錯誤：【。

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

A.詞法分析、語法分析和代碼優化

B.代碼生成、代碼優依Di司法分析

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

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

錯誤：

26、在狀態轉換圖中，結點代表一,用圓圈表示。

A.輸入緩沖區

B.向前搜索

C.字符串

D.狀態

錯誤：【D】

27、在產生式中，符號"一"（"::="）表示一

A.等于

B.恒等于

C.取決于

D.定義為

錯誤：[D]

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

A.正規文法

BLR(O文法)

C.LL(1)文法

D.右線性文法

錯誤：[C]

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

A.識別表達式

B.識別語言單詞

C.識別語句

D.識別程序

錯誤：⑻

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

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

ea

A.+123

B.-1.

C.6

D.—11.47

錯誤：【D】

31、不能被如下狀態轉換圖識別的句子是—o

A.aOb

B.alOlOb

C.bOOb

D.ab

錯誤：[D]

32、LR語法分析棧中存放的狀態是識別文法規范句型—的DFA狀態。

A.前綴

B.活前綴

C.句柄

D.LR(0)項目

錯誤:⑻

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

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

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

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

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

錯誤：[A]

34、設有文法G［法為:STa|b|(A)A-SdA|S則FIRSTVRS)=

A.{a,b,(}

B.{a,b,)}

C.{a,b,C)}

D.{a,b,d}

錯誤：【A】

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

A.歸約

B.移進

C.接收

D.待約

錯誤:⑻

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

A.abcd+*+

B.abcd+*+

C.abc+*d+

D.a+bc*d+

錯誤：［A］

37、用高級語言編寫的程序經編譯后產生的程序叫—。

A.源程序

B.目標程序

C.連接程序

D.解釋程序

錯誤：[B]

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

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

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

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

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

錯誤：[A]

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

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

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

C.當發現錯誤時，跳過錯誤所在的語法單位繼續分析下去

D.當發現錯誤時立即停止編譯，待用戶改正錯誤后再繼續編譯

錯誤：【C】

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

A.表達式

B.產生式

C.單詞

D.語句

錯誤：【C】

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

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

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

f(y,a)=Sf{y:b}={x,y}

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

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

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

狀態圖，如下圖所示。

(正確得2分)

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

Ih

{X}{x,y}{y}

一{&y}

{x,y}{&y}

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

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

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

短語、句柄和素短語。

。矩語:s、a、（a）、S,（a）、⑸（3））3（2分）〃

如lifts語;a、S3…（1分）d

句柄:S3??（1分）d

正確答案：6素矩語…Ti分）”

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、設有基本塊：T1:=A+BT2:=5M:=T2木4T3:=C-DT4:=M+T3L:=T1率T3T4:=A+BN:=T4

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

序列。

正確答案：DAG（6分，每個父節點1分，合并節點1分）：

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

5、設有以下文法：G[S]：SfaAbDeldAfBSDleBfSAc|cD|eD-*Se|￡求出

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

正確答案:FOLLOW(S)=FIRST(D)UFIRST(Ac)UFIRST(c)

U{#}={a,d}U{a,d,c,e}U{e}U{#}={a,c,d,e4}FOLLOW(A)=F1RST(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構造識別其規范句

型所有活前綴的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、?I、U態集中有移進-歸約沖突和歸約-歸約沖突，所以該文法不是

LR(O)文法。y

對于I中：,歸約項目￡:*<??移進項目S—S?a?j

而：{a}-Cl-FOLLOW(S^z)=-{?}?『?{#}?=■

對于I中：,歸約項自T-*f-移進項自S—.揖］身

而：{a}-Cl-FOLLOV(T)=-{a}-A-{f}-=0^

對于I中：?歸約項目Tif§2??歸約項目S-*Sa.-4J

而:FOLLOW(T-A-FOLLOW(S)=?{f}?Cl?{?#,?a?d?}?=0)“

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

ACTION^com

狀萄a*-'dvSvT.

0,oIP?J

1，卬u升’

2,s§一4<

3，rWri"

4,o

5-如口o“?

6?丁

7，Sg0oa

8/oo/

9，r**

SLR(1)分析表:

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

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

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

First(S)={(,a}

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

FOLLOW(S)={,#}

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

FIRST((DA{a}=<t>

FIRST(S,L)A{)}=<t>

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

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

一

(a9}

SSf(LSfa

LLfS,LLfS,LLf)

L(G)={ab,

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

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

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

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

正確答案：當b在口口活躍時，生成優化后的代碼為a=bO)cOb=adOd=b

c=d+cO

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

提取左公因子；

S—(L)aS，

S'-S|￡

L—SL'

正確答案：(消除左遞歸正確得3分，提取左公因子正確得2分)U-SL除

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

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

A.正規文法

B.LR(O文法)

C.LL(1)文法

D.右線性文法

錯誤：【C】

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

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

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

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

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

錯誤：【C】

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

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

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

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

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

錯誤：【A】

14、若a為終結符，則A-a-a0是一項目。

歸約

進

A.移

B.

C收

接

約

D.待

錯誤：【B】

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

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

A.+123

B.一1.

C.6

D.一11.47

錯誤：【D】

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

A.(a,b,()

B.{a,b,))

C.{a,b,(,)}

D.(a,b,d}

錯誤：【A】

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

???EfE?八?「{E.val,=,E.val???T.

???EfT.............{E.val-=,T.val}<j

?..T—?TS-n-,,?{T.val-=-T.val-+-n.val,}P

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

常規意義下的算術運算符)：則分析句子1.八2八?3?#?4其值為.......。'

A.10

B.34

C.14

D.54

錯誤：【C】

18、用高級語言編寫的程序經編譯后產生的程序叫_____o

A.源程序

B.目標程序

C.連接程序

D.解釋程序

錯誤：【B】

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

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

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

C.當發現錯誤時，跳過錯誤所在的語法單位繼續分析下去

D,當發現錯誤時立即停止編譯，待用戶改正錯誤后再繼續編譯

錯誤：【C】

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

A.詞法分析、語法分析和代碼優化

B.代碼生成、代碼優化和詞法分析

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

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

錯誤：【C】

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

A.識別表達式

B.識別語言單詞

C.識別語句

D.識別程序

錯誤：【B】

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

A.L(G[S])={anbn|n20}

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

C.L(G[S])={anbn|n21}

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

錯誤：【C】

23、LR語法分析棧中存放的狀態是識別文法規范句型的DFA狀態。

A.前綴

B.活前綴

C.句柄

D.LR(0)項目

錯誤：

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}上的正閉包運算產生的是:

A.￡

B.a

C.aa

D.ab

錯誤：【A】

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

A.語法分析

B.語義分析

C.詞法分析

D.代碼優化

錯誤：【口

?S.T.xVWxWK.......................p*rint--“1”"

?S-->.y...........................print--“2”?

28、已知屬性文法G[S]:基............Print-"3”.則若輸入

“xxxxyzz”，文法將輸出____o

A.11233

B.23131

C.11231

D.33211

錯誤：【B】

29、不可能是目標代碼。

A.匯編指令代碼

B.可重定位指令代碼

C.絕對指令代碼

D.中間代碼

錯誤：【D】

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

A.{a'()

B.{a'))

C.{a'(,}

D.{a-),}

錯誤：【A】

31、在產生式中，符號“一”（"：：=”）表示—

A.等于

B.恒等于

C.取決于

D.定義為

錯誤：【D】

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

譯程序。

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

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

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

D.連接程序或運行程序

錯誤：【C】

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

移進

推

“

法

A.最左

推導

B.“

C移進

”歸約法”

推導

D.”歸約法”

錯誤：【c】

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

A.輸入緩沖區

B.向前搜索

C.字符串

D.狀態

錯誤：【D】

35、不能被如下狀態轉換圖識別的句子是

A.aOb

B.alOlOb

C.bOOb

D.ab

錯誤：【D】

36、同正規式(a|b)x等價的正規式為

A.(a|b)+

B.a*|b*

C.(ab)*

D.(a*|b*)+

錯誤：3

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

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

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

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

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

錯誤：【A】

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

階段使用。

A.表達式

B.產生式

C.單詞

D.語句

錯誤：【C】

39、正規式M1和M2等價是指

A.Ml和M2的狀態數相等

B.Ml和卜12的有向邊條數相等

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

D.Ml和M2狀態數和有向邊條數相等

錯誤：

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

A.上下文無關文法

B.上下文有關文法

C.正規文法

D.短語文法

錯誤：[B]

41、正規式的運算符讀作

A.或

B.連接

C.閉包

D.乘

錯誤：【C】

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

A.abO

B.aOcOl

C.aaab

D.bcblO

錯誤：【B】

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

A.單詞的種別碼

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

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

D.單詞的自身值

錯誤：【C】

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

A.直接短語

B.句柄

C.最左素短語

D.素短語

錯誤：【B】

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

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

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

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

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

錯誤：【D】

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

是文法G的一個。

選

候

式

型

A.句

B.

生

C產

式

詞

D.單

錯誤：【B】

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

A.詞法檢查

B.語義檢查

C.語法檢查

D.地址分