編譯原理復(fù)習(xí)題

編譯原理復(fù)習(xí)題

一、是非題

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

3.每個(gè)文法都能改寫(xiě)為L(zhǎng)L（1）文法。（X）

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

5.LR分析方法是自頂向下語(yǔ)法分析方法。（X）

6.“用高級(jí)語(yǔ)言書(shū)寫(xiě)的源程序都必須通過(guò)編譯，產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行”這種說(shuō)法。（x）

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

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

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

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

11.日機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。（X）

12.遞歸下降分析法是自頂向下分析方法。（V）

13.產(chǎn)生式是用于定義詞法成分的一種書(shū)寫(xiě)規(guī)則。（x）

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

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

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

（x）

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

18.解釋程序適用于COBOL和FORTRAN語(yǔ)言。（x）

19.一個(gè)LL⑴文法一定是無(wú)二義的。（J）

20.正規(guī)文法產(chǎn)生的語(yǔ)言都可以用.上下文無(wú)關(guān)文法來(lái)描述。（J）

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

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

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

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

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

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

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

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

28.一個(gè)算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對(duì)應(yīng)。（Y）

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

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

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

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

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

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

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

36.設(shè)r和s分別是正規(guī)式,則有L（r|s戶L（r）L（s）。（x）

37.確定的自動(dòng)機(jī)以及不確定的自切機(jī)都能正確地識(shí)別正規(guī)集。（、）

38.詞法分析作為單獨(dú)的一遍來(lái)處理較好。（x）

39.構(gòu)造LR分析滯的任務(wù)就是產(chǎn)生LR分析表。（Y）

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

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

42.LR分析技術(shù)無(wú)法適用二義文法。（x）

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

44.程序中的表達(dá)式語(yǔ)句在語(yǔ)義翻譯時(shí)不需要回填技術(shù)。（力

45.刈?中間代碼的優(yōu)化依賴于具體的計(jì)算機(jī)。（x）

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

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

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

49.編譯程序與具體的機(jī)器有關(guān)，與具體的語(yǔ)言無(wú)關(guān)。（X）

二、選擇題（請(qǐng)?jiān)谇袄ㄌ?hào)內(nèi)選擇最確切的一項(xiàng)作為答案劃一個(gè)勾，多劃按錯(cuò)論）

1.一個(gè)編譯程序中，不僅包含詞法分析，（A）,中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分。

A.語(yǔ)法分析B.文法分析C.語(yǔ)言分析I）.解釋分析

2.語(yǔ)法分析器則可以發(fā)現(xiàn)源程序中的（D）。

A.語(yǔ)義錯(cuò)誤B.語(yǔ)法和語(yǔ)義錯(cuò)誤C.錯(cuò)誤并校正D.語(yǔ)法錯(cuò)誤

3.解釋程序處理語(yǔ)言時(shí)，大多數(shù)采用的是（B）方法。

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

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

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

1）.以上方法都可以

4.編譯程序是一種（B）。

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

5.文法分為四種類型，即0型、1型、2型、3型。其中3型文法是（B）。

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

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

還應(yīng)包括（C）。

A.模擬執(zhí)行^B.解釋希C.表格處理和出錯(cuò)處理D.符號(hào)執(zhí)行器

7.一個(gè)句型中的最左（B）稱為該句型的句柄。

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

8.文法G[E]：

E->T|E+T

JFIT*F

F->a|（E）

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

①（E+T）②E+T③F④F*（E+T）

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

9.詞法分析器用于識(shí)別（C）。

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

10.在自底向上的語(yǔ)法分析方法中，分析的關(guān)鍵是（A）。

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

11.文法G產(chǎn)生的（D）的全體是該文法描述的語(yǔ)言。

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

12.若文法G定義的語(yǔ)言是無(wú)限集，則文法必然是（A）。

A.遞歸的B.前后文無(wú)關(guān)的C.二義性的D.無(wú)二義性的

13.四種形式語(yǔ)言文法中，1型文法又稱為（C）文法。

A.短語(yǔ)結(jié)構(gòu)文法B.前后文無(wú)關(guān)文法C.前后文有關(guān)文法D.正規(guī)文法

14.一個(gè)文法所描述的語(yǔ)言是（A）。

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

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

A.語(yǔ)法分析B.中間代碼生成C.詞法分析D.目標(biāo)代碼生成

16.（B）是兩類程序語(yǔ)言處理程序。

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

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

17.數(shù)組的內(nèi)情向量中肯定不含有數(shù)組的（D）的信息。

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

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

及一組（D）。

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

19.文法分為四種類型，即。型、I型、2型、3型。其中2型文法是（D）。

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

20.文法G所描述的語(yǔ)言是（C）的集合。

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

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

21.詞法分析器用于識(shí)別（C）。

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

22.文法分為四種類型，即0型、1型、2型、3型。其中。型文法是（A）。

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

24.（A）是一種典型的解釋型語(yǔ)言。

A.BASICB.CC.FORTRAND.PASCAL

25.與編譯系統(tǒng)相比，解釋系統(tǒng)（D）。

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

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

26.月高級(jí)語(yǔ)言編寫(xiě)的程序經(jīng)編譯后產(chǎn)生的程序叫（B）。

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

27.詞法分析器用于識(shí)別（A）。

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

28.編寫(xiě)一個(gè)計(jì)算機(jī)高級(jí)語(yǔ)言的源程序后，到正式上機(jī)運(yùn)行之前，一般要經(jīng)過(guò)（B）這幾步:

⑴編輯⑵編譯⑶連接（4）運(yùn)行

A.⑴⑵（3）（4）B.⑴⑵⑶C.（1）⑶D.⑴（4）

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

A.編譯器B.匯編器C.解釋器D.預(yù)處理器

31.詞法分析器的輸出結(jié)果是（C）。

A.單詞的種別編碼B.單詞在符號(hào)表中的位置C.單詞的種別編碼和自身值D.單詞自身值

32.正規(guī)式M1和M2等價(jià)是指（C）。

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

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

33.文法G：S-xSx|y所識(shí)別的語(yǔ)言是（C）。

A.xyxB.(xyx)*C.xnyxn{n>0)D.x*yx*

34.如果文法G是無(wú)二義的，則它的任何句子a（A）o

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ù)相同

35.構(gòu)造編譯程序應(yīng)掌握（D）。

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

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

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

37.表達(dá)式（1AVB）八（CVD）的逆波蘭表示為（B）。

A.ABVACDVB.A-）BVCDVAC.ABVqCDVAD.AnBVACDV

38.優(yōu)化可生成（D）的目標(biāo)代碼。

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

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

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

A.強(qiáng)度削弱B.刪除歸納變量C.刪除多余運(yùn)算D.代碼外提

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

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

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

41.編譯程序絕大多數(shù)時(shí)間花在（D）上。

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

42.編譯程序是對(duì)（D）。

A.匯編程序的翻譯B.高級(jí)語(yǔ)言程序的解釋執(zhí)行C.機(jī)器語(yǔ)言的執(zhí)行D.高級(jí)語(yǔ)言的翻譯

43.采用自上而下分析，必須（C）,

A.消除左遞歸B.消除右遞歸C.消除回溯D.提取公共左因子

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

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

45.若a為終結(jié)符，則A->a?ap為（B）項(xiàng)目。

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

46.間接三元式表示法的優(yōu)點(diǎn)為（A）。

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

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

47.基本塊內(nèi)的優(yōu)化為（B）。

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

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

48.在目標(biāo)代碼生成階段，符號(hào)表用（D）。

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

49.若項(xiàng)目集Ik含有A->a?,則在狀態(tài)k時(shí)，僅當(dāng)面臨的輸入符號(hào)a￡FOLLOW（A）時(shí)，才采取?”動(dòng)作的

一定是（D）。

A.LALR文法B.LR（O）文法C.LR⑴文法D.SLR⑴文法

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

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

三、填空題

1.編許程序的工作過(guò)程一般可以劃分為詞法分析，語(yǔ)法分析，語(yǔ)義分析，中間代碼生成，代碼優(yōu)化等幾個(gè)基本階段,

同時(shí)還會(huì)伴有—表格處理—和—出錯(cuò)處理

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

3.產(chǎn)生式是用于定義—語(yǔ)法成分_的一種書(shū)寫(xiě)規(guī)則。

4.設(shè)G是一個(gè)給定的文法，S是文法的開(kāi)始符號(hào)，如果S->x（其中x￡VT*）,則稱x是文法的一個(gè)一句子

5.自頂向下的語(yǔ)法分析方法的基本思想是：從文法的一開(kāi)始符號(hào)—開(kāi)始，根據(jù)給定的輸入串并按照文法的產(chǎn)

生式一步一步的向下進(jìn)行_直接推導(dǎo)—，試圖推導(dǎo)出文法的一句子—，使之與給定的輸入串_匹配

6.常用的參數(shù)傳遞方式有一傳地出傳值和傳名。

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

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

9.一個(gè)典型的編譯程序中，不僅包括一詞法分析—、_語(yǔ)法分析—、_中間代碼生成一、代碼優(yōu)化、目標(biāo)代

碼生成等五個(gè)部分，還應(yīng)包括表格處理和出錯(cuò)處理。

10.從功能上說(shuō)，程序語(yǔ)言的語(yǔ)句大體可分為_(kāi)執(zhí)行性一語(yǔ)句和—說(shuō)明性一語(yǔ)句兩大類。

II.掃描器的任務(wù)是從_源程序一中識(shí)別出一個(gè)個(gè)一單詞符號(hào)

12.產(chǎn)生式是用于定義一語(yǔ)法范疇—的一種書(shū)寫(xiě)規(guī)則。

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

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

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

16.逆波蘭式ab+c+d*e-所表達(dá)的表達(dá)式為_(kāi)（a+b+c）*d-e。

17.語(yǔ)法分析最常用的兩類方法是一自上而下—和一自下而.卜.一分析法。

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

19.掃描器是—詞法分析器一，它接受輸入的一源程序?qū)υ闯绦蜻M(jìn)行一詞法分析一并識(shí)別出一個(gè)個(gè)單詞

符號(hào)，其輸出結(jié)果是單詞符號(hào)，供語(yǔ)法分析器使用。

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

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

22.后綴式abc-/所代表的表達(dá)式是_a/(b-c)__0

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

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

25.語(yǔ)法分析基于一上下文無(wú)關(guān)一文法進(jìn)行，即識(shí)別的是該類文法的句子。語(yǔ)法分析的有效工具是一語(yǔ)法樹(shù)一。

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

每步被直接歸約的是一句柄

27.語(yǔ)義分析階段所生成的與源程序等價(jià)的中間表示形式可以有一逆波蘭一、—四無(wú)式表示_與一三元式表

示一等。

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

29.一個(gè)文法能用有窮多個(gè)規(guī)則描述無(wú)窮的符號(hào)串集合(語(yǔ)言)是因?yàn)槲姆ㄖ写嬖谟幸贿f歸_定義的規(guī)則。

四、簡(jiǎn)答題

1.寫(xiě)文法，使其語(yǔ)言是偶正整數(shù)的集告要求：

⑴允許0打頭；

(2)不允許0打頭。

解：⑴G網(wǎng)=({S,P,D,N},{0,1,2,...,9}.P,S)

P:

S->PD|D

P->NP|N

D->0|2|4|6|8

N->0|l|2|3|4|5|6|7|8|9

(2)G1S[=({S,P,R,D,N,Q},{0,1,2,...,9心)

P:

S->PD|P0|D

P->NR|N

R->QR|Q

D->2|4|6|8

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

Q->0|l|2|3|4|5|6|7|8|9

2.構(gòu)造正規(guī)式相應(yīng)的NFA:l(0|l)*101

0

解1(011)*101對(duì)應(yīng)的NFA為1

3.寫(xiě)出表達(dá)式(a+b*c)/(a+b)—d的逆波蘭表示和三元式序列。

逆波蘭表示：abc*+ab+/d—

三元式序列：

①(*.b,c)

②(十,a,①)

③(+,a,b)

④(/,②，③)

⑤(一，④，d)

4.已知文法G[S]為:

S->dAB

A—>aA|a

B->Bb|e

G[S|產(chǎn)生的語(yǔ)言是什么？

nm

答:G[S]產(chǎn)生的語(yǔ)言是L(G[S])={dab|n>\jn>0}o

5.構(gòu)造正規(guī)式相應(yīng)的DFA:1(1010*11(010)*l)*0o

解：1(1010*|1(010)*1)*0對(duì)應(yīng)的NFA為

6.已知文法G(S)

S->a|A|(T)

T->T,S|S

寫(xiě)出句子((a,a),a)的規(guī)范歸約過(guò)程及每一步的句柄。

解：

句型歸約規(guī)則句柄

((a,a),a)S—>aa

((S,a),a)T->SS

((T,a),a)S—>aa

((T,S),a)T—T,ST,S

((S),a)TTSS

((T),a)S->S(T)(T)

(S,aiT—SS

(T,a)S—*aa

(T,S)T->T,ST,S

(T)STD(T)

S

7.寫(xiě)一個(gè)文法，使其語(yǔ)言是奇數(shù)集，且每個(gè)奇數(shù)不以0開(kāi)頭。

解：文法G(N)：

NTAB|B

ATAC|D

B->1|3|5|7|9

D->B2|4|6|8

C->0|D

8.設(shè)文法G(S)：

S—>(L)|aS|a

L->L,S|S

(1)消除左遞歸和回溯：

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

解：⑴

S->(L)|aS'

S」S|￡

L->SL'

LJSU|￡

(2)

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

FIRST(S')={,a,e}FOLLOW(S')={#,,,)}

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

FIRST(L')={,,￡)FOLLOW(L')={)}

9.已知文法G(E)

E->T|E+T

T->F|T*F

F-(E)|i

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

(2)給出句型(T*F+i)的短語(yǔ)、素短語(yǔ)。

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

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

素短語(yǔ):T*F,i

10.Whilea>0Vb<0do

Begin

X：=X+1；

ifa>0thena：=a—1

elseb：=b+l

End；

翻譯成四元式序列。

解：

⑴a,。，5)

(2)(j,一,—,3)

(3)(j<,b,0,5)

(4)(j,—?—，15)

(5)(+,X,1,Tl)

(6)(：=,Tl,一，X)

(7)(j>,a,0,9)

(8)(j,—,12)

(9)(-,a,I,T2)

(10)(：=,T2,a)

(U)(j，1)

(12)(+,b,1,T3)

(13)(：=,T3,b)

(14)0，一，一，1)

(15)

11.寫(xiě)出下列表達(dá)式的三地址形式的中間表示。

(1)5+6*(a+b);

(2)forj:=lto10doa[j+j]:=0o

答：(1)100:U:=a+b

101:t2:=6*tl

102:6=5+12

(2)100:j:=l

101:ifj>10gotoNEXT

102:i:=j+j

103:a[i]:=0

12.設(shè)基本塊p由如下語(yǔ)句構(gòu)成：

TO:=3.14;

T1:=2*T0;

T2:=R+r;

A:=T1*T2；

B:=A;

T3:=2*T0;

TA：-R+r;

T5:=T3*T4;

T6:=R-r；

B:=T5*T6；

試給出基本塊p的DAGo

13.寫(xiě)出表達(dá)式（a+b）/（a-b-（a+b*c）的三元序列及四元序列。

解：（1）三元式：

①（一,a,b）

②（一，a,b）

③"①，②）

④（*,b,c）

⑤（十，a,④）

⑥（-,③，⑤）

（2）四元式:

①（一,a,b,Tl）

②（一，a,b,T2）

③（/,Tl,T2,T3）

④（*,b,c,T4）

⑤（一,a,T4,T5）

⑥（一，T3,T5,T6）

14.寫(xiě)一個(gè)文法使其語(yǔ)言為偶數(shù)集，且每個(gè)偶數(shù)不以0開(kāi)頭。

解：文法G（S）：

S->AB|B|A0

A->AD|C

B->2|4|6|8

C->1|3|5|7|9|B

D-0|C

15.設(shè)文法G（S）：

S->S+aF|aF|+aF

F—**aF|*a

（1）消除左遞歸和回溯；

（2）構(gòu)造相應(yīng)的FIRST和Follow集合。

解：（1）

S->aFS'|+aFS'

S'->+aFSK

F->*aF'

F'->F|￡

(2)

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

FIRST(S')={+,￡}FOLLOW(S')={#}

FIRST(F)={*}FOLLoW(F)=(+,井}

FIRST(F)={*,e}FOLLOW[+,#}

16.簡(jiǎn)要說(shuō)明語(yǔ)義分析的基本功能。

答：語(yǔ)義分析的基本功能包括：確定類型、類型檢查、語(yǔ)義處理和某些靜態(tài)語(yǔ)義檢查。

17.考慮文法G[S]:

S—(T)|a+S|a

T->T,S|S

消除文法的左遞歸及提取公共左因子。

解：消除文法G[S]的左遞歸：

S—>(T)|a+S|a

T—ST'

TJ,ST1￡

提取公共左因子：

S->(T)|aS'

S'->+SI￡

T-ST'

TfST|￡

18.試為表達(dá)式w+(a+b)*(c+d/(e-10)+8)寫(xiě)出相應(yīng)的逆波蘭表示。

解：wab+cde10-/+8+*+

19.按照三種基本控制結(jié)構(gòu)文法將下面的語(yǔ)句翻譯成四元式序列：

while(A<CAB<D)

(

if(A>1)C=C+1;

elsewhile(A<D)

A=A+2;

)。

解：該語(yǔ)句的四元式序列如下(其中El、E2和E3分別對(duì)應(yīng)AVCABVD、A>1A<D,并且關(guān)系運(yùn)算符優(yōu)先級(jí)

高)：

100(j<,A,C,102)

101

102(j<,B.D,104)

1030.113)

104(j=A,1,106)

105(j.___108)

106(+,C,1,C)

107(j-U2)

108(j<,A,D,H0)

109G，___H2)

110(+,A,2,A)

III(j,__108)

112(j._,_,100)

113

20.已知文法GfS］為S->aSb|Sb|b,試證明文法G［S］為二義文法。

證明：

由文法G⑸：S->aSb|Sb|b,對(duì)句子aabbbb對(duì)應(yīng)的兩棵語(yǔ)法樹(shù)為:

aSb

/K

aSb

bb

因此，文法G[S]為二義文法。

21.文法G[S]為:

S->Ac|aB

A->ah

B->bc

寫(xiě)出L(G[S])的全部元素。

解：S=>Ac=>abc

或S=>aB=>abc

所以L(G[S]尸{abc}

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

解：先構(gòu)造NFA：

確定化:

01

XA

AAAB

ABACAB

ACAABY

ABYACAB

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

01

XA

AAB

BCB

CAD

DCB

所以，可得DFA為:

S->a|q(T)

T->T,S|S

對(duì)(a,(a,a)和(((a,a),A,(a)),a)的最左推導(dǎo)。

解：對(duì)(a,(a,a)的最左推導(dǎo)為：

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

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

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

對(duì)(((a,a),八,(a)),a)的最左推導(dǎo)為:

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

=>((TS),S)=>((T,S,S),S)=>((S,S,S),S)

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

=>(((a,S),S,S),S)=>(((a,a),S,S),S)=>(((a,a),A,S),S)

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

=>(((a,a),A,(a)),a)

24.文法:

S->MH|a

H->LSo|E

K->dML|￡

L->eHf

M->K|bLM

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

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

FIRSTFOLLOW

s{a4b,c,e)｛機(jī)。｝

M{d,e,b){eAo}

H{y}{加}

L母岫島。,#｝

K{d,M{eAo}

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

aodefb

S->a

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

H->s->LSo->S->￡

L->eHf

K->8->dML->￡->2

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

25.敘述由下列正規(guī)式描述的語(yǔ)言

(a)0(0|l)*0

(b)((e10)1*)*

(c)(0|1)*0(011)(0|1)

(d)0*10*10*10*

(e)(0()|11)*((01|10)(00|l1)*(01|10)(00|ll)*)*

解：(a)以0開(kāi)頭、以。結(jié)尾的所有0和1的串。

(b)由。和1組成的串，包括空串.

⑹倒數(shù)第3個(gè)字符為0,由0和1組成的串。

(d)含有3個(gè)1的所有。和1的串。

⑹由偶數(shù)個(gè)0和偶數(shù)個(gè)1構(gòu)成的所有()和I的串。

26.已知文法G［S］：

S-*(L)|a

L-L,S|S

為句子(a,(a,a))構(gòu)造最左推導(dǎo)和最右推導(dǎo)。

解：句子(a,(a,a))的最左推導(dǎo)為：

S=>(L)=>(L,S)=>(S,S)=>(a,S)=>(a,(L))=>(a,(L,S))=(a,(S,S))=>(a,(a,S))=>(a,(a,a))

句子(a,(a,a))的最右推導(dǎo)為：

S=>(L)=>(L,S)=>(l,(L))=>(L,(L,S))=>(L,(L,a))=>(L,(S,a))=>(L,(a,a))=(S,(a,a))=(a,(a,a))

五.計(jì)算題

1.構(gòu)造下述文法G［S］的自動(dòng)機(jī)：

S->A0

A->A()|S1|O

該自動(dòng)機(jī)是確定的嗎？若不確定，貝］對(duì)它確定化。

解：由于該文法的產(chǎn)生式S->A0,A->AO|S1中沒(méi)有字符集VT的輸入，所以不是確定的自動(dòng)機(jī)。要將其他確定

化，必須先用代入法得到它對(duì)應(yīng)的正規(guī)式。把S?A0代入產(chǎn)生式A?S1有：A=A0|AO110=A(0|01)|0=0(0|01)*o代

入S->A0有該文法的正規(guī)式：0(0|01)*0,所以，改寫(xiě)該文法為確定的自動(dòng)機(jī)為：

由于狀態(tài)A有3次輸入0的重復(fù)輸入，所以上圖只是NFA,下面將它確定化：

下表由子集法將NFA轉(zhuǎn)換為

DFA:

IIo-c-closure(MoveIb-e-closure(Move7b(I,i))

A[W]B[X]

B[X]C[X,Y,Z]

C[X,Y,Z]C[X,Y,Z]B[X]

由上表可知DFA為:

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

E->TE'

E'->+E|￡

T->FT'

V->T|e

F->PF'

F->*F'|e

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

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

(2)證明這個(gè)方法是LL(I)的。

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

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

FIRST集合有：

FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,A};

FIRST(E尸什同

FIRST(T)=FIRST(F)=F1RST(P)={(,a,b?);

FIRST(T')=FIRST(T)UF}={(,a,b,人間;

FIRST(F)=FIRST(P)={(,a,b,A);

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

FIRST(P)={(,a,b?!;

FOLLOW集合有：

FOLLOW(E)={),#};

FOLLOW(E')=FOLLOW(E)={),#};

FOLLOW(T)=FIRST(E')UFOLLOW(E)={+,),#}，不包含￡

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

FOLLOW(F)=FIRST(T')UFOLLOW(T)={(,a,b,A,+,),#);//不包含￡

HOLLOW(E)=FOLLOW(F)=HRSrcr)UHOLLOW(T)={(,a,b,A,+,),#};

FOLLOW(P)=FIRST(F')UFOLLOW(F尸{*,(,a,bj,+,),#};〃不包含￡

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

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

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

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

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

SELECT(T->FT')=FIRST(F)={(,a,b,A};

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

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

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

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

SELECT(F'->￡)=FOLLOW(F')={(,a,b,A,+,),#)；

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

SELECT(P->a)={a}

SELECT(P->b)={b)

SELECT(P->A)={A)

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

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

文法G[E]的預(yù)測(cè)分析表如下：

A

+*()ab#

EITE'TIE'-?TE’->TEr

Ez3+E

T?FT'->FTZ->FT;1FT

Tz->e-?TIT

F3PF’->FF,?PF'-?PF

Ff-^*F,->6￡

P3(E)9a-?b

3.己知NFA=()x,y,z),{0,l)M(x)4z)),其中:

M(x,())={z},M(y,())={x,y},M(z,O)={x,z},M(x,1)={x},M(y,l)=(p,M(zJ)={y},構(gòu)造相應(yīng)的DFA并最小化。

下表由子集法將NFA轉(zhuǎn)換為DFA

IIo-￡-closure(Mov0Ii二e-closure(Move

A[x]B[z]A[x]

B[z]C[x,z]D[y]

C[x,z]C[x,z]E[x,y]

D[y]E[x,y]

E[x,y]F[x,y,z]A[x]

F[x,y,z]F[x,y,z]E[x,y]

下面籽該DFA最小化：

(1)首先將它的狀態(tài)集分成兩個(gè)子集：P1={A,D,E},P2={B,C,F)

(2)IX分P2:由于F(FJ)=F(C,1)=E,F(F,O)=F并且F(C,O)=C,所以F,C等價(jià)。由于F(B.O)=F(C,O)=C,F(B,1)=D,F(C,1)=E,

而D,E不等價(jià)(見(jiàn)下步)，從而B(niǎo)與C,F可以區(qū)分。有P21={C,F},P22={B}。

(3)區(qū)分Pl:由于A,E輸入。到終態(tài)，而D輸入0不到終態(tài)，所以D與A,E可以區(qū)分，有Pl1={A,E},P12={D}。

(4)由于F(A,O)=B,F(E,O)=FjiiB,F不等價(jià)，所以A,E可以區(qū)分。

(5)綜上所述，DFA可以區(qū)分為P={{A},{B},{D},{E},{C,F}}。所以最小化的DFA如下：

4.已知文法為：

S->an(T)

T->T,S|S

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

解：加入非終結(jié)符ST方法的增廣文法為:

S'->S

S->a

S->A

S->(T)

T->T,S

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

百天號(hào)

A

a)J#sT

Io：I::L：I：II:

S，SS->aaS-X-T)S0S?

T->>T,S

S"T->?S

Sf⑴S-??a

S>(T)

Iiacc

Ic

L

I:I：LIIt：Is：

S-?(*T)s。S^(T9

Tf?T,S—,S

—?S

S->,a

S3」

S+⑴

Is：I；:L：

SIT)S3(TATIT,-S

T—T-，SST?a

S3」

S>(T)

L

IT：

L：I：LIL

T->T,*S—T,s?

S->ba

S3」

s>cr)

I,

從I：表可看出，不存在移進(jìn)-歸約沖突以及歸約歸約沖突，該文法是LR(O)文法。

從而有下面的LR(O)分析表：

ACTIONGOTO

狀態(tài)A

a()#ST

0工s5s1

1acc

2XiXiXiXlXlXl

3r2r：r：工二r2r:

4s：S5S65

5S：So

6r5r5r5Xsr5r?

7Xjr5XjX3r5X3

8s：S5S9

9rrrr▲V■r

5.已知文法

A->aAd|aAb|E

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

解：增加一個(gè)非終結(jié)符S/后，產(chǎn)生原文法的增廣文法有：

S'->A

A->aAd|aAb|e

下面構(gòu)造它的LR(O)項(xiàng)目集規(guī)范