編譯原理考試題解答

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

2、S是文法的開始符號， 如果S ,.x（其 中x V*）,則稱x是文法的一個句型。8）句子答：句子一一設(shè) G是一個給定的文法，S是文法的開始符號，如果S鼻（其中x Vt ）,則稱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ī)貝農(nóng)12）語法制導(dǎo)翻譯答：語法制導(dǎo)翻譯一一語法制導(dǎo)翻譯就是在語法

3、分析的過程中，當(dāng)進(jìn)行推導(dǎo)或歸約時同步完成附加在所使用的產(chǎn)生式上的語義規(guī)則描述的動作， 從而實現(xiàn)語義處理。13）后綴式答：后綴式一種把運算量（操作數(shù)）寫在前面，把算符寫在后面（后綴）的表示法。14）短語答：短語一一設(shè) GZ是給定文法，w=xuy V,為該文法的句型，如果滿足下 面兩個條件： Z , xUy ； U , u ；則稱句型xuy中的子串u是句型xuy的短語。或：句型語法樹的全部子樹的葉從左到右排列起來構(gòu)成的符號串均是句型的短語。15）基本塊答：基本塊一一源程序或者中間代碼程序中只有一個入口和一個出口的順序執(zhí)行的代碼段。16）語義規(guī)則答：對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，稱

4、為語義規(guī)則。17）語法分析答：語法分析一一按文法的產(chǎn)生式識別輸入的符號串是否為一個句子的分析過程。18）四元式答：四元式是一個帶有四個域的記錄結(jié)構(gòu)，這四個域分別稱為操作符域、左運算對象域、右運算對象域及運算結(jié)果域。二.簡答題：1）什么是句子？什么是語言？解答：句子設(shè)G是一個給定的文法，S是文法的開始符號，如果S Jc（其中x Vt ）,則稱x是文法的一個句子。語言語言是句子的集合?；蛞灰辉O(shè)GS是給定文法，則由文法G所定義的語言L（G）可描 述為：L（G） = x | S ,x,x Vt*。2）DFA與NFA有何區(qū)別？解答:DFA與NFA的區(qū)別表現(xiàn)為兩個方面：一是NFA可以有若干個開始狀態(tài)， 而

5、DFA僅只有一個開始狀態(tài)。另一方面，DFA的映象M是從KX刀到K,而NFA的映象M是從KXE到K的子集，即映象 M將產(chǎn)生一個狀 態(tài)集合（可能為空集），而不是單個狀態(tài)。3）自頂向下的語法分析方法的基本思想是什么？解答:從文法的開始符號開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步 一步的向下進(jìn)行直接推導(dǎo)，試圖推導(dǎo)出文法的句子，使之與給定的輸 入串匹配。4）自底向上的語法分析方法的基本思想是什么？解答:從給定的輸入串（終結(jié)符串）開始，根據(jù)文法的規(guī)則一步一步的向上 進(jìn)行直接歸約，試圖歸約到文法的開始符號。5）一個上下文無關(guān)文法 G包括哪四個組成部分？解答:一組非終結(jié)符號，一組終結(jié)符號，一個開始符號，以

6、及一組產(chǎn)生式。6）在自底向上的語法分析方法中，分析的關(guān)鍵是什么？解答：關(guān)鍵是尋找句柄。7）在自頂向下的語法分析方法中，分析的關(guān)鍵是什么？解答：關(guān)鍵是選擇候選式。8）編譯程序中語法分析器接收以什么為單位的輸入？ 解答：接收以單詞為單位的輸入。9）若一個文法是遞歸的，則它所產(chǎn)生的語言的句子是可枚舉的嗎？ 解答:它所產(chǎn)生的語言的句子不是可枚舉的，而是無窮多個。10）編譯程序生成的目標(biāo)程序是不是一定是機器語言的程序？ 解答:不一定是機器語言的程序。11）詞法分析器是用于做什么的？ 解答:詞法分析器是用于識別單詞的。12）“用高級語言書寫的源程序都必須通過編譯，產(chǎn)生目標(biāo)代碼后才能投入運行”這種說法正確嗎

7、？解答 :不正確。13）把匯編語言程序翻譯成機器可執(zhí)行的目標(biāo)程序的工作是由什么完成 的？解答:由匯編器（匯編程序）完成的。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）常用的中間語言種類有哪幾種？解答:常用的中間語言種類有逆波蘭表示、三元式、四元式和樹形表示。17）文法G所描述的語言是什么的集合？解答:是由文法的開始符號

8、推出的所有終結(jié)符串的集合?；蛘f是句子的集 合。18） 喬姆斯基把文法分為四種類型，即0型、1型、2型、3型。其中2型 文法叫什么？解答:2型文法叫上下文無關(guān)文法。19）編譯程序是一種解釋程序嗎？還是什么程序？解答:編譯程序是一種翻譯程序。20）按邏輯上劃分，編譯程序第二步工作是什么？解答:編譯程序第二步工作是語法分析。21）源程序是用高級語言編寫的，目標(biāo)程序是機器語言程序或匯編語言程序，則其翻譯程序稱為什么？解答:其翻譯程序稱為編譯程序。22）編譯方式與解釋方式的根本區(qū)別為什么？解答:編譯方式與解釋方式的根本區(qū)別在于是否生成目標(biāo)代碼。23）常見的動態(tài)存貯分配策略有哪兩種？解答:常見的兩種動態(tài)存

9、貯分配策略是棧式動態(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） 在語法分析處理中，F(xiàn)IRST集合、FOLLOW集合、SELECT集合均是什么 集合？解答 ： 均是終結(jié)符集。29）通常一個編譯程序中應(yīng)包括

10、哪七個部分？解答 ： 通常一個編譯程序中應(yīng)包含詞法分析，語法分析，語義分析與中間 代碼生成， 代碼優(yōu)化， 目標(biāo)代碼生成以及表格處理和出錯處理等七個部分。32）如果編譯程序生成的目標(biāo)程序是匯編語言程序，則源程序的執(zhí)行分為 哪三個階段？解答 ： 源程序的執(zhí)行分為三個階段 ： 編譯階段，匯編階段和運行階段。33）翻譯程序是這樣一種程序，它能夠?qū)⒂檬裁崔D(zhuǎn)換成與其等價的用乙語 言書寫的程序？解答 ： 能夠?qū)?用甲語言書寫的程序 轉(zhuǎn)換成與其等價的用乙語言書寫的程序。34） 說明下面文法 GS是二義性文法：St SaS|SbS|cSd|eS|f 解答:fafbf 是文法GS的一個句子，并且有兩個不同的最右推

11、導(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

12、（N）：Nt L.L|LLt LB|B Bt 0|1三應(yīng)用題1 ）消除下列文法 GA 的左遞歸。Et E-T I TTt T/F I FFt （E） I i解答：消除文法 GE 的左遞歸后得到：Et te'E't -T E ' IsTt ftT't /ft 'l£Ft (E) I i 2)消除下列文法 GA的左遞歸。At AaBI BBt BbCI CCt eDI DDT (A) I d解答：消除文法GA的左遞歸后得到:A t BA，A ，t aBA'IsB t CB"B't bcB'IsCteDI DDt (

13、A) I d把此自動機轉(zhuǎn)換為確定自動機DFA解答：有狀態(tài)矩陣如圖:其中：開始狀態(tài)：0終止?fàn)顟B(tài)：2a b=00,1 212-21 2極小化后:ab=001 20101 2-21 212從而可得DFA如圖:U構(gòu)造一個等價的有限自動機。4)正規(guī)式(a|b ) a(a|b)解答:四設(shè)計題(1 )給定文法GS及相應(yīng)翻譯方案為：1 . S Sprint:a ?a2. S r Dprint:a 1»b3. D D, iprint:a ?c4. D ipri nt:a 1 »da. 按chomsky分類法，文法 G屬于哪一型文法？b. 符號串ri,i,i 是不是該文法的一個句型，請證實。c

14、. 若是句型，寫出該句型的所有短語、簡單短語，以及句柄。d. 構(gòu)造識別該文法的活前綴的 DFAe. 判斷該文法是LR( 0)還是SLR (1)，并構(gòu)造其相應(yīng)的語法分析表。f. 對于ri,i,i這個輸入符號串，經(jīng)該翻譯方案翻譯后的輸出是什么？ 解答：a. 文法G屬于2型(上下文無關(guān))文法。b. 符號串r i,i,i是該文法的一個句型。證：S =S : rD二 rD, i= rD , i , i = r i , i , i，得證?；蜃C：構(gòu)造語法樹見圖4,可知符號串r i,i,i是該文法的一個句型。c. 句型r i,i,i的短語有：r i,i,i ;i,i,i :i,i :第一個i簡單短語有：第一個

15、i句柄有：第一個id. 求得文法G的識別全部活前綴的 DFA見圖3:圖3識別全部活前綴的 DFAe. T在項目集I4中存在沖突項目，文法G不是LR (0)文法。FOLLOW(S=#FOLLOW(S)=#FOLLOW(D)= , ,#而由于 , afollow(S)= , n#=，所以文法 g是slr( 1)文 法。求得文法G的SLR (1)分析表見表1 :ACTIONGOTOri#SD0S211acc2S3434SsR>5S66R3R3表1 SLR (1)分析表圖4句子的語法樹f 可以先求得該句子的語法樹(見圖 4),然后通過剪枝的方式進(jìn)行歸約， 最后歸約到文法的開始符號，在歸約的過程中

16、同步產(chǎn)生輸出符號串dccba。即對于r i,i,i這個輸入符號串，該翻譯方案的輸出是：dccba(2 )給定文法：(1) St bTc(2) St a(3) Tt R(4) FT R/S(5) RT Sa) 符號串ba/ac是不是該文法的一個句子，請證實。b) 若是句子，寫出該句子的所有短語、簡單短語和句柄。c) 為該文法設(shè)計翻譯方案，使句型 bR/bTc/bSc/ac 經(jīng)該翻譯方案翻譯后 輸出下列串：Sbc0342031320解答：a) 符號串ba/ac是該文法的一個句子。/ S : bTc二 bRc : bR/Sc二 bS/Sc= ba/Sc 二 ba/ac , 得證?；颍航o出符號串ba/

17、ac的語法樹如右圖，則判定符號串ba/ac是該文法的一個句子。b) 給出句型ba/ac的語法樹如右圖：則可求得句型 adbb的短語有：ba/ac,a/a,第1個a,第2個a簡單短語有：第1個a,第2個a句柄有：第1個a(1)St bTcpri nt(“0 ”)(2)St apri nt(“ 1”)(3)Tt rpri nt(“ 2”)(4)ft r/spri nt(“ 3”)(5)ft spri nt(a A »4)按照歸約過程，則給定文法的相應(yīng)翻譯方案為:S aRRS(3) 設(shè)有基本塊：t1:=3*At2:=2*Ct3:=t1+t2t4:=t3+5t5:=2*Ct6:=3*At7:=t6+t5E:=t7-1F:=t4-Ea) 畫出DAG圖；b) 假設(shè)基本塊出口時只有 序列。解答：a)構(gòu)造DAG見右圖。E，F(xiàn)還被引用,請寫出優(yōu)化后的三地址代碼Enilb)優(yōu)化后的三地址代碼序列為:t1:=3*At2:=2*Ct3:=t1+t2t4:=t3+5E:=t3-1F:=t4-E19 t4n10+ i17 t3,t7+ -冷13t1，t6n6 t2,t5c）給出句型bR/bTc/bSc/ac 的語法樹如右圖:五轉(zhuǎn)換題:給定下列中綴式(運算符優(yōu)先級按常規(guī)理解)，分別寫出等價的逆波蘭 式和四元式。1) a < bA a > 0V b v 0解答：逆波蘭式為：abw