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

1、編譯原理復(fù)習(xí)題一、是非題1.計(jì)算機(jī)高級(jí)語(yǔ)言翻譯成低級(jí)語(yǔ)言只有解釋一種方式。（X）3 .每個(gè)文法都能改寫(xiě)為 LL（1）文法。（X）4 .算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。（腦5 .LR 分析方法是自頂向下語(yǔ)法分析方法。（X）6 .“用高級(jí)語(yǔ)言書(shū)寫(xiě)的源程序都必須通過(guò)編譯，產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行”這種說(shuō)法。（X）7 .一個(gè)句型的句柄一定是文法某產(chǎn)生式的右部。（J8 .僅考慮一個(gè)基本塊，不能確定一個(gè)賦值是否真是無(wú)用的。（腦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)貯存分配策略。（兇11 .甲機(jī)上的某編譯

2、程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。（X）12 .遞歸下降分析法是自頂向下分析方法。（V）13 .產(chǎn)生式是用于定義詞法成分的一種書(shū)寫(xiě)規(guī)則。（兇14 .在 SLR（1）分析法的名稱中，S 的含義是簡(jiǎn)單的。（J15 .綜合屬性是用于“自上而下”傳遞信息。（X）16 .符號(hào)表中的信息欄中登記了每個(gè)名字的屬性和特征等有關(guān)信息，如類型、種屬、所占單元大小、地址等等。（乃17 .程序語(yǔ)言的語(yǔ)言處理程序是一種應(yīng)用軟件。（兇18 .解釋程序適用于 COBOL 和 FORTRAN 語(yǔ)言。（內(nèi)19 .一個(gè) LL（l）文法一定是無(wú)二義的。（儲(chǔ)20 .正規(guī)文法產(chǎn)生的語(yǔ)言都可以用上下文無(wú)

3、關(guān)文法來(lái)描述。（儲(chǔ)21 .一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被認(rèn)為是初態(tài)，最多只有一個(gè)終態(tài)。(X).目標(biāo)代碼生成時(shí)，應(yīng)考慮如何充分利用計(jì)算機(jī)的寄存器的問(wèn)題。（/.逆波蘭法表示的表達(dá)式亦稱后綴式。（M.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱這個(gè)文法是二義的。（儲(chǔ).數(shù)組元素的地址計(jì)算與數(shù)組的存儲(chǔ)方式有關(guān)。（腦.算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。（乃.編譯程序是對(duì)高級(jí)語(yǔ)言程序的解釋執(zhí)行。（X）.一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一的終態(tài)。（兇.一個(gè)算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對(duì)應(yīng)。（，）.語(yǔ)法分析時(shí)必須先消除文法中的左遞歸。（為.LR 分析法在自左至右掃描輸入串時(shí)就

4、能發(fā)現(xiàn)錯(cuò)誤，但不能準(zhǔn)確地指出出錯(cuò)地點(diǎn)。（V.逆波蘭表示法表示表達(dá)式時(shí)無(wú)須使用括號(hào)。（，）.靜態(tài)數(shù)組的存儲(chǔ)空間可以在編譯時(shí)確定。（V）.進(jìn)行代碼優(yōu)化時(shí)應(yīng)著重考慮循環(huán)的代碼優(yōu)化，這對(duì)提高目標(biāo)代碼的效率將起更大作用。（儲(chǔ).兩個(gè)正規(guī)集相等的必要條件是他們對(duì)應(yīng)的正規(guī)式等價(jià)。（儲(chǔ).一個(gè)語(yǔ)義子程序描述了一個(gè)文法所對(duì)應(yīng)的翻譯工作。（兇.設(shè) r 和 s 分別是正規(guī)式，則有 L（r|s）=L（r）L（s）。（X）.確定的自動(dòng)機(jī)以及不確定的自動(dòng)機(jī)都能正確地識(shí)別正規(guī)集。（J.詞法分析作為單獨(dú)的一遍來(lái)處理較好。（X）.構(gòu)造 LR 分析器的任務(wù)就是產(chǎn)生 LR 分析表。（J.規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過(guò)程。（V）.同心

5、集的合并有可能產(chǎn)生新的移進(jìn)”/歸約”沖突。（X）2222232425262728293031323334353637383940414243.LR 分析技術(shù)無(wú)法適用二義文法。（X）.樹(shù)形表示和四元式不便于優(yōu)化，而三元式和間接三元式則便于優(yōu)化。（乃44 .程序中的表達(dá)式語(yǔ)句在語(yǔ)義翻譯時(shí)不需要回填技術(shù)。（V45 .對(duì)中間代碼的優(yōu)化依賴于具體的計(jì)算機(jī)。（X）46 .若一個(gè)句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。（為47 .在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。（X）48 .削減運(yùn)算強(qiáng)度破壞了臨時(shí)變量在一基本塊內(nèi)僅被定義一次的特性。（兇49 .編譯程序與具體的機(jī)器有關(guān)，與具體的語(yǔ)言無(wú)關(guān)。（

6、兇二、選擇題（請(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ǔ)言分析 D.解釋分析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í)行D.以上方法都可以4 .編譯程序是一種（B）。A.匯編程序 B.翻譯程序 C.解釋程序 D.目標(biāo)程序5 .文

7、法分為四種類型，即 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 .文法 GE:E-TE+TT-FIT*FF-aI（E）該文法句型 E+F*（E+T）的簡(jiǎn)單短語(yǔ)是下列符號(hào)串中的（B）。（E+T）E+TFF*（E+T）A.和B.和C.和D.9 .詞

8、法分析器用于識(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.可能唯一

9、，好可能不唯一 D.都不對(duì)15 .（B）和代碼優(yōu)化部分不是每個(gè)編譯程序都必需的。A.語(yǔ)法分析B.中間代碼生成C.詞法分析D.目標(biāo)代碼生成16 .（B）是兩類程序語(yǔ)言處理程序。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 .文法分為四種類型，即 0 型、1 型、2 型、3 型。其中 2 型文法是（D）。A.短語(yǔ)文法 B.正則文法 C.上下文有關(guān)文法 D.上下文無(wú)關(guān)文法A.高級(jí)語(yǔ)言程序和低級(jí)語(yǔ)言程序B.解釋程序和編譯程序C.編譯程序和操作系統(tǒng)D.系統(tǒng)程序和應(yīng)用程序17.數(shù)組的內(nèi)情向

10、量中肯定不含有數(shù)組的（D）的信息。A.維數(shù)B.類型C.維上下界D.各維的界差20 .文法 G 所描述的語(yǔ)言是（C）的集合。A.文法 G 的字母表 V 中所有符號(hào)組成的符號(hào)串C.由文法的開(kāi)始符號(hào)推出的所有終極符串21 .詞法分析器用于識(shí)別（C）。A.字符串 B.語(yǔ)句 C.單詞22 .文法分為四種類型，即A.短語(yǔ)文法24 .（A）是一種典型的解釋型語(yǔ)言。A.BASICB.CC.FORTRAN25 .與編譯系統(tǒng)相比，解釋系統(tǒng)（D）。A.比較簡(jiǎn)單，可移植性好，執(zhí)行速度快C.比較簡(jiǎn)單，可移植性差，執(zhí)行速度慢B.文法 G 的字母表 V 的閉包 V*中的所有符號(hào)串D.由文法的開(kāi)始符號(hào)推出的所有符號(hào)串D.標(biāo)識(shí)

11、符0 型、1 型、2 型、3 型。其中 0 型文法是（A）。B.正則文法 C.上下文有關(guān)文法D.PASCALB.比較復(fù)雜D.比較簡(jiǎn)單D.上下文無(wú)關(guān)文法,可移植性好，執(zhí)行速度快,可移植性好，執(zhí)行速度慢26.用高級(jí)語(yǔ)言編寫(xiě)的程序經(jīng)編譯后產(chǎn)生的程序叫(B)。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)這幾步：(1)編輯(2)編譯(3)連接(4)運(yùn)行A.(1)(2)(3)(4)B.(1)(2)(3)C.(1)(3)D.(1)(4)29 .把匯編語(yǔ)言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由(B)

12、完成的。A.編譯器 B.匯編器 C.解釋器 D.預(yù)處理器31 .詞法分析器的輸出結(jié)果是(C)。A.單詞的種別編碼 B.單詞在符號(hào)表中的位置 C.單詞的種別編碼和自身值 D.單詞自身值32 .正規(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ù)相等33 .文法 G:S-xSx|y 所識(shí)別的語(yǔ)言是(C)。A.xyxB.(xyx)*C.xnyxn(n0)D.x*yx*34 .如果文法 G 是無(wú)二義的，則它的任何句子 a(A)。A.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)必定相

13、同 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.程序變量A.源程序 B.目標(biāo)程序 C.連接程序D.解釋程序37 .表達(dá)式仁 AVB)A(CVD)的逆波蘭表示為(B)。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)

14、優(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à)可歸約串

15、。A.直接短語(yǔ) B.句柄 C.最左素短語(yǔ) D.素短語(yǔ)45 .若 a 為終結(jié)符，則 A-”已 3 為（B）項(xiàng)目。A.歸約 B.移進(jìn) C.接受 D.待約46 .間接三元式表示法的優(yōu)點(diǎn)為（A）。AABV/CDVB.AnBVCDVAC.ABWCDVAD.AnBVACDVA.采用間接碼表，便于優(yōu)化處理 B.節(jié)省存儲(chǔ)空間，不便于表的修改C.便于優(yōu)化處理，節(jié)省存儲(chǔ)空間 D.節(jié)省存儲(chǔ)空間，不便于優(yōu)化處理47 .基本塊內(nèi)的優(yōu)化為（B）。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

16、-，則在狀態(tài) k 時(shí)，僅當(dāng)面臨的輸入符號(hào) aCFOLLOW(A)時(shí)，才采取 A-“”動(dòng)作的一定是(D)。A.LALR 文法 B.LR(0)文法 C.LR(1)文法 D.SLR(1)文法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-

17、x(其中 xCVT*),則稱 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ī)則。9 .一個(gè)典型的編譯程序中，不僅包括詞法分析、語(yǔ)法分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括表格處理和出錯(cuò)處理。A.代碼外提，刪除歸納變量B.刪除多余運(yùn)算，刪除無(wú)用賦值10 .從功能上說(shuō)，程序

18、語(yǔ)言的語(yǔ)句大體可分為執(zhí)行性語(yǔ)句和說(shuō)明性語(yǔ)句兩大類。11 .掃描器的任務(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è)名字的屬性包括類型和作用域。16 .逆波蘭式 ab+c+d*e-所表達(dá)的表達(dá)式為(a+b+c)*d-e。17 .語(yǔ)法分析最常用的兩類方法是自上而下和自下而上分析法。18 .計(jì)算機(jī)執(zhí)行用高級(jí)語(yǔ)言編寫(xiě)的程序主要有兩種途徑：解釋和編譯。19 .掃描器是詞法分析器,它接受輸入的源程序，對(duì)源程序進(jìn)行詞法分析

19、并識(shí)別出一個(gè)個(gè)單詞符號(hào)，其輸出結(jié)果是單詞符號(hào)，供語(yǔ)法分析器使用。20 .自上而下分析法采用移進(jìn)、歸約、錯(cuò)誤處理、接受等四種操作。21 .一個(gè) LR 分析器包括兩部分：一個(gè)總控程序和1張分析表。22 .后綴式 abc-/所代表的表達(dá)式是 a/(b-c)_。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ǔ)義分析

20、階段所生成的與源程序等價(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ù)的集合，要求:(1)允許 0 打頭；(2)不允許 0 打頭。解：(1)GS=(S,P,D,N,0,1,2,9,P,S)P:S-PD|DP-NP|ND-0|2|4|6|8N-0|1|2|3|4|5|6|7|8|9(2)GS=(S,P,R,D,N,Q,0,1,2,9,P,S)P:S-PD|P0|DP-NR|NR-QR|

21、QD-2|4|6|8N-1|2|3|4|5|6|7|8|9Q-0|1|2|3|4|5|6|7|8|92 .構(gòu)造正規(guī)式相應(yīng)的 NFA:1(0|1)*101解 1(0|1)*101 對(duì)應(yīng)的 NFA 為3 .寫(xiě)出表達(dá)式(a+b*c)/(a+b)d 的逆波蘭表示和三元式序列。0三元式序列：（*,b,c）（十,a,）（+,a,b）（/,，）（，d）4 .已知文法 GS為:SfdABAfaA|aB-Bb|GS產(chǎn)生的語(yǔ)言是什么?答：GS產(chǎn)生的語(yǔ)言是 L(GS)=danbm|n1,m0。5 .構(gòu)造正規(guī)式相應(yīng)的 DFA:1(1010*|1(010)*1)*0逆波蘭表示:abc*+ab+/dNFAS-a|A|(T

22、)TfT,S|S寫(xiě)出句子(a,a),a)的規(guī)范歸約過(guò)程及每一步的句柄。解：句型歸約規(guī)則句柄(a,a),a)S-aa(S,a),a)TfSS(T,a),a)S-aa(T,S),a)T-T,ST,S(S),a)T-SS(T),a)S-S(T)(T)(S,a)T-SS(T,a)S 一 aa(T,S)T-T,ST,S(T)S 一(T)(T)S7.寫(xiě)一個(gè)文法，使其語(yǔ)言是奇凌 攵集，且每個(gè)奇數(shù)不以0 開(kāi)頭。解：文法 G(N):NfAB|BAfAC|DB-1|3|5|7|9D-B|2|4|6|8C-0|D8.設(shè)文法 G(S):S 一(L)|aS|aL-L,S|S(1)消除左遞歸和回溯；(2)計(jì)算每個(gè)非終結(jié)符

23、的 FIRST 和 FOLLOW。解：S 一(L)|aSS-S|L-SLLSL|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)=(T+i)=(T*F+i)(2)短語(yǔ)：(T*F+i),T*F+i,T*F,i素短語(yǔ)：T*F,i(2)FIRST)S)=(,aFIRST(S)=,a,4FIRST(L)=(,aFIRST(L)=,49.已知文法 G(E)E-T|E+TT-F|T*FFOLLOW(S)=#,)FOLLOW(S)=#,)FOLLOW(L)=)FOLLOW(L=)10

24、. Whilea0Vbv0doBeginX：=X+1;ifa0thena:=a1elseb:=b+1End;翻譯成四元式序列。解：(1) (j,a,0,5)(2) (j,3)(3) (j10gotoNEXT102: i:=j+j103: ai:=0104:基本塊 p 由如下語(yǔ)句構(gòu)成:T0:=3.14;T1:=2*T0;T2:=R+r;A:=Tl*T2;B:=A;T3:=2*T0;T4:=R+r;T5:=T3*T4;T6:=R-r;B:=T5*T6;試給出基本塊 p 的 DAG13.寫(xiě)出表達(dá)式（a+b）/（a-b-（a+b*c）的三元序列及四元序列。解：（1）三兀式:（十,a,b）（一，a,b）

25、（/,，）（*,b,c）（十,a,）（，）（2）四元式：(十,a,b,T1)(一,a,b,T2)(/,T1,T2,T3)(*,b,c,T4)(十,a,T4,T5)(一，T3,T5,T6)解：基本塊 p 的 DAG 圖:*14.寫(xiě)一個(gè)文法使其語(yǔ)言為偶數(shù)集，且每個(gè)偶數(shù)不以0 開(kāi)頭。解：文法 G(S):S-AB|B|A0AfAD|CB-2|4|6|8C-1|3|5|7|9|BD-0|C15 .設(shè)文法 G(S):S 一 S+aF|aF|+aFF-*aF|*a(1)消除左遞歸和回溯；(2)構(gòu)造相應(yīng)的 FIRST 和 Follow 集合。解：(1)S-aFS|+aFSS-+aFS|F-*aFF-F|(2)

26、FIRST(S)=a,+FOLLOW(S)=#FIRST(S)=+,eFOLLOW(S)=#FIRST(F)=*FOLLoW(F)=(+,#FIRST(F)=*,sFOLLOW(+,#16 .簡(jiǎn)要說(shuō)明語(yǔ)義分析的基本功能。答：語(yǔ)義分析的基本功能包括：確定類型、類型檢查、語(yǔ)義處理和某些靜態(tài)語(yǔ)義檢查。17 .考慮文法 GS:S 一(T)|a+S|aT 一 T,S|S消除文法的左遞歸及提取公共左因子。解：消除文法 GS的左遞歸：S 一(T)|a+S|aT-STTT|e提取公共左因子：S 一(T)|aSS-S|&T-STTT|e18 .試為表達(dá)式 w+(a+b)*(c+d/(e-10)+8)寫(xiě)出相應(yīng)的逆

27、波蘭表示。解：wab+cde10-/+8+*+19 .按照三種基本控制結(jié)構(gòu)文法將下面的語(yǔ)句翻譯成四元式序列：while(ACAB1)C=C+1;elsewhile(AD)A=A+2;解：該語(yǔ)句的四元式序列如下(其中 E1、E2 和 E3 分別對(duì)應(yīng) AvCABvD、A/和 AR,并且關(guān)系運(yùn)算符優(yōu)先級(jí)(Wj):100(j,A,C,102)101(j,_,_,113)102(jAc|aBA-abB-bc S=Ac=abcS=aB=abc確定化所以 L(GS)=abcL(GS)的全部元素先構(gòu)造 NFA22.構(gòu)造正規(guī)式 1(0|1)*101 相應(yīng)的 DFA01XAAAABABACABACAABYABY滁

28、AB重新命名，令 AB 為 B、AC 為 C、ABY 為 D 得：01XAAABBCBCADD;C0S-a|T)T-T,S|S對(duì)(a,(a,a)和(a,a),A,(a),a)的最左推導(dǎo)。解：又(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)為:寸(a,a),A,(a),a)的最左推導(dǎo)為:S=(T)=(T,S)=(S,S)=(T),S)=(T,S),S)=(T,S,S),S)=(S,S,S),S)=(T),S,S),S)=(T,S),S,S),S)=(S,S),S,S),S)=(a,

29、S),S,S),S)=(a,a),S,S),S)=(a,a)F,S),S)=(a,a,(T),S)=(a,a)F,(S),S)=(a,a)F,(a),S)=(a,a),A,(a),a)24.文法：S-MH|aH-LSo|K-dML|L-eHfM-K|bLM判斷 G 是否為 LL(1)文法，如果是，構(gòu)造 LL(1)分析表。解：各符號(hào)的 FIRST 集和 FOLLOW 集為:FIRStFOLLOWS氈 g叮顫M#,。H泣 3L局。，到K植M小,總口預(yù)測(cè)分析表為:adefb#S“MHpMHM-K-K-KH一L|-eHfK-E一二由于預(yù)測(cè)分析表中無(wú)多重入口，所以可判定文法是 LL(1)的。25.敘述由

30、下列正規(guī)式描述的語(yǔ)言(a)0(0|1)*0(c)(0|1)*0(0|1)(0|1)(d)0*10*10*10*(e)(00|11)*(01|10)(00|11)*(01|10)(00|11)*)*解：(a)以 0 開(kāi)頭、以 0 結(jié)尾的所有 0 和 1 的串。(b)由 0 和 1 組成的串，包括空串。(c)倒數(shù)第 3 個(gè)字符為 0,由 0 和 1 組成的串。(d)含有 3 個(gè) 1 的所有 0 和 1 的串。(e)由偶數(shù)個(gè) 0 和偶數(shù)個(gè) 1 構(gòu)成的所有 0 和 1 的串。26.已知文法GS:S-(L)|aL-L,S|S為句子(a,(a,a)構(gòu)造最左推導(dǎo)和最右推導(dǎo)。解：句子(a,(a,a)的最左推導(dǎo)

31、為：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)造下述文法 GS的自動(dòng)機(jī)：S-A0A-A0|S1|0該自動(dòng)機(jī)是確定的嗎？若不確定，則對(duì)它確定化。解：由于該文法的產(chǎn)生式 S-A0,A-A0|S1 中沒(méi)有字符集 VT 的輸入，所以不是確定的自動(dòng)機(jī)。要將其他確把 S?A0 代入產(chǎn)生式 A?S1 有：A=A01A01|0=

32、A(0|01)|0=0(0|01)*代入 S-A0 有該文法的正規(guī)式：0(0|01)*0,所以，改寫(xiě)該文法為確定的自動(dòng)機(jī)為由于狀態(tài) A 有 3 次輸入 0 的重復(fù)輸入，所以上圖只是 NFA,下面將它確定化:DFA:I-f-creflWbpsit=3小皿或aAV1回3XiCX,Y,ZC國(guó)工ZBtX2 .對(duì)下面的文法 GE-TEE-+E|T-FTT-T|F-PFF-*F|P-(E)|a|b|A(1)計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的 FIRST 集和 FOLLOW 集定化，必須先用代入法得到它對(duì)應(yīng)的正規(guī)式。下表由子集法將NFA 轉(zhuǎn)換為由上表可知 DFA 為:0(2)證明這個(gè)方法是 LL(1)的。(3)構(gòu)

33、造它的預(yù)測(cè)分析表。解：(1)計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的 FIRST 集和 FOLLOW 集。FIRST 集合有：FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)=(,a,br;FIRST(E)=+,FIRST(T)=FIRST(F)=FIRST(P)=(,a,b,A;FIRST(T尸F(xiàn)IRST(T)U產(chǎn)(,a,b,A,密FIRST(F)=FIRST(P)=(,a,b,A;FIRST(F)=FIRST(P)=*,s;FIRST(P)=(,a,b,A;FOLLOW 集合有：FOLLOW(E)=),#;FOLLOW(E)=FOLLOW(E)=),#;FOLLOW(T)=FIR

34、ST(E)UFOLLOW(E)=+,),#;/不包含F(xiàn)OLLOW(T)=FOLLOW(T)=FIRST(E)UFOLLOW(E)=+,),#;FOLLOW(F)=FIRST(T)UFOLLOW(T)=(,a,b,A,+,),#;/不包含F(xiàn)OLLOW(F)=FOLLOW(F)=FIRST(T)UFOLLOW(T)=(,a,b,A,+,),#;FOLLOW(P尸F(xiàn)IRST(F)UFOLLOW(F)=*,(,a,b,A,+,),#;不包含(2)證明這個(gè)方法是 LL(1)的。各產(chǎn)生式的 SELECT 集合有：SELECT(E-TE)=FIRST(T)=(,a,b,A;SELECT(E-+E)=+;SE

35、LECT(E-9=FOLLOW(E/)=),#SELECT(T-FT)=FIRST(F)=(,a,br;SELECT(T-T)=FIRST(T)=(,a,b,A;SELECT(T-)=FOLLOW(T/)=+,),#;SELECT(F-PF)=FIRST(P)=(,a,b,A;SELECT(F-*F)=*;SELECT(F-9=FOLLOW(F尸(,a,b,A,+,),#;SELECT(P-(E)尸(SELECT(P-a)=aSELECT(P-b)=bSELECT(P-A)=A可見(jiàn)，相同左部產(chǎn)生式的 SELECT 集的交集均為空，所以文法 GE是 LL(1)文法。(3)構(gòu)造它的預(yù)測(cè)分析表。文法

36、 GE的預(yù)測(cè)分析表如下：十*()at#ETIETTETT甲TIET9FTTFTT,T4TT3T6TT 岑FTPFTFF檸2FTPF一函今T今CT-5P今（E）T*Th3 .已知 NFA=(x,y,z,0,1,M,x,z)，其中:M(x,0)=z,M(y,0)=x,y,M(z,0)=x,z,M(x,1)=x,M(y,1)=（）,M（z,1）=y,構(gòu)造相應(yīng)的 DFA 并最小化。解：根據(jù)題意有 NFA 圖：下表由子集法將 NFA 轉(zhuǎn)換為 DFAITo-e-ciourefMaqTQ0總)Ij=礫?卻nefM?用TQf)AxFBTJinBzCb.3E*yC=1DyE區(qū)yE反yAxFbcjy?工zE肛y卜

37、面將該 DFA 最小化:(1)首先將它的狀態(tài)集分成兩個(gè)子集：P1=A,D,E,P2=B,C,F(2)區(qū)分 P2:由于 F(F,1)=F(C,1)=E,F(F,0)=F 并且 F(C,0)=C,所以F,C 等價(jià)。由于 F(B,0)=F(C,0)=C,F(B,1)=D,F(C,1)=E,而 D,E 不等價(jià)(見(jiàn)下步)，從而 B 與 C,F 可以區(qū)分。有 P21=C,F,P22=B(3)區(qū)分 P1:由于 A,E 輸入 0 到終態(tài)，而 D 輸入 0 不到終態(tài)，所以 D 與 A,E 可以區(qū)分，有 P11=A,E,P12=D(4)由于 F(A,0)=B,F(E,0)=F,而 B,F 不等價(jià)，所以 A,E 可以區(qū)分。綜上所述，DFA 可以區(qū)分為 P=A,B,D,E,C,F。所以最小化的 DFA 如下：4.已知文法為:S-aF|(T)T-T,S|S構(gòu)造它的 LR(0)分析表。解：加入非終結(jié)符 S,方法的增廣文法為：S-SS-a