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

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

一、選擇

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

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

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

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

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

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

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

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

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

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

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

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

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

生成等五個部分。

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

7.詞法分析器用于識別_C_.

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

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

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

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

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

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

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

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

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

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

A.()源程序命令被逐個直接解釋執(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中所有符號組成的符號串

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

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

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

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

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

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

號一，一個開始符號，以及一組—D―o

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

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

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

1/110

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

C.()表格處理和出錯處理D.()符號執(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.一個句型中的最左_B稱為該句型的句柄。

A.()短語B.()簡單短語C.()素短語D.()終結(jié)符號

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

是文法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)的簡單短語是下列符號串中的。

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

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

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

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

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

22.詞法分析器用于識別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)是識別規(guī)范句型C—的DFA狀態(tài)。

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

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.一個文法所描述的語言是—A—。

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

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

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

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

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

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

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

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

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

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

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

一個開始符號，以及一組—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.一個上下文無關(guān)文法G包括四個組成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號,

一個開始符號，以及一組—D—。

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

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

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

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

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

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

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

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

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

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

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

步：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A.()運行時間較短B.()占用存儲空間較小

C.()運行時間短但占用內(nèi)存空間大D.()運行時間短且占用存儲空間小

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

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

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

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

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

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

3/110

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

D.()標(biāo)識符的行號

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

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

51.編譯程序是對_D_=

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

時，才采取“A->a.”動作的一定是_D—。

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

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

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

A.()先請先放B.()先請后放

C.()后請先放D.()任意

二、判斷

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

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

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

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

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

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

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

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

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

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

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

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

說法。(X)

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

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

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

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

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

4/110

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

36.一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。（X）

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

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

39.逆波蘭表示法表示表達式時無須使用括號。（J）

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

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

（X）

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

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

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

€確定的的自動機以及不確定的自動機都能正確地識別正集（J）

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

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

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

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

突（X）

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

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

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

三、填空

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

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

__O

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

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

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

5/110

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

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

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

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

是文法的一個句子—o

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

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

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

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

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

地向上進行—直接歸約力求歸約到文法的一開始符號―。

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

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

的部分錯誤。

13.一個句型中的最左簡單短語稱為該句型的一句柄。

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

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

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

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

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

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

規(guī)進行的。

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

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

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

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

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

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

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

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

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

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

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

29.詞法分析基于_正則—文法進行，即識別的單詞是該類文法的句子。

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

效工具是—語法樹—。

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

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

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

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

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

31一個文法能用有窮多個規(guī)則描述無窮的符號串集合(語言)是因為文法中存在有—遞

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

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

6/110

四、綜合題

1.已知文法G(E)

EfTE+T

TfF|T*F

F-(E)|i

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

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

解：

(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

簡單短語：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)分析表。

解：各符號的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->dMLuhguy5t

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

L->eHf{e}

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

M->bLM

預(yù)測分析表

a0dfb*

s，皿->KB

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

H->S->LSc

L->sHf

K->dML?>￡

8/110

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

4.對下面的文法G：

E->TE'

E'->+E|三

T->FT'

T->T|_e_

F->PF'

F'->*F'e

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

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

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

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

解(1)計算這個文法的每個非終結(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

⑵證明這個方法是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ù)測分析表。文法G[E]的預(yù)測

分析表如下：

*

+*()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)計算G[S]的FIRSTVT和LASTVT。

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

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

解：(1)各符號的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)前符號剩余輸入串移進或歸約

1#*<((a,a)#移進

2(<aa,a)#移進

3

枚aa>.9a)#歸約

4財(?.*a)#移迸

5<F.,<aA)#移進

6電aA>))#歸約

7w(>))*歸約

8般FS)律移進

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)項目集規(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)

工

從上表可看此不存在移進-歸約沖突以及歸約歸約沖突，該文法是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)分析表，并對輸入串a(chǎn)b#給出分析過程。解：增加一個

非終結(jié)符S/后，產(chǎn)生原文法的增廣文法有：S'-〉A(chǔ)A->aAd|aAb|e下面構(gòu)造它的LR(O)項目集規(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存在移進-歸約沖突，該文法不是LR(0)文法。對于10來說有：

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

歸約，為其他時報錯。對于12來說有也有與10完全相同的結(jié)論。這就是說，以上的移進-歸約沖突

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

其SLR(1)分析表為:

ACnosGOTO

abd?▲

0SrXiT?八1

1MC

2StXBX3X>3

3$S>

4V：Isr：Zz

5XBT>rs2*

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

㈱媵收SABACT