編譯原理考試題及答案匯總

編譯原理考試題及答案匯總

一、選擇

1.將編譯程序分成若干個(gè)“遍”是為了一B_。

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

B.使程序的結(jié)構(gòu)更加清晰

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

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

2.正規(guī)式MI和M2等價(jià)是指_C_。

A.MI和M2的狀態(tài)數(shù)相等B.Ml和M2的有向弧條數(shù)相等。

C.Ml和M2所識(shí)別的語言集相等D.Ml和M2狀態(tài)數(shù)和有向弧條數(shù)相等

3.中間代碼生成時(shí)所依據(jù)的是_C_?

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

4.后綴式ab+cd+/可用表達(dá)式_B_來表示。

A.a+b/c+dB.(a+b)/(c+d)C.a+b/(c+d)D.a+b+c/d

6.一個(gè)編譯程序中，不僅包含詢法分析，_A,中間代碼生成，代碼優(yōu)化，目標(biāo)代碼

生成等五個(gè)部分。

A.()語法分析B.()文法分析C.()語言分析D.()解釋分析

7.詞法分析器用于識(shí)別_C_.

A.()字符串B.()語句C.()單詞D.()標(biāo)識(shí)符

8.語法分析器則可以發(fā)現(xiàn)源程序中的—D_?

A.()語義錯(cuò)誤B.()語法和語義錯(cuò)誤

C.()錯(cuò)誤并校正D.()語法錯(cuò)誤

9.下面關(guān)于解釋程序的描述正確的是_B_.

(1)解釋程序的特點(diǎn)是處理程序時(shí)不產(chǎn)生目標(biāo)代碼

(2)解釋程序適用于COBOL和FORTRAN語言

(3)解釋程序是為打開編譯程序技術(shù)的僵局而開發(fā)的

A.()(1)(2)B.()(1)C.()(1)(2)(3)D.()(2)(3)

10.解釋程序處理語言時(shí)，大多數(shù)采用的是_B_方法。

A.()源程序命令被逐個(gè)直接解釋執(zhí)行

B.()先將源程序轉(zhuǎn)化為中間代碼，再解釋執(zhí)行

C.()先將源程序解釋轉(zhuǎn)化為目標(biāo)程序，再執(zhí)行

D.()以上方法都可以

11.編譯過程中，語法分析器的任務(wù)就是_B—。

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

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

A.()(2)(3)B.()(2)(3)(4)C.()(1)(2)(3)D.()(1)(2)(3)(4)

12.編譯程序是一種_C_o

A.()匯編程序B.()翻譯程序C.()解釋程序D.()目標(biāo)程序

13.文法G所描述的語言是其：—的集合。

A.()文法G的字母表V中所有符號(hào)組成的符號(hào)串

B.()文法G的字母表V的閉包V*中的所有符號(hào)串

C.()由文法的開始符號(hào)推出的所有終極符串

D.()由文法的開始符號(hào)推出的所有符號(hào)串

14.文法分為四種類型，即0型、1型、2型、3型。其中3型文法是—B_?

A.()短語文法B.()正則文法C.()上下文有關(guān)文法D.()上下文無關(guān)文法

15.一個(gè)上下文無關(guān)文法G包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符

號(hào)一，一個(gè)開始符號(hào)，以及一組—D―o

A.()句子B.()句型C.()單詞D.()產(chǎn)生式

16.通常一個(gè)編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)

代碼生成等五個(gè)部分，還應(yīng)包括/O

1/110

A.()模擬執(zhí)行器B.()解釋器

C.()表格處理和出錯(cuò)處理D.()符號(hào)執(zhí)行器

17.文法G[N]=(,{N,B},N,{N-b|bB,B-bN}),該文法所描述的

語言是C

A.()L(G[N])={bi|i>0}B.()L(G[N])={b2i|i20}

C.()L(G[N])={b2i+l|i20}D.()L(G[N])={b2i+l|i21}

18.一個(gè)句型中的最左_B稱為該句型的句柄。

A.()短語B.()簡(jiǎn)單短語C.()素短語D.()終結(jié)符號(hào)

19.設(shè)G是一個(gè)給定的文法，S是文法的開始符號(hào)，如果S->x(其中xGV*),則稱x

是文法G的一個(gè)_B_。

A.()候選式B.()句型C.()單詞D.()產(chǎn)生式

20.文法G[E]：

E-T|E+T

T-F|T*F

F-a|(E)

該文法句型E+F*(E+T)的簡(jiǎn)單短語是下列符號(hào)串中的。

①(E+T)②E+T③F④F*(E+T)

A.()①和③B.()②和③C.()③和④D.()③

21.若一個(gè)文法是遞歸的，則它所產(chǎn)生的語言的句子—A—。

A.()是無窮多個(gè)B.()是有窮多個(gè)

C.()是可枚舉的D.()個(gè)數(shù)是常量

22.詞法分析器用于識(shí)別C_o

A.()句子B.()句型C.()單詞D.()產(chǎn)生式

23.在語法分析處理中，F(xiàn)IRST集合、FOLLOW集合、SELECT集合均是—B___。

A.()非終極符集B.()終極符集C.()字母表D.7)狀態(tài)集

24.在自底向上的語法分析方法中，分析的關(guān)鍵是_A_。

A.()尋找句柄B.()尋找句型C.()消除遞歸D.()選擇候選式

25.在LR分析法中，分析棧中存放的狀態(tài)是識(shí)別規(guī)范句型C—的DFA狀態(tài)。

A.()句柄B.()前綴C.()活前綴D.()LR(O)項(xiàng)目

26.文法G產(chǎn)生的_【)—的全體是該文法描述的語言。

A.()句型B.()終結(jié)符集C.()非終結(jié)符集D.()句子

27.若文法G定義的語言是無限集，則文法必然是A_

A.()遞歸的B.()前后文無關(guān)的

C.()二義性的D.()無二義性的

28.四種形式語言文法中，1型文法又稱為—A―文法。

A.()短語結(jié)構(gòu)文法B.()前后文無關(guān)文法

C.()前后文有關(guān)文法D.()正規(guī)文法

29.一個(gè)文法所描述的語言是—A—。

A.()唯一的B.()不唯一的

C.()可能唯一，好可能不唯一D.()都不對(duì)

30._B_和代碼優(yōu)化部分不是每個(gè)編譯程序都必需的。

A.()語法分析B.()中間代碼生成

C.()詞法分析D.()目標(biāo)代碼生成

31._B是兩類程序語言處理程序。

A.()高級(jí)語言程序和低級(jí)語言程序B.()解釋程序和編譯程序

C.()編譯程序和操作系統(tǒng)D.()系統(tǒng)程序和應(yīng)用程序

32.數(shù)組的內(nèi)情向量中肯定不含有數(shù)組的_八的信息。

A.()維數(shù)B.()類型C.()維上下界D.()各維的界差

33.一個(gè)上下文無關(guān)文法G包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào),

一個(gè)開始符號(hào)，以及一組—D—。

A.()句子B.()句型

2/110

c.()單詞D.()產(chǎn)生式

34.文法分為四種類型，即0型、1型、2型、3型。其中2型文法是—1)_。

A.()短語文法B.()正則文法

C.()上下文有關(guān)文法D.()上下文無關(guān)文法

35.一個(gè)上下文無關(guān)文法G包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào),

一個(gè)開始符號(hào)，以及一組—D—。

A.()句子B.()句型C.()單詞D.()產(chǎn)生式

36._A_是一種典型的解釋型語言。

A.()BASICB.()CC.()FORTRAND.()PASCAL

37.與編譯系統(tǒng)相比，解釋系統(tǒng)—D_。

A.()比較簡(jiǎn)單，可移植性好，執(zhí)行速度快

B.()比較復(fù)雜，可移植性好，執(zhí)行速度快

C.()比較簡(jiǎn)單，可移植性差，執(zhí)行速度慢

D.()比較簡(jiǎn)單，可移植性好，執(zhí)行速度慢

38.用高級(jí)語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫_B—。

A.()源程序B.()目標(biāo)程序C.()連接程序D.()解釋程序

39.編寫一個(gè)計(jì)算機(jī)高級(jí)語言的源程序后，到正式上機(jī)運(yùn)行之前，一般要經(jīng)過—B_這幾

步：

(1)編輯⑵編譯(3)連接(4)運(yùn)行

A.()(1)(2)(3)(4)B.()(1)(2)(3)C.()(1)(3)D.()(1)(4)

40.把匯編語言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由_A_完成的。

A.()編譯器B.()匯編器

C.()解釋器D.()預(yù)處理器

41.詞法分析器的輸出結(jié)果是_C—。

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

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

42.文法G：S-xSx|y所識(shí)別的語言是_C—。

A.()xyxB.()(xyx)*C.()xnyxn(n20)D.()x*yx*

43.如果文法G是無二義的，則它的任何句子a_A_。

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

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

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

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

44.構(gòu)造編譯程序應(yīng)掌握_D_。

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

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

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

A.()指示器B.()臨時(shí)變量

C.()符號(hào)表D.()程序變量

46.表達(dá)式(~iAVB)A(C\/D)的逆波蘭表示為_B_。

A.()-IABVACDVB.()A-)BVCDVA

C.()ABV-]CDVAD.()A-|BVACDV

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

A.()運(yùn)行時(shí)間較短B.()占用存儲(chǔ)空間較小

C.()運(yùn)行時(shí)間短但占用內(nèi)存空間大D.()運(yùn)行時(shí)間短且占用存儲(chǔ)空間小

48.下列_C—優(yōu)化方法不是針對(duì)循環(huán)優(yōu)化進(jìn)行的。

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

C.()刪除多余運(yùn)算D.()代碼外提

49.編譯程序使用_B_區(qū)別標(biāo)識(shí)符的作用域。

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

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

3/110

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

D.()標(biāo)識(shí)符的行號(hào)

50.編譯程序絕大多數(shù)時(shí)間花在—D_上。

A.()出錯(cuò)處理B.()詞法分析C.()目標(biāo)代碼生成D.()表格管理

51.編譯程序是對(duì)_D_=

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

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

52.采用自上而下分析，必須_C—。

A.()消除左遞歸B.()消除右遞歸

C.()消除回溯D.()提取公共左因子

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

A.()直接短語B.()句柄

C.()最左素短語D.()素短語

54.若a為終結(jié)符，則A->a?aB為B—項(xiàng)目.

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

55.間接三元式表示法的優(yōu)點(diǎn)為_A—。

A.()采用間接碼表，便于優(yōu)化處理B.()節(jié)省存儲(chǔ)空間，不便于表的修改

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

56.基本塊內(nèi)的優(yōu)化為_B_?

A.()代碼外提，刪除歸納變量B.()刪除多余運(yùn)算，刪除無用賦值

C.()強(qiáng)度削弱，代碼外提D.()循環(huán)展開，循環(huán)合并

57.在目標(biāo)代碼生成階段，符號(hào)表用—D_?

A.()目標(biāo)代碼生成B.()語義檢查C.()語法檢查D.()地址分配

58.若項(xiàng)目集Ik含有A->a?,則在狀態(tài)k時(shí)，僅當(dāng)面臨的輸入符號(hào)aGFOLLOW(A)

時(shí)，才采取“A->a.”動(dòng)作的一定是_D—。

A.()LALR文法B.()LR(O)文法

C.()LR(1)文法D.()SLR⑴文法

59.堆式動(dòng)態(tài)分配申請(qǐng)和釋放存儲(chǔ)空間遵守_D—原則。

A.()先請(qǐng)先放B.()先請(qǐng)后放

C.()后請(qǐng)先放D.()任意

二、判斷

1.計(jì)算機(jī)高級(jí)語言翻譯成低級(jí)語言只有解釋一種方式。(X)

2.在編譯中進(jìn)行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯(cuò)誤。(X)

3.甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系

統(tǒng)功能完全相同。(J)

4.正則文法其產(chǎn)生式為A->a,A->Bb,A,BeVN,a、bWVT。(X)

5.每個(gè)文法都能改寫為LL(1)文法。(J)

6.遞歸下降法不允許任一非終極符是直接左遞歸的。(J)

7.算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。(X)

8.自底而上語法分析方法的主要問題是候選式的選擇。(X)

9.LR法是自頂向下語法分析方法。(X)

10.簡(jiǎn)單優(yōu)先文法允許任意兩個(gè)產(chǎn)生式具有相同右部。(義)

11.“用高級(jí)語言書寫的源程序都必須通過編譯，產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行”這種

說法。(X)

12.若一個(gè)句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。(X)

13.一個(gè)句型的句柄一定是文法某產(chǎn)生式的右部。(V)

14.在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。(X)

15.僅考慮一個(gè)基本塊，不能確定一個(gè)賦值是否真是無用的。(V)

16.削減運(yùn)算強(qiáng)度破壞了臨時(shí)變量在一基本塊內(nèi)僅被定義一次的特性。(V)

4/110

17.在中間代碼優(yōu)化中循環(huán)上的優(yōu)化主要有不變表達(dá)式外提和削減運(yùn)算強(qiáng)度。（X）

18.數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。（x）

19.編譯程序與具體的機(jī)器有關(guān)，與具體的語言無關(guān)。（x）

20.遞歸下降分析法是自頂向上分析方法。（J）

21.產(chǎn)生式是用于定義詞法成分的一種書寫規(guī)則。（X）

22.LR法是自頂向下語法分析方法。（X）

23.在SLR（1）分析法的名稱中，S的含義是簡(jiǎn)單的。（V）

24.綜合屬性是用于“自上而下”傳遞信息。（X）

25.符號(hào)表中的信息欄中登記了每個(gè)名字的屬性和特征等有關(guān)信息，如類型、種屬、所占

單元大小、地址等等。（X）

26.程序語言的語言處理程序是一種應(yīng)用軟件。（X）

27.一個(gè)LL（1）文法一定是無二義的。（X）

28.正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。（X）

29.一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是初態(tài)，最多只有一個(gè)終態(tài)。（V）

30.目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問題。（X）

31.逆波蘭法表示的表達(dá)式亦稱后綴式。（J）

32.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語法樹，則稱這個(gè)文法是二義的。（V）

33.數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。（X）

34.對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用動(dòng)態(tài)貯存分配策略。（X）

35.編譯程序是對(duì)高級(jí)語言程序的解釋執(zhí)行。（X）

36.一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一的終態(tài)。（X）

37.語法分析時(shí)必須先消除文法中的左遞歸。（X）

38.LR分析法在自左至右掃描輸入串時(shí)就能發(fā)現(xiàn)錯(cuò)誤，但不能準(zhǔn)確地指出出錯(cuò)地點(diǎn)。（V）

39.逆波蘭表示法表示表達(dá)式時(shí)無須使用括號(hào)。（J）

40.靜態(tài)數(shù)組的存儲(chǔ)空間可以在編譯時(shí)確定。（X）

41.進(jìn)行代碼優(yōu)化時(shí)應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對(duì)提高目標(biāo)代碼的效率將起更大作用。

（X）

42.兩個(gè)正規(guī)集相等的必要條件是他們對(duì)應(yīng)的正規(guī)式等價(jià)。（X）

43.一個(gè)語義子程序描述了一個(gè)文法所對(duì)應(yīng)的翻譯工作。（X）

44.r和s分別是正規(guī)式,則有L（r|s）=L（r）L（s）.（X）

€確定的的自動(dòng)機(jī)以及不確定的自動(dòng)機(jī)都能正確地識(shí)別正集（J）

?分析作為單獨(dú)的一遍來處理較好。（X）

《LR分析器的任務(wù)就是產(chǎn)生LR分析表。（J）

48.歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。（V）

49.同心集的合并有可能產(chǎn)生新的“移進(jìn)”/“歸約”沖

突（X）

50.1R分析技術(shù)無法適用二義文法。（X）

51樹形表示和四元式不便于優(yōu)化，而三元式和間接三元式則便于優(yōu)化。（X）

52序中的表達(dá)式語句在語義翻譯時(shí)不需要回填技術(shù)。（V）

三、填空

1.編譯程序的工作過程一般可以劃分為詞法分析,語法分析,語義分析,中間代

碼生成，代碼優(yōu)化等幾個(gè)基本階段，同時(shí)還會(huì)伴有_表格處理—和—出錯(cuò)處理

__O

r若源程序是用高級(jí)語言編寫的,—目標(biāo)程序_是機(jī)器語言程序或匯編程序，

則其翻譯程序稱為—編譯程序—。

3.編譯方式與解釋方式的根本區(qū)別在于—是否生成目標(biāo)代碼—0

5/110

4.對(duì)編譯程序而言，輸入數(shù)據(jù)是—源程序輸出結(jié)果是—目標(biāo)程序―。

5.產(chǎn)生式是用于定義—語法成分—的一種書寫規(guī)則。

6.語法分析最常用的兩類方法是—自上而下—和—自下而上—分析法

7.設(shè)G是一個(gè)給定的文法,S是文法的開始符號(hào)，如果S->x(其中xGVT*),則稱x

是文法的一個(gè)句子—o

8.遞歸下降法不允許任一非終極符是直接—左__遞歸的。

9.自頂向下的語法分析方法的基本思想是：從文法的一開始符號(hào)—開始，根據(jù)給定的輸

入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行一直接推導(dǎo)一，試圖推導(dǎo)出文法的一句子

—,使之與給定的輸入串—匹配―。

10.自底向上的語法分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步

地向上進(jìn)行—直接歸約力求歸約到文法的一開始符號(hào)―。

11常用的參數(shù)傳遞方式有—傳地址傳值和傳名。

12.在使用高級(jí)語言編程時(shí),首先可通過編譯程序發(fā)現(xiàn)源程序的全部—語法—錯(cuò)誤和語義

的部分錯(cuò)誤。

13.一個(gè)句型中的最左簡(jiǎn)單短語稱為該句型的一句柄。

14.對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱為一語義規(guī)則—。

15.一個(gè)典型的編譯程序中，不僅包括—詞法分析—、_語法分析—、—中間代碼生成

―、代碼優(yōu)化、目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括表格處理和出錯(cuò)處理。

16.從功能上說，程序語言的語句大體可分為—執(zhí)行性__語句和—說明性—語句兩大類。

17.產(chǎn)生式是用于定義_語法范疇—的一種書寫規(guī)則。

18.語法分析是依據(jù)語言的—語法—規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語言的—語義—

規(guī)進(jìn)行的。

19.語法分析器的輸入是一單詞符號(hào)串—,其輸出是—語法單位—o

20.產(chǎn)生式是用于定義—語法成分_的一種書寫規(guī)則。

21.逆波蘭式ab+c+d*e-所表達(dá)的表達(dá)式為_(a+b+c)*d-e__。

22.語法分析最常用的兩類方法是—自上而下—和—自下而上一分析法。

23.計(jì)算機(jī)執(zhí)行用高級(jí)語言編寫的程序主要有兩種途徑：―解釋_和_編譯_0

24.掃描器是—詞法分析器—，它接受輸入的—源程序—，對(duì)源程序進(jìn)行一詞法分析—

并識(shí)別出一個(gè)個(gè)單詞符號(hào),其輸出結(jié)果是單詞符號(hào)，供語法分析器使用.

25.自上而下分析法采用—移進(jìn)_、歸約、錯(cuò)誤處理、—接受—等四種操作。

26.一個(gè)LR分析器包括兩部分：一個(gè)總控程序和—一張分析表

27.后綴式abc-/所代表的表達(dá)式是_a/(b_c)_。

28.局部?jī)?yōu)化是在_基本塊一范圍內(nèi)進(jìn)行的一種優(yōu)化。

29.詞法分析基于_正則—文法進(jìn)行，即識(shí)別的單詞是該類文法的句子。

30.語法分析基于一上下文無關(guān)—文法進(jìn)行，即識(shí)別的是該類文法的句子。語法分析的有

效工具是—語法樹—。

31.分析句型時(shí)，應(yīng)用算符優(yōu)先分析技術(shù)時(shí)，每步被直接歸約的是—最左素短語—，而應(yīng)

用LR分析技術(shù)時(shí)，每步被直接歸約的是—句柄

32語義分析階段所生成的與源程序等價(jià)的中間表示形式可以有—逆波蘭―、—三元式表

示—與—四元式表示—等。

38按Chomsky分類法，文法按照—規(guī)則定義的形式—進(jìn)行分類。

31一個(gè)文法能用有窮多個(gè)規(guī)則描述無窮的符號(hào)串集合(語言)是因?yàn)槲姆ㄖ写嬖谟小f

歸—定義的規(guī)則。

35.一個(gè)名字的屬性包括—類型—和—作用域—。一

6/110

四、綜合題

1.已知文法G(E)

EfTE+T

TfF|T*F

F-(E)|i

⑴給出句型(T*F+i)的最右推導(dǎo)；

⑵給出句型(T*F+i)的短語、簡(jiǎn)單短語、句柄、素短語、最左素短語。

解：

(1)最右推導(dǎo)：E->T->F->(E)->(E+T)->(E+F)->(E+i)->(T+i)->(T*F+i)

(2)短語：(T*F+i),T*F+i,T*F,i

簡(jiǎn)單短語：T*F,i

句柄：T*F

素短語：T*F,i

最左素短語：T*F

2.構(gòu)造正規(guī)式1(0|1)*101相應(yīng)的DFA。

01

XA

AAAB

ABACAB

ACAABY

ABYACAB

重新命名，令A(yù)B為B、AC為C、ABY為D得：

01

XA

AAB

BcB

CAD

DCB

7/110

所以，可得DFA為:

1

S->MH|a

H->LSo|上.

K->dML|_e_

L->eHf

M->K|bLM

判斷G是否為LL(1)文法，如果是，構(gòu)造LL(1)分析表。

解：各符號(hào)的FIRST集和FOLLOW集為：

FIRSTFOLLOW

S他&b,?,e)怖。}

M9則

H(*Xo)

L的{0通用。網(wǎng)

K{&?}{e屈。}

各產(chǎn)生式SELECT集為:

SELECT

S->MH{d,b,e,#,o)

S->a{a}

H->LSo(e)

H->e{#,f,0)

K->dMLqljiyh6

K->_e.{e,#,o)

L->eHf{e}

M->K{d,e,#,o}

M->bLM

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

a0dfb*

s，皿->KB

M->R->K->K->bLM->K

H->S->LSc

L->sHf

K->dML?>￡

8/110

由于預(yù)測(cè)分析表中無多重入口，所以可判定文法是LL(1)的。

4.對(duì)下面的文法G：

E->TE'

E'->+E|三

T->FT'

T->T|_e_

F->PF'

F'->*F'e

P->(E)|a|b|"

⑴計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST集和FOLLOW集。(4分)

(2)證明這個(gè)方法是LL(1)的。(4分)

(3)構(gòu)造它的預(yù)測(cè)分析表。(2分)

解(1)計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST集和FOLLOW集。

FIRST集合有：

FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,"}:

FIRST?)={+,e}

FIRST(T)-FIRST(F)=FIRST(P)={(,a,b,"};

FIRST(T，)=FIRST(T)U.{e}={(,a,b,",e};

FIRST(F)=FIRST(P)={(,a,b,"};

FIRST(F')=FIRST(P)={*,e};

FIRST(P)={(,a,b,:

FOLLOW集合有：

FOLLOW(E)={),#};

FOLLOW(E")=FOLLOW(E)={),#};FOLLOW(T)=FIRST(E')qFOLLOW(E)={+,),#};〃不包含

FOLLOW(T')=FOLLOW(T)=FIRST(E')UFOLLOW(E)={+,),#};

FOLLOW(F)=FIRST(T，)UFOLLOW(T)={(,a,bj,+,),#};〃不包含e

FOLLOW(F')=FOLLOW(F)=FIRST(T，)UFOLLOW(T)={(,a,b,;

FOLLOW(P)=FIRST(F')UFOLLOW(F)={*,(,a,b,~,+,),#};//不包含e

⑵證明這個(gè)方法是LL(1)的。

各產(chǎn)生式的SELECT集合有：

SELECT(E->TE')=FIRST(T)={(,a,b,"};

SELECT(E'->+E)={+};

SELECT(E'->且=FOLLOW(E/)={),#}

SELECT(T->FT")=FIRST(F)={(,a,b,;

SELECT(T'->T)=FIRST(T)={(,a,b,1;

SELECT(T'->J_)=FOLLOW(T/)={+,),#};

SELECT(F->PF')=FIRST(P)={(,a,b,“};

SELECT(F'->*F')={*};

SELECT(F'->t)=FOLLOW(F,)={(,a,b,;

SELECT(P->(E))={(}

SELECT(P->a)={a}

SELECT(P->b)=

SELECT(P->*)={*}

9/110

可見，相同左部產(chǎn)生式的SELECT集的交集均為空，所以文法G[E]是LL(D文法。

(3)構(gòu)造它的預(yù)測(cè)分析表。文法G[E]的預(yù)測(cè)

分析表如下：

*

+*()ab#

E-4TE-4TE，-4TE/TTE

E，T+E->￡

ITFT'TFT'~FT'

T-8eTT

F?PF'-?PFTPF'->PF1

FT￡->eT￡Te今e

PT(E)TaTb4

5.已知文法G[S]為：

S->an(T)

T->T,S|S

(1)計(jì)算G[S]的FIRSTVT和LASTVT。

(2)構(gòu)造G[S]的算符優(yōu)先關(guān)系表并說明G[S]是否未算符優(yōu)先文法。

(3)給出輸入串(a,a)#的算符優(yōu)先分析過程。

解：(1)各符號(hào)的FIRSTVT和LASTVT：

FIRSTVTLASTVT

Sa、%(a、2

T9\，(,、a、\)

(2)算符優(yōu)先關(guān)系表:

A

a()9春

a>>>

(<<=<

)A>>

9<<>><

A>

#<<

(3)句子句,a)#分析過程如下:

步驟棧優(yōu)先關(guān)系當(dāng)前符號(hào)剩余輸入串移進(jìn)或歸約

1#*<((a,a)#移進(jìn)

2(<aa,a)#移進(jìn)

3

枚aa>.9a)#歸約

4財(cái)(?.*a)#移迸

5<F.,<aA)#移進(jìn)

6電aA>))#歸約

7w(>))*歸約

8般FS)律移進(jìn)

9<F))>##歸約

10翻修##10/110接受

6.已知文法為：

S->aT|(T)

T->T,S|S

構(gòu)造它的LR(O)分析表。

解：加入非終結(jié)符S',方法的增廣文法為：

s'->s

S->a

s->*

S->(T)

T->T,S

T->S下面構(gòu)造它的LR(O)項(xiàng)目集規(guī)范族為:

.-C)?sT

X.3Zr：Z3Xu

V-?一s-*(*nS--W*

T-**T,S

Sf."T->?S

Sf?(T>$-???

*■??

ST?<n

Xi*cc

I-

IiZr1.XLB

S->(?T>T->S*5—(T?)

—T?.$

Sf?

sf■一

X?iIf1

S->CT->3-><T>?T-*T.?S

S

Sf?.

sf-<n

It

1:1

I?iI*II.

T->T#-ST->T,S-

Sf?'

(T)

工

從上表可看此不存在移進(jìn)-歸約沖突以及歸約歸約沖突，該文法是LR(O)文法。從而有下面的LR(O)分

析表：

ACTIO.COTO

狀森

a-()?ST

0Srs>S1

1acc

2XBXBr1r?r?

3Xrx?XrXtVrKt

4s?S.s66

65：馬

6Xtx?XeXtr?Ft

7*r>x?r>

8StS、Sg

9KrrTXr

7.已知文法為：

A->aAd|aAb|e

11/110

判斷該文法是否是SLR(l)文法，若是構(gòu)造相應(yīng)分析表，并對(duì)輸入串a(chǎn)b#給出分析過程。解：增加一個(gè)

非終結(jié)符S/后，產(chǎn)生原文法的增廣文法有：S'-〉A(chǔ)A->aAd|aAb|e下面構(gòu)造它的LR(O)項(xiàng)目集規(guī)范族

為：

abdA

口

I；.I?

￡一嗔STQ

A->fAb

A+Md

A廿AT?心

A+

%acc

1IM

ATdAdATM?d

A吟a?如ATWb

A+aAd

A*

InIiIts

ATaATAT?。ATM/

It

A-^aAb,

Lt

AfaAd?

從上表可看出，狀態(tài)10和12存在移進(jìn)-歸約沖突，該文法不是LR(0)文法。對(duì)于10來說有：

FOLLOW(A)D{a}={b,d,#}C{a}=0),所以在10狀態(tài)下面臨輸入符號(hào)為a時(shí)移進(jìn)，為b,d,#時(shí)

歸約，為其他時(shí)報(bào)錯(cuò)。對(duì)于12來說有也有與10完全相同的結(jié)論。這就是說，以上的移進(jìn)-歸約沖突

是可以解決的，因此該文法是SLR(1)文法。

其SLR(1)分析表為:

ACnosGOTO

abd?▲

0SrXiT?八1

1MC

2StXBX3X>3

3$S>

4V：Isr：Zz

5XBT>rs2*

對(duì)輸入串a(chǎn)b#給出分析過程為:

㈱媵收SABACT