最新編譯原理復(fù)習(xí)題(經(jīng)典)

1、精品文檔精品文檔精品文檔精品文檔精品文檔精品文檔編譯原理復(fù)習(xí)題一、是非題1.計(jì)算機(jī)高級(jí)語(yǔ)言翻譯成低級(jí)語(yǔ)言只有解釋一種方式。(X).每個(gè)文法都能改寫為L(zhǎng)L(1)文法。(X).算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。(J).LR分析方法是自頂向下語(yǔ)法分析方法。(X).用高級(jí)語(yǔ)言書寫的源程序都必須通過(guò)編譯，產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行這種說(shuō)法。(x).一個(gè)句型的句柄一定是文法某產(chǎn)生式的右部。().僅考慮一個(gè)基本塊，不能確定一個(gè)賦值是否真是無(wú)用的。().在中間代碼優(yōu)化中循環(huán)上的優(yōu)化主要有不變表達(dá)式外提和削減運(yùn)算強(qiáng)度。(x).對(duì)于數(shù)據(jù)空間的存貯分配，F(xiàn)ORTRAN采用動(dòng)態(tài)貯存分配策略。(x).甲機(jī)上的某編

2、譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。(x).遞歸下降分析法是自頂向下分析方法。().產(chǎn)生式是用于定義詞法成分的一種書寫規(guī)則。(x).在SLR(1)分析法的名稱中，S的含義是簡(jiǎn)單的。().綜合屬性是用于自上而下傳遞信息。(x).符號(hào)表中的信息欄中登記了每個(gè)名字的屬性和特征等有關(guān)信息，如類型、種屬、所占單元大小、地址等等。(x).程序語(yǔ)言的語(yǔ)言處理程序是一種應(yīng)用軟件。(x).解釋程序適用于COBOL和FORTRAN語(yǔ)言。(x).一個(gè)LL(l)文法一定是無(wú)二義的。(J).正規(guī)文法產(chǎn)生的語(yǔ)言都可以用上下文無(wú)關(guān)文法來(lái)描述。(J).一張轉(zhuǎn)換圖只包含有限個(gè)狀態(tài)，其中有一個(gè)被

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

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

5、文檔精品文檔精品文檔.LR分析技術(shù)無(wú)法適用二義文法。(x).樹形表示和四元式不便于優(yōu)化，而三元式和間接三元式則便于優(yōu)化。(x).程序中的表達(dá)式語(yǔ)句在語(yǔ)義翻譯時(shí)不需要回填技術(shù)。().對(duì)中間代碼的優(yōu)化依賴于具體的計(jì)算機(jī)。(x).若一個(gè)句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。(x).在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。(x).削減運(yùn)算強(qiáng)度破壞了臨時(shí)變量在一基本塊內(nèi)僅被定義一次的特性。(x).編譯程序與具體的機(jī)器有關(guān)，與具體的語(yǔ)言無(wú)關(guān)。(x)二、選擇題(請(qǐng)?jiān)谇袄ㄌ?hào)內(nèi)選擇最確切的一項(xiàng)作為答案劃一個(gè)勾，多劃按錯(cuò)論)一個(gè)編譯程序中，不僅包含詞法分析，(A)，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成

6、等五個(gè)部分。A.語(yǔ)法分析B.文法分析C.語(yǔ)言分析D.解釋分析語(yǔ)法分析器則可以發(fā)現(xiàn)源程序中的(D)。A.語(yǔ)義錯(cuò)誤B.語(yǔ)法和語(yǔ)義錯(cuò)誤C.錯(cuò)誤并校正D.語(yǔ)法錯(cuò)誤解釋程序處理語(yǔ)言時(shí),大多數(shù)采用的是(B)方法。A.源程序命令被逐個(gè)直接解釋執(zhí)行B.先將源程序轉(zhuǎn)化為中間代碼，再解釋執(zhí)行C.先將源程序解釋轉(zhuǎn)化為目標(biāo)程序，再執(zhí)行D.以上方法都可以編譯程序是一種(B)。A.匯編程序B.翻譯程序C.解釋程序D.目標(biāo)程序文法分為四種類型，即0型、1型、2型、3型。其中3型文法是(B)。A.短語(yǔ)文法B.正則文法C.上下文有關(guān)文法D.上下文無(wú)關(guān)文法通常一個(gè)編譯程序中，不僅包含詞法分析，語(yǔ)法分析，中間代碼生成，代碼優(yōu)化，目

7、標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括(C)。A.模擬執(zhí)行器B.解釋器C.表格處理和出錯(cuò)處理D.符號(hào)執(zhí)行器一個(gè)句型中的最左(B)稱為該句型的句柄。A.短語(yǔ)B.簡(jiǎn)單短語(yǔ)C.素短語(yǔ)D.終結(jié)符號(hào)文法GE：ET|E+TTF|T*FFI(E)該文法句型EF*(ET)的簡(jiǎn)單短語(yǔ)是下列符號(hào)串中的(B)。(E+T)E+TFF*(E+T)A.和B.和C.和D.詞法分析器用于識(shí)別(C)。A.句子8.句型C.單詞D.產(chǎn)生式在自底向上的語(yǔ)法分析方法中，分析的關(guān)鍵是(A)。A.尋找句柄B.尋找句型C.消除遞歸D.選擇候選式文法G產(chǎn)生的(D)的全體是該文法描述的語(yǔ)言。A.句型B.終結(jié)符集C.非終結(jié)符集D.句子若文法G定義的語(yǔ)言是

8、無(wú)限集，則文法必然是(A)。A.遞歸的B.前后文無(wú)關(guān)的C.二義性的D.無(wú)二義性的四種形式語(yǔ)言文法中，1型文法又稱為(C)文法。A.短語(yǔ)結(jié)構(gòu)文法B.前后文無(wú)關(guān)文法C.前后文有關(guān)文法D.正規(guī)文法一個(gè)文法所描述的語(yǔ)言是(A)。A.唯一的B.不唯一的C.可能唯一，好可能不唯一D.都不對(duì)精品文檔(B)和代碼優(yōu)化部分不是每個(gè)編譯程序都必需的。A.語(yǔ)法分析B.中間代碼生成C.詞法分析D.目標(biāo)代碼生成(B)是兩類程序語(yǔ)言處理程序。A.高級(jí)語(yǔ)言程序和低級(jí)語(yǔ)言程序B.解釋程序和編譯程序C.編譯程序和操作系統(tǒng)D.系統(tǒng)程序和應(yīng)用程序數(shù)組的內(nèi)情向量中肯定不含有數(shù)組的(D)的信息。A.維數(shù)8.類型C.維上下界D.各維的界

9、差一個(gè)上下文無(wú)關(guān)文法G包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開始符號(hào)，以及一組(D)。A.句子8.句型C.單詞D.產(chǎn)生式文法分為四種類型，即0型、1型、2型、3型。其中2型文法是(D)。A.短語(yǔ)文法B.正則文法C.上下文有關(guān)文法D.上下文無(wú)關(guān)文法文法G所描述的語(yǔ)言是(C)的集合。B.文法G的字母表V的閉包V*B.文法G的字母表V的閉包V*中的所有符號(hào)串C.由文法的開始符號(hào)推出的所有終極符串C.由文法的開始符號(hào)推出的所有終極符串21.詞法分析器用于識(shí)別(C)。A.字符串B.語(yǔ)句C.單詞22.文法分為四種類型，即0型、1型、2型、A.短語(yǔ)文法B.正則文法C.(A)是一種典型的

10、解釋型語(yǔ)言。A.BASICB.CC.FORTRAN.與編譯系統(tǒng)相比，解釋系統(tǒng)(D)。A.比較簡(jiǎn)單，可移植性好，執(zhí)行速度快C.比較簡(jiǎn)單，可移植性差，執(zhí)行速度慢D.由文法的開始符號(hào)推出的所有符號(hào)串D.標(biāo)識(shí)符。其中0型文法是(A)。上下文有關(guān)文法D.上下文無(wú)關(guān)文法D.PASCALB.比較復(fù)雜，可移植性好，執(zhí)行速度快D.比較簡(jiǎn)單，可移植性好，執(zhí)行速度慢用高級(jí)語(yǔ)言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫(B)。A.源程序B.目標(biāo)程序C.連接程序D.解釋程序詞法分析器用于識(shí)別(A)。A.字符串B.語(yǔ)句C.單詞D.標(biāo)識(shí)符編寫一個(gè)計(jì)算機(jī)高級(jí)語(yǔ)言的源程序后,到正式上機(jī)運(yùn)行之前，一般要經(jīng)過(guò)(B)這幾步:編輯(2)編譯(3)

11、連接(4)運(yùn)行A.(1)(2)(3)(4)B.(1)(2)(3)C.(1)(3)D.(1)(4)把匯編語(yǔ)言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由(B)完成的。A.編譯器B.匯編器C.解釋器D.預(yù)處理器.詞法分析器的輸出結(jié)果是(C)。A.單詞的種別編碼B.單詞在符號(hào)表中的位置C.單詞的種別編碼和自身值D.單詞自身值.正規(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ù)相等.文法G：SxSxy所識(shí)別的語(yǔ)言是(C)。A.xyxB.(xyx)*C.xnyxn(n0)D.x*yx*.如果文法G是無(wú)二義的

12、，則它的任何句子(A)。A.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹必定相同B.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹可能不同C.最左推導(dǎo)和最右推導(dǎo)必定相同D.可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語(yǔ)法樹相同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.程序變量.表達(dá)式(AVB)八(CVD)的逆波蘭表示為(B)。A.ABVACDVB.ABVCDVAC.ABVCDVAD.ABVACDV.優(yōu)化可生成(D)的目標(biāo)代碼。B.占用存儲(chǔ)空間較小AB.占用存儲(chǔ)空間較小C.運(yùn)行時(shí)間短但占用內(nèi)存空間大D.運(yùn)行

13、時(shí)間短且占用存儲(chǔ)空間小.下列(C)優(yōu)化方法不是針對(duì)循環(huán)優(yōu)化進(jìn)行的。A.A.強(qiáng)度削弱B.刪除歸納變量.編譯程序使用(B)區(qū)別標(biāo)識(shí)符的作用域。A.說(shuō)明標(biāo)識(shí)符的過(guò)程或函數(shù)名C.說(shuō)明標(biāo)識(shí)符的過(guò)程或函數(shù)的動(dòng)態(tài)層次.編譯程序絕大多數(shù)時(shí)間花在(D)上。C.刪除多余運(yùn)算D.代碼外提B.說(shuō)明標(biāo)識(shí)符的過(guò)程或函數(shù)的靜態(tài)層次D.標(biāo)識(shí)符的行號(hào)A.出錯(cuò)處理B.詞法分析C.目標(biāo)代碼生成D.表格管理.編譯程序是對(duì)(D)。A.匯編程序的翻譯B.高級(jí)語(yǔ)言程序的解釋執(zhí)行C.機(jī)器語(yǔ)言的執(zhí)行D.高級(jí)語(yǔ)言的翻譯.采用自上而下分析，必須(C)。A.消除左遞歸B.消除右遞歸C.消除回溯D.提取公共左因子.在規(guī)范歸約中，用(B)來(lái)刻畫可歸約串

14、。A.直接短語(yǔ)B.句柄C.最左素短語(yǔ)D.素短語(yǔ).若a為終結(jié)符，則A-a為(B)項(xiàng)目。A.歸約B.移進(jìn)C.接受D.待約.間接三元式表示法的優(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)化為(47.基本塊內(nèi)的優(yōu)化為(B)。A.代碼外提，刪除歸納變量C.強(qiáng)度削弱，代碼外提B.D.刪除多余運(yùn)算，刪除無(wú)用賦值循環(huán)展開，循環(huán)合并.在目標(biāo)代碼生成階段，符號(hào)表用(D)。A.目標(biāo)代碼生成B.語(yǔ)義檢查C.語(yǔ)法檢查D.地址分配.若項(xiàng)目集1k含有A-，則在狀態(tài)k時(shí)，僅當(dāng)面臨的輸入符號(hào)aFOLLOW(A)時(shí)，才

15、采取A-動(dòng)作的一定是(D)。A.LALR文法B.LR(0)文法C.LR文法D.SLR文法.堆式動(dòng)態(tài)分配申請(qǐng)和釋放存儲(chǔ)空間遵守(D)原則。A.先請(qǐng)先放B.先請(qǐng)后放C.后請(qǐng)先放D.任意三、填空題.編譯程序的工作過(guò)程一般可以劃分為詞法分析,語(yǔ)法分析,語(yǔ)義分析,中間代碼生成,代碼優(yōu)化等幾個(gè)基本階段,同時(shí)還會(huì)伴有_表格處理_和_出錯(cuò)處理_。.編譯方式與解釋方式的根本區(qū)別在于_是否生成目標(biāo)代碼_。.產(chǎn)生式是用于定義_語(yǔ)法成分_的一種書寫規(guī)則。.設(shè)G是一個(gè)給定的文法，S是文法的開始符號(hào)，如果S-x(其中xVT*),則稱x是文法的一個(gè)句子。.自頂向下的語(yǔ)法分析方法的基本思想是：從文法的_開始符號(hào)開始，根據(jù)給定

16、的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行_直接推導(dǎo)，試圖推導(dǎo)出文法的_句子，使之與給定的輸入串_匹配_。.常用的參數(shù)傳遞方式有_傳地址_，傳值和傳名。.一個(gè)句型中的最左簡(jiǎn)單短語(yǔ)稱為該句型的_句柄_。.對(duì)于文法的每個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，稱為_語(yǔ)義規(guī)則_。精品文檔精品文檔精品文檔精品文檔精品文檔精品文檔精品文檔精品文檔9一個(gè)典型的編譯程序中，不僅包括_詞法分析_、_語(yǔ)法分析_、_中間代碼生成_、代碼優(yōu)化、目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括表格處理和出錯(cuò)處理。從功能上說(shuō)，程序語(yǔ)言的語(yǔ)句大體可分為_執(zhí)行性_語(yǔ)句和_說(shuō)明性_語(yǔ)句兩大類。掃描器的任務(wù)是從_源程序_中識(shí)別出一個(gè)個(gè)_單詞符號(hào)_

17、。產(chǎn)生式是用于定義_語(yǔ)法范疇_的一種書寫規(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ǔ)言編寫的程序主要有兩種途徑：_解釋_和_編譯_。19掃描器是_詞法分析器_，它接受輸入的_源程序_，對(duì)源程序進(jìn)行_詞法分析_并識(shí)別出一個(gè)個(gè)單詞符號(hào)，其輸出結(jié)果是單詞符號(hào)，供語(yǔ)法分析器使用。20自上而下分析

18、法采用_移進(jìn)_、歸約、錯(cuò)誤處理、_接受_等四種操作。.一個(gè)LR分析器包括兩部分：一個(gè)總控程序和一張分析表_。.后綴式abc-/所代表的表達(dá)式是a/(b-c)_。23局部?jī)?yōu)化是在_基本塊_范圍內(nèi)進(jìn)行的一種優(yōu)化。.詞法分析基于_正則_文法進(jìn)行，即識(shí)別的單詞是該類文法的句子。.語(yǔ)法分析基于_上下文無(wú)關(guān)_文法進(jìn)行，即識(shí)別的是該類文法的句子。語(yǔ)法分析的有效工具是_語(yǔ)法樹_。.分析句型時(shí)，應(yīng)用算符優(yōu)先分析技術(shù)時(shí)，每步被直接歸約的是最左素短語(yǔ),而應(yīng)用LR分析技術(shù)時(shí)，每步被直接歸約的是_句柄_。.語(yǔ)義分析階段所生成的與源程序等價(jià)的中間表示形式可以有_逆波蘭_、_四無(wú)式表示_與_三元式表示_等。.按Chomsk

19、y分類法，文法按照規(guī)則定義的形式進(jìn)行分類。.一個(gè)文法能用有窮多個(gè)規(guī)則描述無(wú)窮的符號(hào)串集合(語(yǔ)言)是因?yàn)槲姆ㄖ写嬖谟衉遞歸_定義的規(guī)則。四、簡(jiǎn)答題.寫一文法，使其語(yǔ)言是偶正整數(shù)的集合,要求：(1)允許0打頭；(2)不允許0打頭。解：(1)S(SPDN0129PS)P:S-PD|Dp-npinD-0|2|4|6|8N-0|1|2|3|4|5|6|792)S(SPRDNQ0129PS)P:S-PD|P0|DP-NR|NR-QR|QD-2|4|6|8N-1|2|3|4|5|6|79Q-0|1|2|3|4|5|6|79.構(gòu)造正規(guī)式相應(yīng)的NFA:1(0|1)*101精品文檔精品文檔精品文檔精品文檔解1（0

20、11）*101對(duì)應(yīng)的NFA為.寫出表達(dá)式（a+b*c）/（a+b）d的逆波蘭表示和三兀式序列。逆波蘭表示：abc*ab/d三元式序列：（*，b，c）（十,a,）（，a，b）（/,，）（一，d）已知文法GS為：SdAAaAlablGS產(chǎn)生的語(yǔ)言是什么？答：GS產(chǎn)生的語(yǔ)言是L（GS）=danbmln1,m0。構(gòu)造正規(guī)式相應(yīng)的DFA:1(1010*l1(010)*1)*0。解1(1010*l1(010)解1(1010*l1(010)*1)*0對(duì)應(yīng)的NFA為解：句型歸約規(guī)則句柄(a，a)，a)Saa(S，a)，a)TSS(T，a)，a)Saa(T，S)，a)TT,ST，S(S)，a)TSS精品文檔，S

21、al八l(T)TT,SIS寫出句子(a，a)a）的規(guī)范歸約過(guò)程及每一步的句柄。精品文檔精品文檔精品文檔精品文檔精品文檔精品文檔(T),a)SS(T)(T)(S,a)TSS(T,a)Saa(T,S)TT,ST,S(T)S(T)(T)S7.寫一個(gè)文法，使其語(yǔ)言是奇數(shù)集，且每個(gè)奇數(shù)不以0開頭。解：文法G(N)：NBIBIB1II5I7I9BI211180I8.設(shè)文法G(S)：S(L)IaSIaLL，SIS(1)消除左遞歸和回溯；(2)計(jì)算每個(gè)非終結(jié)符的FIRST和FOLLOWo解：(1)S(L)IaSSSILSLLSLI(2)FIRST)S)(2)FIRST)S)=(,aFIRST(S)=,a,FI

22、RST(L)=(,aFIRST(L)=,9.已知文法G(E)ETIE+TTFIT*FFOLLOW(S)=#,)FOLLOW(S)=#,)FOLLOW(L)=)FOLLOW(L=)F(E)Ii(1)給出句型(1*F+i)的最右推導(dǎo)；(2)給出句型(1*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,iWhilea0Vb0thena：=a1elseb：=b+1End；翻譯成四元式序列。解：(j,a,0,5)精品文檔(j，3)(j10gotoNEXT:i:=

23、j+j:ai:=0設(shè)基本塊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的DAG。解：基本塊p的DAG圖：寫出表達(dá)式（a+b）/（a-b-（a+b*c）的三元序列及四元序列。解：（1）三元式：（十,a,b）（一，a,b）（/,，）（*,b,c）（十,a,）（一，）（2）四元式：（十,a,b,T1）（一，a,b,T2）（/,T1,T2,T3）（*,b,c,T4）（十,a,T4,T5）（一，T3,T5,T6）寫一個(gè)文法使其語(yǔ)言為偶數(shù)集，且每個(gè)偶數(shù)

24、不以0開頭。解：文法G（S）：SABIBIA0AADIB2I4I6I81I3I5II9IBD0I設(shè)文法G（S）：SS+aFIaFI+aFF*aFI*a（1）消除左遞歸和回溯；（2）構(gòu)造相應(yīng)的FIRST和Follow集合。解：（1）S-aFSI+aFSS-+aFSIF-*aFF-FI精品文檔精品文檔精品文檔精品文檔(2)FIRST(2)FIRST(S)=a,FIRST(S)=+,FIRST(F)=*FIRST(F)二*,+并且關(guān)系運(yùn)算符優(yōu)先級(jí)FOLLOW(S)=#FOLLOW(S)=#FOLLoW(F)=(+,#FOLLOW(+，簡(jiǎn)要說(shuō)明語(yǔ)義分析的基本功能。答：語(yǔ)義分析的基本功能包括:確定類型、

25、類型檢查、語(yǔ)義處理和某些靜態(tài)語(yǔ)義檢查?？紤]文法GS:S(T)a+SaTT,SS消除文法的左遞歸及提取公共左因子。解：消除文法GS的左遞歸：S(T)a+SaTSTT,ST提取公共左因子：S(T)aSS+STSTT,ST試為表達(dá)式w+(a+b)*(c+d/(e-10)+8)寫出相應(yīng)的逆波蘭表示。解：wab+cde10-/+8+*+按照三種基本控制結(jié)構(gòu)文法將下面的語(yǔ)句翻譯成四元式序列：while(AC八BD)i(A1)C=C+1;elewhile(AD)A=A+2;。解：該語(yǔ)句的四元式序列如下(其中E1、E2和E3分別對(duì)應(yīng)ACABA1和AD,高)：100(j,A,C,102)101(j,_,_,11

26、3)102(jAc|aBA-abB-bc寫出L(GS)的全部元素。解：S=Ac=abc或S=aB=abc所以L(GS)=abc.構(gòu)造正規(guī)式1(011)*101相應(yīng)的DFA。確定化：解：先構(gòu)造NFA：確定化：a,1XA：AAABABACAEACAABYABY,AC.AB重新命名，令A(yù)B為B、AC為C、ABY為D得:精品文檔精品文檔精品文檔精品文檔精品文檔精品文檔精品文檔精品文檔0,1XAAABB-CBADDCB：所以，可得DFA為:1.文法S-a1Al(T)T-T,SlS對(duì)(a,(a,a)和(a,a),A,(a),a)的最左推導(dǎo)。解：對(duì)(a,(a,a)的最左推導(dǎo)為：S=(T)=(T,S)=(S,

27、S)=(a,S)二(a,(T)=(a,(T,S)=(a,(S,S)二(a,(a,S)=(a,(a,a)對(duì)(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,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).文法：S-MHlaH-LSolK-dMLlL-eHfM-K

28、lbLM判斷G是否為L(zhǎng)L(1)文法，如果是，構(gòu)造LL(1)分析表。解：各符號(hào)的FIRST集和FOLLOW集為：FIRSTFOLLOWS桐M.3以【遇aH上明冉口甫K殖雙預(yù)測(cè)分析表為:a0ef：b#SMHM-黑-K4sLK-E_.由于預(yù)測(cè)分析表中無(wú)多重入口，所以可判定文法是LL(1)的。25敘述由下列正規(guī)式描述的語(yǔ)言(a)0(0|1)*0(b)(10)1*)*(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開頭、以0結(jié)尾的所有0和1的串。(b)由0和1組成的串，包括空串。(c)

29、倒數(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)為：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ī)：

30、S-A0A-A0|S1|0該自動(dòng)機(jī)是確定的嗎？若不確定,則對(duì)它確定化。解：由于該文法的產(chǎn)生式S-A0,A-A0IS1中沒有字符集VT的輸入，所以不是確定的自動(dòng)機(jī)。要將其他確定化，必須先用代入法得到它對(duì)應(yīng)的正規(guī)式。把S?A0代入產(chǎn)生式A?S1有：A=A01A01I0=A(0I01)I0=0(0I01)*。代入S-A0有該文法的正規(guī)式：0(0|01)*0,所以,改寫該文法為確定的自動(dòng)機(jī)為：由于狀態(tài)A有3次輸入0的重復(fù)輸入，所以上圖只是NFA,下面將它確定化：下表由子集法將NFA轉(zhuǎn)換為DFA:I工-c-ciosun(Ivi&ven泡0).Il-(Move用伍刀jAM,BXBC及工ZC區(qū)Y汨?ft工z

31、BX2對(duì)下面的文法G：E-TEE-+EIT-FTT-TIF-PFF-*FIP-(E)lalb1A(1)計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST集和FOLLOW集。證明這個(gè)方法是LL(1)的。構(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)=FIRST(P)=(,a,b,A;FIRST(T)=FIRST(T)U=(,a,b,A,；FIRST(F)=FIRST(P)=(,a,b,A;FIRST(F)=

32、FIRST(P)=*,;FIRST(P)=(,a,b,A;FOLLOW集合有：FOLLOW(E)=),#;FOLLOW(E)=FOLLOW(E)=),#;FOLLOW(T)=FIRST(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)=FIRST(F)UFOLLOW(F)=*,(,a,b,A,+,

33、),#；不包含(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-)=FLL(T)=,),;SELECT(F-PF)=FIRST(P)=(,a,b,A;SELECT(F-*F)=*;SELECT(F-)=FLL(F)=(,a,b,A,),；SELECT(P-(E)=(SE

34、LECT(P-a)=aSELECT(P-b)=bSELECT(P-A)=A可見，相同左部產(chǎn)生式的SELECT集的交集均為空，所以文法GE是LL(1)文法。(3)構(gòu)造它的預(yù)測(cè)分析表。文法GE的預(yù)測(cè)分析表如下：+I：a:%fu#ETIE，TTE，.T-WTTE犁；今短T了TFT彩FtTFT，-FTXs。宅離T-3.TTTfEF今加一PF錦百.今F。十3已知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圖：0下表由子集法將NFA轉(zhuǎn)換為DF

35、A：IIo-E-ciosun(Ivf&ve7b,f70)-Ii=qNo甌m(Move弗fEJ)-Ak-BhAxBz：C5aPly工。區(qū)z：d7：E卜yE瓦貨FbazAkFk;灰工F/孔zEky精品文檔精品文檔精品文檔精品文檔精品文檔精品文檔精品文檔精品文檔下面將該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à)(見下步)，從而B與C，F(xiàn)可以區(qū)分。有P21=C,F,P22=B。區(qū)分P1:由于A，E輸入0到終態(tài)，而D輸入0不到終態(tài)，所以D與A，E可以區(qū)分，有P11=A,E,P12=D。(4