編譯原理考試題解答

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

2、S是文法的開始符號， 如果S ,.x（其 中x V*）,則稱x是文法的一個句型。8）句子答：句子一一設 G是一個給定的文法，S是文法的開始符號，如果S鼻（其中x Vt ）,則稱x是文法的一個句子。9）非終結符答：非終結符一一出現(xiàn)在文法產生式的左部且能派生出符號或符號串的那些符號稱為非終結符號。10）終結符答：終結符一一出現(xiàn)在文法產生式的右部且不能派生出符號或符號串的那些符號稱為終結符號。11）屬性文法答：一個屬性文法形式的定義為一個三元組AG AG=（ G V, E）。其中G為一個上下文無關文法； V為屬性的有窮集；E為一組語義規(guī)貝農12）語法制導翻譯答：語法制導翻譯一一語法制導翻譯就是在語法

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

4、為語義規(guī)則。17）語法分析答：語法分析一一按文法的產生式識別輸入的符號串是否為一個句子的分析過程。18）四元式答：四元式是一個帶有四個域的記錄結構，這四個域分別稱為操作符域、左運算對象域、右運算對象域及運算結果域。二.簡答題：1）什么是句子？什么是語言？解答：句子設G是一個給定的文法，S是文法的開始符號，如果S Jc（其中x Vt ）,則稱x是文法的一個句子。語言語言是句子的集合?；蛞灰辉OGS是給定文法，則由文法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將產生一個狀 態(tài)集合（可能為空集），而不是單個狀態(tài)。3）自頂向下的語法分析方法的基本思想是什么？解答:從文法的開始符號開始，根據給定的輸入串并按照文法的產生式一步 一步的向下進行直接推導，試圖推導出文法的句子，使之與給定的輸 入串匹配。4）自底向上的語法分析方法的基本思想是什么？解答:從給定的輸入串（終結符串）開始，根據文法的規(guī)則一步一步的向上 進行直接歸約，試圖歸約到文法的開始符號。5）一個上下文無關文法 G包括哪四個組成部分？解答:一組非終結符號，一組終結符號，一個開始符號，以

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

7、？解答 :不正確。13）把匯編語言程序翻譯成機器可執(zhí)行的目標程序的工作是由什么完成 的？解答:由匯編器（匯編程序）完成的。14）圖示運行時存儲空間的劃分（分為哪幾個區(qū)） 解答:一般分為靜態(tài)區(qū)和動態(tài)區(qū)：程序代碼區(qū)、靜態(tài)數據區(qū)、棧區(qū)和堆區(qū)15）詞法分析的主要任務是什么？解答:詞法分析器的任務是對構成源程序的字符串從左到右逐個字符逐個 字符地進行掃描，依次把它們識別為一個一個具有獨立意義的單詞， 并確定其屬性，再轉換為長度統(tǒng)一的屬性字并輸出。16）常用的中間語言種類有哪幾種？解答:常用的中間語言種類有逆波蘭表示、三元式、四元式和樹形表示。17）文法G所描述的語言是什么的集合？解答:是由文法的開始符號

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

9、貯分配策略是棧式動態(tài)分配策略和堆式動態(tài)分配 策略。24）常用的參數傳遞方式有哪三種？解答 : 常見的參數傳遞方式有傳地址、傳值和傳名三種方式。25）語法分析的任務是什么？解答 : 語法分析的任務是識別給定的終結符串是否為給定文法的句子。26）局部優(yōu)化是局限于一個什么范圍內的一種優(yōu)化？ 解答 : 是局限于一個基本塊范圍內的一種優(yōu)化。27）文法等價的定義是什么？解答：設G1和G2是給定的文法，如果有 L （G1） = L （G2）,則稱G1與G2 等價。28） 在語法分析處理中，F(xiàn)IRST集合、FOLLOW集合、SELECT集合均是什么 集合？解答 ： 均是終結符集。29）通常一個編譯程序中應包括

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

11、導。（1）S => SaS => SaSbS => SaSbf=> Safbf=> fafbf（2）S => SbS => Sbf=> SaSbf => Safbf=> fafbf 因此說明此文法有二義性。35）在屬性文法中，綜合屬性與繼承屬性是如何傳遞信息的？解答 : 綜合屬性用于自下而上傳遞信息， 繼承屬性用于自上而下傳遞信息。36）代碼優(yōu)化的主要目標是什么？解答 : 代碼優(yōu)化的主要目標是如何提高目標程序的運行速度和如何減少目 標程序運行時所需的空間。37） 寫一個文法，使其語言是無符號二進制實數（不含指數）。 解答 : 文法 G

12、（N）：Nt L.L|LLt LB|B Bt 0|1三應用題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把此自動機轉換為確定自動機DFA解答：有狀態(tài)矩陣如圖:其中：開始狀態(tài)：0終止狀態(tài)：2a b=00,1 212-21 2極小化后:ab=001 20101 2-21 212從而可得DFA如圖:U構造一個等價的有限自動機。4)正規(guī)式(a|b ) a(a|b)解答:四設計題(1 )給定文法GS及相應翻譯方案為：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. 構造識別該文法的活前綴的 DFAe. 判斷該文法是LR( 0)還是SLR (1)，并構造其相應的語法分析表。f. 對于ri,i,i這個輸入符號串，經該翻譯方案翻譯后的輸出是什么？ 解答：a. 文法G屬于2型(上下文無關)文法。b. 符號串r i,i,i是該文法的一個句型。證：S =S : rD二 rD, i= rD , i , i = r i , i , i，得證?；蜃C：構造語法樹見圖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),然后通過剪枝的方式進行歸約， 最后歸約到文法的開始符號，在歸約的過程中

16、同步產生輸出符號串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) 為該文法設計翻譯方案，使句型 bR/bTc/bSc/ac 經該翻譯方案翻譯后 輸出下列串：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)按照歸約過程，則給定文法的相應翻譯方案為:S aRRS(3) 設有基本塊：t1:=3*At2:=2*Ct3:=t1+t2t4:=t3+5t5:=2*Ct6:=3*At7:=t6+t5E:=t7-1F:=t4-Ea) 畫出DAG圖；b) 假設基本塊出口時只有 序列。解答：a)構造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 的語法樹如右圖:五轉換題:給定下列中綴式(運算符優(yōu)先級按常規(guī)理解)，分別寫出等價的逆波蘭 式和四元式。1) a < bA a > 0V b v 0解答：逆波蘭式為：abw