可以微信掃碼觀看

河南城建

《編譯原理》復(fù)習(xí)題丨楊海振整理丨20150521

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

1．構(gòu)造編譯程序應(yīng)掌握 ? 。D

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

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

2．編譯程序絕大多數(shù)時(shí)間花在 ? 上。D

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

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

3．DFAM(見(jiàn)圖1-1)接受的字集為 ? 。D

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)的逆波蘭表示是 ? ? ? ? 。(@代表后綴式中的求負(fù)運(yùn)算符) C

a. ?abc*cd-b@a*+/-@ ? ? ? ? ? ? ? ?b. ?a@bc*cd-b@a*+/-

c. ?a@bc*cd-/b@a*+- ? ? ? ? ? ? ? ?d. ?a@bc*/cd-b@a*+-

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

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

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

6．若B為非終結(jié)符，則A→α·Bβ為 ? 項(xiàng)目。D

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

c. 接受 ? ? ? ? ? ? ? ? ? ? d. 待約

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

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

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

8．有文法G及其語(yǔ)法制導(dǎo)翻譯如下所示(語(yǔ)義規(guī)則中的*和+分別是常規(guī)意義下的算術(shù)運(yùn)算符)：

E→E⁽¹⁾∧ T {E.val = E⁽¹⁾.val* T.val}

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

T→T⁽¹⁾#n ? ?{T.val = T⁽¹⁾.val+ n.val }

T→ n ? ? ? ?{T.val = n.val}

則分析句子1∧ 2 ∧ 3 # 4其值為 ? ? ? ?。 C

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

9．如果文法G是無(wú)二義的，則它的任何句子α ? 。　A

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)作的是： ? 。B

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

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

11．編譯程序是對(duì) ? 。D

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

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

12．詞法分析器的輸出結(jié)果是 ? 。C

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

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

13．正規(guī)式M1和M2等價(jià)是指 ? 。C

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é)符，則A→α·aβ為 ? 項(xiàng)目。B

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

c. 接受 ? ? ? ? ? ? ? ? ? ? d. 待約

16．語(yǔ)法分析時(shí)所依據(jù)的是 ? ? 。A

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

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

17．文法G：S→xSx|y所識(shí)別的語(yǔ)言是 ? 。C

a. xyx ? ? ? ? ? ? ? ? ? ? ? ? ? b. (xyx)*

c. xⁿyxⁿ (n≥0) ? ? ? ? ? ? ? ? ? ?d. x*yx*

18．如果文法G是無(wú)二義的，則它的任何句子α ? 。　A

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)作的是： ? 。C

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

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

20．詞法分析器的輸出結(jié)果是 ? 。C

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

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

21．-a-(b*c/(c-d)+(-b)*a)的逆波蘭表示是 ? ? ? ? 。(@代表后綴式中的求負(fù)運(yùn)算符) C

a. ?abc*cd-b@a*+/-@ ? ? ? ? ? ? ? ? ? b. ?a@bc*cd-b@a*+/-

c. ?a@bc*cd-/b@a*+- ? ? ? ? ? ? ? ? ? d. ?a@bc*/cd-b@a*+-

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

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

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

23．若B為非終結(jié)符，則A→α· 為 ? 項(xiàng)目。A

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

c. 接受 ? ? ? ? ? ? ? ? ? ? d. 待約

24．文法G：S→xSx|xS|y所識(shí)別的語(yǔ)言是 ? 。 ?A

a. x^myxⁿ(m≥n≥0) ? ? ? ? ? ? ? ? b. (xyx)* ? ? ?

c. xⁿyxⁿ(n≥0) ? ? ? ? ? ? ? ? ? ? d. x*yx*

25．有文法G及其語(yǔ)法制導(dǎo)翻譯如下所示(語(yǔ)義規(guī)則中的*和+分別是常規(guī)意義下的算術(shù)運(yùn)算符)：

E→E⁽¹⁾∧ T {E.val = E⁽¹⁾.val* T.val}

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

T→T⁽¹⁾#n ? ?{T.val = T⁽¹⁾.val+ n.val }

T→ n ? ? ? ?{T.val = n.val}

則分析句子2∧ 3 # 4其值為 ? ? ? ?。 C

a. 10 ? ? ? ? ? ? ? ? ? ? ? ? ?b. 21 ?

c. 14 ? ? ? ? ? ? ? ? ? ? ? ? ?d. 24

26．間接三元式表示法的優(yōu)點(diǎn)為 ? 。 A

a. 采用間接碼表，便于優(yōu)化處理 ?

b. 節(jié)省存儲(chǔ)空間，不便于表的修改

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

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

27．下列動(dòng)作中，不是自上而下分析動(dòng)作的是： ? 。C

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

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

28．同正規(guī)式(a|b)+等價(jià)的正規(guī)式是______B___________。

A．(a|b)* ? ? B．(a|b)(a|b)* ? ? C．(ab)*(ab) ? ? D．(a|b)|(a|b)*

29．稱(chēng)有限自動(dòng)機(jī)A1和A2等價(jià)是指_______D________。

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)序列稱(chēng)為_(kāi)_____B________。

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

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

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

32．一個(gè)文法G，若________C____________，則稱(chēng)它是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é)符，則A→α·aβ為_(kāi)______B______項(xiàng)目。

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

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

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

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

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

S’ → S print(S.num)

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

S → a S.num = 0

L →L(1),S L.num = L(1).num + S.num

L →S L.num= S.num

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

A．0 B．1 C．2 D．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)集S＝{a,b}上的正閉包運(yùn)算產(chǎn)生的是：(A　)

A. ε ? ? ? ? ? ? ? ? ? ? ? ? ? ? B.　a

C.　aa ? ? ? ? ? ? ? ? ? ? ? ? ? D.　ab

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

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

C.單詞的自身值和單詞的種類(lèi)碼 ? ? D.單詞的種類(lèi)碼

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á)式(┐a∨b)∧(c∨d)的逆波蘭表示為(B)。

A．┐ab∨∧cd∨ ? ? ? ? ? ? ?B．a┐b∨cd∨∧

C．ab∨┐cd∨∧ ? ? ? ? ? ? ?D．a┐b∨∧cd∨

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

E→E(1) ∧ T ?{E.val = E(1).val * T.val}

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

T→T(1)# n ? ? {T.val = T(1).val + n.val }

T→ n ? ? ? ? {T.val = n.val}

則分析句子2∧ 3 # 4其值為(C ?)。

A. 10 ? ? ? ? ? ? ? ? ? ? ? ? ? ? B. 21

C. 14 ? ? ? ? ? ? ? ? ? ? ? ? ? ? D. 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’ → S print(S.num)

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

S → a ? ? S.num = 0

L →L(1),S ? ?L.num = L(1).num + S.num

L →S ? L.num = S.num

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

A．0 ? ? ? ? ? ?B．1

C．2 ? ? ? ?D．4

48.若a為終結(jié)符，則A→α.aβ為(B　)。

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

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

49.若B為非終結(jié)符，則A→α.Bβ為(C　)。

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

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

50. 項(xiàng)目A→α.為(A　)。

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. 該行必定填滿“rj” ? ? ? ?B. 該行未必填滿“rj”

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

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

A. 活前綴 ? ? ? ? ? ? ? ? ? B. 前綴

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

54.文法G：S→ x xS | y 所識(shí)別的語(yǔ)言是(D　)。

A．xxy* ? ? ?B．(xxy)* ? ? ?C．xx*yx ? ? D．(xx)*y

55.若狀態(tài)k含有項(xiàng)目“A→α.”，對(duì)任意非終結(jié)符a，都用規(guī)則“A→α”歸約的語(yǔ)法分析方法是(B　)。

A．LALR分析法 ? ? B．LR(0)分析法

C．LR(1)分析法 ? ? 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)集S＝{a,b}上的正閉包運(yùn)算產(chǎn)生的是：(A　)

A. ε ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?B.　a

C.　aa ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?D.　ab

59.表達(dá)式(┐a∨b)∧(e∨f)的逆波蘭表示為(B )。

A．┐ab∨∧ef∨ ? ? ? ? ? ? ? ? ? ? ?B．a┐b∨ef∨∧

C．ab∨┐ef∨∧ ? ? ? ? ? ? ? ? ? ? ? D．a┐b∨∧ef∨

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

E→E(1) ∧ T {E.val = E(1).val * T.val}

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

T→T(1)# n ? ?{T.val = T(1).val + n.val }

T→ n ? ? ? ?{T.val = n.val}

則分析句子3∧ 3 # 4其值為(B ?)。

A. 10 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?B. 21

C. 14 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?D. 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’ → S print(S.num)

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

S → a ? ?S.num = 0

L →L(1),S L.num = L(1).num + S.num

L →S ? L.num = S.num

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

A．0 ? ? ? ?B．1

C．2 ? ? ? ?D．4

63. 在SLR(1)的Action表中，如果某行中存在標(biāo)記為“rj”的欄，則：(B　)

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

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

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

A. 活前綴 ? ? ? ? ? ? ? ? ? B. 前綴

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

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

A．xy* ? ? ? ? ? ? ? ? ? ? ?B．(xy)*

C．xx*yx ? ? ? ? ? ? ? ? ? ?D．x*y

66.若狀態(tài)k含有項(xiàng)目“A→α.”，且僅當(dāng)輸入符號(hào)a∈FOLLOW(A)時(shí)，才用規(guī)則“A→α”歸約的語(yǔ)法分析方法是(D　)。

A．LALR分析法 ? ? ? ? B．LR(0)分析法

C．LR(1)分析法 ? ? ? ? ? ? D．SLR(1)分析法

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

T→T*F|F

F→F↑P|P

P→(T)|a

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

A.(T*F) ? B. T*F ? ? ? ?C. P ? ? ? ? D. P↑(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 ? ? )。

A．E′→E. ? ? B．L→. ? ?C．L→-.L ? D．F→L*F.

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

S→bAb ? ? ? ?print ?“1”

A→(B ? ? ? print ?“2”

A→a ? ? ? ? ?print ?“3”

B→aA) ? ? ? ?print ?“4”

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

A．32224441 B．34242421 C．12424243 D．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 ? ? ?)

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

T→T*F|F

F→F↑P|P

P→(T)|a

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

A.(T*F) ? B. T*F ? ? ? ?C. P ? ? ? ? D. P↑(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 ? ? ?)。

A．E′→.E ? ? B．L→. ? ?C．L→-.L ? D．F→L*.F

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

S→B ? ? ? ?print ?B.vers

B→a ? ? ? ? B.vers=a

B→b ? ? ? ? ? B.vers=b

B→Ba ? ? ? ? B.vers=a+B.vers

B→Bb ? ? ? ? B.vers=b+B.vers

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

A．aabb B．abab C．bbaa D．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 ? ? ?)

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

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

85．在LR(0)的ACTION子表中，如果某一行中有標(biāo)記為“r_j”的欄，則_______C__________。

A．該行既有r_j又有S_j ? ? ? ? ? ? ?B．其它行也有r_j

C．該行一定填滿r_j ? ? ? ? ? ? ? ? D．該行未填滿r_j

86．同正規(guī)式(a|b)+等價(jià)的正規(guī)式是_________B________________。

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é)符，則A→α·aβ為_(kāi)______B______項(xiàng)目。

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

89．一個(gè)文法G，若________C____________，則稱(chēng)它是LL(1)文法。

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

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

90．LR分析器的核心部分是一張分析表，該表由_______D___________組成。

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

91．構(gòu)造編譯程序應(yīng)該掌握_______D__________。

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

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

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

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

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

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

A．連接運(yùn)算“·” ?B．或運(yùn)算“|” C．閉包運(yùn)算“*” ? D．括號(hào)“(”和“)”

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

A．G1：S→aS|bS|ε ? B．G2：S→aSb|ε C．G3：S→aS|Sb|ε ? D．G4：S→abS|ε

96．由文法的開(kāi)始符號(hào)出發(fā)經(jīng)過(guò)若干步(包括0步)推導(dǎo)產(chǎn)生的文法符號(hào)序列稱(chēng)為_(kāi)_____B________。

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

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

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

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

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

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

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

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

100．稱(chēng)正規(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ò)程通常可分為5個(gè)階段詞法分析階段、 語(yǔ)法分析階段、 語(yǔ)義分析和中間代碼生成階段、優(yōu)化階段和目標(biāo)代碼生成階段。

6．如果編譯階段生成的目標(biāo)程序是某特定計(jì)算機(jī)系統(tǒng)的機(jī)器代碼程序，則源程序的執(zhí)行分為兩大階段： 編譯階段 和 ?運(yùn)行階段 。

7．對(duì)編譯程序而言，輸入數(shù)據(jù)是 ? ? 源程序 ? ? ，輸出結(jié)果是 ? ? 目標(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)、遞歸下降子程序)

2．文法中的終結(jié)符集和非終結(jié)符集的交集是 空集 ?。

3．一個(gè)句型的最左直接短語(yǔ)稱(chēng)為該句型的___句柄________________。

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

5．自下而上語(yǔ)法分析中分析器的動(dòng)作有_移進(jìn) ? 、____歸約 ?、__接受_ ?、__報(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(1)分析器由 ?一張LL(1)分析表(預(yù)測(cè)分析表) ?、 ?一個(gè)先進(jìn)后出分析棧 ? 和一個(gè) 控制程序(表驅(qū)動(dòng)程序)組成。

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

11．LR(0)分析法的名字中，“L”表示自左至右分析輸入串，“R”表示 采用最右推導(dǎo)的逆過(guò)程即最左歸約。“0”表示 向右查看0個(gè)字符 。

12．LL(1)分析法中，第一個(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(1)文法的充分必要條件是：對(duì)每一個(gè)非終結(jié)符A的任何兩個(gè)不同產(chǎn)生式A→α|β，有下面的條件成立：(1) ? ? FIRST(α)∩FIRST(β)= ? ? ? ；(2)假若，則有 FIRST(α) ∩ FOLLOW(A) = ? ? ?。

15．對(duì)于LL(1)文法中的任何產(chǎn)生式A→α|β，則需要滿足__First(_α)∩First(β)=Φ ? ? ?、

_若_β=>*ε,則_First(_α) ∩__Follow(A)=_Φ_。

16．LR分析器的核心部分是一張分析表，該表包括 動(dòng)作(ACTION)表和 ?狀態(tài)轉(zhuǎn)換(GOTO)表 等兩個(gè)子表。

17．關(guān)于非終結(jié)符A的直接左遞歸產(chǎn)生式：A→Aα|β，其中α、β是任意的符號(hào)串且β不以A開(kāi)頭，則可以將A的產(chǎn)生式改寫(xiě)為右遞歸的形式為： A→βA’ , A’→αA’|ε 。

18．在消除回溯，提取公共左因子時(shí)，關(guān)于A的產(chǎn)生式A→ δβ₁ | δβ₂ | … | δβ_i |β_i+1 | …| β_j，可以改寫(xiě)為： A → δA’| β_i+1 | …| β_j，A’ →β₁| … |β_i ?。

19．設(shè)G[S]是一文法，如果符號(hào)串x是從識(shí)別符號(hào)推導(dǎo)出來(lái)的，即有x，則稱(chēng)x是文法G[S]的____句型__，若x僅由終結(jié)符號(hào)組成，即，則稱(chēng)x為文法G[S]的__句子 。

20．已知文法G[S]:

S→eT|RT ? ? ? ?T→DR|ε ?R→dR|ε ? ?D→a|bd

求FIRST(S)={e，d，a，b，ε}______；FOLLOW(D)=_{d，#} ? 。

語(yǔ)義處理部分：

1．文法符號(hào)的屬性有兩種，一種稱(chēng)為 繼承屬性 ，另一種稱(chēng)為 綜合屬性 。

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)的屬性有兩種，一種稱(chēng)為 繼承屬性 ，另一種稱(chēng)為 綜合屬性 。

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).。(× )

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

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

4．由于LR(0)分析表構(gòu)造簡(jiǎn)單，所以它的描述能力強(qiáng)，適用面寬；LR(1)分析表因構(gòu)造復(fù)雜而描述能力弱，適用面窄。(× )

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

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

7．LL(1)文法一定不含左遞歸和二義性。(√ )

8．所有LR分析器的總控程序都是一樣的，只是分析表各有不同。(√ )

9．無(wú)論是三元式表示還是間接三元式表示的中間代碼，其三元式在三元式表中的位置一旦確定就很難改變。(√ )

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

11．最左推導(dǎo)也被稱(chēng)為規(guī)范推導(dǎo)。(× ?)

12．運(yùn)算對(duì)象排列的先后順序在后綴式和中綴式中不同。(× ?)

13．出現(xiàn)在移進(jìn)-歸約分析器棧中的內(nèi)容被稱(chēng)為文法G的活前綴。(√ ?)

14．LR方法可以分析含有左遞歸的文法。( √ )

15．三元式的編號(hào)具有雙重含義，既代表此三元式，又代表三元式存放的結(jié)果。(√ ?)

16．語(yǔ)義規(guī)則中的屬性有兩種：綜合屬性與繼承屬性。(√ ?)

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

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

19．四元式的編號(hào)具有雙重含義，既代表此四元式，又代表四元式存放的結(jié)果。(× )

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

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

22．對(duì)于任何一個(gè)正規(guī)式e，都存在一個(gè)DFA A，使得L(e)=L(A)。( √ ? ? )

23．最小化的DFA，它的狀態(tài)數(shù)最小。( ? √ ? ?)

24．NFA的確定化算法具有消除ε邊的功能。( ? √ ? ?)

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

26．一個(gè)語(yǔ)言的文法是不唯一的。( ?√ ? ?)

27．語(yǔ)法錯(cuò)誤校正的目的是為了把錯(cuò)誤改正過(guò)來(lái)。( ? × ? )

28．源程序和目標(biāo)程序是等價(jià)關(guān)系。( ? √ ? )

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

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

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

32．最小化的DFA所識(shí)別接受的正規(guī)集最小。( ? × ? )

33．一個(gè)語(yǔ)言(如C語(yǔ)言)的句子是有窮的。( ? ?× )

34．LL(1)方法又稱(chēng)為預(yù)測(cè)分析方法。( √ ? ? )

35．一個(gè)LL(1)文法是無(wú)二義和無(wú)回溯方法。( ?√ ? ?)

36．語(yǔ)法分析器可以檢查出程序中的所有錯(cuò)誤。( ?× ? ?)

37．LR分析法是自上而下的語(yǔ)法分析方法。( ? × ? )

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

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

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

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

E. 出錯(cuò)處理

2. 令S＝{a,b}，則S上的符號(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]：S→CD Ab→bA

　　C→aCA Ba→aB

? ? ? ? C→bCB Bb→bB

　　AD→aD C→ε

　　BD→bD D→ε

　　Aa→bD

是(ABE　)。

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è)編譯器可能有的階段為(ABCDE　)

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

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

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

7 令S＝{a,b}，則S上的所有以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. LR(0)分析法

C. LALR(1)分析法 ? ? ? ? ? ?D. LL(1)分析法

E. SLR(1)分析法

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

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

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

10．令S＝{a,b}，則S上的符號(hào)串的全體可用下面的正規(guī)式表示。(ABE　)

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

C. (a|b)⁺ ?D. (ab)* ? E. (a*b*)*

11．下列符號(hào)串是符號(hào)集S＝{a,b}上的正規(guī)式的有：(　ABCDE)

A. ε ? B.　a ?C.　ab D.　(ab｜a)(ab｜a)

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．令S＝{a,b}，則S上的所有以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)*

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á)式((a|b)*|aa)*b的NFA。

解：

2．令文法G[N]為 ? ? ? G[N]: N→D|ND

D→0|1|2|3|4|5|6|7|8|9

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

解：最左推導(dǎo)：NND NDD DDD 5DD 56D 568

最右推導(dǎo)：NND N8 ?ND8N68 D68 568

3．給出字母表Σ={a,b}上的同時(shí)只有奇數(shù)個(gè)a和奇數(shù)個(gè)b的所有串的集合的正規(guī)文法；

解： G[S]：S→aA|bB

A→aS|bC|b

B→bS|aC|a

C→bA|aB|ε

4．給定文法：S→(L)| a

? ? ? ? ? ? L→L,S | S

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

解：

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

S’→S S.depth = 0

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

S →a print(S.depth)

L →L⁽¹⁾,S L⁽¹⁾.depth= L.depth; S.depth = L.depth

L →S S.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)的后綴式。

解： abcd- -*efgh- -i*$$ ?

6．判斷文法G[S]:S → BA

A ?→ BS | d

B ?→ aA| bS | c

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

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

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

求其FOLLOW集如下：

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

由A → BS | d 得：

FIRST(BS) ∩ FIRST(‘d’)= {a, b, c} ∩ ze8trgl8bvbq = Φ

由B → aA| bS | c 得

FIRST(aA) ∩ FIRST(bS) ∩FIRST(c) = {a} ∩{b}∩ {c} =Φ

由于文法G[S]不存在形如β→ε的產(chǎn)生式，故無(wú)需求解形如FIRST(α)∩ FOLLOW(A)的值，也即文法G[S]是一個(gè)LL(1)文法。

7．對(duì)于文法G[E]:E→E+T | T

T→T+P | P

P→(E) | i

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

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

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

句柄：P；

8．已知文法G[A]:A→aABl|a

B→Bb|d

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

解：G[A′]：A→aA′

A′→ABl | ε

B→dB′

B′→bB′| ε

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

if (x＞y) m= 1;

else ?m=0;

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

2 (j,_,_,5)

3 (=,1,_,m)

4 (j,_,_,6)

5 (=,0,_,m)

6:

10．將以下DFA最小化。(8分)

解：

11．設(shè)M=({x,y},{a,b}, f, x, {y})為一非確定的有限自動(dòng)機(jī)，其中f定義如下：

f(x,a)={x,y} ? ? ? f{x,b}={y}

f(y,a)=Φ ? ? ? ? f{y,b}={x,y}

試構(gòu)造相應(yīng)的確定有限自動(dòng)機(jī)M′。(12分)

解：對(duì)照自動(dòng)機(jī)的定義M=(S,Σ,f,So,Z)，由f的定義可知f(x,a)、f(y,b)均為多值函數(shù)，因此M是一非確定有限自動(dòng)機(jī)。

先畫(huà)出NFAM相應(yīng)的狀態(tài)圖，如下圖所示。

用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣，如下表所示。

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

M′=({0,1,2},{a,b},f,0,{1,2})，

M′狀態(tài)轉(zhuǎn)換圖如下圖所示。

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

12．試構(gòu)造下述文法的SLR(1)分析表。(13分)

G[A]: A→aABl|a

B→Bb|d

解：拓廣文法

(0)S→A

(1)A→aABl

(2)A→a

(3)B→Bb

(4)B→d

First(A)={a}follow(A)={#，d}

First(B)=ze8trgl8bvbqfollow(B)={l}

SLR(1)分析表如下：

13．將下面的語(yǔ)句翻譯成四元式序列：(7分)

if (x＞y) m= 1;

else ?m=x+y;

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

2 (j,_,_,5)

3 (=,1,_,m)

4 (j,_,_,7)

5 (+,x,y,T₁)

6 (=, T₁,_,m)

7:

14. 試構(gòu)造下述文法的LL(1)分析表。(15分)

G[S]: S→(L)|a

L→L，S|S

解：消除左遞歸：

G(S): S ? (L) | a

L ? SL’

L’ ? , SL’| ε

構(gòu)造FIRST集，如下：

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

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

(3)FIRST(L’)= {,, ε}

構(gòu)造FOLLOW集如下：

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

(2)FOLLOW(L)= {)}

(3)FOLLOW(L’)= {)}

LL(1)分析表

15．判斷文法G[S]:S → BA

A ?→ BS | d

B ?→ aA| bS | c

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

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

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

求其FOLLOW集如下：

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

由A → BS | d 得：

FIRST(BS) ∩ FIRST(‘d’)= {a, b, c} ∩ ze8trgl8bvbq = Φ

由B → aA| bS | c 得

FIRST(aA) ∩ FIRST(bS) ∩FIRST(c) = {a} ∩{b}∩ {c} =Φ

由于文法G[S]不存在形如β→ε的產(chǎn)生式，故無(wú)需求解形如FIRST(α)∩ FOLLOW(A)的值，也即文法G[S]是一個(gè)LL(1)文法。

16．對(duì)于文法G[E]:E→E+T | T

T→T+P | P

P→(E) | i

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

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

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

句柄：P；

17．已知文法G[S]:S→aSbS|bSaS|ε

試證明G[S]是二義文法

證明：該文法產(chǎn)生的語(yǔ)言是a的個(gè)數(shù)和b的個(gè)數(shù)相等的串的集合。該文法二義，例如句子abab有兩種不同的最左推導(dǎo)。

SaSbSabSabaSbSababSabab

SaSbSabSaSbSabaSbSababSabab

18．將下面的語(yǔ)句翻譯成四元式序列：

while(a

if (c＞d) x=y+z

解：100(j

101 (j,_,_,107)

102 (j>,c,d,104)

103 (j,_,_,106)

104 (+,y ,z ,t)

105 (=,t ,_ ,x)

106 (j,_,_,100)

107:

19．構(gòu)造正規(guī)表達(dá)式a(aa)*bb(bb)*a的最小化的確定有限自動(dòng)機(jī)M′。

解： 先畫(huà)出正規(guī)式相應(yīng)的NFAM狀態(tài)圖，如下圖所示。

用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣，如下表所示。

將狀態(tài)分為終態(tài)集{Y}和非終態(tài)集{X,1,2,3,4,5}

因?yàn)?#xff5b;X,1,2,3,4,5｝a={1,2,1,_,Y,_}

所以非終態(tài)集分為{X,1,2},{3,5},{4}

因?yàn)閧X,1,2}b={_,3,_},所以分為

最后得到集合{X,2},{1},{3,5},{4},{Y}重新命名為1，2，3，4，5得到最小化的DFAM′狀態(tài)轉(zhuǎn)換矩陣和狀態(tài)轉(zhuǎn)換圖如下圖所示。

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

20．試構(gòu)造下述文法的SLR(1)分析表。

G[A]: A→aABl|a

B→Bb|d

解：拓廣文法

(0)S→A

(1)A→aABl

(2)A→a

(3)B→Bb

(4)B→d

First(A)={a}follow(A)={#，d}

First(B)=ze8trgl8bvbqfollow(B)={l}

SLR(1)分析表如下：

21．畫(huà)出編譯程序的總體結(jié)構(gòu)圖，簡(jiǎn)述各部分的主要功能。

解：編譯程序的總體框圖如下所示：

(1)詞法分析器，又稱(chēng)掃描器，它接受輸入的源程序，對(duì)源程序進(jìn)行詞法分析，識(shí)別出一個(gè)個(gè)單詞符號(hào)，其輸出結(jié)果是二元式(單詞種別，單詞自身的值)流。

(2)語(yǔ)法分析器，對(duì)單詞符號(hào)串進(jìn)行語(yǔ)法分析(根據(jù)語(yǔ)法規(guī)則進(jìn)行推導(dǎo)或歸約)，識(shí)別出程序中的各類(lèi)語(yǔ)法單位，最終判斷輸入串是否構(gòu)成語(yǔ)法上正確的句子。

(3)語(yǔ)義分析及中間代碼生成器，按照語(yǔ)義規(guī)則對(duì)語(yǔ)法分析器歸約出(或推導(dǎo)出)的語(yǔ)法單位進(jìn)行語(yǔ)義分析并把它們翻譯成一定形式的中間代碼。編譯程序可以根據(jù)不同的需要選擇不同的中間代碼形式，有的編譯程序甚至沒(méi)有中間代碼形式，而直接生成目標(biāo)代碼。

(4)優(yōu)化器對(duì)中間代碼進(jìn)行優(yōu)化處理。一般最初生成的中間代碼執(zhí)行效率都比較低，因此要做中間代碼的優(yōu)化，其過(guò)程實(shí)際上是對(duì)中間代碼進(jìn)行等價(jià)替換，使程序在執(zhí)行時(shí)能更快，并占用更小的空間。

(5)目標(biāo)代碼生成器，把中間代碼翻譯成目標(biāo)程序。中間代碼一般是一種與機(jī)器無(wú)關(guān)的表示形式，只有把它再翻譯成與機(jī)器硬件直接相關(guān)的機(jī)器能識(shí)別的語(yǔ)言，即目標(biāo)程序，才能在機(jī)器上運(yùn)行。

(6)表格管理模塊保持一系列的表格，登記源程序的各類(lèi)信息和編譯各階段的進(jìn)展?fàn)顩r。編譯程序各個(gè)階段所產(chǎn)生的中間結(jié)果都記錄在表格中，所需要的信息也大多從表格中獲取，整個(gè)編譯過(guò)程都在不斷和表格打交道。

(7)出錯(cuò)處理程序?qū)Τ霈F(xiàn)在源程序中的錯(cuò)誤進(jìn)行處理。如果源程序有錯(cuò)誤，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯(cuò)誤，把有關(guān)錯(cuò)誤信息報(bào)告給用戶。編譯程序的各個(gè)階段都有可能發(fā)現(xiàn)錯(cuò)誤，出錯(cuò)處理程序要對(duì)發(fā)現(xiàn)的錯(cuò)誤進(jìn)行處理、記錄，并反映給用戶。

22．對(duì)于文法G(S)：

S → (L) | aS | a

L → L, S | S

(1) 畫(huà)出句型(S,(a))的語(yǔ)法樹(shù)。

(2) 寫(xiě)出上述句型的所有短語(yǔ)、直接短語(yǔ)和句柄。

解：

(1) 句型(S,(a))的語(yǔ)法樹(shù)如下圖所示：

(2) 從語(yǔ)法樹(shù)中可以找到(3分)短語(yǔ)：a; (a); ?S; ?S,(a); ?(S, (a))

直接短語(yǔ)：a; ?S

句柄：S

23．構(gòu)造一文法，使其描述的語(yǔ)言L= {ω |ω ∈ (a,b)*，且ω中含有相同個(gè)數(shù)的a和b}。

解：

S→ ε| aA|bB

A→ b| bS| aAA

B→ a| aS| bBB

24．分別給出表達(dá)式–(a*(b-c))+d的逆波蘭表示和四元式表示。

解：(1)逆波蘭式：abc-*@d+ 其中使用@代表一目減運(yùn)算 ?

(2)四元式： ?

①(-, b, c, T₁)

②(*, a, T₁,T₂)

③(@, T2, _, T₃)

④(+, T₃,d, T₄)

25．把下列語(yǔ)句翻譯為四元式序列：

while (A > B)

if (C > D)

X = Y * Z

else

X = Y + Z

解：

(1) (j>, A, B, 3)

(2) (j, _, _, 11)

(3) (j>, C, D, 5)

(4) (j, _, _, 8)

(5) (*, Y, Z, T₁)

(6) (=, T₁,_, X)

(7) (j, _, _, 1)

(8) (+, Y, Z, T₂)

(9) (=, T₂,_, X)

(10) (j, _, _, 1)

(11)

26．構(gòu)造一個(gè)DFA，它接受Σ= {0,1}上所有滿足如下條件的字符串：每個(gè)1后面都有0直接跟在右邊。

解：(1)0*(0|10)*0*或者(0|10)* ?

(2)

①NFA ? (2分)

②子集法確定化

• I	I0	I1
  {X, 0, 1, 3, Y}	{0, 1, 3, Y}	{2}
  {0, 1, 3, Y}	{0, 1, 3, Y}	{2}
  {2}	{1, 3, Y}	-
  {1, 3, Y}	{1, 3, Y}	{2}

重新命名狀態(tài)，即得：

• S	0	1
  1	2	3
  2	2	3
  3	4	-
  4	4	3

③最小化

首先分為終態(tài)集和非終態(tài)集{3} {1, 2, 4} 因?yàn)?/strong>1₀= 2 2₀ = 2 4₀ = 4狀態(tài)均屬于集合{1,2, 4}，所以對(duì)于輸入符號(hào)0不能區(qū)分開(kāi)1，2，4三個(gè)狀態(tài)；1₁= 3 2₁ = 3 4₁ =3狀態(tài)均屬于集合{3}，所以對(duì)于輸入符號(hào)1也不能區(qū)分開(kāi)1，2，4三個(gè)狀態(tài)；因此最終的狀態(tài)劃分即為:{3} {1, 2, 4}，其對(duì)應(yīng)的DFA如下圖所示：

27．已知文法G(S)：

S→S*aP|aP| *aP

P→+aP|+a

(1) 將文法G(S)改寫(xiě)為LL(1)文法G’(S)；

(2) 寫(xiě)出文法G’(S)的預(yù)測(cè)分析表。

解：

(1)消除左遞歸，文法變?yōu)?#xff1a; ?

S→aPS’|*aPS’

S’→*aPS’| ε

P→+aP|+a

提取公共左因子，文法變?yōu)?/strong>G’(S)： ?

S→aPS’|*aPS’

S’→*aPS’|ε

P→+aP’

P’→P| ε

(2)計(jì)算每個(gè)非終結(jié)符的FIRST集和FOLLOW集：

FIRST(S) = {a, *} FOLLOW(S) = {#}

FIRST(S’) = {*, ε} FOLLOW(S’)= {#}

FIRST(P) = {+} FOLLOW(P) = {*, #}

FIRST(P’) = {+, ε} FOLLOW(P’)= {*, #}

構(gòu)造該文法的預(yù)測(cè)分析表如下：(5分)

• 	*	+	a	#
  S	S→*aPS’		S→aPS’
  S’	S’→ *aP			S’→ ε
  P		P→+aP’
  P’	P’→ε	P’→P		P’→ε

28．已知文法G(S)：

S→aS | bS | a

(1) 構(gòu)造識(shí)別該文法所產(chǎn)生的活前綴的DFA；

(2) 判斷該文法是LR(0)還是SLR(1)，并構(gòu)造所屬文法的LR分析表。

解：

(1)將文法G(S)拓廣為G’(S’)：

(0) S’→S

(1) S→aS

(2) S→bS

(3) S→a

識(shí)別該文法所產(chǎn)生的活前綴的DFA：

(2)在狀態(tài)I₂存在“移近-歸約”沖突，因此該文法不是LR(0)文法。

計(jì)算S的FOLLOW集合：

FOLLOW(S)= {#}

I₂中的沖突用FOLLOW集合可以解決，所以該文法是SLR(1)文法。

構(gòu)造SLR(1)分析表如下：

• • • 狀態(tài)	ACTION			GOTO
      	a	b	#	S
      0	s2	s3		1
      1			acc
      2	s2	s3	r3	4
      3	s2	s3		5
      4			r1
      5			r2

29．將下圖所示的非確定有限自動(dòng)機(jī)(NFA)變換成等價(jià)的確定有限自動(dòng)機(jī)(DFA)。其中，X為初態(tài)，Y為終態(tài)。

【解】 用子集法將NFA確定化，如圖所示。

確定化的DFA如下圖所示：

30．對(duì)正規(guī)式(a|b)*abb構(gòu)造其等價(jià)的NFA。

【解】

31．下面的文法產(chǎn)生0和1的串，即二進(jìn)制的正整數(shù)，請(qǐng)給出決定每個(gè)二進(jìn)制數(shù)的值(十進(jìn)制形式)的語(yǔ)法制導(dǎo)定義。

【解】定義值屬性為.val，翻譯方案如下：

B ? B₁0 { B.val = B₁.val ?2 }

B ? B₁1 { B.val = B₁.val ?2 + 1 }

B ? 1 { B.val= 1 }

B ? 0 { B.val= 0 }

32．把算術(shù)表達(dá)式?(a+ b) ? (c + d)+ (e+ f) 翻譯成等價(jià)的四元式序列(序號(hào)從0開(kāi)始)。

【解】

0(+，a,b ,T1)

1(uminus，T1，-，T2)

2(+，c,d , T3)

3(*，T2，T3，T4)

4(+，e，f，T5)

5(+，T4，T5，T6)

33．設(shè)有文法G[S]:

S→a|(T)|?

T→T,S|S

試給出句子(a,a,a)的最左推導(dǎo)。

【解】(1)(a,a,a)的最左推導(dǎo)

S=>(T)=>(T,S)=>(T,S,S)=>(S,S,S)=>(a,S,S)=>(a,a,S)=>(a,a,a)

34．已知文法Ｇ：

S → ?( ?L ?| ?a

L → ?S ?, ?L ?| ?)

判斷是不是LL(1)文法，如果是請(qǐng)構(gòu)造文法Ｇ 的預(yù)測(cè)分析表，如果不是請(qǐng)說(shuō)明理由。

【解】

1)求各非終結(jié)符的FISRT 集和FOLLOW 集：

= { (, a )

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

FOLLOW(S) = {, ?# }

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

FIRST(( ?L)∩{a}=Φ

FIRST(S ?, ?L)∩{)}=Φ

所以是LL(1)文法

2)預(yù)測(cè)分析表：

• 	(	a	,	}	#
  S	S→ ( L	S→ a
  L	L→ S , L	L→ S , L		L → )

35．文法

S ?A a | b A c | d c | b d a

A ? d

構(gòu)造識(shí)別活前綴的DFA。請(qǐng)根據(jù)這個(gè)DFA來(lái)判斷該文法是不是SLR(1)文法并說(shuō)明理由。

【解】

Follow(S)={#}

Follow(A)={a,c}

I4存在沖突且Follow(A)∩{c}={c}

I7存在沖突且Follow(A)∩{a}={a}

所以不是SLR(1)文法

36．將下圖所示的確定有限自動(dòng)機(jī)(DFA)最小化。其中，X為初態(tài)，Y為終態(tài)。

【解】 先劃分為終態(tài)集{Y}和非終態(tài)集I={X,1,2,3}

X面對(duì)輸入符號(hào)b時(shí)下一狀態(tài)屬于I，而1,2,3面對(duì)輸入符號(hào)b時(shí)下一狀態(tài)屬于{Y}，故劃分為{X}、{1,2,3}

非終態(tài)2和非終態(tài)3面對(duì)輸入符號(hào)a的下一狀態(tài)相同，而1不同，即最簡(jiǎn)狀態(tài){X}、{1}、{2，3}、{Y}。按順序重新命名為0、1、2、3，則得到最簡(jiǎn)DFA，

37．請(qǐng)畫(huà)出識(shí)別無(wú)符號(hào)十進(jìn)制整數(shù)的狀態(tài)轉(zhuǎn)換圖

【解】

38．設(shè)有文法G[S]:

S→S*S|S+S|(S)|i

該文法是否為二義文法,并說(shuō)明理由？

【解】該文法是二義文法，因?yàn)樵撐姆ù嬖诰渥觟*i+i,該句子有兩棵不同的語(yǔ)法樹(shù)如圖所示。

39．程序的文法如下：

P → D

D → D;D| id : T | proc id; D; S

寫(xiě)一語(yǔ)法制導(dǎo)定義，打印該程序一共聲明了多少個(gè)id

【解】 屬性num表示id個(gè)數(shù)

P→D print(D.num)

D→D(1)；D(2) D.num= D(1).num + D(2).num

D→id : T D.num = 1

D→proc id; D(1); S D.num = D(1).num + 1

例：procid; proc id; id : T; S; S(從語(yǔ)法樹(shù)分析入手)

(注意：本例只是幫助學(xué)生理解題意，不是答案部分)

40．把下列語(yǔ)句翻譯為四元式序列(四元式序號(hào)從1開(kāi)始)：

? ? ? while(A > B)

if (C > D)

X = Y * Z

? ? ? ? ? else

X = Y + Z

【解】(1)(j>, A, B, 3)

? (2)(j, _, _, 11)

(3) (j>, C, D, 5)

(4) (j, _, _, 8)

(5) (*, Y, Z, T1)

(6) (=, T1, _, X)

(7) (j, _, _, 1)

(8) (+, Y, Z, T2)

(9) (=, T2, _, X)

(10) (j, _, _, 1)

(11)

41.構(gòu)造下面文法的LL(1)分析表。

G[D]:D ?TL

T?int | real

L?id R

R?, id R | ?

【解】FIRST(T)={int real } FOLLOW(T)={id }

FIRST(L)={ id } ? ? ? FOLLOW(L)={ #}

FIRST(R)={ , ? ?} ? FOLLOW(R)={ #}

FIRST(D)={ int real} FOLLOW(D)={#}

因?yàn)镕IRST(int)∩FIRST(real)=Φ

FIRST(, idR)∩FOLLOW(R)=Φ

所以是LL(1)文法，LL(1)分析表如下：