武漢理工編譯原理復(fù)習(xí)題目(很全哦)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上一.名詞解釋：1)前綴答：前綴是指符號串任意首部。2)可歸前綴答：可歸前綴是指規(guī)范句型的一個前綴，這種前綴包含句柄且不含句柄之后的任何符號。3)活前綴答：活前綴規(guī)范句型的一個前綴，這種前綴不含句柄之后的任何符號。 或給定文法規(guī)范句型的可歸前綴的任意首部。4)簡單短語答：簡單短語設(shè)GZ是給定文法,w=xuyV+，為該文法的句型,如果滿足下面兩個條件: Z xUy； Uu； 則稱句型xuy 中的子串u是句型xuy的簡單短語。5)掃描遍答：掃描遍指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描一次。6)句柄答：句柄給定句型中的最左簡單短語就是句柄。7)句型答：句型設(shè)G是一個給定

2、的文法，S是文法的開始符號，如果Sx(其中xV*),則稱x是文法的一個句型。*8)句子答：句子設(shè)G是一個給定的文法，S是文法的開始符號，如果S x（其中xVT*），則稱x是文法的一個句子。9)非終結(jié)符答：非終結(jié)符出現(xiàn)在文法產(chǎn)生式的左部且能派生出符號或符號串的那些符號稱為非終結(jié)符號。10)終結(jié)符答：終結(jié)符出現(xiàn)在文法產(chǎn)生式的右部且不能派生出符號或符號串的那些符號稱為終結(jié)符號。11）屬性文法答：一個屬性文法形式的定義為一個三元組AG，AG=（G，V，E）。 其中G為一個上下文無關(guān)文法；V為屬性的有窮集；E為一組語義規(guī)則。12）語法制導(dǎo)翻譯答：語法制導(dǎo)翻譯語法制導(dǎo)翻譯就是在語法分析的過程中，當(dāng)進(jìn)行推導(dǎo)

3、或歸約時同步完成附加在所使用的產(chǎn)生式上的語義規(guī)則描述的動作，從而實現(xiàn)語義處理。或：為文法中每個產(chǎn)生式配上一組語義規(guī)則，并且在語法分析過程中，隨著分析的步步進(jìn)展，當(dāng)進(jìn)行推導(dǎo)或歸約時同步完成附加在所使用的產(chǎn)生式上的語義規(guī)則描述的動作，從而進(jìn)行翻譯的辦法稱作語法制導(dǎo)翻譯。13）后綴式答：后綴式一種把運算量（操作數(shù)）寫在前面，把算符寫在后面（后綴）的表示法。14）短語答：短語設(shè)GZ是給定文法,w=xuyV+，為該文法的句型,如果滿足下面兩個條件: Z xUy； U u； 則稱句型xuy 中的子串u是句型xuy的短語?；颍壕湫驼Z法樹的全部子樹的葉從左到右排列起來構(gòu)成的符號串均是句型的短語。15）基本塊答

4、：基本塊源程序或者中間代碼程序中只有一個入口和一個出口的順序執(zhí)行的代碼段。16）語義規(guī)則答：對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，稱為語義規(guī)則。17）語法分析答：語法分析按文法的產(chǎn)生式識別輸入的符號串是否為一個句子的分析過程。18）四元式答：四元式是一個帶有四個域的記錄結(jié)構(gòu)，這四個域分別稱為操作符域、左運算對象域、右運算對象域及運算結(jié)果域。二簡答題：1) 什么是句子？ 什么是語言?*解答：句子設(shè)G是一個給定的文法，S是文法的開始符號，如果S x（其中xVT*），則稱x是文法的一個句子。語言語言是句子的集合?；蛟O(shè)GS是給定文法，則由文法G所定義的語言L(G)可描述為：L(G)xSx,x

5、VT* 。2) DFA與NFA有何區(qū)別 ? 解答:DFA與NFA的區(qū)別表現(xiàn)為兩個方面:一是NFA可以有若干個開始狀態(tài)，而DFA僅只有一個開始狀態(tài)。另一方面，DFA的映象M是從K到K，而NFA的映象M是從K到K的子集，即映象M將產(chǎn)生一個狀態(tài)集合（可能為空集），而不是單個狀態(tài)。3) 自頂向下的語法分析方法的基本思想是什么?解答:從文法的開始符號開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行直接推導(dǎo)，試圖推導(dǎo)出文法的句子，使之與給定的輸入串匹配。4) 自底向上的語法分析方法的基本思想是什么?解答:從給定的輸入串（終結(jié)符串）開始，根據(jù)文法的規(guī)則一步一步的向上進(jìn)行直接歸約，試圖歸約到文法的開

6、始符號。5) 一個上下文無關(guān)文法G包括哪四個組成部分？解答:一組非終結(jié)符號，一組終結(jié)符號，一個開始符號，以及一組產(chǎn)生式。6) 在自底向上的語法分析方法中，分析的關(guān)鍵是什么？解答:關(guān)鍵是尋找句柄。7) 在自頂向下的語法分析方法中，分析的關(guān)鍵是什么？解答:關(guān)鍵是選擇候選式。8) 編譯程序中語法分析器接收以什么為單位的輸入？解答: 接收以單詞為單位的輸入。9) 若一個文法是遞歸的，則它所產(chǎn)生的語言的句子是可枚舉的嗎？解答: 它所產(chǎn)生的語言的句子不是可枚舉的，而是無窮多個。10) 編譯程序生成的目標(biāo)程序是不是一定是機(jī)器語言的程序？解答:不一定是機(jī)器語言的程序。11) 詞法分析器是用于做什么的？解答:詞

7、法分析器是用于識別單詞的。12) “用高級語言書寫的源程序都必須通過編譯,產(chǎn)生目標(biāo)代碼后才能投入運行”這種說法正確嗎？解答: 不正確。13) 把匯編語言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由什么完成的？程序代碼區(qū)靜態(tài)數(shù)據(jù)區(qū)棧區(qū)堆區(qū)解答: 由匯編器（匯編程序）完成的。14)圖示運行時存儲空間的劃分（分為哪幾個區(qū)）。 解答: 一般分為靜態(tài)區(qū)和動態(tài)區(qū)： 程序代碼區(qū)、靜態(tài)數(shù)據(jù)區(qū)、棧區(qū)和堆區(qū)15)詞法分析的主要任務(wù)是什么？ 解答:詞法分析器的任務(wù)是對構(gòu)成源程序的字符串從左到右逐個字符逐個字符地進(jìn)行掃描，依次把它們識別為一個一個具有獨立意義的單詞，并確定其屬性，再轉(zhuǎn)換為長度統(tǒng)一的屬性字并輸出。16)常用

8、的中間語言種類有哪幾種？解答: 常用的中間語言種類有逆波蘭表示、三元式、四元式和樹形表示。17）文法G所描述的語言是什么的集合？解答:是由文法的開始符號推出的所有終結(jié)符串的集合?；蛘f是句子的集合。18）喬姆斯基把文法分為四種類型，即0型、1型、2型、3型。其中2型文法叫什么？解答: 2型文法叫上下文無關(guān)文法。19）編譯程序是一種解釋程序嗎？還是什么程序？解答:編譯程序是一種翻譯程序。20）按邏輯上劃分，編譯程序第二步工作是什么？解答: 編譯程序第二步工作是語法分析。21）源程序是用高級語言編寫的，目標(biāo)程序是機(jī)器語言程序或匯編語言程序 ，則其翻譯程序稱為什么？解答: 其翻譯程序稱為編譯程序。22

9、）編譯方式與解釋方式的根本區(qū)別為什么？解答:編譯方式與解釋方式的根本區(qū)別在于是否生成目標(biāo)代碼。23）常見的動態(tài)存貯分配策略有哪兩種？解答:常見的兩種動態(tài)存貯分配策略是棧式動態(tài)分配策略和堆式動態(tài)分配策略。24）常用的參數(shù)傳遞方式有哪三種？解答:常見的參數(shù)傳遞方式有傳地址、傳值和傳名三種方式。25）語法分析的任務(wù)是什么？解答:語法分析的任務(wù)是識別給定的終結(jié)符串是否為給定文法的句子。26）局部優(yōu)化是局限于一個什么范圍內(nèi)的一種優(yōu)化？解答: 是局限于一個基本塊范圍內(nèi)的一種優(yōu)化。27）文法等價的定義是什么？解答: 設(shè)G1和G2是給定的文法，如果有L（G1）= L（G2），則稱G1與G2等價。28）在語法分

10、析處理中，F(xiàn)IRST集合、FOLLOW集合、SELECT集合均是什么集合？解答: 均是終結(jié)符集。29）通常一個編譯程序中應(yīng)包括哪七個部分？解答: 通常一個編譯程序中應(yīng)包含詞法分析，語法分析，語義分析與中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成以及表格處理和出錯處理等七個部分。32）如果編譯程序生成的目標(biāo)程序是匯編語言程序，則源程序的執(zhí)行分為哪三個階段？解答: 源程序的執(zhí)行分為三個階段: 編譯階段，匯編階段和運行階段。33）翻譯程序是這樣一種程序，它能夠?qū)⒂檬裁崔D(zhuǎn)換成與其等價的用乙語言書寫的程序？解答:能夠?qū)⒂眉渍Z言書寫的程序轉(zhuǎn)換成與其等價的用乙語言書寫的程序。34）說明下面文法GS是二義性文法：SS

11、aS|SbS|cSd|eS|f解答:fafbf是文法GS的一個句子，并且有兩個不同的最右推導(dǎo)。（1）S = SaS = SaSbS = SaSbf= Safbf= fafbf （2）S = SbS = Sbf= SaSbf = Safbf= fafbf因此說明此文法有二義性。35）在屬性文法中，綜合屬性與繼承屬性是如何傳遞信息的？解答: 綜合屬性用于自下而上傳遞信息，繼承屬性用于自上而下傳遞信息。36）代碼優(yōu)化的主要目標(biāo)是什么？解答: 代碼優(yōu)化的主要目標(biāo)是如何提高目標(biāo)程序的運行速度和如何減少目標(biāo)程序運行時所需的空間。37）寫一個文法，使其語言是無符號二進(jìn)制實數(shù)（不含指數(shù)）。解答:文法G(N)：

12、 NL.L|L LLB|B B0|1三應(yīng)用題1）消除下列文法GA的左遞歸。EE-TTTT/FFF( E )i解答：消除文法GE的左遞歸后得到：ETEE-T ETFTT/FTF( E )i2） 消除下列文法GA的左遞歸。AAaBBBBbCCCeDDD(A)d解答：消除文法GA的左遞歸后得到：A BA AaBAB CBBbcBCeDDD(A)d3）給定下列自動機(jī)：其中：開始狀態(tài)：0 終止?fàn)顟B(tài)：2aaa0bbb12把此自動機(jī)轉(zhuǎn)換為確定自動機(jī)DFA。 a b0 01 201 01 22 1 2 1 2a b 0 0,1 2 1 2 2 1 2解答： 有狀態(tài)矩陣如圖：-02aaba101bbb02bab

13、b1極小化后：a從而可得DFA如圖：4）正規(guī)式（a|b）*a(a|b) 構(gòu)造一個等價的有限自動機(jī)。解答：a,baab012四設(shè)計題（1）給定文法GS 及相應(yīng)翻譯方案為：1SS print:“a”2Sr D print:“b”3DD，i print:“c”4Di print:“d”a. 按chomsky分類法，文法G屬于哪一型文法？ b. 符號串ri,i,i是不是該文法的一個句型，請證實。 c. 若是句型，寫出該句型的所有短語、簡單短語，以及句柄。d. 構(gòu)造識別該文法的活前綴的DFA。 e. 判斷該文法是LR（0）還是SLR（1），并構(gòu)造其相應(yīng)的語法分析表。 f. 對于ri,i,i這個輸入符號串

14、，經(jīng)該翻譯方案翻譯后的輸出是什么？ 解答：a文法G屬于2型(上下文無關(guān))文法。b符號串r i,i,i是該文法的一個句型。證：SSrDrD，i rD，i，i r i，i，i，得證。或證：構(gòu)造語法樹見圖4，可知符號串r i,i,i是該文法的一個句型。c句型r i,i,i的短語有：r i,i,i； i,i,i；i,i； 第一個i簡單短語有：第一個i 句柄有：第一個id求得文法G的識別全部活前綴的DFA見圖3：I1:SS.I0:S.S S.rDI2:Sr.DD.D，iD.irI4:SrD.DD.，iD，SI5:DD，.iI3:Di.iiI6:DD，i.圖3 識別全部活前綴的DFAe在項目集I4中存在沖

15、突項目，文法G不是LR（0）文法。FOLLOW(S)=#FOLLOW(S)=#FOLLOW(D)= ，,#而由于 ，F(xiàn)OLLOW(S)= ，#=，所以文法G是SLR（1）文法。SrSDDi，iDi，圖4 句子的語法樹求得文法G的SLR（1）分析表見表1：ACTIONGOTOr，i#SD0S211acc2S343R4R44S5R25S66R3R3表1 SLR（1）分析表f可以先求得該句子的語法樹（見圖4），然后通過剪枝的方式進(jìn)行歸約，最后歸約到文法的開始符號，在歸約的過程中同步產(chǎn)生輸出符號串dccba。即對于r i,i,i這個輸入符號串，該翻譯方案的輸出是：dccba （2）給定文法:（1）Sb

16、Tc （2）Sa（3）TR（4）RR/S（5）RSa)符號串ba/ac是不是該文法的一個句子，請證實。b)若是句子，寫出該句子的所有短語、簡單短語和句柄。c)為該文法設(shè)計翻譯方案，使句型bR/bTc/bSc/ac經(jīng)該翻譯方案翻譯后,輸出下列串：SbcRRS/aSTa 解答：a) 符號串ba/ac是該文法的一個句子。SbTcbRcbR/ScbS/Scba/Scba/ac，得證?；颍航o出符號串ba/ac的語法樹如右圖，則判定符號串ba/ac是該文法的一個句子。b)給出句型ba/ac的語法樹如右圖：則可求得句型adbb的短語有：ba/ac,a/a,第1個a, 第2個a 簡單短語有：第1個a, 第2個

17、a 句柄有：第1個ac)給出句型bR/bTc/bSc/ac的語法樹如右圖：SbcRRS/SaRRSRSbcT/TbcT按照歸約過程，則給定文法的相應(yīng)翻譯方案為： （1）SbTc print(“0”)（2）Sa print(“1”)（3）TR print(“2”)（4）RR/S print(“3”)（5）RS print(“4”)（3）設(shè)有基本塊： t1:=3*At2:=2*Ct3:=t1+t2t4:=t3+5t5:=2*Ct6:=3*At7:=t6+t5E:=t7-1F:=t4-Ea)畫出DAG圖；b)假設(shè)基本塊出口時只有E，F(xiàn)還被引用，請寫出優(yōu)化后的三地址代碼序列。5+*+*t4t1,t62A3n11n2n3n5n6n8En7F1n4t2,t5t3,t7n9Cn10n11n12解答：a)構(gòu)造DAG：見右圖。b)優(yōu)化后的三地址代碼序列為：t1:=3*At2:=2*Ct3:=t1+t2t4:=t3+5E:=t3-1F:=t4-E五轉(zhuǎn)換題： 給定下列中綴式 (運算符優(yōu)先級按常規(guī)理解) ，分別寫出等價的