編譯原理考試題解答

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

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

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

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

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

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

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

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

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

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

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)程序的運(yùn)行速度和如何減少目 標(biāo)程序運(yùn)行時(shí)所需的空間。37） 寫一個(gè)文法，使其語言是無符號(hào)二進(jìn)制實(shí)數(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把此自動(dòng)機(jī)轉(zhuǎn)換為確定自動(dòng)機(jī)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)造一個(gè)等價(jià)的有限自動(dòng)機(jī)。4)正規(guī)式(a|b ) a(a|b)解答:四設(shè)計(jì)題(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. 符號(hào)串ri,i,i 是不是該文法的一個(gè)句型，請(qǐng)證實(shí)。c

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

15、i句柄有：第一個(gè)id. 求得文法G的識(shí)別全部活前綴的 DFA見圖3:圖3識(shí)別全部活前綴的 DFAe. T在項(xiàng)目集I4中存在沖突項(xiàng)目，文法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)行歸約， 最后歸約到文法的開始符號(hào)，在歸約的過程中

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

17、ac的語法樹如右圖，則判定符號(hào)串ba/ac是該文法的一個(gè)句子。b) 給出句型ba/ac的語法樹如右圖：則可求得句型 adbb的短語有：ba/ac,a/a,第1個(gè)a,第2個(gè)a簡(jiǎn)單短語有：第1個(gè)a,第2個(gè)a句柄有：第1個(gè)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è)基本塊出口時(shí)只有 序列。解答：a)構(gòu)造DAG見右圖。E，F(xiàn)還被引用,請(qǐng)寫出優(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ùn)算符優(yōu)先級(jí)按常規(guī)理解)，分別寫出等價(jià)的逆波蘭 式和四元式。1) a < bA a > 0V b v 0解答：逆波蘭式為：abw