一、單項(xiàng)選擇題

1.構(gòu)造編譯程序應(yīng)掌握oD

a.源程序b.目標(biāo)語(yǔ)言

c.編譯方法d.以上三項(xiàng)都是

2.編譯程序絕大多數(shù)時(shí)間花在±oD

a.出錯(cuò)處理b.詞法分析

c.目標(biāo)代碼生成d.表格管理

3.DFAM（見(jiàn)圖17）接受的字集為oD

a.以0開(kāi)頭的二進(jìn)制數(shù)組成的集合

b.以0結(jié)尾的二進(jìn)制數(shù)組成的集合

C.含奇數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合

d.含偶數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合

4.-a-(b*c/(c-d)+(-b)*a)的逆波蘭表示是o（@代表后綴式中

的求負(fù)運(yùn)算符）C

a.abc*cd_b@a*+/_@b.a@bc*cd-b@a*+/—

a@bc*cd-/b@a*4-d.a@bc*/cd-b@a*+_

5.在規(guī)范歸約中，用來(lái)刻畫(huà)可歸約串。B

a.直接短語(yǔ)b.句柄

c.最左素短語(yǔ)d.素短語(yǔ)

6.若B為非終結(jié)符，則ATa-BB為項(xiàng)目。D

a.歸約b.移進(jìn)

c.接受d.待約

7.中間代碼生成時(shí)所依據(jù)的是oC

a.語(yǔ)法規(guī)則b,詞法規(guī)則

c.語(yǔ)義規(guī)則d.等價(jià)變換規(guī)則

8.有文法G及其語(yǔ)法制導(dǎo)翻譯如下所示（語(yǔ)義規(guī)則中的*和+分別是常規(guī)意

義下的算術(shù)運(yùn)算符）:

ETE⑴AT{E.val=E(1).val*T.val}

ETT{E.val=T.val)

TTT”)#n{T.vaI=T(1>.val+n.val}

TTn{T.vaI=n.vaI}

則分析句子1A2A3#4其值為oC

a.10b.34c.14d.54

9.如果文法G是無(wú)二義的，則它的任何句子aoA

a.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)必定相同

b.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)可能不同

c.最左推導(dǎo)和最右推導(dǎo)必定相同

d.可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語(yǔ)法樹(shù)相同

10.下列動(dòng)作中，不是自下而上分析動(dòng)作的是：―oB

a.移進(jìn)b.展開(kāi)

c.接受d.報(bào)錯(cuò)

11.編譯程序是對(duì)oD

a.匯編程序的翻譯b.高級(jí)語(yǔ)言程序的解釋執(zhí)行

c.機(jī)器語(yǔ)言的執(zhí)行d.高級(jí)語(yǔ)言的翻譯

12.詞法分析器的輸出結(jié)果是—oC

a,單詞的種別編碼b,單詞在符號(hào)表中的位置

c.單詞的種別編碼和自身值d.單詞自身值

13.正規(guī)式M1和M2等價(jià)是指oC

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

b.M1和M2的有向邊條數(shù)相等

c.M1和M2所識(shí)別的語(yǔ)言集相等

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

14.在規(guī)范歸約中，用來(lái)刻畫(huà)可歸約串。B

a.直接短語(yǔ)b,句柄

c.最左素短語(yǔ)d,素短語(yǔ)

15.若a為終結(jié)符，則ATa-aB為項(xiàng)目。B

a.歸約b.移進(jìn)

c.接受d.待約

16.語(yǔ)法分析時(shí)所依據(jù)的是oA

a.語(yǔ)法規(guī)則b.詞法規(guī)則

c.語(yǔ)義規(guī)則d.等價(jià)變換規(guī)則

17.文法G：STxSx|y所識(shí)別的語(yǔ)言是oC

a.xyxb.(xyx)*

c.xnyxn(nS^O)d.x*yx*

18.如果文法G是無(wú)二義的，則它的任何句子aoA

a.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)必定相同

b.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)可能不同

c.最左推導(dǎo)和最右推導(dǎo)必定相同

d,可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語(yǔ)法樹(shù)相同

19.下列動(dòng)作中，不是自上而下分析動(dòng)作的是：—oC

a.匹配b,展開(kāi)

c.移進(jìn)d.報(bào)錯(cuò)

20.詞法分析器的輸出結(jié)果是—oC

a.單詞的種別編碼b.單詞在符號(hào)表中的位置

c.單詞的種別編碼和自身值d.單詞自身值

21.-a-(b*c/(c-d)+(-b)*a)的逆波蘭表示是。(@代表后綴式

中的求負(fù)運(yùn)算符)C

C.便于優(yōu)化處理，節(jié)省存儲(chǔ)空間

d.節(jié)省存儲(chǔ)空間，不便于優(yōu)化處理

27.下列動(dòng)作中，不是自上而下分析動(dòng)作的是：oC

a.匹配b.展開(kāi)

c.接受d.報(bào)錯(cuò)

28.同正規(guī)式(a|b)+等價(jià)的正規(guī)式是Bo

A.(a|b)*B.(a|b)(a|b)*C.(ab)*(ab)D.(a|b)

I(a|b)*

29.稱有限自動(dòng)機(jī)A1和A2等價(jià)是指Do

A.A1和A2都是定義在一個(gè)字母表上的有限自動(dòng)機(jī)

B.A1和A2狀態(tài)數(shù)和有向邊數(shù)相等

C.A1和A2狀態(tài)數(shù)或有向邊數(shù)相等

D.A1和A2所能識(shí)別的字符串集合相等

30.由文法的開(kāi)始符號(hào)出發(fā)經(jīng)過(guò)若干步(包括0步)推導(dǎo)產(chǎn)生的文法符號(hào)

序列稱為Bo

A.語(yǔ)言B.句型C.句子D.句柄

31.在自上而下的語(yǔ)法分析中，應(yīng)從C開(kāi)始分析。

A.句型B.句子C.文法開(kāi)始符號(hào)D.句柄

32.一個(gè)文法G,若C,則稱它是LL(1)文法。

A.G中不含左遞歸B.G無(wú)二義性

C.G的LL(1)分析表中不含多重定義的條目D.G中產(chǎn)生式不含左公

因子

33.在規(guī)范歸約中，用B來(lái)刻畫(huà)可歸約串。

A.直接短語(yǔ)B.句柄C.素短語(yǔ)D.短語(yǔ)

34.若a為終結(jié)符，則ATa-a（3為B項(xiàng)目。

A.歸約B.移進(jìn)C.接受D.待約

35.中間代碼生成時(shí)所依據(jù)的是Co

A.詞法規(guī)則B.語(yǔ)法規(guī)則C.語(yǔ)義規(guī)則D.等價(jià)變換規(guī)

則

36.文法G[S]及其語(yǔ)法制導(dǎo)翻譯定義如下:

產(chǎn)生式語(yǔ)義動(dòng)作

S'TSprint(S.num)

ST(L)S.num=L.num+1

STaS.num=0

LTL⑴，SL.num=L(1).num+S.num

LTSL.num=S.num

若輸入為（a.（a））,且采用自底向上的分析方法，則輸出為C

A.0B.1C.2D.4

37.四元式之間的聯(lián)系是通過(guò)B實(shí)現(xiàn)的。

A.指示器B.臨時(shí)變量C.符號(hào)表D.程序變量

38.將編譯程序分成若干”遍二是為了（B）。

A.提高程序的執(zhí)行效率B.使程序的結(jié)構(gòu)更為清晰

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

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

39.一個(gè)編譯程序在編譯時(shí)，大多數(shù)時(shí)間花在（D）上。

A.出錯(cuò)處理B.詞法分析

C.目標(biāo)代碼生成D.表格管理及處理

40.下列符號(hào)串不可以由符號(hào)集E={a,b}上的正閉包運(yùn)算產(chǎn)生的是：(A)

C.aaD.ab

41.詞法分析器的輸出是：(C

A.單詞在符號(hào)表中的位置B.單詞的自身值

C.單詞的自身值和單詞的種類碼D,單詞的種類碼

42.兩個(gè)DFA等價(jià)是指：(D)

A.這兩個(gè)DFA的狀態(tài)數(shù)相同

B.這兩個(gè)DFA的狀態(tài)數(shù)和有向弧條數(shù)都相等

C.這兩個(gè)DFA的有向弧條數(shù)相等

D.這兩個(gè)DFA接受的語(yǔ)言相同

43.生成中間代碼時(shí)所依據(jù)的是(C)。

A.語(yǔ)法規(guī)則B.詞法規(guī)則

C.語(yǔ)義規(guī)則D.等價(jià)變換規(guī)則

44.表達(dá)式"aVb)A(cVd)的逆波蘭表示為(B)。

A.-|abVAcdVB.a-|bVcdVA

C.abVqcdVAD.aqbVAcdV

45.有文法G及其語(yǔ)法制導(dǎo)翻譯如下所示(語(yǔ)義規(guī)則中的*和+分別是常規(guī)意

義下的算術(shù)運(yùn)算符)：

ETE(1)AT[E.val=E(1).val*T.val)

ETT[E.val=T.val}

T->T(1)#n{T,vaI=T(1).vaI+n.vaI)

TTn(T.vaI=n.vaI)

則分析句子2A3#4其值為(C)o

A.10B.21

C.14D.24

46.表達(dá)式a+b+c+d的逆波蘭表示為(B)。

A.a+bc+d+B.ab+c+d+

C.ab+cd++D.abc+d++

47.文法G[S]及其語(yǔ)法制導(dǎo)翻譯定義如下:

產(chǎn)生式語(yǔ)義動(dòng)作

S'TSprint(S.num)

ST(L)S.num=L.num+1

S-?aS.num=0

LTL⑴,SL.num=L(1).numS.num

LTSL.num;S.num

若輸入為（a,（a））,且采用自底向上的分析方法，則輸出為（C)。

A.0B.1

C.2D.4

48.若a為終結(jié)符，貝ljATa.a[3為（B）。

A.歸約項(xiàng)目B.移進(jìn)項(xiàng)目

C.待約項(xiàng)目D.接受項(xiàng)目

49.若B為非終結(jié)符，貝IjATa.B0為（C）。

A.歸約項(xiàng)目B.移進(jìn)項(xiàng)目

C.待約項(xiàng)目D.接受項(xiàng)目

50.項(xiàng)目ATa.為(A)o

A.歸約項(xiàng)目B.移進(jìn)項(xiàng)目

C.待約項(xiàng)目D.接受項(xiàng)目

51.語(yǔ)法分析器的輸入是：（A）

A.Token序列B.源程序

C.目標(biāo)程序D.符號(hào)表

52.在LR(0)的Action表中,如果某行中存在標(biāo)記為“rj”的欄，則:

(A)

A.該行必定填滿B.該行未必填滿，丁

C.其他行可能也有“門”D.goto表中也可能有“rj”

53.LR分析過(guò)程中棧內(nèi)存儲(chǔ)的是(A)。

A.活前綴B.前綴

C.歸約活前綴D.項(xiàng)目

54.文法G：STxxS|y所識(shí)別的語(yǔ)言是（D）。

A.xxy*B.(xxy)*C.xx*yxD.(xx)*y

55.若狀態(tài)k含有項(xiàng)目“ATa.\對(duì)任意非終結(jié)符a,都用規(guī)則“ATa”

歸約的語(yǔ)法分析方法是(B)。

A.LALR分析法B.LR(0)分析法

C.LRCI)分析法D.SLR(1)分析法

56.在編譯過(guò)程中,如果遇到錯(cuò)誤應(yīng)該（C）。

A,把錯(cuò)誤理解成局部的錯(cuò)誤

B.對(duì)錯(cuò)誤在局部范圍內(nèi)進(jìn)行糾正，繼續(xù)向下分析

C.當(dāng)發(fā)現(xiàn)錯(cuò)誤時(shí)，跳過(guò)錯(cuò)誤所在的語(yǔ)法單位繼續(xù)分析下去

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

57.將編譯程序分成若干“遍二是為了（B）

A.提高程序的執(zhí)行效率B.使程序的結(jié)構(gòu)更為清

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

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

58.下列符號(hào)串不可以由符號(hào)集E={a,b}上的正閉包運(yùn)算產(chǎn)生的是：（A）

A.EB.a

C.aaD.ab

59.表達(dá)式（1aVb）A（eVf）的逆波蘭表示為（B）。

A.-]abVAefVB.a-]bVefVA

C.abV-iefVAD.a-|bVAefV

60.有文法G及其語(yǔ)法制導(dǎo)翻譯如下所示(語(yǔ)義規(guī)則中的*和+分別是常規(guī)意

義下的算術(shù)運(yùn)算符)：

ETE(1)AT{E.val=E(1).val*T.val)

ETT{E.val=T.val)

TTT(1)#n[T.val=T(1).val+n.val)

T->n{T.val=n.vaI}

則分析句子3A3#4其值為(B)o

A.10B.21

C.14D.24

61.表達(dá)式a+b+c的逆波蘭表示為（B）。

A.a+bc+B.ab+c+

C.+abc+D.abc++

62.文法G[S]及其語(yǔ)法制導(dǎo)翻譯定義如下:

產(chǎn)生式語(yǔ)義動(dòng)作

S'TSprint(S.num)

ST(L)S.num=L.num+1

STaS.num=0

LTL⑴，SL.num=L(1).num+S.num

LTSL.num=S.num

若輸入為(a,a),且采用自底向上的分析方法，則輸出為(B)。

A.0B.1

C.2D.4

63.在SLR(1)的Action表中，如果某行中存在標(biāo)記為。丁的欄，則:

(B)

A.該行必定填滿。丁B.該行未必填滿“rj”

C.其他行可能也有“rj”D.goto表中也可能有“rj”

64.一個(gè)(D)指明了在LR分析過(guò)程中的某個(gè)時(shí)刻所能看到產(chǎn)生式多大

一部分。

A.活前綴B.前綴

C.歸約活前綴D.項(xiàng)目

65.文法G：STxS|y所識(shí)別的語(yǔ)言是(D)。

A.xy*B.(xy)*

C.xx*yxD.x*y

66.若狀態(tài)k含有項(xiàng)目“ATQ.”，且僅當(dāng)輸入符號(hào)a《FOLLOW(A)時(shí)，才用

規(guī)則“ATa”歸約的語(yǔ)法分析方法是(D)o

A.LALR分析法B.LR(O)分析法

C.LR(1)分析法D.SLR⑴分析法

67.設(shè)有文法G[T]:

TTT*F|F

FTFTP|P

PT(T)|a

該文法句型T*PT(T*F)的句柄是下列符號(hào)串(C)

A.(T*F)B.T*FC.PD.PT(T*F)

68.LR分析表中的轉(zhuǎn)移表(goto)是以(B)作為列標(biāo)題的。

A.終結(jié)符B.非終結(jié)符C.終結(jié)符或非終結(jié)符D.表示狀態(tài)

的整形數(shù)

69.編譯程序的語(yǔ)法分析器必須輸出的信息是(A)

A.語(yǔ)法錯(cuò)誤信息B.語(yǔ)法規(guī)則信息C.語(yǔ)法分析過(guò)程

D.語(yǔ)句序列

70.下列項(xiàng)目中為可移進(jìn)項(xiàng)目的是(C)o

A.E'TE.B.LT.C.LT-.LD.FTL*F.

71.有一語(yǔ)法指導(dǎo)定義如下:

STbAbprintU[，，

AT(Bprint“2”

ATaprint“3”

BTaA)print“4”

若輸入序列為b(a(a(aa)))b,且采用自底向上的分析方法，則輸出序

列為（B)

A.32224441B.34242421C.12424243D.34442212

72.同正規(guī)式（a|b）*等價(jià)的正規(guī)式為（D）

A.（a|b）+B.a*|b*C.（ab）*D.（a*|b*）+

73.詞法分析器的加工對(duì)象是（C）

A.中間代碼B.單詞C.源程序D.元程序

74.在自下而上的語(yǔ)法分析中，應(yīng)從（B）開(kāi)始分析。

A.句型B.句子C.文法開(kāi)始符號(hào)D.句柄

75.賦值語(yǔ)句X:=-(a+b)/(c-d)-(a+b*c)的逆波蘭表示是(C)

A.Xab+cd-/-bc*a+-:二

B.Xab+/cd-bc*a:-

C.Xab+-cd-/abe*■t―:-

D.Xab+cd-/abc*+-:-

76.設(shè)有文法G[T]:

TTT*F|F

FTFTP|P

PT⑴Ia

該文法句型T*FT(T*F)的句柄是下列符號(hào)串(B)

A.(T*F)B.T*FC.PD.PT(T*F)

77.LR分析表中的動(dòng)作表(action)是以(D)作為列標(biāo)題的。

A.終結(jié)符B.非終結(jié)符C.終結(jié)符或非終結(jié)符D.終結(jié)符和

結(jié)束符$

78.下列項(xiàng)目中為可歸約項(xiàng)目的是（B)o

A.E’T.EB.LT.C.LT-.LD.FTL*.F

79.有一語(yǔ)法指導(dǎo)定義如下，其中+表示符號(hào)連接運(yùn)算：

STBprintB.vers

BTaB.vers=a

BTbB.vers二b

BTBaB.vers=a+B.vers

BTBbB.vers=b+B.vers

若輸入序列為abab,且采用自底向上的分析方法，則輸出序列為

D)

A.aabbB.ababC.bbaaD.baba

80.同正規(guī)式(a|b)*等價(jià)的正規(guī)式為(D)

A.(a|b)+B.a*|b*C.(ab)*D.(a*|b*)+

共4頁(yè)第1頁(yè)

81.詞法分析器的加工對(duì)象是(C)

A.中間代碼B.單詞C.源程序D.元程序

82.在自上而下的語(yǔ)法分析中，應(yīng)從(C)開(kāi)始分析。

A.句型B.句子C.文法開(kāi)始符號(hào)D.句柄

83.賦值語(yǔ)句X:=-(a+b)/(c-d)-(a+b*c)的逆波蘭表示是(C)

E.Xab+cd-/_bc*a+-:-

F.Xab+/cd-bc*a--:-

G.Xab+-cd-/abe*+一：二

H.Xab+cd-/abc*+—:=

84.編譯程序不能檢查、處理的錯(cuò)誤是程序中的Bo

A.靜態(tài)語(yǔ)義檢查B.動(dòng)態(tài)語(yǔ)義檢查C.語(yǔ)法錯(cuò)誤D.詞

法錯(cuò)誤

85.在LR(0)的ACTION子表中，如果某一行中有標(biāo)記為的欄，則

C__________O

A.該行既有門又有&B.其它行也有門

C.該行一定填滿門D.該行未填滿門

86.同正規(guī)式(a|b)+等價(jià)的正規(guī)式是Bo

A.(a|b)*B.(a|b)(a|b)*C.(ab)*(ab)D.(a|b)|

(a|b)*

87.在規(guī)范歸約中，用一B一來(lái)刻畫(huà)可歸約串。

A,直接短語(yǔ)B.句柄C.素短語(yǔ)D.短語(yǔ)

88.若a為終結(jié)符，則ATa-ap為B項(xiàng)目。

A,歸約B.移進(jìn)C.接受D.待約

89.一個(gè)文法G,若C,則稱它是LL(1)文法。

A.G中不含左遞歸B.G無(wú)二義性

C.G的LL(1)分析表中不含多重定義的條目D.G中產(chǎn)生式不含左公因

子

90.LR分析器的核心部分是一張分析表，該表由汗__________組

成。

A.ACTION表B.GOTO表C.預(yù)測(cè)分析表D.ACTION表和

GOTO表

91.構(gòu)造編譯程序應(yīng)該掌握^_________o

A.源程序B.目標(biāo)語(yǔ)言C.編譯方法D.以上三項(xiàng)都

92.在遞歸子程序方法中，若文法存在左遞歸，則會(huì)使分析過(guò)程產(chǎn)生

_Do

A.回溯B.非法調(diào)用C.有限次調(diào)用D.無(wú)限循環(huán)

93.最左簡(jiǎn)單子樹(shù)的葉結(jié)點(diǎn)，自左至右排列組成句型的

C____________0

A.短語(yǔ)B.句型C.句柄D.間接短語(yǔ)

94.如果一個(gè)正規(guī)式所代表的集合是無(wú)窮的，則它必含有的運(yùn)算是

C___________O

A.連接運(yùn)算“?"B.或運(yùn)算C.閉包運(yùn)算”D.括號(hào)

和

95.同正規(guī)式a*b*等價(jià)的文法是Co

A.G1：STaS|bS|EB.G2：S->aSb|EC.G3：STaS|Sb|ED.G4：

STabS|E

96.由文法的開(kāi)始符號(hào)出發(fā)經(jīng)過(guò)若干步（包括0步）推導(dǎo)產(chǎn)生的文法符號(hào)

序列稱為上一°

A.語(yǔ)言B.句型C.句子D.句柄

97.四元式之間的聯(lián)系是通過(guò)一B____________實(shí)現(xiàn)的。

A.指示器B,臨時(shí)變量C.符號(hào)表D.程序變量

98.編譯程序的語(yǔ)法分析器必須輸出的信息是Ao

A.語(yǔ)法錯(cuò)誤信息B.語(yǔ)法規(guī)則信息C.語(yǔ)法分析過(guò)程D.語(yǔ)

句序列

99.LL(1)分析法中“1”的含義是在輸入串中查看一個(gè)輸入符號(hào)，其目

的是￡O

A.確定最左推導(dǎo)B.確定句柄

C.確定使用哪一個(gè)產(chǎn)生式進(jìn)行展開(kāi)D.確定是否推導(dǎo)

100.稱正規(guī)式R1和R2等價(jià)是指C

A.R1和R2都是定義在同一個(gè)字母表上的正規(guī)式

B.R1和R2使用的運(yùn)算符相同

C.R1和R2代表同一個(gè)正規(guī)集

D.R1和R2代表不同的正規(guī)集

二、填空題

概述部分：

1.編譯程序的開(kāi)發(fā)常常采用自編譯、交叉編譯、自展和移植等技

術(shù)實(shí)現(xiàn)。

2.解釋程序和編譯程序的區(qū)別在于是否生成目標(biāo)程序。

3.如果編譯程序生成的目標(biāo)程序是匯編語(yǔ)言程序，則源程序的執(zhí)行分為3

個(gè)階段：編譯階段、匯編階段和運(yùn)行階段°

4,編譯程序工作過(guò)程中，第一階段輸入是一源程序，最后階段的輸出為

目標(biāo)程序。

5.編譯過(guò)程通?？煞譃?個(gè)階段詞法分析階段、語(yǔ)法分析階段、語(yǔ)

義分析和中間代碼生成階段、優(yōu)化階段和目標(biāo)代碼生成階段。

6.如果編譯階段生成的目標(biāo)程序是某特定計(jì)算機(jī)系統(tǒng)的機(jī)器代碼程序，則

源程序的執(zhí)行分為兩大階段；編譯階段和運(yùn)行階段。

7.對(duì)編譯程序而言，輸入數(shù)據(jù)是一源程序，輸出結(jié)果是a

標(biāo)程序。

8.貫穿于編譯程始終的工作有符號(hào)表處理和出錯(cuò)處理。

詞法分析部分：

1.詞法分析的工作是將源程序中的字符串變換成單詞符號(hào)流的過(guò)

程，所遵循的是語(yǔ)言的構(gòu)詞規(guī)則。

2.若兩個(gè)正規(guī)式所表示的正規(guī)集相同,則認(rèn)為二者是等價(jià)的。

3.若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者是等價(jià)的。

4.正規(guī)式R1和R2等價(jià)是指表示相同的正規(guī)

5.詞法分析器的輸入是源程序字符串，輸出結(jié)構(gòu)是一二元式(單詞種別，

單詞自身的值)。詞法分析所遵循的是語(yǔ)言的構(gòu)詞規(guī)則。

6.確定的有限自動(dòng)機(jī)是一個(gè)五元組，包含的五個(gè)元分別是：狀態(tài)集合、字

母表、初態(tài)、終態(tài)集、狀態(tài)轉(zhuǎn)換函數(shù)集合。

7.有限自動(dòng)機(jī)是更一般化的狀態(tài)轉(zhuǎn)換圖，它分為確定的有限自動(dòng)機(jī)DFA

和非確定的有限自動(dòng)機(jī)NFA兩種。

8.NFA和DFA的區(qū)別主要有兩點(diǎn)：其一是NFA可以有若干個(gè)初始狀態(tài)，

而DFA僅有一個(gè)初始狀態(tài)；其二是一NFA的狀態(tài)轉(zhuǎn)換函數(shù)f不是單值函數(shù)，而

是一個(gè)多值函數(shù)。

語(yǔ)法分析部分：(基本概念、LL(1)、LR(0)、SLR(1)、遞歸下降子程序)

1.語(yǔ)法分析的方法通常分為兩類：自上而下分析方法和自下

而上分析方法。

2.文法中的終結(jié)符集和非終結(jié)符集的交集是―。

3.一個(gè)句型的最左直接短語(yǔ)稱為該句型的o

4.規(guī)范歸約是一最右推導(dǎo)的逆過(guò)程。

5.自下而上語(yǔ)法分析中分析器的動(dòng)作有移進(jìn)、—?dú)w約、接受

—、報(bào)錯(cuò)_。

6.自上而下語(yǔ)法分析中分析器的動(dòng)作有匹配終結(jié)符一、展開(kāi)非終

結(jié)符、分析成功、報(bào)錯(cuò)。

7.常用的自上而下語(yǔ)法分析方法有遞歸下降子程序方法和預(yù)測(cè)分析表方法

(LL(1)方法)。

8.常用的自下而上語(yǔ)法分析方法有算符優(yōu)先分析法和LR分析法、

9.一個(gè)LL⑴分析器由一張LL(1)分析表(預(yù)測(cè)分析表)、一個(gè)

先進(jìn)后出分析棧和一個(gè)控制程序(表驅(qū)動(dòng)程序)組成。

10.一個(gè)LR分析器由分析棧、分析表和總控程序三個(gè)部分組成。

11.LR(0)分析法的名字中，表示自左至右分析輸入串，表示采

用最右推導(dǎo)的逆過(guò)程即最左歸約°“0”表示向右查看0個(gè)字符。

12.LLCI)分析法中，第一個(gè)L的含義是.從左到右掃描輸入串；第二個(gè)

L的含義是分析過(guò)程中采用最左推導(dǎo)；“1”的含義是只需向右查看一個(gè)符

號(hào)就可以決定如何推導(dǎo)。

13.LR(1)文法的含義是：L表明自左至右掃描輸入串.R表明—

采用最右推導(dǎo)的逆過(guò)程(最左歸約)方法進(jìn)行分析。

14.一個(gè)上下文無(wú)關(guān)文法是LL⑴文法的充分必要條件是：對(duì)每一個(gè)非終結(jié)

符A的任何兩個(gè)不同產(chǎn)生式ATa|(3.有下面的條件成立：(1)FIRST(a)

「FIRST(B)=0；(2)假若夕則有FIRST(Q)AFOLLOW(A)二

QO

15.對(duì)于LL(1)文法中的任何產(chǎn)生式ATa|(3,則需要滿足First(a)

CFirst(B)二①、

若_B=>*L貝I]First(_a)ClFollow(A)=_①」。

16.LR分析器的核心部分是一張分析表，該表包括動(dòng)作(ACTIO心表和

狀態(tài)轉(zhuǎn)換(GOTO)表等兩個(gè)子表。

17.關(guān)于非終結(jié)符A的直接左遞歸產(chǎn)生式：ATAalB,其中a、B是任意

的符號(hào)串且B不以A開(kāi)頭，則可以將A的產(chǎn)生式改寫(xiě)為右遞歸的形式為：AT

",A'TaA'|￡。

18.在消除回溯，提取公共左因子時(shí)，關(guān)于A的產(chǎn)生式A-46|6P

2I-I63iIPMI-I8i.可以改寫(xiě)為：AT8A'|Bw|…|B

j,A’tBiiTBi。

19.設(shè)G[S]是一文法，如果符號(hào)串x是從識(shí)別符號(hào)推導(dǎo)出來(lái)的，即有S=x,

?

則稱x是文法G[S]的句型,若x僅由終結(jié)符號(hào)組成，即S=x./e%,則

稱x為文法G[S]的句子。

20.已知文法G[S]:

S->eT|RTTTDR|￡RTdR|￡D->a|bd

求FIRST(S)={e,d,a,b、￡}；FOLLOW(D)={d,#}0

語(yǔ)義處理部分：

1.文法符號(hào)的屬性有兩種，一種稱為繼承屬性,另一種稱為綜合屬

X。

2.編譯過(guò)程中，常見(jiàn)的中間語(yǔ)言形式有逆波蘭表示法、抽象語(yǔ)法樹(shù)、

三元式、四元式。

3.語(yǔ)法制導(dǎo)翻譯的方法就是為每個(gè)產(chǎn)生式配上一個(gè)翻譯子程序（語(yǔ)義動(dòng)

作或語(yǔ)義子程序），并在語(yǔ)法分析的同時(shí)執(zhí)行它們。

4.編譯過(guò)程中，常見(jiàn)的中間語(yǔ)言形式有逆波蘭表示法、抽象語(yǔ)法樹(shù)、

三元式、四元式。

5.詞法分析器的輸入是一源程序字符串，輸出結(jié)構(gòu)是一二元式（單詞種

別，單詞自身的值）。

6.文法符號(hào)的屬性有兩種，一種稱為繼承屬性』另一種稱為綜合屬

性。

7.四元式之間的聯(lián)系是通過(guò).臨時(shí)變量實(shí)現(xiàn)的。

8.在屬性文法中，終結(jié)符只有綜合屬性。

9.編譯過(guò)程中，常見(jiàn)的中間語(yǔ)言形式有逆波蘭式、抽象語(yǔ)法樹(shù)、

三元式、四元式。

10.語(yǔ)法制導(dǎo)翻譯的方法就是為每個(gè)產(chǎn)生式配上一個(gè)翻譯子程序（語(yǔ)義

動(dòng)作或語(yǔ)義子程序）.并在語(yǔ)法分析的同時(shí)執(zhí)行它們。

11.目前較常見(jiàn)的語(yǔ)言語(yǔ)義的描述形式是一屬性文法一，并使用語(yǔ)

法制導(dǎo)翻譯方法完成對(duì)語(yǔ)法成分的翻譯。

三、判斷題

1.設(shè)r和s分別為正規(guī)式，則有L（r|s）=L（r）|L（s）.o（X）

2.一個(gè)文法的所有句型的集合形成該文法所能接受的語(yǔ)言。（X）

3.語(yǔ)法分析之所以采用上下文無(wú)關(guān)文法是因?yàn)樗拿枋瞿芰ψ顝?qiáng)。（X）

4.由于LR（0）分析表構(gòu)造簡(jiǎn)單，所以它的描述能力強(qiáng)，適用面寬；LR（1）

分析表因構(gòu)造復(fù)雜而描述能力弱，適用面窄。（X）

5.逆波蘭表示法表示表達(dá)式時(shí)無(wú)需使用括號(hào)。（V）

6.自動(dòng)機(jī)M和M'的狀態(tài)個(gè)數(shù)不同，則二者必不等價(jià)。（X）

7.LL（1）文法一定不含左遞歸和二義性。（V）

8.所有LR分析器的總控程序都是一樣的，只是分析表各有不同。（V）

9.無(wú)論是三元式表示還是間接三元式表示的中間代碼，其三元式在三元式

表中的位置一旦確定就很難改變。（V）

10.三地址語(yǔ)句類似于匯編語(yǔ)言代碼，可以看成中間代碼的一種抽象形式。

（V）

11.最左推導(dǎo)也被稱為規(guī)范推導(dǎo)。（X）

12.運(yùn)算對(duì)象排列的先后順序在后綴式和中綴式中不同。（X）

13.出現(xiàn)在移進(jìn)-歸約分析器棧中的內(nèi)容被稱為文法G的活前綴。（V）

14.LR方法可以分析含有左遞歸的文法。（V）

15.三元式的編號(hào)具有雙重含義，既代表此三元式，又代表三元式存放的

結(jié)果。（V）

16.語(yǔ)義規(guī)則中的屬性有兩種：綜合屬性與繼承屬性。（V）

17.移進(jìn)-歸約分析器的格局中棧的內(nèi)容一般是文法符號(hào)與狀態(tài)。（V）

18.由于遞歸下降子程序方法較LL（1）方法簡(jiǎn)單，因此它要求文法不必是

LL（1）文法。（X）

19.四元式的編號(hào)具有雙重含義，既代表此四元式，又代表四元式存放的

結(jié)果。（X）

20.用高級(jí)語(yǔ)言編寫(xiě)的源程序必須經(jīng)過(guò)編譯，產(chǎn)生目標(biāo)程序后才能運(yùn)行。

（X）

21.源程序到目標(biāo)程序的變換是等價(jià)變換，即兩者結(jié)構(gòu)不同，但語(yǔ)義是一

致的。（)

22.對(duì)于任何一個(gè)正規(guī)式e,都存在一個(gè)DFAA,使得L（e）=L（A）。

（V）

23.最小化的DFA,它的狀態(tài)數(shù)最小。（V）

24.NFA的確定化算法具有消除￡邊的功能。（V）

25.每個(gè)非終結(jié)符產(chǎn)生的終結(jié)符號(hào)串都是該語(yǔ)言的子集。（X）

26.一個(gè)語(yǔ)言的文法是不唯一的。（V）

27.語(yǔ)法錯(cuò)誤校正的目的是為了把錯(cuò)誤改正過(guò)來(lái)。（X）

28.源程序和目標(biāo)程序是等價(jià)關(guān)系。（V）

29.編譯程序中錯(cuò)誤處理的任務(wù)是對(duì)檢查出的錯(cuò)誤進(jìn)行修改。（X）

30.使用有限自動(dòng)機(jī)可以實(shí)現(xiàn)單詞的識(shí)別。（V）

31.一個(gè)非確定的有限自動(dòng)機(jī)NFA可以通過(guò)多條路徑識(shí)別同一個(gè)符號(hào)串。

（V）

32.最小化的DFA所識(shí)別接受的正規(guī)集最小。（X）

33.一個(gè)語(yǔ)言（如C語(yǔ)言）的句子是有窮的。（X）

34.LL（1）方法又稱為預(yù)測(cè)分析方法。（V）

35.一個(gè)LL（1）文法是無(wú)二義和無(wú)回溯方法。（V）

36.語(yǔ)法分析器可以檢查出程序中的所有錯(cuò)誤。（X）

37.LR分析法是自上而下的語(yǔ)法分析方法c（X）

三、多項(xiàng)選擇題

1.編譯器的各個(gè)階段的工作都涉及到（AE）

A.表格處理B.詞法分析

C.語(yǔ)法分析D.語(yǔ)義分析

E.出錯(cuò)處理

2.令Z={a,b},則Z上的符號(hào)串的全體可用下面的正規(guī)式表示。（ABE）

A.(a|b)*B.(a*|b*)*

C.(a|b)+D.(ab)*

E.(a*b*)*

3.自上而下的分析方法有：（AD）

A.遞歸下降分析法B.LR(0)分析法

C.LALR(1)分析法D.LL（1）分析法

E.SLR(1)分析法

4.文法G：G[S]：STCDAbTbA

CTaCABaTaB

CTbCBBbTbB

ADTaDCTE

BDTbDDTE

AaTbD

是

(AE)o

A.0型文法B.1型文法

C.2型文法D.3型文法

E.上下文有關(guān)文法

5.對(duì)LR分析表的構(gòu)造，有可能存在的動(dòng)作沖突有：（AD）

A.移進(jìn)/歸約沖突B.移進(jìn)/移進(jìn)沖突

C.歸約沖突D.歸約/歸約沖突

E.移進(jìn)沖突

6.一個(gè)編譯器可能有的階段為（ABODE)

A.詞法分析B.語(yǔ)法分析

C.語(yǔ)義分析D.中間代碼生成

E.目標(biāo)代碼生成

7令2={a,b},則E上的所有以b開(kāi)頭，后跟若干個(gè)（可為0個(gè)）ab的符

號(hào)串的全體可用下面的正規(guī)式表示。（AB)

A.b(ab)*B.(ba)*b

C.b(a|b)+D.(ba)+b

E.b(a|b)*

8.自下而上的分析方法有:(BCE)

A.遞歸下降分析法B.（0）分析法

C.LALR(1)分析法D.（1）分析法

E.SLR（1）分析法

9.一般來(lái)說(shuō),編譯器可分為前端和后端,下列編譯階段可被劃分為編譯的

前端的有：（ABCDE)

A.詞法分析B.語(yǔ)法分析

C.語(yǔ)義分析D.中間代碼生成E.中間代碼優(yōu)化

10.令2={a,b},則2上的符號(hào)串的全體可用下面的正規(guī)式表示c（ABE）

A.(a|b)*B.(a*|b*)*

C.(a|b)+D.(ab)*E.(a*b*)*

11.下列符號(hào)串是符號(hào)集E={a,b}上的正規(guī)式的有：（ABCDE）

A.EB.aC.abD.(abIa)(abIa)

E.ab|ab

12.正規(guī)式服從的代數(shù)規(guī)律有：（ABDE）

A.“或”運(yùn)算服從交換律B,“或”運(yùn)算服從結(jié)合律

C.“連接”運(yùn)算服從交換律D,“連接”運(yùn)算服從結(jié)合律

E.“連接”運(yùn)算可對(duì)“或”運(yùn)算進(jìn)行分配

13.令X={a,b},則2上的所有以b開(kāi)頭，后跟若干個(gè)(可為0個(gè))

ab的符號(hào)串的全體可用下面的正規(guī)式表示。(AB)

A.b(ab)*B.(ba)*bC.b(a|b)+

D.(ba)+bE.b(a|b)*

14.一個(gè)LR分析器包括：(ADE)

A.一個(gè)總控程序B.一個(gè)項(xiàng)目集

C.一個(gè)活前綴D.一個(gè)分析棧

E.一張分析表

15.LR分析器的核心部分是一張分析表，該表包括(DE)等子表。

A.LL(1)分析表B.LR(1)分析表

C.SLR(1)分析表D.Action表

E.goto表

16.Action表中的每一項(xiàng)Action[S,a]所表示的動(dòng)作可能為：(ABCD)

A.移進(jìn)B.接受C.歸約

D.出錯(cuò)E.待約

五.簡(jiǎn)答題

1.構(gòu)造正規(guī)表達(dá)式a(aa)*bb(bb)*a(aa)*的NFA。

解：

2.構(gòu)造正規(guī)表達(dá)式（匕此）*憶牛*1）的肝八。

解：

2.令文法G[N]為G[N]:NTD|ND

D->O|1|2|3|4|5|6|7|8|9

給出句子568的最左、最右推導(dǎo)。

解：最左推導(dǎo)：NnNDnNDDnDDDn5DDn56Dn568

最右推導(dǎo)：N=>ND=>N8nND8nN68=D68=>568

3.給出字母表2={a,b}上的同時(shí)只有奇數(shù)個(gè)a和奇數(shù)個(gè)b的所有串的集合

的正規(guī)文法；

解:G[S]：STaA|bB

A->aS|bC|b

BTbS|aC|a

CTbA|aB|E

4.給定文法：ST(L)a

LTL,S|S

請(qǐng)書(shū)寫(xiě)語(yǔ)義規(guī)則，求輸出句子中每一個(gè)a的括號(hào)嵌套深度。

解：

用繼承屬性depth表示嵌套深度，則

S'TSS.depth=0

ST(L)L.depth=S.depth+1

STaprint(S.depth)

LTL⑴，SLC1).depth=L.depth;S.depth=L.depth

LTSS.depth=L.depth

5.表達(dá)式a*b-c-d$e$f-g-h*i中，運(yùn)算符的優(yōu)先級(jí)由高到低依次為-、*、

$,且均為右結(jié)合，請(qǐng)寫(xiě)出相應(yīng)的后綴式。

解：abed--*efgh_-i*$$

6.判斷文法G[S]:STBA

ATBS|d

BaA|bS|c

是否為L(zhǎng)L⑴文法.

解：對(duì)于該文法求其FIRST集如下：

FIRST(S)={a,b,c};FIRST(A)={a,b,c,d};FIRST(B)={a,

b,c}o

求其FOLLOW集如下:

FOLLOW(S)={a,b,c,d,#};FOLLOW(A)={a,b,c,d,#};FOLLOW(B)

={a,b,c,d,#}o

由ATBS|d得：

FIRST(BS)DFIRST('d')={a,b,c}Ahbdtzta二①

由BTaA|bS|c得

FIRST(aA)AFIRST(bS)AFIRST(c)={a}AA{c］二①

由于文法G［S］不存在形如(3TE的產(chǎn)生式，故無(wú)需求解形如FIRST(a)

AFOLLOWS)的值，也即文法G［S］是一個(gè)LL⑴文法。

7.對(duì)于文法G[EGETE+T|T

TTT+P|P

PT(E)|i

寫(xiě)出句型P+T+(E+i)的所有短語(yǔ)、直接短語(yǔ)、句柄。

解：短語(yǔ)：P、P+T、i、E+i、(E+i八P+T+(E+i)；

直接短語(yǔ)：P、i;

句柄：P;

8.已知文法G[A]:ATaABl|a

BTBb|d

試給出與G[A]等價(jià)的LL(1)文法G[A，]；

解：G[A，]：ATaA'

A，TABI|E

BTdB'

B，TbB'|E

9.將下面的語(yǔ)句翻譯成四元式序列:

if(x>y)m=1;

eIsem=0;

解：1(j>,x,y,3)

2(j._,5)

3(=,1,m)

4(j,_,6)

5(=0,m)

6:

10.將